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

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.