66
Recherche avec menaces
Nous présentons dans ce chapitre des algorithmes de recherche qui permettent non
seulement de faire une sélection sévère des coups à envisager mais aussi de donner des
résultats plus fiables que les algorithmes sélectifs de recherche classiques comme la recherche avec coup nul, puisque ces résultats sont prouvés. En effet les algorithmes avec
menaces analysent les raisons pour lesquelles une menace marche et utilisent ces raisons
pour trouver l'ensemble complet des coups qui invalident la menace. Ainsi ils n'oublient
jamais de réfutation et sont tout de même sélectifs. Les algorithmes qui utilisent des vérifications de menaces améliorent à la fois le temps de réponse des programmes de jeux et
leur précision.
4.2 Le Phutb all
Le Football des philosophes (ou Phutball) est un jeu décrit dans Winning Ways [6] ,
un ouvrage sur la théorie combinatoire des jeux [29] appliquée à de nombreux jeux. Il a
été surnommé Phutball par J. H. Conway. Les auteurs de Winning Ways pensent que ce
jeu ne peut pas être totalement analysé par la théorie combinatoire des jeux (cf chapitre
14) car il est trop complexe.
Le Football des philosophes a été imaginé par Conway pour un damier 19x15. Les
buts étant les lignes de longueur 15. Il est aussi joué sur des damiers de Go l 9x l 9. Une
pierre noire représente la balle et les pierres blanches représentent les joueurs de Football.
To utes les pièces sont communes aux deux joueurs, et les deux joueurs ont les mêmes
coups légaux.
La partie commence avec un damier vide, la balle est placée sur l'intersection centrale.
Ensuite, à chaque coup, chaque joueur doit (i) soit poser une nouvelle pierre blanche
sur une intersection vide (ii) soit faire sauter la balle par dessus des pierres blanches en
enlevant les pierres sautées au fur et à mesure de ses sauts.
Un saut peut être dans n'importe laquelle des 8 directions. On peut prendre une ligne
continue de pierres en sautant par dessus. On peut effectuer plusieurs sauts dans des directions différentes dans le même coup. Le but du jeu est de faire parvenir la balle sur la
première ligne du camp adverse, ou derrière cette première ligne.
La figure 4. 1 donne une partie de Phutball 9x9. Après le coup numéro 11, la balle est
sur la dernière ligne à droite et c'est donc le joueur Gauche qui a gagné.
La complexité algorithmique du Phutball n'a pas encore été trouvée. To utefois, le
simple problème de déterminer si le joueur qui a la main peut gagner en un coup est déjà
NP-complet [32).
Exercice : É crire une classe Phutball qui représente un damier et qui permet de jouer
des coups sur le modèle de la classe Virus du chapitre un. É crire un programme de Phutball qui joue aléatoirement.
Recherche avec menaces
Nous présentons dans ce chapitre des algorithmes de recherche qui permettent non
seulement de faire une sélection sévère des coups à envisager mais aussi de donner des
résultats plus fiables que les algorithmes sélectifs de recherche classiques comme la recherche avec coup nul, puisque ces résultats sont prouvés. En effet les algorithmes avec
menaces analysent les raisons pour lesquelles une menace marche et utilisent ces raisons
pour trouver l'ensemble complet des coups qui invalident la menace. Ainsi ils n'oublient
jamais de réfutation et sont tout de même sélectifs. Les algorithmes qui utilisent des vérifications de menaces améliorent à la fois le temps de réponse des programmes de jeux et
leur précision.
4.2 Le Phutb all
Le Football des philosophes (ou Phutball) est un jeu décrit dans Winning Ways [6] ,
un ouvrage sur la théorie combinatoire des jeux [29] appliquée à de nombreux jeux. Il a
été surnommé Phutball par J. H. Conway. Les auteurs de Winning Ways pensent que ce
jeu ne peut pas être totalement analysé par la théorie combinatoire des jeux (cf chapitre
14) car il est trop complexe.
Le Football des philosophes a été imaginé par Conway pour un damier 19x15. Les
buts étant les lignes de longueur 15. Il est aussi joué sur des damiers de Go l 9x l 9. Une
pierre noire représente la balle et les pierres blanches représentent les joueurs de Football.
To utes les pièces sont communes aux deux joueurs, et les deux joueurs ont les mêmes
coups légaux.
La partie commence avec un damier vide, la balle est placée sur l'intersection centrale.
Ensuite, à chaque coup, chaque joueur doit (i) soit poser une nouvelle pierre blanche
sur une intersection vide (ii) soit faire sauter la balle par dessus des pierres blanches en
enlevant les pierres sautées au fur et à mesure de ses sauts.
Un saut peut être dans n'importe laquelle des 8 directions. On peut prendre une ligne
continue de pierres en sautant par dessus. On peut effectuer plusieurs sauts dans des directions différentes dans le même coup. Le but du jeu est de faire parvenir la balle sur la
première ligne du camp adverse, ou derrière cette première ligne.
La figure 4. 1 donne une partie de Phutball 9x9. Après le coup numéro 11, la balle est
sur la dernière ligne à droite et c'est donc le joueur Gauche qui a gagné.
La complexité algorithmique du Phutball n'a pas encore été trouvée. To utefois, le
simple problème de déterminer si le joueur qui a la main peut gagner en un coup est déjà
NP-complet [32).
Exercice : É crire une classe Phutball qui représente un damier et qui permet de jouer
des coups sur le modèle de la classe Virus du chapitre un. É crire un programme de Phutball qui joue aléatoirement.