126
Rec herc he en meilleur d'abord pour les jeux à deux joueurs
borescence, on peut évaluer les noeuds incrémentalement en ne recalculant que ceux par
lesquels on est passé.
On peut améliorer les performances de PN-search en utilisant le nombre de coups
possibles pour initialiser les DN aux noeuds OU et pour initialiser les PN aux noeuds
ET, on peut aussi utiliser une fonction qui évalue la difficulté de prouver une feuille pour
initialiser les PN et les DN.
De plus lorsqu' on cherche à prouver la valeur d' un jeu qui a plus de résultats possibles que gagné ou perdu, par exemple à Fanorona qui a des résultats nuls, on utilise
une recherche dichotomique avec des tests sur les bornes des résultats plutôt que sur les
résultats : par exemple on commence par une recherche qui cherche à prouver le gain, et
si elle échoue on fait une autre recherche pour décider entre la perte et la nulle.
Exercice : É crire un classe Connect qui joue au jeu d' aligner 3 pions sur un goban
11x11. É crire ensuite un programme qui résout ce jeu avec l ' algorithme proof number
search.
6.2 L'algorithme PN2
L' alghorithme PN 2 [13) est une extension de PN-search qui repousse ses limites de
mémoire. Il permet de résoudre des problèmes plus complexes au prix d'une recherche
plus longue. Il réduit la mémoire nécessaire à une recherche PN en l 'échangeant contre
du temps de calcul. Au lieu d' évaluer directement les feuilles de l ' arbre développé par
PN-search, PN 2 effectue une deuxième recherche PN pour les feuilles de l ' arbre. Les
PN et les DN des feuilles de la recherche principale sont initialisés avec les PN et les
DN de la racine de la recherche secondaire. Cette astuce permet d' explorer des arbres
beaucoup plus grands qu' avec PN-search à taille mémoire constante, et moyennant une
perte de temps. Cependant, la limitation principale de PN-search est la capacité mémoire.
L' algorithme PN 2 permet donc de résoudre des problèmes plus complexes que PN.
Exercice : É crire un programme qui utilise PN 2 pour résoudre le jeu d' aligner quatre
pions sur un damier 15xl5.
6.3 L' algorithme PN*
PN* [8 1] est un algorithme PN en profondeur d' abord, ce qui permet de résoudre les
problèmes de mémoire. De la même manière que MTD(f) qui est une version en profondeur d' abord de SSS* et que IDA * qui est une version en profondeur d' abord de A* , PN *
est un algorithme plus simple à programmer et plus efficace que PN-search.
L' idée de PN* est d' utiliser un seuil sur le nombre de feuilles restant à prouver. Si le
nombre de feuilles dépasse ce seuil il suffit alors de couper la branche correspondante.
Rec herc he en meilleur d'abord pour les jeux à deux joueurs
borescence, on peut évaluer les noeuds incrémentalement en ne recalculant que ceux par
lesquels on est passé.
On peut améliorer les performances de PN-search en utilisant le nombre de coups
possibles pour initialiser les DN aux noeuds OU et pour initialiser les PN aux noeuds
ET, on peut aussi utiliser une fonction qui évalue la difficulté de prouver une feuille pour
initialiser les PN et les DN.
De plus lorsqu' on cherche à prouver la valeur d' un jeu qui a plus de résultats possibles que gagné ou perdu, par exemple à Fanorona qui a des résultats nuls, on utilise
une recherche dichotomique avec des tests sur les bornes des résultats plutôt que sur les
résultats : par exemple on commence par une recherche qui cherche à prouver le gain, et
si elle échoue on fait une autre recherche pour décider entre la perte et la nulle.
Exercice : É crire un classe Connect qui joue au jeu d' aligner 3 pions sur un goban
11x11. É crire ensuite un programme qui résout ce jeu avec l ' algorithme proof number
search.
6.2 L'algorithme PN2
L' alghorithme PN 2 [13) est une extension de PN-search qui repousse ses limites de
mémoire. Il permet de résoudre des problèmes plus complexes au prix d'une recherche
plus longue. Il réduit la mémoire nécessaire à une recherche PN en l 'échangeant contre
du temps de calcul. Au lieu d' évaluer directement les feuilles de l ' arbre développé par
PN-search, PN 2 effectue une deuxième recherche PN pour les feuilles de l ' arbre. Les
PN et les DN des feuilles de la recherche principale sont initialisés avec les PN et les
DN de la racine de la recherche secondaire. Cette astuce permet d' explorer des arbres
beaucoup plus grands qu' avec PN-search à taille mémoire constante, et moyennant une
perte de temps. Cependant, la limitation principale de PN-search est la capacité mémoire.
L' algorithme PN 2 permet donc de résoudre des problèmes plus complexes que PN.
Exercice : É crire un programme qui utilise PN 2 pour résoudre le jeu d' aligner quatre
pions sur un damier 15xl5.
6.3 L' algorithme PN*
PN* [8 1] est un algorithme PN en profondeur d' abord, ce qui permet de résoudre les
problèmes de mémoire. De la même manière que MTD(f) qui est une version en profondeur d' abord de SSS* et que IDA * qui est une version en profondeur d' abord de A* , PN *
est un algorithme plus simple à programmer et plus efficace que PN-search.
L' idée de PN* est d' utiliser un seuil sur le nombre de feuilles restant à prouver. Si le
nombre de feuilles dépasse ce seuil il suffit alors de couper la branche correspondante.