Chapitre 6
Recherche en meilleur d'abord
pour les jeux à deux joueurs
Proof Number search [4] , Conspiracy Number search [59, 77) et B * [7, 9) sont des
algorithmes de recherche en meilleur d' abord. Ils ont été utilisés pour résoudre certains
jeux comme Puissance 4 [2], Go-Moku [3] ou plus récemment Fanorona [74).
Le principe des algorithmes de recherche en meilleur d' abord est de garder l ' arbre en
mémoire et de l ' analyser afin de choisir la feuille la plus intéressante à développer.
6.1 L'algorithme Proof Number Search
Proof Number Search (PN-search) permet de prouver qu'un jeu ou qu' une position
est gagnée pour un joueur. Le résultat de l ' algorithme est binaire ; il renvoie 1 s ' il réussit
à prouver le gain et 0 sinon.
PN-search marche particulièrement bien sur les arbres ET/OU quand le nombre de
coups légaux varie beaucoup et qu' on peut élaguer de grandes parties de l ' arbre.
A chaque coup, PN-search cherche à calculer le coût de prouver la valeur de la racine.
Pour cela il calcule le coût de prouver la valeur 1 à chaque noeud de l ' arbre ainsi que le
coût de le prouver la valeur O.
Chaque noeud comporte un Proof Number (PN) qui estime le coût de prouver 1 et un
Oisproof Number (ON) qui estime le coût de prouver O. Une feuille est terminale si elle
correspond à une position gagnée ou perdue. Une feuille non terminale a un PN de 1 et
un ON de 1. Une feuille gagnée a un PN de 0 et un ON infini alors qu' une feuille perdue
a un PN infini et un ON de O.
Recherche en meilleur d'abord
pour les jeux à deux joueurs
Proof Number search [4] , Conspiracy Number search [59, 77) et B * [7, 9) sont des
algorithmes de recherche en meilleur d' abord. Ils ont été utilisés pour résoudre certains
jeux comme Puissance 4 [2], Go-Moku [3] ou plus récemment Fanorona [74).
Le principe des algorithmes de recherche en meilleur d' abord est de garder l ' arbre en
mémoire et de l ' analyser afin de choisir la feuille la plus intéressante à développer.
6.1 L'algorithme Proof Number Search
Proof Number Search (PN-search) permet de prouver qu'un jeu ou qu' une position
est gagnée pour un joueur. Le résultat de l ' algorithme est binaire ; il renvoie 1 s ' il réussit
à prouver le gain et 0 sinon.
PN-search marche particulièrement bien sur les arbres ET/OU quand le nombre de
coups légaux varie beaucoup et qu' on peut élaguer de grandes parties de l ' arbre.
A chaque coup, PN-search cherche à calculer le coût de prouver la valeur de la racine.
Pour cela il calcule le coût de prouver la valeur 1 à chaque noeud de l ' arbre ainsi que le
coût de le prouver la valeur O.
Chaque noeud comporte un Proof Number (PN) qui estime le coût de prouver 1 et un
Oisproof Number (ON) qui estime le coût de prouver O. Une feuille est terminale si elle
correspond à une position gagnée ou perdue. Une feuille non terminale a un PN de 1 et
un ON de 1. Une feuille gagnée a un PN de 0 et un ON infini alors qu' une feuille perdue
a un PN infini et un ON de O.