7 .6 Corrigés des exercices
7 .6 Corrigés des exercices
7.6.1 Nombre de positions à 6 pièces aux Échecs
147
Une solution non optimale consisterait à allouer 64 x 63 x 62 x 61 x 60 x 59 octets.
Une meilleure solution consiste à forcer le roi noir dans un huitième de l'échiquier,
il n'a donc que I O positions possibles. Pour les quatre positions sur la diagonale on peut
forcer le roi blanc dans une moitié de l'échiquier.
Le nombre de positions du roi blanc pour chaque position du roi noir est donc :
/
\
1
1
1
1
1
1
1
1
1
30
1
1
55 30
1
1
55 55 30
1
1
58 58 58 33 1
\
/
Remarque : on ne peut faire les rotations et les symétries que pour les finales sans
pions.
On a donc 3 x 30 + 3 x 55 + 3 x 58 + 33 = 462 façons de placer les deux rois.
Pour les finales à 6 pièces chacune des 4 pièces restantes peut être placée sur 64 cases,
on a donc 64 4 (16M) combinaisons de pièces, donc pour une seule configuration de 6
pièces on a 7.75 * 10 9 positions ce qui occuppe 8 Go. Si chaque position est stockée
comme un bit, pour un seul tableau, on a besoin de 970 Mo de mémoire.
On peut noter au passage que K. Thompson n'a pas écrit lui même les générateurs de
positions antérieures mais qu 'il a écrit un programme qui les écrivaient pour chaque finale
différente.
Les finales à 6 pièces sont 64 fois plus grandes que les finales à 5 pièces. De plus il
y a 5 fois plus de finales à 6 pièces que de finales à 5 pièces et les finales à 6 pièces sont
à peu près deux fois plus longues que les finales à 5 pièces. Donc les finales à 6 pièces
prennent 1000 fois plus de temps à construire que les finales à 5 pièces. Des algorithmes
de gestion mémoire comme LRU (Least Recently Used = Décharger la zone mémoire la
moins récemment utilisée) peuvent être utiles pour optimiser l'utilisation de la mémoire
en analyse rétrograde.