Combien de parties possibles aux dames ? L'arbre des coups compté demi-coup par demi-coup
Aux dames internationales, les Blancs ont 9 premiers coups, et les Noirs 9 réponses à chacun : 81 débuts de partie. Et ensuite ? Nous avons fait énumérer par le moteur du site toutes les suites de coups légaux depuis la position de départ, sans en oublier une, pour les quatre règlements que tu peux choisir sur la page de jeu. Résultat : après seulement 9 demi-coups (5 coups blancs et 4 coups noirs), il existe déjà 41 022 423 suites différentes sur le damier 10×10, environ neuf fois plus que sur un damier 8×8 avec les mêmes règles. Ce compte réserve aussi deux surprises : une rafle qui revient à sa case de départ, et des règlements qui se séparent dès le quatrième ou le cinquième demi-coup.
Compter les suites de coups, une par une
Les programmeurs de jeux appellent ce calcul un « perft » : on part de la position initiale, on joue chaque coup légal, puis chaque réponse légale, et ainsi de suite jusqu'à une profondeur fixée, en comptant les suites obtenues. Ce n'est pas une estimation ni une simulation : chaque suite est réellement jouée par le moteur de règles qui arbitre tes parties sur le site, avec la prise obligatoire, la prise majoritaire quand le règlement l'impose, la prise en arrière des pions et la dame volante.
Deux précisions pour bien lire les chiffres. D'abord, on compte des suites de coups, pas des positions : 1. 31-26 18-22 2. 34-30 et 1. 34-30 18-22 2. 31-26 mènent à la même position, mais comptent pour deux suites. Ensuite, on compte en demi-coups, c'est-à-dire qu'un coup blanc et un coup noir font deux demi-coups.
Le tableau : quatre règlements, dix demi-coups
| Demi-coups joués | Internationales (10×10) | Brésiliennes (8×8) | Russes (8×8) | Anglaises (8×8) |
|---|---|---|---|---|
| 1 | 9 | 7 | 7 | 7 |
| 2 | 81 | 49 | 49 | 49 |
| 3 | 658 | 302 | 302 | 302 |
| 4 | 4 265 | 1 469 | 1 469 | 1 469 |
| 5 | 27 117 | 7 473 | 7 482 | 7 361 |
| 6 | 167 140 | 37 628 | 37 986 | 36 768 |
| 7 | 1 049 442 | 187 302 | 190 146 | 179 740 |
| 8 | 6 483 961 | 907 830 | 929 899 | 845 931 |
| 9 | 41 022 423 | 4 431 766 | 4 570 586 | 3 963 680 |
| 10 | non calculé | 21 560 022 | 22 444 032 | 18 391 564 |
Aux dames anglaises, ce sont les Noirs qui jouent le premier coup ; la position de départ étant symétrique, cela ne change pas les comptes. La profondeur 10 n'a pas été calculée sur le damier 10×10 : elle demandait plusieurs fois le temps de calcul que nous nous étions fixé.
À partir du quatrième demi-coup, chaque demi-coup supplémentaire multiplie le nombre de suites par 6,2 à 6,5 sur le damier 10×10, et par 4,6 à 5,1 sur les damiers 8×8. Cet écart, répété demi-coup après demi-coup, suffit à creuser la différence : à 9 demi-coups, les dames internationales comptent 9,3 fois plus de suites que les dames brésiliennes, qui appliquent pourtant exactement les mêmes règles sur un damier plus petit. Plus de pions, plus de cases, donc plus de choix à chaque coup : c'est l'une des raisons pour lesquelles le jeu sur 100 cases est bien plus loin d'être résolu que les dames anglaises (notre guide des différences entre variantes donne les ordres de grandeur du nombre de positions).
Le moteur du site retombe sur les chiffres publiés
Ce genre de compte sert d'abord à vérifier un programme : si deux moteurs écrits indépendamment trouvent le même nombre de suites, il y a de bonnes chances que tous deux appliquent correctement les règles. Nous avons trouvé des valeurs de référence publiées pour deux des quatre règlements.
- Dames internationales : en juillet 2008, le programmeur Ed Gilbert a publié sur le forum néerlandais damforum.nl les comptes de la position de départ jusqu'à 11 demi-coups. Le moteur du site retrouve ses neuf premières valeurs à l'unité près, jusqu'à 41 022 423.
- Dames anglaises : la suite est référencée dans l'encyclopédie des suites d'entiers OEIS sous le numéro A133046, entrée créée en 2007 par Jonathan Schaeffer, le chercheur qui a résolu les dames anglaises avec le programme Chinook. Le moteur du site retrouve les dix premières valeurs, jusqu'à 18 391 564.
Pour les dames brésiliennes et russes, nous n'avons pas comparé nos comptes à une source extérieure : ils s'appuient sur le même moteur, validé par les deux règlements ci-dessus, mais restent nos propres calculs.
La rafle qui revient à son point de départ
Dans le même fil de 2008, un autre programmeur, Bert Tuyt, trouvait 6 483 971 suites à 8 demi-coups, soit 10 de plus que Ed Gilbert, et supposait que l'écart venait de son générateur de coups, qui ne supprimait pas les coups en double (même départ, même arrivée, pièces prises dans un autre ordre). Notre moteur reproduit exactement ces deux nombres : 6 483 971 si l'on garde les doublons, 6 483 961 si on les retire. Ces 10 doublons viennent de 10 positions atteintes en 7 demi-coups, dont voici la première trouvée.
Le pion noir de la case 17 prend quatre pions et termine sa rafle sur sa case de départ. Il peut tourner dans un sens ou dans l'autre : les deux trajets prennent les mêmes pièces et finissent sur la même case. Pour le règlement, c'est un seul coup, puisqu'un coup se définit par sa case de départ, sa case d'arrivée et les pièces prises. Un programme qui compte les trajets plutôt que les coups en voit deux. Au passage, cette position illustre deux règles des dames internationales : le pion prend en arrière (deux des quatre sauts reculent), et une rafle peut repasser par sa case de départ, libérée dès le début du coup.
La suite qui y mène est absurde pour les Blancs, qui perdent quatre pions d'un seul coup. Mais le compte ne juge pas : il énumère tout ce que les règles permettent, bons coups comme gaffes.
Quand les règlements se séparent
Sur le damier 8×8, les trois règlements donnent exactement le même nombre de suites pendant quatre demi-coups : 7, 49, 302 puis 1 469. Ils ne se séparent dans le tableau qu'au cinquième demi-coup. Mais les coups, eux, diffèrent parfois plus tôt.
- Brésiliennes contre anglaises. Dès le troisième demi-coup joué, 22 positions offrent des coups différents selon le règlement. Exemple : après 21-17 9-13 22-18 (numérotation du site, de 1 à 32), le pion noir de la case 13 doit prendre. Aux brésiliennes, il prend deux pions, le second en reculant (13x15) ; avec les règles anglaises, où le pion ne prend pas en arrière, il n'en prend qu'un (13x22). Un coup imposé dans chaque cas : le compte reste identique, mais les positions ne le sont plus.
- Brésiliennes contre russes. Ces deux règlements ne diffèrent que par deux règles : la prise au choix des dames russes (pas de prise majoritaire) et la promotion d'un pion en pleine rafle. La première joue dès que quatre demi-coups ont été joués, dans 9 positions. La figure ci-dessous montre la première trouvée.
Sur dix demi-coups, l'effet s'accumule : les dames russes comptent 4 % de suites de plus que les brésiliennes, parce que la prise au choix laisse des options que la prise majoritaire supprime. Et les dames brésiliennes en comptent 17 % de plus que les dames anglaises, où les pions ne prennent qu'en avant.
Une prise obligatoire dans près d'une position sur deux
Le banc a aussi relevé, à chaque profondeur, les positions où le camp au trait est obligé de prendre. Aux dames internationales, c'est le cas de 15 des 81 positions après deux demi-coups (18,5 %), puis de 37,7 % après trois demi-coups, et de 46,3 % des 6 483 961 suites de 8 demi-coups. Sur 8×8, la proportion tourne aussi autour de 45 à 49 % entre 7 et 9 demi-coups, selon le règlement.
Ce chiffre est bien plus élevé que dans des parties réelles. Dans notre article sur la prise obligatoire en chiffres, l'ordinateur du site jouant contre lui-même, entre 30 et 36 % des coups d'ouverture (34 pièces ou plus sur le damier) étaient des prises. L'explication est simple : le compte donne le même poids à chaque suite, y compris à toutes celles où un camp met un pion en prise sans raison. Un joueur qui calcule évite une bonne partie de ces lignes. L'arbre des coups mesure ce que les règles permettent, pas ce que jouent les bons joueurs.
Ce qu'il faut retenir
- L'arbre grossit très vite. Plus de 41 millions de suites après 9 demi-coups aux dames internationales, environ six fois plus à chaque demi-coup supplémentaire. Personne ne calcule tout : on calcule les coups forcés, les prises et les menaces, et on juge le reste à l'œil.
- Le damier 10×10 n'est pas un 8×8 agrandi. Avec les mêmes règles, il offre neuf fois plus de suites après 9 demi-coups. Si tu passes des dames brésiliennes aux internationales, attends-toi à des parties plus longues à lire.
- Un coup, c'est un départ, une arrivée et des pièces prises. Quand deux trajets prennent les mêmes pions et finissent sur la même case, c'est le même coup. Et une rafle peut finir là où elle a commencé : pense à ce cas quand tu cherches les prises de ton adversaire.
- Vérifie le règlement avant de calculer une prise. La même position peut imposer un coup aux dames brésiliennes et en permettre deux aux dames russes, après quatre demi-coups seulement. Sur la page de jeu, les règles de la variante choisie sont rappelées sous le damier.
Pour les règles complètes de chaque variante, lis notre guide des règles du jeu de dames, et pour bien choisir tes premiers coups parmi les neuf possibles, le guide des ouvertures. Puis joue aux dames en ligne : contre l'ordinateur, tu choisis le damier 10×10 ou l'un des trois règlements sur 8×8.