How to model this kind of artificial intelligence?

Question

While playing to this game I wondered how an AI controlling either the detectives either the criminal could work.

For lazy people the aim of the game is simple:

• the board game is an undirected graph that has 4 kinds of edges (that can also overlap for the same pair of vertices), each kind is a type of transport that requires a specific kind of ticket

• detectives have a bunch of tickets to move around this graph, one move per turn (which means from a node to another node). The criminal can do the same set of moves (plus 3 exclusive paths) but with no limits on tickets

• the criminal is usually hidden to detectives but it has to show up himself in 5 specific turns (and then hide again)

• if detectives are able to catch him (one of them must occupy the same cell of the criminal) before 24 moves then they win, otherwise the criminal wins

• the criminal has to show which ticket he uses each turn but he also has 1 black ticket per detective (let's assume 5) that can be used to verify this thing

• the criminal also has two 2x tickets that allow him to use two tickets (and so two movements) in the same turn

I can think effectively about an AI for the criminal that it would be just a minimax tree that tries to choose movements that maximize the number of moves needed by detectives to reach him (it seems to be a good metric) but I cannot think anything enough cool for detectives which should cooperate and try to guess where the criminal can be by looking at tickets it uses.

It's just for fun but do you know any cool ideas to work out something quite clever?

Answer 1

You can refer this link, as it has the implementation of Scotland Yard but the problem of the fugitive AI is that it chooses the best move that's not the smarter one. It's just the best according to a distance metric, which doesn't take into account the tricks like likeness to backtrack on moves.

You can also apply Monte-Carlo Tree Search for the Game of Scotland Yard. The basic MCTS algorithm is designed for two-player games with perfect information. When using MCTS in a game with imperfect information, the algorithm has to be altered slightly.

If you wish to know more about Artificial Intelligence visit this Artificial Intelligence Course.