← Retour au blog

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.

🎮 Jouer aux Dames

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)
19777
281494949
3658302302302
44 2651 4691 4691 469
527 1177 4737 4827 361
6167 14037 62837 98636 768
71 049 442187 302190 146179 740
86 483 961907 830929 899845 931
941 022 4234 431 7664 570 5863 963 680
10non calculé21 560 02222 444 03218 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.

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.

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950
Après 1. 31-27 17-22 2. 37-31 22-28 3. 33x22 12-17 4. 27-21, les Noirs doivent jouer 17x17 : le pion fait le tour par 26, 37, 28, 17 et prend quatre pions (barrés). Il peut aussi faire le même tour dans l'autre sens, par 28, 37, 26, 17 : mêmes pièces prises, même case d'arrivée, donc un seul coup.

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.

1234567891011121314151617181920212223242526272829303132
Après 1. 21-17 10-15 2. 23-18 9-14 (numérotation du site, de 1 à 32), les Blancs doivent prendre. En bleu, 17x19, qui prend deux pions (barrés) : c'est le seul coup aux dames brésiliennes. En rouge, 18x9, qui ne prend qu'un pion : interdit aux brésiliennes par la prise majoritaire, permis aux dames russes.

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

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.

À lire aussi

← Retour au blog Jouer aux Dames
Nouveautés 1/6
Voir tous nos défis du jour
Tu aimeras aussi
Voir tous les jeux →