Geek Answers Handbook

How to simulate such artificial intelligence?

during the game this game I wondered how the AI ​​controlling the criminal detectives could work.

For lazy people, the goal of the game is simple:

  • a board game is an undirected graph that has 4 types of edges (which can also intersect for one pair or vertices), each view is a type of transport that requires a certain type of ticket
  • detectives have a bunch of tickets to move around this schedule, one move per turn (which means from node to another node). A criminal can perform the same set of moves (plus 3 exclusive paths), but without tick restrictions
  • the criminal is usually hidden from the detectives, but he must prove himself in 5 specific forms (and then hide again).
  • if the detectives can catch him (one of them must occupy the same cell of the criminal) up to 24 moves, then they win, otherwise the crime wins
  • the offender must show which ticket he uses each turn, but he also has 1 black ticket for one detective (even supposedly 5), which can be used to reduce this thing.
  • the criminal also has two 2x tickets that allow him to use two tickets (and therefore two movements) in the same queue

I can effectively think of the AI ​​for the criminal, that it will be just a minmax tree that tries to select movements that maximize the number of movements needed for detectives to achieve it (this seems to be a good indicator), but I can’t think that for detectives who must cooperate, and try to guess where the criminal may be, you might think that he is looking at the tickets that he uses.

It's just for fun, but now you have cool ideas to work out something pretty smart?

+7
language-agnostic artificial-intelligence
source share
4 answers

You asked how to do this, and not how to solve this problem effectively:

It can be easily modeled as a partially observable Markov decision making process ( wiki link ). This works for both detectives and criminals. POMDP is a very general model.

+1
source share

I like this game, and I think for detectives you want to simulate the likelihood that the criminal is in every place. From time to time you know the exact position of the offender, and then you can take into account the following steps that he takes to determine where he may be.

Once you have this, I'm not quite sure how to optimize the movements of detectives. You can move detectives to reduce the set of opportunities, effectively oppressing the criminal. But I am sure that there is a higher-level strategy related to tickets, and not exhaustive.

+1
source share

I would suggest that some kind of monte carlo implementation would be a great candidate for this, i.e. imitating thousands of combinations and choosing the one that ends with the best result in most cases. Since the culprit should be visible at 5 revolutions, the branch coefficient should remain under control, although MC also showed that he is very good in games with a high branch coefficient, i.e. Go

0
source share

To ensure collaboration between detectives, you need to model them as a team, not as individuals. Minimax is still a good way, but (unfortunately) your branching factor will increase.

Instead of getting through all the detectives creating what seems to be the best for everyone, instead, for your team of detectives, you develop each permutation of moves that they could make. If teamwork helps in this game, then minimax will facilitate the rearrangements in which detectives work together.

I’m not sure that it will be practical, 5 detectives with 24 layers may work too much, but it would be interesting to try, and is that right?

0
source share

More articles:


All Articles