La búsqueda de números de prueba (abreviatura: 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.
Usando un objetivo binario (por ejemplo, el primer jugador gana el juego), los árboles de juego de juegos de información perfecta de dos personas se pueden mapear en un árbol y – o . Los nodos maximizadores se convierten en nodos OR, y los nodos minimizados se asignan a los nodos AND. Para todos los nodos, los números de prueba y refutación se almacenan y se actualizan durante la búsqueda.
A cada nodo del árbol de juego parcialmente expandido se asocian 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 hoja que deben probarse para probar el nodo. De manera análoga, un número de refutación representa el número mínimo de hojas que deben refutarse para refutar el nodo. Debido a que el objetivo del árbol es demostrar una victoria forzada, los nodos ganadores se consideran probados. Por lo tanto, tienen el número de prueba 0 y el número de refutación ∞. Los nodos perdidos o dibujados se consideran refutados. Tienen el número de prueba ∞ y el número de refutación 0. Los nodos de hoja desconocidos tienen un número de prueba y de refutación de unidad. 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 deben probarse 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 todos los hijos deben ser refutados. 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 más probado para expandir es el siguiente. Empezamos por la raíz. Luego, en cada nodo OR se selecciona como sucesor al hijo con el número de prueba más bajo, y en cada nodo Y se selecciona como sucesor al hijo con el número de prueba más bajo. Finalmente, cuando se alcanza un nodo hoja, se expande y se evalúan sus hijos.
Los números de prueba y refutación representan límites inferiores en el número de nodos que se evaluarán para probar (o refutar) ciertos nodos. Al seleccionar siempre el nodo más comprobante (refutado) para expandir, se genera una búsqueda eficiente.
Algunas variantes de búsqueda de números de prueba como dfPN, PN 2 , PDS-PN [2] se han desarrollado para abordar los requisitos de memoria bastante grandes del algoritmo.