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 graphs that has 4 kinds of edges (that can also overlap for same pair or 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 tickes
• 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 vanify 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 minmax 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 now any cool ideas to work out something quite clever?

Answer 1

In order to get teamwork going between the detectives you need to model them as a team rather than as individuals. Minimax is still a good way to go but (sadly) your branching factor is going to soar.

Instead of stepping through all the detectives making what appears to be the best for each instead for your team of detectives you work out each permutation of moves they could make. If teamwork helps in this game then the minimax will favour the permutations in which the detectives are working together.

I'm not sure if it will be practical, 5 detectives for 24 ply might be too much work but it'd be fun to try and that's the point right?

Answer 2

You've asked how to model this, not how to solve this efficiently:

It can be easily modeled as a partially observable markov decision process (wiki link). This works both for the detectives and the criminal. POMDPs are a very generic model.

Answer 3

I'd imagine some kind of a monte carlo implementation would be an excellent candidate for this, ie. simulating thousands of combinations and choosing the one that ends with the best result most of the time. Since the criminal has to be visible for 5 turns, the branching factor should stay well under control, although MC has also been shown to be a very good technique in games of high branching factor, ie. Go.

Answer 4

I love this game, and I think for the detectives you want to model the probability that the criminal is at each location. Every once in a while you know the exact position of the criminal, and then you can take into account the following moves he makes to determine which spots he could possibly be at.

Once you have this, I'm not quite sure how to optimize the detectives moves. You can move the detectives to reduce the set of possibilities, effectively corraling the criminal. But I'm sure there is also some higher level strategy needed surrounding the tickets and not running out of them.