Búsqueda de número de prueba

La búsqueda de número de prueba (abreviado: búsqueda PN) es un algoritmo de búsqueda de árbol de juego inventado por Victor Allis , ^{[ 1 ]} con aplicaciones principalmente en solucionadores de final de juego , pero también para subobjetivos durante los juegos.

Utilizando un objetivo binario (por ejemplo, el primer jugador gana la partida), los árboles de juego de juegos de información perfecta para dos personas se pueden representar como un árbol AND-OR . Los nodos de maximización se convierten en nodos OR, y los nodos de minimización se convierten en nodos AND. Para todos los nodos, se almacenan los números de prueba y refutación, que se actualizan durante la búsqueda.

A cada nodo del árbol de juego parcialmente expandido se le asocian un número de prueba y un número de refutación. Un número de prueba representa el número mínimo de nodos hoja que deben probarse para probar el nodo. De forma análoga, un número de refutación representa el número mínimo de hojas que deben refutarse para refutar el nodo. Dado que el objetivo del árbol es probar una victoria forzada, los nodos ganadores se consideran probados. Por lo tanto, tienen un número de prueba de 0 y un número de refutación infinito. Los nodos perdidos o empatados se consideran refutados. Tienen un número de prueba infinito y un número de refutación de 0. Los nodos hoja desconocidos tienen un número de prueba y de refutación de uno. El número de prueba de un nodo AND interno es igual a la suma de los números de prueba de sus hijos, ya que para probar un nodo AND todos los hijos deben ser probados. El número de refutación de un nodo AND es igual al mínimo de los números de refutación de sus hijos. El número de refutación de un nodo OR interno es igual a la suma de los números de refutación de sus hijos, ya que para refutar un nodo OR es necesario refutar todos sus hijos. Su número de prueba es igual al mínimo de los números de prueba de sus hijos.

El procedimiento para seleccionar el nodo con mayor número de pruebas para su expansión es el siguiente: comenzamos en la raíz. Luego, en cada nodo OR, se selecciona como sucesor el hijo con el menor número de pruebas, y en cada nodo AND, se selecciona como sucesor el hijo con el menor número de refutación. Finalmente, al llegar a un nodo hoja, este se expande y se evalúan sus hijos.

Los números de prueba y refutación representan límites inferiores para la cantidad de nodos que deben evaluarse para probar (o refutar) ciertos nodos. Al seleccionar siempre el nodo que más prueba (o refuta) para expandir, se genera una búsqueda eficiente.

Se han desarrollado algunas variantes de búsqueda de número de prueba como dfPN, PN ² , PDS-PN ^{[ 2 ]} para abordar los requisitos de memoria bastante grandes del algoritmo.

A. Kishimoto, MHM Winands, M. Müller y JT. Saito (2012) Búsqueda en árboles de juego utilizando números de prueba: Los primeros veinte años , ICGA, 35(3):131–156, pdf