¿Cómo modelar este tipo de inteligencia artificial?

Question

mientras jugaba al juego this Me preguntaba cómo una inteligencia artificial controlando a cualquiera de los detectives o el delincuente podría funcionar.

para la gente perezosa que el objetivo del juego es simple:

• el juego de mesa es un grafos no dirigidos que tiene 4 tipos de bordes (que también pueden solaparse para un mismo par o vértices), cada clase es una tipo de transporte que requiere un tipo específico de ticket
• detectives tienen un montón de tickets para moverse por este gráfico, un movimiento por turno (lo que significa que de un nodo a otro nodo). El criminal puede hacer el mismo conjunto de movimientos (más 3 rutas exclusivas) pero sin límites en ticks
• el criminal generalmente está oculto para los detectives pero tiene que aparecer en 5 turnos específicos (y luego volver a ocultarse)
• si los detectives pueden atraparlo (uno de ellos debe ocupar la misma celda del delincuente) antes de 24 movimientos, entonces ganan; de lo contrario, el criminal gana
• el delincuente debe mostrar qué boleto usa cada turno pero también tiene 1 boleto negro por detective (supongamos 5) que se puede usar para eliminar esta cosa
• el criminal también tiene dos boletos 2x que le permiten usar dos boletos (y por lo tanto dos movimientos) en el mismo turno

Puedo pensar de manera efectiva en una IA para el criminal que sería solo un árbol minmax que trata de elegir movimientos que maximicen el número de movimientos necesarios para que los detectives lo alcancen (parece ser una buena métrica) pero No puedo pensar en nada lo suficientemente genial para los detectives que deberían cooperar y tratar de adivinar dónde está el delincuente mirando las entradas que usa.

Es solo por diversión pero ¿tiene alguna idea genial para resolver algo bastante inteligente?

Answer 1

Ha pedido a modelar esto, no la forma de resolver esto de manera eficiente:

Se puede modelarse fácilmente como un proceso de decisión de Markov parcialmente observable (wiki link). Esto funciona tanto para los detectives como para el criminal. Los POMDP son un modelo muy genérico.

Answer 2

Me encanta este juego, y creo que para los detectives querrás modelar la probabilidad de que el criminal esté en cada ubicación. De vez en cuando conoce la posición exacta del delincuente, y luego puede tener en cuenta las siguientes acciones que realiza para determinar en qué lugares podría estar.

Una vez que tenga esto, no estoy muy seguro de cómo optimizar los movimientos detectives. Puede mover a los detectives para reducir el conjunto de posibilidades, acorralando efectivamente al criminal. Pero estoy seguro de que también se necesita una estrategia de alto nivel para rodear las entradas y no quedarse sin ellas.

Answer 3

Imagino que algún tipo de implementación de monte carlo sería un excelente candidato para esto, es decir. simulando miles de combinaciones y eligiendo la que termina con el mejor resultado la mayor parte del tiempo. Como el criminal debe ser visible durante 5 turnos, el factor de ramificación debe mantenerse bajo control, aunque también se ha demostrado que MC es una muy buena técnica en juegos de alto factor de ramificación, es decir. Ir.

Answer 4

Para poder trabajar en equipo entre los detectives necesita modelarlos como un equipo y no como individuos. Minimax sigue siendo un buen camino por recorrer, pero (lamentablemente) su factor de ramificación se disparará.

En lugar de pasar a través de todos los detectives haciendo lo que parece ser lo mejor para cada uno para su equipo de detectives, usted calcula cada permutación de movimientos que podrían hacer. Si el trabajo en equipo ayuda en este juego, el minimax favorecerá las permutaciones en las que los detectives trabajan juntos.

No estoy seguro si será práctico, 5 detectives para 24 capas podrían ser demasiado trabajo pero sería divertido intentarlo y ese es el punto ¿no?