144
Bases de données de finales
de positions gagnantes dans ce goulot d'étranglement il n'y a souvent qu'un seul coup
gagnant ou un seul coup qui réduit la distance au gain. Ce sont des position très difficiles
à jouer. C'est la raison pour laquelle les positions dans la cloche de droite ont longtemps
été réputées comme étant des parties nulles par de grands analystes. Dans ces position, le
mat est très difficile à trouver. Dans d'autres finales, les analyses aboutissaient au résultat
correct mais pour de mauvaises raisons, réfutées par la base de données.
7 .2 Les Dames anglaises
Les Dames anglaises sont l'équivalent anglais des Dames françaises. Elles sont jouées
sur un damier 8x8, et les pions promus qui sont des Rois ont moins de libertés de déplacement que les dames dans les dames françaises.
J. Schaeffer était à l'origine un joueur et un programmeur d' É checs et un spécialiste
des architectures parallèles. Il a par la suite délaissé la programmation des É checs pour
s'intéresser à celle des Dames anglaises. Chinook, son programme de Dames anglaises
utilise une base de données de finales qui contient toutes les positions de fin de parties
contenant 10 pièces ou moins. Cette base de données lui a permis de résoudre les Dames
anglaises en 2007 [80]. Il a prouvé que la position de départ aux Dames anglaises est nulle.
Les bases de données à 10 pièces ont été utilisées pour évaluer les feuilles de l'arbre de
recherche bien avant la fin réelle de la partie.
Des machines parallèles et des réseaux de stations ont été utilisés pour engendrer ces
bases de données.
A peu près la moitié des positions dans une base de données sont des positions de
capture ; elles sont donc résolues lors de la première passe. Par contre, de nombreuses positions sans capture nécessitent des dizaines de passes avant d'être résolues. La technique
itérative qui consiste à reparcourir toutes les positions résolues à chaque fois devient alors
coûteuse puisque de nombreuses positions déjà résolues sont alors reparcourues à chaque
passe. Pour éviter ces parcours inutiles, Chinook utilise une liste des positions trouvées
lors de la dernière itération, et déjoue les coups à partir de ces positions.
L' algorithme qu'il utilise est donné dans l'algorithme 5.
Algorithm 5 Analyse rétrograde dans Chinook
AnalyseChinook ()
1. Affecter à toutes les positions la valeur INCONNU
2. Parcourir et résoudre toutes les positions de capture
3. Parcourir et résoudre toutes les positions sans capture
4. Aller en 3 si une position sans capture a été résolue
5. Affecter à toutes les positions restantes la valeur NULLE
Bases de données de finales
de positions gagnantes dans ce goulot d'étranglement il n'y a souvent qu'un seul coup
gagnant ou un seul coup qui réduit la distance au gain. Ce sont des position très difficiles
à jouer. C'est la raison pour laquelle les positions dans la cloche de droite ont longtemps
été réputées comme étant des parties nulles par de grands analystes. Dans ces position, le
mat est très difficile à trouver. Dans d'autres finales, les analyses aboutissaient au résultat
correct mais pour de mauvaises raisons, réfutées par la base de données.
7 .2 Les Dames anglaises
Les Dames anglaises sont l'équivalent anglais des Dames françaises. Elles sont jouées
sur un damier 8x8, et les pions promus qui sont des Rois ont moins de libertés de déplacement que les dames dans les dames françaises.
J. Schaeffer était à l'origine un joueur et un programmeur d' É checs et un spécialiste
des architectures parallèles. Il a par la suite délaissé la programmation des É checs pour
s'intéresser à celle des Dames anglaises. Chinook, son programme de Dames anglaises
utilise une base de données de finales qui contient toutes les positions de fin de parties
contenant 10 pièces ou moins. Cette base de données lui a permis de résoudre les Dames
anglaises en 2007 [80]. Il a prouvé que la position de départ aux Dames anglaises est nulle.
Les bases de données à 10 pièces ont été utilisées pour évaluer les feuilles de l'arbre de
recherche bien avant la fin réelle de la partie.
Des machines parallèles et des réseaux de stations ont été utilisés pour engendrer ces
bases de données.
A peu près la moitié des positions dans une base de données sont des positions de
capture ; elles sont donc résolues lors de la première passe. Par contre, de nombreuses positions sans capture nécessitent des dizaines de passes avant d'être résolues. La technique
itérative qui consiste à reparcourir toutes les positions résolues à chaque fois devient alors
coûteuse puisque de nombreuses positions déjà résolues sont alors reparcourues à chaque
passe. Pour éviter ces parcours inutiles, Chinook utilise une liste des positions trouvées
lors de la dernière itération, et déjoue les coups à partir de ces positions.
L' algorithme qu'il utilise est donné dans l'algorithme 5.
Algorithm 5 Analyse rétrograde dans Chinook
AnalyseChinook ()
1. Affecter à toutes les positions la valeur INCONNU
2. Parcourir et résoudre toutes les positions de capture
3. Parcourir et résoudre toutes les positions sans capture
4. Aller en 3 si une position sans capture a été résolue
5. Affecter à toutes les positions restantes la valeur NULLE