La búsqueda de variación principal (a veces equiparada con el NegaScout prácticamente idéntico ) 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 . Domina 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 una ordenación precisa de los nodos para aprovechar esta ventaja.
NegaScout funciona mejor cuando hay un buen orden de movimiento. En la práctica, el orden de los movimientos suele estar determinado por búsquedas previas menos profundas. Produce más cortes que alfa-beta asumiendo 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 eso es cierto buscando en los nodos restantes con una ventana nula (también conocida como ventana de exploración; cuando alfa y beta son iguales), que es más rápido que buscar con la ventana alfa-beta normal. 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 los movimientos es bueno. Con un orden de movimiento aleatorio, NegaScout llevará más tiempo que el alfa-beta normal; aunque no explorará ningún nodo que alpha-beta no lo hizo, 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. Da una prueba de la corrección de NegaScout en su libro. [1]
Otro algoritmo de búsqueda llamado SSS * teóricamente puede resultar en menos nodos buscados. Sin embargo, su formulación original tiene problemas prácticos (en particular, se basa en gran medida en una lista ABIERTA 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 utilizan 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 podrían hacer comparaciones directas usando programas de juego. No superó a NegaScout en la práctica. Otro algoritmo de búsqueda, que tiende a funcionar mejor que NegaScout en la práctica, es el algoritmo del mejor primero llamado MTD (f) , aunque ninguno de los dos domina al otro. Hay árboles en los que NegaScout busca menos nodos que SSS * o MTD (f) y viceversa.
NegaScout se asemeja a SCOUT, inventado por Judea Pearl en 1980, que fue el primer algoritmo en superar al alfa-beta y en ser probado asintóticamente óptimo. [3] [4] Las ventanas nulas, con β = α + 1 en una configuración negamax, fueron inventadas de forma independiente por JP Fishburn y utilizadas en un algoritmo similar a SCOUT en un apéndice de su Ph.D. tesis, [5] en un algoritmo alfa-beta paralelo, [6] y en el último subárbol de un nodo raíz del árbol de búsqueda. [7]
La idea
La mayoría de los movimientos no son aceptables para ambos jugadores, por lo que no necesitamos buscar por completo en cada nodo para obtener la puntuación exacta. El puntaje exacto solo se necesita en la variación principal (una secuencia de movimientos aceptables para ambos jugadores) que se espera que se propague hasta la raíz. En la búsqueda iterativa de profundización, la iteración anterior ya ha establecido tal secuencia. En un nodo que tiene una puntuación que termina dentro de la ventana, que se llama PV-nodo, buscamos el primer movimiento, que se considera mejor, en una ventana completa para establecer un límite. Eso es necesario para demostrar que otros movimientos son inaceptables. Realizamos una búsqueda de ventana cero para probar si un movimiento puede ser mejor. Dado que una búsqueda de ventana cero es mucho más barata, puede ahorrar mucho esfuerzo. Si descubrimos que un movimiento puede aumentar el alfa, hacemos una nueva búsqueda con la ventana completa para obtener la puntuación exacta. [8] [9]
Pseudocódigo
la función pvs (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 para cada hijo del nodo hacer si el hijo es el primer hijo, entonces puntuación: = −pvs (hijo, profundidad - 1, −β, −α, −color) else puntuación: = −pvs (hijo, profundidad - 1, −α - 1, −α, −color) (* búsqueda con una ventana nula *) si αón>entonces puntuación: = −pvs (hijo, profundidad - 1, −β, −score, −color) (* si falló alto, haga una nueva búsqueda completa *) α: = max (α, puntuación) si α ≥ β entonces rompe (* corte beta *) regresa α
Ver también
Referencias
- ^ A. Reinefeld. Spielbaum-Suchverfahren. Informatik-Fachbericht 200, Springer-Verlag, Berlín (1989), ISBN 3-540-50742-6
- ^ Plaat, Aske; Jonathan Schaeffer; Wim Pijls; Arie de Bruin (noviembre de 1996). "Mejor primero algoritmos Minimax de profundidad fija" . Inteligencia artificial . 87 (1–2): 255–293. doi : 10.1016 / 0004-3702 (95) 00126-3 .
- ^ Pearl, J., "SCOUT: Un algoritmo de búsqueda de juegos simple con propiedades óptimas probadas", Actas de la Primera Conferencia Nacional Anual sobre Inteligencia Artificial, Universidad de Stanford, 18-21 de agosto de 1980, págs. 143-145.
- ^ Pearl, J., "Propiedades asintóticas de árboles Minimax y procedimientos de búsqueda de juegos" , Inteligencia artificial, vol. 14, núm. 2, págs. 113-138, septiembre de 1980.
- ^ Fishburn, JP, "Análisis de aceleración en algoritmos distribuidos", Prensa de investigación de UMI ISBN 0-8357-1527-2 , 1981, 1984.
- ^ Fishburn, JP, Finkel, RA y Lawless, SA, Actas de "Búsqueda paralela alfa-beta en Arachne" 1980 Int. Conf. Procesamiento paralelo, IEEE, 26 al 29 de agosto de 1980, págs. 235-243.
- ^ Fishburn, JP, "Una optimización de la búsqueda alfa-beta" ACM SIGART Bulletin , número 72, julio de 1980, págs. 29-31.
- ^ Judea Pearl (1980). Propiedades asintóticas de árboles Minimax y procedimientos de búsqueda de juegos. Inteligencia artificial, vol. 14, No. 2
- ^ Murray Campbell, Tony Marsland (1983). Una comparación de algoritmos de búsqueda de árboles Minimax. Inteligencia artificial, vol. 20, núm. 4, págs. 347-367. ISSN 0004-3702.