Negamax

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 que ⁠ ⁠${\displaystyle \min(a,b)=-\max(-b,-a)}$ 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 que mueve busca un movimiento que maximice la negación del valor resultante del movimiento: esta posición sucesora debe haber sido valorada por definición 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 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 juego) 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 búsqueda de negamax es encontrar el valor de puntuación del nodo del jugador que está jugando en el nodo raíz. El pseudocódigo a continuación muestra el algoritmo base de 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 := máx(valor, −negamax(hijo, profundidad − 1, −color))
    valor
 de retorno

(*Llamada inicial al nodo raíz del jugador A*)
negamax(nodo raíz, profundidad, 1)

(*Llamada inicial al 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 secundario que finalmente establece la mejor puntuación del nodo raíz también representa el mejor movimiento a realizar. 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 conservarlo ni devolverlo 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 de los nodos en los que el jugador A está a punto de jugar y donde el jugador A es el jugador que maximiza 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 que minimiza 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 (por ejemplo, en una partida de ajedrez, si es el turno de las blancas y las blancas están ganando, debe devolver un valor positivo. Sin embargo, si es el turno de las negras, debe devolver un valor negativo).

La función negamax(nodo, profundidad) es 
    si la profundidad = 0 o el nodo es un nodo terminal , entonces 
        devuelve evaluationPosition() // Desde la perspectiva del jugador actual
    valor := −∞
    Para cada hijo del nodo hacer
        valor := máx(valor, −negamax(hijo, profundidad − 1))
    valor
 de retorno

// Ejemplo de elección del mejor movimiento en una partida de ajedrez utilizando la función negamax anterior.
 La función think(boardState) es
    allMoves := generateLegalMoves(estadodeltablero)
    mejorMovimiento := null
    mejorEvaluacion := -∞

    para cada movimiento en allMoves
        tablero.aplicar(mover)
        evaluarMover := -negamax(estadodeltablero, profundidad=3)
        tablero.deshacer(mover)
        si evaluarMover > mejorEvaluación
            mejorMovimiento := movimiento
            mejorEvaluación := evaluarMovimiento

    Devolver mejor movimiento

Las optimizaciones de algoritmos para minimax también son igualmente aplicables para Negamax. La poda alfa-beta puede reducir la cantidad de nodos que el algoritmo negamax evalúa en un árbol de búsqueda de manera similar a su uso con el algoritmo minimax.

El pseudocódigo para la búsqueda negamax con limitación de profundidad y 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 hacer
        valor := máx(valor, −negamax(hijo, profundidad − 1, −β, −α, −color))
        α := máx(α, valor)
        Si α ≥ β entonces 
            se rompe  (*corte*)
     valor
 de retorno

(*Llamada inicial al nodo raíz del jugador A*)
negamax(nodo raíz, profundidad, −∞, +∞, 1)

Alfa (α) y beta (β) representan los límites superior e inferior de 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 el árbol.

Cuando negamax encuentra un valor de nodo secundario fuera de un rango alfa/beta, la búsqueda negamax corta, eliminando así porciones del árbol de juego de la exploración. Los cortes son implícitos en función del valor de retorno del nodo. Un valor de nodo que se encuentre 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 ningún límite α y β. Si un valor de retorno de 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 finalmente descarta cualquier resultado de límite de valor. Dichos valores no contribuyen ni afectan el valor negamax en su nodo raíz.

Este pseudocódigo muestra la variante fail-soft de la poda alfa-beta. La variante fail-soft nunca devuelve α o β directamente como valor de nodo. Por lo tanto, un valor de nodo puede estar fuera de los límites iniciales de rango α y β establecidos con una llamada a la función negamax. Por el contrario, la poda alfa-beta fail-hard siempre limita un valor de nodo en el rango de α y β.

Esta implementación también muestra un orden de movimiento opcional antes del bucle foreach que evalúa los nodos secundarios. El orden de movimiento ^[2] es una optimización para la poda alfa-beta que intenta adivinar los nodos secundarios más probables que arrojan la puntuación del nodo. El algoritmo busca primero esos nodos secundarios. El resultado de las conjeturas correctas es anterior y se producen cortes alfa/beta más frecuentes, por lo que se podan ramas adicionales del árbol de juego y los nodos secundarios restantes del árbol de búsqueda.

Las tablas de transposición memorizan de forma selectiva los valores de los nodos en el árbol de juego. La transposición es un término que indica que se puede llegar a una posición determinada del tablero de juego de más de una manera con distintas secuencias de movimientos.

Cuando negamax busca en el árbol de juego y encuentra el mismo nodo varias veces, una tabla de transposición puede devolver un valor calculado previamente del nodo, lo que evita tener que volver a calcular el valor del nodo, lo que puede resultar largo y duplicado. El rendimiento de Negamax mejora especialmente en el caso de á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
    alfaOrig := α

    (*Búsqueda en la tabla de transposición; el nodo es la clave de búsqueda para ttEntry *)
    ttEntry := transpositionTableLookup(nodo)
    si ttEntry.is_valid y ttEntry.depth ≥ depth entonces 
        si ttEntry.flag = EXACT entonces 
            devuelve ttEntry.value
         de lo contrario si ttEntry.flag = LOWERBOUND entonces
            α := máx(α, ttEntrada.valor)
        De lo contrario, si ttEntry.flag = UPPERBOUND entonces
            β := min(β, ttEntrada.valor)

        Si α ≥ β entonces 
            devuelve ttEntry.value

    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 := −∞
    Para cada niño en childNodes, haga
        valor := máx(valor, −negamax(hijo, profundidad − 1, −β, −α, −color))
        α := máx(α, valor)
        Si α ≥ β entonces 
            se rompe

    (*Almacén de la tabla de transposición; 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 el valor es ≥ β entonces
        ttEntry.flag := LÍMITE INFERIOR
    demás
        ttEntry.flag := EXACTO
    ttEntry.depth := profundidad
    ttEntry.is_valid := verdadero
    transpositionTableStore(nodo, ttEntry)

    valor
 de retorno

(*Llamada inicial al 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 dar como resultado 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 valor verdadero del nodo. Por lo tanto, el código debe preservar y restaurar la relación del 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 juego en sus tablas. Esto es necesario ya que la cantidad de nodos que negamax visita a menudo excede por mucho el tamaño de la tabla de transposición. Las entradas de tabla perdidas u omitidas no son críticas y no afectarán el resultado de negamax. Sin embargo, las entradas perdidas pueden requerir que negamax vuelva a calcular ciertos valores de nodos del árbol de juego con mayor frecuencia, lo que afecta el rendimiento.

• George T. Heineman; Gary Pollice y Stanley Selkow (2008). "Capítulo 7: Búsqueda de caminos en 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 la búsqueda α-β". Análisis de la aceleración en algoritmos distribuidos (revisión de la tesis doctoral de 1981) . UMI Research Press . pp. 107–111. ISBN 0-8357-1527-2.

• Negamax en la Wiki de Programación de Ajedrez
• Una implementación C99 del algoritmo Negamax para el juego Tic-Tac-Toe