La búsqueda Negamax es una forma variante de búsqueda minimax que se basa en la propiedad de suma cero de un juego de dos jugadores .
Este algoritmo se basa en el hecho de que para simplificar la implementación del algoritmo minimax . Más precisamente, el valor de una posición para el jugador A en tal juego es la negación del valor para el jugador B. Por lo tanto, el jugador en movimiento busca una jugada que maximice la negación del valor resultante de la jugada: esta posición sucesora por definición, debe haber sido valorado por el oponente. El razonamiento de la oración anterior funciona independientemente de si A o B están en movimiento. Esto significa que se puede utilizar un solo procedimiento para valorar ambas posiciones. Esta es una simplificación de codificación sobre minimax, que requiere que A seleccione el movimiento con el sucesor de valor máximo mientras que B selecciona el movimiento con el sucesor de valor mínimo.
No debe confundirse con negascout , un algoritmo para calcular el valor minimax o negamax rápidamente mediante el uso inteligente de la poda alfa-beta descubierta en la década de 1980. Tenga en cuenta que la poda alfa-beta es en sí misma una forma de calcular el valor minimax o negamax de una posición rápidamente al evitar la búsqueda de ciertas posiciones poco interesantes.
La mayoría de los motores de búsqueda adversarios se codifican mediante alguna forma de búsqueda negamax.
Algoritmo base Negamax
NegaMax opera en los mismos árboles de juego que los usados con el algoritmo de búsqueda minimax. Cada nodo y nodo raíz del árbol son estados de juego (como la configuración del tablero de juego) de un juego de dos jugadores. Las transiciones a los nodos secundarios representan movimientos disponibles para un jugador que está a punto de jugar desde un nodo determinado.
El objetivo de búsqueda negamax es encontrar el valor de puntuación del nodo para el jugador que está jugando en el nodo raíz. El pseudocódigo a continuación muestra el algoritmo base negamax, [1] con un límite configurable para la profundidad de búsqueda máxima:
la función negamax (nodo, profundidad, color) es si la profundidad = 0 o el nodo es un nodo terminal, entonces devuelve el color × el valor heurístico del nodo valor: = −∞ para cada hijo del nodo hacer valor: = max (valor, negamax (hijo, profundidad - 1, −color)) return −valor
(* Llamada inicial para el nodo raíz del jugador A *)negamax (nodo raíz, profundidad, 1)
(* Llamada inicial para el nodo raíz del jugador B *)negamax (nodo raíz, profundidad, -1)
El nodo raíz hereda su puntuación de uno de sus nodos secundarios inmediatos. El nodo hijo que finalmente establece la mejor puntuación del nodo raíz también representa el mejor movimiento para jugar. Aunque la función negamax que se muestra solo devuelve la mejor puntuación del nodo, las implementaciones prácticas de negamax conservarán y devolverán tanto el mejor movimiento como la mejor puntuación para el nodo raíz. Solo la mejor puntuación del nodo es esencial con los nodos que no son raíz. Y el mejor movimiento de un nodo no es necesario para retener ni devolver para los nodos que no son raíz.
Lo que puede resultar confuso es cómo se calcula el valor heurístico del nodo actual. En esta implementación, este valor siempre se calcula desde el punto de vista del jugador A, cuyo valor de color es uno. En otras palabras, los valores heurísticos más altos siempre representan situaciones más favorables para el jugador A. Este es el mismo comportamiento que el algoritmo minimax normal . El valor heurístico no es necesariamente el mismo que el valor de retorno de un nodo debido a la negación del valor por negamax y el parámetro de color. El valor de retorno del nodo negamax es una puntuación heurística desde el punto de vista del jugador actual del nodo.
Las puntuaciones de Negamax coinciden con las puntuaciones de minimax para los nodos donde el jugador A está a punto de jugar, y donde el jugador A es el jugador maximizador en el equivalente de minimax. Negamax siempre busca el valor máximo para todos sus nodos. Por lo tanto, para los nodos del jugador B, la puntuación minimax es una negación de su puntuación negamax. El jugador B es el jugador minimizador en el equivalente minimax.
Las variaciones en las implementaciones negamax pueden omitir el parámetro de color. En este caso, la función de evaluación heurística debe devolver valores desde el punto de vista del jugador actual del nodo.
Negamax con poda alfa beta
Las optimizaciones de algoritmos para minimax también son igualmente aplicables para Negamax. La poda alfa-beta puede disminuir la cantidad de nodos que el algoritmo negamax evalúa en un árbol de búsqueda de una manera similar a su uso con el algoritmo minimax.
El pseudocódigo para la búsqueda negamax limitada en profundidad con poda alfa-beta es el siguiente: [1]
la función negamax (nodo, profundidad, α, β, color) es si la profundidad = 0 o el nodo es un nodo terminal, entonces devuelve el color × el valor heurístico del nodo childNodes: = generateMoves (nodo) childNodes: = orderMoves (childNodes) valor: = −∞ foreach niño en childNodes do valor: = max (valor, −negamax (hijo, profundidad - 1, −β, −α, −color)) α: = max (α, valor) si α ≥ β entonces rompe (* cut-off *) valor de retorno
(* Llamada inicial para el nodo raíz del jugador A *)negamax (nodo raíz, profundidad, −∞, + ∞, 1)
Alfa (α) y beta (β) representan los límites superior e inferior para los valores de los nodos secundarios a una profundidad de árbol determinada. Negamax establece los argumentos α y β para el nodo raíz en los valores más bajos y más altos posibles. Otros algoritmos de búsqueda, como negascout y MTD (f) , pueden inicializar α y β con valores alternativos para mejorar aún más el rendimiento de la búsqueda de árboles.
Cuando negamax encuentra un valor de nodo hijo fuera de un rango alfa / beta, la búsqueda de negamax corta de ese modo partes del árbol del juego de la exploración. Los cortes están implícitos en función del valor de retorno del nodo. Un valor de nodo que se encuentra dentro del rango de su α y β inicial es el valor exacto (o verdadero) del nodo. Este valor es idéntico al resultado que devolvería el algoritmo base negamax, sin cortes y sin límites α y β. Si el valor de retorno de un nodo está fuera de rango, entonces el valor representa un límite superior (si valor ≤ α) o inferior (si valor ≥ β) para el valor exacto del nodo. La poda alfa-beta eventualmente descarta cualquier resultado de límite de valor. Dichos valores no contribuyen ni afectan el valor negativo en su nodo raíz.
Este pseudocódigo muestra la variación suave de la poda alfa-beta. Fail-soft nunca devuelve α o β directamente como un valor de nodo. Por lo tanto, un valor de nodo puede estar fuera de los límites del rango inicial α y β establecidos con una llamada de función negamax. Por el contrario, la poda alfa-beta infalible siempre limita un valor de nodo en el rango de α y β.
Esta implementación también muestra el orden de movimiento opcional antes del bucle foreach que evalúa los nodos secundarios. Move ordering [2] es una optimización para la poda alfa beta que intenta adivinar los nodos secundarios más probables que producen la puntuación del nodo. El algoritmo busca primero esos nodos secundarios. El resultado de buenas suposiciones es que se producen cortes alfa / beta más temprano y más frecuentes, lo que elimina las ramas adicionales del árbol del juego y los nodos secundarios restantes del árbol de búsqueda.
Negamax con tablas de poda y transposición alfa beta
Las tablas de transposición memorizan selectivamente los valores de los nodos en el árbol del juego. La transposición es un término que hace referencia a que una posición determinada del tablero de juego se puede alcanzar de más de una forma con diferentes secuencias de movimientos del juego.
Cuando negamax busca en el árbol del juego y encuentra el mismo nodo varias veces, una tabla de transposición puede devolver un valor previamente calculado del nodo, omitiendo el recálculo potencialmente largo y duplicado del valor del nodo. El rendimiento de Negamax mejora especialmente para árboles de juegos con muchas rutas que conducen a un nodo determinado en común.
El pseudocódigo que agrega funciones de tabla de transposición a negamax con poda alfa / beta se proporciona de la siguiente manera: [1]
función negamax (nodo, profundidad, α, β, color) es alphaOrig: = α (* Búsqueda de tabla de transposición; el nodo es la clave de búsqueda para ttEntry *) ttEntry: = transpositionTableLookup (nodo) si ttEntry es válido y ttEntry.depth ≥ profundidad, entonces si ttEntry.flag = EXACT entonces devuelve ttEntry.value else si ttEntry.flag = LOWERBOUND entonces α: = max (α, ttEntry.value) de lo contrario, si ttEntry.flag = UPPERBOUND entonces β: = min (β, ttEntry.value) Si α ≥ β luego volver ttEntry.value si la profundidad = 0 o el nodo es un nodo terminal , devuelve el color × el valor heurístico del nodo childNodes: = generateMoves (nodo) childNodes: = orderMoves (childNodes) valor: = −∞ para cada niño en childNodes hacer valor: = max (valor, −negamax (hijo, profundidad - 1, −β, −α, −color)) α: = max (α, valor) si α ≥ β entonces rompe (* Transposition Table Store; el nodo es la clave de búsqueda para ttEntry *) ttEntry.value: = valor si valor ≤ alphaOrig entonces ttEntry.flag: = LÍMITE SUPERIOR de lo contrario, si valor ≥ β entonces ttEntry.flag: = LOWERBOUND demás ttEntry.flag: = EXACT ttEntry.depth: = profundidad transpositionTableStore (nodo, ttEntry) valor de retorno
(* Llamada inicial para el nodo raíz del jugador A *)negamax (nodo raíz, profundidad, −∞, + ∞, 1)
La poda alfa / beta y las restricciones de profundidad de búsqueda máxima en negamax pueden resultar en una evaluación parcial, inexacta y totalmente omitida de los nodos en un árbol de juego. Esto complica la adición de optimizaciones de la tabla de transposición para negamax. No es suficiente rastrear solo el valor del nodo en la tabla, porque el valor puede no ser el verdadero valor del nodo. Por lo tanto, el código debe preservar y restaurar la relación de valor con los parámetros alfa / beta y la profundidad de búsqueda para cada entrada de la tabla de transposición.
Las tablas de transposición suelen tener pérdidas y omitirán o sobrescribirán los valores anteriores de ciertos nodos del árbol de juego en sus tablas. Esto es necesario ya que el número de visitas negamax de nodos a menudo excede con creces el tamaño de la tabla de transposición. Las entradas de la tabla perdidas u omitidas no son críticas y no afectarán el resultado negamax. Sin embargo, las entradas perdidas pueden requerir que negamax vuelva a calcular ciertos valores de nodo del árbol de juego con más frecuencia, lo que afecta el rendimiento.
Referencias
- George T. Heineman; Gary Pollice y Stanley Selkow (2008). "Capítulo 7: búsqueda de caminos en la IA". Algoritmos en pocas palabras . Oreilly Media . págs. 213–217. ISBN 978-0-596-51624-6.
- John P. Fishburn (1984). "Apéndice A: algunas optimizaciones de búsqueda α-β". Análisis de aceleración en algoritmos distribuidos (revisión de la tesis doctoral de 1981) . Prensa de investigación UMI . págs. 107-111. ISBN 0-8357-1527-2.
- ^ a b c Breuker, Dennis M. Memoria versus búsqueda en juegos , Universidad de Maastricht, 16 de octubre de 1998
- ^ Schaeffer, Jonathan The History Heuristic and Alpha-Beta Search Enhancements in Practice , IEEE Transactions on Pattern Analysis and Machine Intelligence, 1989