Generalized Proof Number Search
Tristan Cazenave, Abdallah Saffidine · Base Institutionnelle de Recherche de l'université Paris-Dauphine (BIRD) (University Paris-Dauphine) · 2011
Nous présentons Generalized Proof Number Search (GPNS) un algorithme fondé sur les Proof Numbers, permettant d’obtenir la valeur de positions dans des jeux à multiples résultats. GPNS est une généralisation directe de Proof Number Search (PNS) : dans le cas des jeux à deux résultats les deux algorithmes se comportent exactement de la même manière. Cependant, GPNS permet de traiter directement une classe plus étendue de jeux. Lorsqu’un jeu à plus de deux résultats, on peut utiliser PNS à plusieurs reprises avec différents objectifs pour obtenir finalement la valeur d’une position. À l’inverse, un seul appel à GPNS est suffisant pour obtenir la même information. Nous présentons des résultats expérimentaux sur la résolution du Puissance 4 et de Woodpush, pour divers tailles de plateaux. Ces résultats montrent le nombre de descentes à effectuer pour résoudre une position donnée, est bien moindre pour GPNS que pour PNS.