La búsqueda Negamax es una variante de la 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 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. Así, el jugador en movimiento busca un movimiento que maximice la negación del valor resultante del movimiento: esta posición sucesora por definición debe haber sido valorado por el oponente. El razonamiento de la frase anterior funciona independientemente de si A o B están en movimiento. Esto significa que se puede utilizar un único 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 seleccione el movimiento con el sucesor de valor mínimo.
No debe confundirse con negascout , un algoritmo para calcular rápidamente el valor minimax o negamax 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 rápidamente el valor minimax o negamax de una posición evitando la búsqueda de ciertas posiciones poco interesantes.
La mayoría de los motores de búsqueda adversarios están codificados utilizando alguna forma de búsqueda negamax.
NegaMax opera en los mismos árboles de juego que los utilizados 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 un juego de dos jugadores. Las transiciones a nodos secundarios representan movimientos disponibles para un jugador que está a punto de jugar desde un nodo determinado.
El objetivo de la búsqueda negamax es encontrar el valor de puntuación del nodo para el jugador que juega en el nodo raíz. El pseudocódigo siguiente muestra el algoritmo base negamax, [1] con un límite configurable para la profundidad máxima de búsqueda:
la función negamax (nodo, profundidad, color) es si profundidad = 0 o el nodo es un nodo terminal, entonces devuelve color × el valor heurístico del nodo valor := −∞ para cada hijo del nodo hacer valor := max(valor, −negamax(niño, profundidad − 1, −color)) valor de retorno
(*Llamada inicial para el nodo raíz del Jugador A*)negamax(nodoraíz, profundidad, 1)
(*Llamada inicial para el nodo raíz del Jugador B*)negamax(nodoraíz, profundidad, −1)
El nodo raíz hereda su puntuación de uno de sus nodos secundarios inmediatos. El nodo secundario 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 retendrán y devolverán tanto el mejor movimiento como la mejor puntuación para el nodo raíz. Sólo la mejor puntuación del nodo es esencial con los nodos que no son raíz. Y no es necesario retener ni regresar el mejor movimiento de un nodo 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 parte de 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 Negamax coinciden con las puntuaciones 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 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.
Negamax se puede implementar sin 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 (Ej: en un juego de ajedrez, si es el turno de las blancas y las blancas están ganando, debería devolver un valor positivo. Sin embargo, si es el turno de las negras, debería devolver un valor negativo).
la función negamax(nodo, profundidad) es si profundidad = 0 o el nodo es un nodo terminal, entonces regresa evaluaPosition() // Desde la perspectiva del jugador actual valor := −∞ para cada hijo del nodo hacer valor := max(valor, −negamax(niño, profundidad − 1)) valor de retorno
// Ejemplo de elección del mejor movimiento en un juego de ajedrez usando la función negamax anterior a la función think(boardState) es todos los movimientos: = generar movimientos legales (estado del tablero) mejorMovida := nulo mejorEvaluación := -∞ para cada movimiento en allMoves tablero.aplicar(mover) evaluarMove := -negamax(boardState, profundidad=3) tablero.deshacer(mover) si evaluarMover > mejorEvaluación mejorMovida := mover mejorEvaluación := evaluarMovimiento devolver mejor movimiento
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 de profundidad limitada con poda alfa-beta es el siguiente: [1]
la función negamax (nodo, profundidad, α, β, color) es si profundidad = 0 o el nodo es un nodo terminal , entonces devuelve color × el valor heurístico del nodo childNodes: = generarMoves (nodo) childNodes := ordenMoves(childNodes) valor := −∞ foreach niño en childNodes hacer valor := max(valor, −negamax(niño, profundidad − 1, −β, −α, −color)) α := máx(α, valor) si α ≥ β entonces rompe (* corte *) valor de retorno
(*Llamada inicial para el nodo raíz del Jugador A*)negamax(raízNodo, profundidad, −∞, +∞, 1)
Alfa (α) y beta (β) representan límites inferior y superior para los valores de los nodos secundarios en 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 en árbol.
Cuando negamax encuentra un valor de nodo secundario fuera de un rango alfa/beta, la búsqueda de negamax corta, eliminando así partes del árbol del juego de la exploración. Los límites son implícitos según el valor de retorno del nodo. Un valor de nodo que se encuentra dentro del rango de sus α y β iniciales 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 el valor ≤ α) o inferior (si el valor ≥ β) para el valor exacto del nodo. La poda alfa-beta eventualmente descarta cualquier resultado con límite de valor. Dichos valores no contribuyen ni afectan el valor negamax 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 valor de nodo. Por lo tanto, un valor de nodo puede estar fuera de los límites de rango iniciales α y β establecidos con una llamada a función negamax. Por el contrario, la poda alfa-beta resistente siempre limita un valor de nodo en el rango de α y β.
Esta implementación también muestra el orden de movimientos opcional antes del bucle foreach que evalúa los nodos secundarios. El orden de movimientos [2] es una optimización para la poda alfa beta que intenta adivinar los nodos secundarios más probables que produzcan la puntuación del nodo. El algoritmo busca primero esos nodos secundarios. El resultado de buenas conjeturas es que se producen cortes alfa/beta más tempranos y más frecuentes, podando así ramas adicionales del árbol de juegos y nodos secundarios restantes del árbol de búsqueda.
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 determinada posición del tablero de juego se puede alcanzar de más de una manera 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 del nodo previamente calculado, omitiendo un nuevo cálculo potencialmente largo y duplicado del valor del nodo. El rendimiento de Negamax mejora particularmente para árboles de juego con muchos caminos 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 a continuación: [1]
la función negamax(nodo, profundidad, α, β, color) es origen alfa := α (* Búsqueda de tabla de transposición; el nodo es la clave de búsqueda para ttEntry *) ttEntry := transposiciónTableLookup(nodo) si ttEntry es válido y ttEntry. Depth ≥ profundidad , entonces si ttEntry.flag = EXACT entonces devuelve ttEntry.value; de lo contrario, si ttEntry.flag = LOWERBOUND, entonces α := máx(α, ttEntry.valor) de lo contrario, si ttEntry.flag = SUPERIOR entonces β := min(β, ttEntrada.valor) si α ≥ β entonces devuelve ttEntry.value si profundidad = 0 o el nodo es un nodo terminal, entonces devuelve color × el valor heurístico del nodo childNodes: = generarMoves (nodo) childNodes := ordenMoves(childNodes) valor := −∞ para cada niño en childNodes hacer valor := max(valor, −negamax(niño, profundidad − 1, −β, −α, −color)) α := máx(α, valor) si α ≥ β entonces romper (* Almacén de tablas de transposición; el nodo es la clave de búsqueda para ttEntry *) ttEntry.valor: = valor si valor ≤ alphaOrig entonces ttEntry.flag := LÍMITE SUPERIOR de lo contrario, si el valor es ≥ β , entonces ttEntry.flag := LÍMITE INFERIOR demás ttEntry.flag := EXACTO ttEntry.profundidad: = profundidad ttEntry.is_valid: = verdadero transposiciónTableStore(nodo, ttEntry) valor de retorno
(*Llamada inicial para el nodo raíz del Jugador A*)negamax(raízNodo, profundidad, −∞, +∞, 1)
La poda alfa/beta y las restricciones de profundidad de búsqueda máxima en negamax pueden dar como resultado una evaluación parcial, inexacta y omitida por completo de los nodos en un árbol de juego. Esto complica agregar optimizaciones de la tabla de transposición para negamax. No es suficiente realizar un seguimiento únicamente del valor del nodo en la tabla, porque es posible que el valor no sea el valor verdadero 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 valores anteriores de ciertos nodos del árbol de juegos en sus tablas. Esto es necesario ya que el número de visitas negamax a los 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 nodos del árbol de juegos con mayor frecuencia, lo que afecta el rendimiento.
