La búsqueda de número de prueba (abreviada: búsqueda PN) es un algoritmo de búsqueda de árbol de juego inventado por Victor Allis , [1] con aplicaciones principalmente en solucionadores de finales, pero también para subobjetivos durante los juegos.
Si se utiliza un objetivo binario (por ejemplo, el primer jugador gana el juego), los árboles de juego de información perfecta para dos personas se pueden mapear a un árbol and-or . Los nodos de maximización se convierten en nodos OR, los nodos de minimización se mapean a nodos AND. Para todos los nodos, se almacenan los números de prueba y refutación, y se actualizan durante la búsqueda.
A cada nodo del árbol de juego parcialmente expandido se le asocia el número de prueba y el número de refutación. Un número de prueba representa el número mínimo de nodos de hoja que se deben probar para probar el nodo. Análogamente, un número de refutación representa el número mínimo de hojas que se deben refutar para refutar el nodo. Debido a 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 0 y un número de refutación ∞. Los nodos perdidos o empatados se consideran refutados. Tienen un número de prueba ∞ y un número de refutación 0. Los nodos de hoja desconocidos tienen un número de prueba y 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 se deben probar todos los hijos. 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 se deben refutar todos los 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 capacidad de prueba para expandir es el siguiente. Comenzamos por la raíz. Luego, en cada nodo OR se selecciona como sucesor al hijo con el menor número de prueba y, en cada nodo AND, se selecciona como sucesor al hijo con el menor número de refutación. Finalmente, cuando se llega a un nodo hoja, se expande y se evalúan sus hijos.
Los números de prueba y refutación representan límites inferiores en la cantidad de nodos que se deben evaluar para probar (o refutar) ciertos nodos. Al seleccionar siempre el nodo más probador (o refutador) para expandir, se genera una búsqueda eficiente.
Se han desarrollado algunas variantes de búsqueda de número de prueba como dfPN, PN 2 , PDS-PN [2] para abordar los requisitos de memoria bastante grandes del algoritmo.
{{cite book}}: CS1 maint: bot: estado de URL original desconocido ( enlace ){{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )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