Búsqueda de variación principal

La búsqueda de variación principal (a veces equiparada con el prácticamente idéntico NegaScout ) es un algoritmo negamax que puede ser más rápido que la poda alfa-beta . Al igual que la poda alfa-beta, NegaScout es un algoritmo de búsqueda direccional para calcular el valor minimax de un nodo en un árbol . Supera a la poda alfa-beta en el sentido de que nunca examinará un nodo que pueda ser podado por alfa-beta; sin embargo, se basa en un ordenamiento preciso de los nodos para aprovechar esta ventaja.

NegaScout funciona mejor cuando hay un buen orden de movimientos. En la práctica, el orden de movimientos suele estar determinado por búsquedas previas menos profundas. Produce más cortes que alfa-beta al asumir que el primer nodo explorado es el mejor. En otras palabras, supone que el primer nodo está en la variación principal . Luego, puede verificar si esto es cierto buscando los nodos restantes con una ventana nula (también conocida como ventana de exploración; cuando alfa y beta son iguales), lo cual es más rápido que buscar con la ventana alfa-beta regular. Si la prueba falla, entonces el primer nodo no estaba en la variación principal, y la búsqueda continúa como alfa-beta normal. Por lo tanto, NegaScout funciona mejor cuando el orden de movimientos es bueno. Con un orden de movimientos aleatorio, NegaScout tardará más tiempo que alfa-beta regular; aunque no explorará ningún nodo que alfa-beta no haya explorado, tendrá que volver a buscar muchos nodos.

Alexander Reinefeld inventó NegaScout varias décadas después de la invención de la poda alfa-beta. En su libro, ofrece una prueba de la corrección de NegaScout. ^{[ 1 ]}

Otro algoritmo de búsqueda llamado SSS* puede, en teoría, resultar en menos nodos buscados. Sin embargo, su formulación original tiene problemas prácticos (en particular, depende en gran medida de una lista OPEN para el almacenamiento) y hoy en día la mayoría de los motores de ajedrez todavía usan una forma de NegaScout en su búsqueda. La mayoría de los motores de ajedrez usan una tabla de transposición en la que se almacena la parte relevante del árbol de búsqueda. Esta parte del árbol tiene el mismo tamaño que tendría la lista OPEN de SSS*. ^{[ 2 ]} Una reformulación llamada MT-SSS* permitió que se implementara como una serie de llamadas de ventana nula a Alpha-Beta (o NegaScout) que usan una tabla de transposición, y se pudieron hacer comparaciones directas usando programas de juego. No superó a NegaScout en la práctica. Otro algoritmo de búsqueda, que sí tiende a hacer mejor que NegaScout en la práctica, es el algoritmo de búsqueda primero el mejor llamado MTD(f) , aunque ninguno de los algoritmos domina al otro. Hay árboles en los que NegaScout busca menos nodos que SSS* o MTD(f) y viceversa.

NegaScout se inspira en SCOUT, inventado por Judea Pearl en 1980, que fue el primer algoritmo en superar a alfa-beta y en demostrarse asintóticamente óptimo. ^{[ 3 ] [ 4 ]} Las ventanas nulas, con β=α+1 en un entorno negamax, fueron inventadas independientemente por JP Fishburn y utilizadas en un algoritmo similar a SCOUT en un apéndice de su tesis doctoral, ^{[ 5 ]} en un algoritmo alfa-beta paralelo, ^{[ 6 ]} y en el último subárbol del nodo raíz de un árbol de búsqueda. ^{[ 7 ]}

La mayoría de los movimientos no son aceptables para ambos jugadores, por lo que no necesitamos explorar cada nodo para obtener la puntuación exacta. Esta puntuación solo se necesita para los nodos de la variación principal (una secuencia óptima de movimientos para ambos jugadores), donde se propagará hasta la raíz. En la búsqueda iterativa de profundización, la iteración anterior ya ha establecido un candidato para dicha secuencia, también conocida como variación principal. Para cualquier nodo no hoja de esta variación principal, sus hijos se reordenan de manera que el siguiente nodo de esta variación principal sea el primer hijo. Se asume que todos los demás hijos resultan en una puntuación peor o igual para el jugador actual (esta suposición se deriva de la suposición de que el candidato PV actual es un PV real). Para probar esto, buscamos el primer movimiento con una ventana completa para establecer un límite superior en la puntuación de los demás hijos, para lo cual realizamos una búsqueda con ventana cero para probar si un movimiento puede ser mejor. Dado que una búsqueda con ventana cero es mucho más económica debido a la mayor frecuencia de cortes beta, esto puede ahorrar mucho esfuerzo. Si encontramos que un movimiento puede aumentar alfa, nuestra suposición se ha refutado para ese movimiento y realizamos una nueva búsqueda con la ventana completa para obtener la puntuación exacta. ^{[ 8 ] [ 9 ]}

La función pvs(nodo, profundidad, α, β, color) es si profundidad = 0 o nodo es un nodo terminal entonces devuelve color × el valor heurístico del nodo para cada hijo del nodo hacer si hijo es el primer hijo entonces puntuación := − pvs(hijo, profundidad − 1, − β, − α, − color) sino puntuación := − pvs(hijo, profundidad − 1, − α − 1, − α, − color) (* búsqueda con una ventana nula *) si α < puntuación < β entonces puntuación := − pvs(hijo, profundidad − 1, − β, − α, − color) (* si falló alto, hacer una búsqueda completa de nuevo *) α := max(α, puntuación) Si α ≥ β , entonces romper (* beta corte *) devolver α

• Heurística asesina

• Teoría de la programación del ajedrez por computadora
• Programación de juegos de estrategia