Negamax - el jugador se mueve dos veces

Question

¿Cómo manejas los juegos donde, si se cumple una condición, se mueve el mismo jugador?

he intentado algo como esto, pero yo no creo que sea del todo bien:

function negamax(node, depth, α, β, color) 
    if node is a terminal node or depth = 0 
     return color * the heuristic value of node 
    else 
     foreach child of node 
      if (condition is met) // the same player moves 
       val := negamax(child, depth-1, α, β, color) 
      else 
       val := -negamax(child, depth-1, -β, -α, -color) 
      if val≥β 
       return val 
      if val≥α 
       α:=val 
     return α 

Answer 1

No intente cambiar el algoritmo minimax en sí mismo para esto, en su lugar, modifique la representación del juego para adaptarse. Básicamente hay dos soluciones:

1. Representan las secuencias de movimientos realizados por un solo jugador como un solo movimiento. Esto funciona cuando el juego es simple, pero no siempre. Escribí un motor de IA para un juego donde generar este árbol (descrito como un "movimiento" en las reglas del juego) es PSPACE difícil (y tenía una n muy grande para juegos reales) lo que significaba que no era computacionalmente factible. Por otro lado, si modelarlo de esta manera es fácil para tu juego en particular, hazlo de esa manera
2. Representa las secuencias de movimientos realizados por un jugador como una secuencia de movimientos alternando movimientos, donde el otro jugador hace cualquier cosa. Es decir, agrega una información al estado del juego siempre que se cumpla su condición, de modo que el único movimiento que el otro jugador puede hacer no cambie el estado. Este método es matemáticamente correcto, y cuando lo usé funcionaba bastante bien en la práctica. La única complejidad a tener en cuenta es que si usas iterative deepening, evaluarás los árboles de juego donde un jugador se mueve muchas veces seguidas. También es posible que hay que tener cuidado en el diseño de la heurística de almacenamiento para ser utilizado con los demás transposition table y hashes

No conozco ningún literatura que discute el problema particular. Me sentí inteligente cuando se me ocurrió la solución 2 anterior, pero sospecho que muchas otras personas han inventado el mismo truco.

Debo decir que conseguir la familia minimax correcta es sorprendentemente difícil. Un truco cuando se diseñan IA de búsqueda de juegos en lenguajes de alto nivel es probar los algoritmos de búsqueda en juegos más simples (tamaño de placa reducido, uso de tres en raya, etc.) para garantizar la corrección. Si el juego es pequeño, puedes a. asegúrese de que sus resultados tengan sentido jugando el juego a mano y b. pruebe algoritmos avanzados como negascout asegurándose de que dan la misma respuesta que naive negamax. También es una buena idea tratar de mantener el código con el comportamiento específico del juego (funciones de evaluación, representaciones del tablero, heurística de búsqueda y almacenamiento, etc.) lejos del código que realiza búsquedas en árbol.

Answer 2

En negamax, se están explorando una estructura de árbol en el que cada nodo tiene hijos que corresponden a los movimientos realizados por un jugador. Si en algún caso un jugador puede moverse dos veces, probablemente desee pensar en el "movimiento" para ese jugador como la secuencia de dos movimientos que ese jugador hace. De manera más general, debes pensar en los hijos del estado del juego actual como todos los estados posibles en los que el jugador actual puede jugar después de su turno. Esto incluye todos los estados del juego alcanzables por un movimiento, más todos los estados del juego alcanzables en dos movimientos si el jugador puede hacer dos movimientos en un turno. Por lo tanto, debe dejar sin cambios la lógica básica de negamax, pero actualice su código para generar estados sucesores para manejar el caso en el que un solo jugador puede moverse dos veces.

Espero que esto ayude!

Answer 3

Cuando se cumple la condición, no disminuya la profundidad.