¿Cómo funciona el algoritmo NegaScout?

En la poda Alpha-Beta, NegaScout afirma que puede acelerar el proceso estableciendo [Alpha, Beta] en [Alpha, Alpha-1].

No entiendo todo el proceso de NegaScout.

¿Como funciona? ¿Cuál es su mecanismo de recuperación cuando fallaron sus adivinanzas?

Perdón por la respuesta tardía (¡ 4 años !)

NegaScout es un algoritmo muy simple. Para entender, debemos revisar la profundización iterativa .

La profundización iterativa es una técnica para que un motor de ajedrez busque profundidad i, luego i + 1, luego i + 2, etc. Este es un ejemplo de programación dinámica. Durante cada iteración tenemos nuestra mejor estimación de cuál sería el mejor movimiento. La mayoría de los motores de ajedrez mantendrían este movimiento en una tabla hash.

Imagine que ahora estamos en la iteración i + 1, y tenemos el mejor movimiento desde la última iteración i. Ahora tenemos 5 nodos para buscar, ¿qué deberíamos hacer?

Si suponemos que hemos hecho un trabajo razonablemente bueno durante nuestra última iteración, el mejor movimiento desde la última iteración (que obtenemos de la tabla hash) también debería ser el mejor movimiento para la iteración actual.

Si nuestra suposición es correcta, deberíamos poder ahorrar tiempo al buscar cada movimiento que no sea el mejor movimiento (los cuatro movimientos que no están en la tabla hash) con a null window. Una ventana nula es algo así como:

score := -pvs(child, depth-1, -α-1, -α, -color)

Nota -α-1e -α. Son los valores alfa y beta que daremos a la próxima recursividad. Como el ancho de la ventana es solo 1, la búsqueda siempre fallará:

• Si falla por debajo de α, el movimiento es peor de lo que ya tenemos, por lo que podemos ignorarlo
• Si falla por encima de β, el movimiento es demasiado bueno para jugar, por lo que podemos ignorarlo
• De lo contrario, tenemos que hacer una nueva búsqueda correctamente

Por supuesto, seguiremos buscando el mejor movimiento (el que obtenemos de la tabla hash) con una ventana alfa y beta adecuada. Necesitamos hacer esto porque necesitamos saber exactamente el valor del nodo, no podemos ignorarlo.

Todo lo que he dicho se implementa en el siguiente pseudocódigo. El pseudocódigo especifica, child is not first childpero esta es una forma de verificar si el movimiento también es el mejor movimiento en la iteración anterior. La tabla hash es la implementación más común.

# Negasort is also termed Principal Variation Search - hence - pvs

function pvs(node, depth, α, β, color)
    if node is a terminal node or depth = 0
        return color x the heuristic value of node

    for each child of node
        if child is not the first child
            # search with a null window
            score := -pvs(child, depth - 1, -α - 1, -α, -color)

            # if it failed high, do a full re-search
            if α < score < β
                score := -pvs(child, depth - 1, -β, -score, -color)
        else
            score := -pvs(child, depth - 1, -β, -α, -color)

        α := max(α, score)

        # beta cut-off
        if α >= β
            break

    return α