142
Algorithm 4 Analyse rétrograde
Analyse ()
initialiser tous les résultats à inconnu
for toutes les positions do
if position terminale then
affecter le résultat de la position
end if
end for
while on trouve de nouveaux résultats do
for toute les positions do
if position de résultat inconnu then
Bases de données de finales
if un coup amène à une position perdante pour l ' adversaire ou tous les coups
amènent à des positions gagnantes pour l ' adversaire then
affecter le résultat de la position
on a trouvé un nouveau résultat
end if
end if
end for
end while
7.1 Les Échecs
7.1.1 Principe de l'algorithme
En sus d 'être l ' auteur du système d'exploitation UNIX, du langage C, et d' avoir obtenu le prestigieux prix Turing, K. Thompson est aussi connu pour avoir créé des bases de
données de finales aux É checs (87, 88] qui ont permis de découvrir de nouvelles connaissances échiquéennes et de jouer les fins de parties mieux que les grands maîtres. Son
programme est bien sûr écrit en langage C.
L' algorithme consiste à effectuer un Minimax à l' envers en partant des positions gagnantes. Pour chaque position terminale, on trouve les positions qui y mènent par un générateur de positions antérieures ; on enregistre les nouvelles positions comme étant des
positions gagnantes en un coup pour Blanc. On trouve alors les positions qui y mènent
par un coup Noir, et on vérifie que tous les coups Noirs de ces positions sont perdants ;
on a alors des positions gagnées pour Blanc à un coup. On réitère le processus jusqu' à ce
qu'on ne trouve plus de nouvelles positions.
L' algorithme convertit une position en un nombre unique, ce nombre est utilisé pour
indicer un tableau de positions d' É checs. On cherche à trouver un codage qui ait un
nombre maximum le plus petit possible afin de minimiser la taille de la base de données.
Exercice : Si on ne considère que les finales sans pions, les positions ont le mêmes
propriétés par symétrie horizontale, verticale ou diagonale. Combien de façons différentes
y a-t-il de placer le roi noir et le roi blanc ? Pour une finale à 6 pièces, quelle est la taille
Algorithm 4 Analyse rétrograde
Analyse ()
initialiser tous les résultats à inconnu
for toutes les positions do
if position terminale then
affecter le résultat de la position
end if
end for
while on trouve de nouveaux résultats do
for toute les positions do
if position de résultat inconnu then
Bases de données de finales
if un coup amène à une position perdante pour l ' adversaire ou tous les coups
amènent à des positions gagnantes pour l ' adversaire then
affecter le résultat de la position
on a trouvé un nouveau résultat
end if
end if
end for
end while
7.1 Les Échecs
7.1.1 Principe de l'algorithme
En sus d 'être l ' auteur du système d'exploitation UNIX, du langage C, et d' avoir obtenu le prestigieux prix Turing, K. Thompson est aussi connu pour avoir créé des bases de
données de finales aux É checs (87, 88] qui ont permis de découvrir de nouvelles connaissances échiquéennes et de jouer les fins de parties mieux que les grands maîtres. Son
programme est bien sûr écrit en langage C.
L' algorithme consiste à effectuer un Minimax à l' envers en partant des positions gagnantes. Pour chaque position terminale, on trouve les positions qui y mènent par un générateur de positions antérieures ; on enregistre les nouvelles positions comme étant des
positions gagnantes en un coup pour Blanc. On trouve alors les positions qui y mènent
par un coup Noir, et on vérifie que tous les coups Noirs de ces positions sont perdants ;
on a alors des positions gagnées pour Blanc à un coup. On réitère le processus jusqu' à ce
qu'on ne trouve plus de nouvelles positions.
L' algorithme convertit une position en un nombre unique, ce nombre est utilisé pour
indicer un tableau de positions d' É checs. On cherche à trouver un codage qui ait un
nombre maximum le plus petit possible afin de minimiser la taille de la base de données.
Exercice : Si on ne considère que les finales sans pions, les positions ont le mêmes
propriétés par symétrie horizontale, verticale ou diagonale. Combien de façons différentes
y a-t-il de placer le roi noir et le roi blanc ? Pour une finale à 6 pièces, quelle est la taille