Dawson's Chess

Introduction

Les échecs de Dawson font partis des jeux/problèmes les plus fascinants découverts par Thomas Rayner Dawson dans les années 1930.

Le jeu de Dawson’s Chess fait parti des jeux combinatoires car il répond aux 5 caractéristiques fondamentales des jeux combinatoires [1] :

  1. présence de 2 joueurs qui jouent alternativement;
  2. le hasard n’existe pas;
  3. il n’y a pas d’informations cachées;
  4. les règles et le but du jeu sont clairs et bien définis;
  5. le jeu s’arrête après un nombre fini de mouvements.

Pour simplifier le jeu aux personnes qui n'ont pas l'habitude de jouer aux échecs, il existe une possibilité de l'analyser comme si on était en train de jouer à: misère tic-tac-toe ou le jeu des piles.

Connaissances pré requises

Pour bien comprendre cet article il y a des connaissances à savoir:

  1. P/N positions (P: previous player win, N: next player win)
  2. Sprague-Grundy theorem page wikipedia en
  3. Mex rule (Mex = "minimal excludent") page wikipedia en
  4. Somme de Nim ($\oplus$ - somme binaire sans report ou XOR) page wikipedia en

Jeu orginal: Dawson's Chess

Nous allons vous présenter le jeu en lui-même

Description de l'aréna

L'aréna des échecs de Dawson est un échiquier à 3 lignes et n colonnes, sur lequel sont positionnés que des pions.
Pour être plus précis, il y a n-pions noirs et n-pions blancs; où n>0.

arena1.png


Fig.1 Dawson's Chees, reprise de [3]

Règles et but du jeu

Le jeu d'échecs de Dawson suit la même règle que le jeu d'échecs normal, donc:

  • les pions se déplacent en horizontal de 1 case
  • les pions ''mangent'' en diagonale
  • les pions ont l'obligation de manger si le cas se présente

Le but du jeu est d'être le dernier joueur qui bouge.

Attention il existe aussi une version du jeu où l'avant dernier joueur qui bouge gagne mais nous n'allons pas traiter ce cas

Exemple d'un match en n=4, Dawson's Chess

example_chess.gif

Fig 2. Example match n=4, Damson's Chess [2]

Dans le cas illustré par la Fig. 2, on peut observer diffèrentes étapes:

  1. le mouvement du rouge de C2 a B2;
  2. suivi par le mouvement obligé du bleu qui doit manger le pion rouge avec A1 en B2;
  3. suivi par le mouvement obligé du rouge qui doit manger le pion bleu avec C1 en B2;
  4. suivi par le mouvement obligé du bleu qui doit manger le pion rouge avec A3 en B2;
  5. suivi par le dernier mouvement obligé du rouge qui doit manger le pion bleu avec C3 en B2;
  6. le mouvement du bleu de A4 en B2 marque sa victoire.

Résumé du jeu: début rouge, 2 mouvements, bleu gagnant.

Misère tic-tac-toe

Description de l'aréna

L'aréna du jeu Misère tic-tac-toe est une ligne avec n-cases vides, avec n>=0.

Règles et but du jeu

Le jeu misère tic-tac-toe est composé de 2 seules règles:

  1. les joueurs positionnent à leur tour un X dans une de case de leur choix;
  2. le X ne peut pas être positionné à côté d'un autre X (une case de distance).

Le but du jeux est d'être le dernier joueur qui positionne un X.

Exemple d'un match en n=4, misère tic-tac-toe

misere_n4.gif

Fig 3. Example match misere tic tac toe n=4 [2]

Dans le cas illustré par la Fig. 3, on peut observer 2 étapes:

  1. le mouvement du premier joueur qui pose son X dans A2, ce qui bloque automatiquement les cases A1 et A3;
  2. le mouvement du deuxième joueur qui pose son X dans A4 et qui gagne le match.

Résumé du jeu: début premier joueur, 2 mouvements, deuxième joueur gagnant.

Similitude entre Dawson's Chess et misère tic-tac-toe

En observant les 2 jeux, on peut identifier une similitude entre:

  • l'évolution de la ligne B du Dawson's Chess
  • et l'évolution de la ligne A du misère tic-tac-toe

En effet, les mouvements 2 à 5 dans le jeu Dawson's Chess correspondent au mouvement 1 du jeu Misère tic-tac-toe, et le mouvement 6 (Dawson's Chess) correspond au mouvement 2 dans misère tic-tac-toe, illustré dans la Fig. 4.

simi.png

Fig 4. Illustration similitude [2]

Cette similitude est démontrable par récurrence, mais elle ne sera pas traitée dans cette wiki.

Stratégie

La stratégie gagnante pour Dawson's chess n'est pas évidente, c'est pourquoi on utilisera la similitude avec misère tic-tac-toe pour la présenter.

idée générale

Le joueur qui commence avec le premier mouvement dans le Dawson's chess a la possibilité de remporter le jeu à condition d'adopter une stratégie spécifique et que le g(n) initiale donne un nombre différent de 0, c'est à dire qu'on ce trouve dans une position N.
Il y a deux stratégies gagnantes, dont une seule universelle, c'est-à-dire qui fonctionne toujours avec n'importe quelle ligne de n cases où $n=[1, 2, \cdots, \infty[$

Cas 1 : nombre de cases : impaire

Nous allons commencer par vous présenter le cas le plus simple, qu'on peut appliquer uniquement avec les lignes qui ont un nombre impaires de cases, plus précisément $2n+1$ cases où $n=[2, 3, \cdots, \infty [$. Comme vous aurez sûrement compris c'est la stratégie par symétrie. D'abord, on coche la case au milieu de la ligne de façon à obtenir deux sous lignes de longueur identique. Ensuite, on joue d'un coté ce que l'autre joueur aura joué de l'autre, c'est-à-dire qu'on copie simplement le mouvement de l'adversaire par symétrie par rapport au milieu. Ce qui se traduit par un dernier mouvement de notre part qui nous fera gagner le match.

Exemple :

X O O X O O X

OXO : 1er joueur = mouvement No 1
XO : 2ème joueur = mouvement No 1
OX : 1er joueur = mouvement No2 symétrique au mouvement No 1 du 2ème joueur, par rapport au X du milieu

Cas 2 : nombre de cases : paire

L'autre stratégie est légèrement plus compliquée. Comme prérequis, il faut avoir compris le nim, l'opération algébrique mex et la séquence de Sprague-Grundy.
Le but du joueur est de mettre son adversaire dans une position P, autrement dit dans une position g(x)=0.
Pour cela, il faut premièrement simuler tous les mouvement possible jusqu'à la moitié, car les suivants donneront les mêmes résultats et on note les cases libres restantes par groupe.

Exemple :

Avec une ligne de n=5 on obtient les résultats suivants :

X O

3 (si on coche la 1ère case)

O X O

2 (si on coche la 2ième case)

O X O

1,1 (si on coche la 3ième case)

Deuxièmement, on doit calculer les $g(x)$; donc si un nombre x est tout seul on note son $g(x)$ directement depuis le tableau que vous trouvez dans le prochain paragraphe. Tandis que si c'est deux ou plus groupes de nombres on doit calculer $g(a) \oplus g(b)$. Si le nombre calculé est égal à 0, le mouvement amènera notre adversaire en position $P$, c'est-à-dire qu'on sera gagnant.

Pour notre exemple on a :

(1)
\begin{align} g(3) = 2 \text{ (N)} \\ g(2) = 1 \text{ (N)} \\ g(1) \oplus g(1) = 0 \text{ (P)} \end{align}

Donc le mouvement à jouer est de cocher la case n° 3 pour cet exemple. Ensuite on procédera de la même façon pour chaque mouvement qu'on joue jusqu'à remplir toute la ligne.

Évidemment si $g(n)$ où n correspond à la longueur de notre ligne, est égale à 0 lors du premier mouvement alors on ne pourra pas gagner, par exemple si $n=8$.

Explication détaillée

Démonstration et jeux online

Pour vous exercer avec la la stratégie, visitez ce site: http://www.math.ucla.edu/~tom/Games/dawson.html bon match!

La séquence de Sprague-Grundy

Avec l'aide du théorème de Sprague-Grundy, on peut définir la séquence de Sprague-Grundy qui nous indique quel choix faire pour avoir l'opportunité de gagner aux jeux d'échecs de Dawson/misère tic-tac-toe.

x g(x) P/N x g(x) P/N x g(x) P/N x g(x) P/N x g(x) P/N
0 0 P 20 0 P 40 1 N 60 1 N 80 2 P
1 1 N 21 1 N 41 1 N 61 1 N 81 4 N
2 1 N 22 1 N 42 0 P 62 0 P 82 4 N
3 2 N 23 3 N 43 3 N 63 4 N 83 5 N
4 0 P 24 0 P 44 3 N 64 5 N 84 5 P
5 3 N 25 2 N 45 2 N 65 3 N 85 9 N
6 1 N 26 1 N 46 2 N 66 7 N 86 3 N
7 1 N 27 1 N 47 4 N 67 4 N 87 3 N
8 0 P 28 0 P 48 4 N 68 8 N 88 0 P
9 3 N 29 4 N 49 5 N 69 1 N 89 1 N
10 3 N 30 5 N 50 5 N 70 1 N 90 1 N
11 2 N 31 2 N 51 2 N 71 2 N 91 3 N
12 2 N 32 7 N 52 3 N 72 0 P 92 0 N
13 4 N 33 4 N 53 3 N 73 3 N 93 2 N
14 0 P 34 0 P 54 0 P 74 1 N 94 1 P
15 5 N 35 1 N 55 1 N 75 1 N 95 1 N
16 2 N 36 1 N 56 1 N 76 0 P 96 0 N
17 2 N 37 2 N 57 3 N 77 3 N 97 4 N
18 3 N 38 0 P 58 0 P 78 3 N 98 5 P
19 3 N 39 3 N 59 2 N 79 2 N 99 3 N

Tab. 1 Sequence de Sprague-Grundy pour les échecs de Dawson [3]

Calculs des valeurs Sprague-Grundy

rappel
Depuis la définition des valeurs Sprague-Grundy on a[1]:

(2)
\begin{align} P-position \Longleftrightarrow SG = 0 \\ N-position \Longleftrightarrow SG > 0 \end{align}

Les valeurs initiales suivantes sont triviales:

(3)
\begin{align} x = 0 \implies g(0) = 0 \end{align}

Ceci est vrai dans chaque jeu combinatoire, car $mex(\emptyset) = 0$, car le joueur se trouve en position P ( i.e dans une position perdante).

(4)
\begin{align} x = 1 \implies g(1) = 1 \end{align}

Ceci est vrai, car $mex({0}) = 1$.

Les valeurs suivantes peuvent être calculées par récurrence grâce à:

(5)
\begin{align} g(x) = mex(g(a)) \text{ }\forall a \in A \end{align}
(6)
\begin{align} A=\{g(\{\text{"somme NIM de tout le sous match dérivé par les disposition possible de X, sur une match de taille x"}\}\} \end{align}
(7)
\begin{align} g(n) = mex(g(a)\oplus g(b))\\ -1 \leq a, b \text{ and } a+b=n-3 \end{align}

Les formules 5,6,7 sont reprises de [3].

Calculs de g(11)

Voici un exemple avec g(11) où nous allons montrer toutes les possibilités que le premier joueur peut effectuer;

X O                  

1ère possibilité: mettre X dans la 1ère case, il nous restera donc 9 cases vides. Il faudra alors utiliser $g(9)={\color{red}3}$.

O X O              

2ème possibilité: mettre X dans la 2ème case $\implies$ reste 8 cases vides et $g(8)={\color{red}0}$.

  O X O              

3ème possibilité: mettre X dans la 3ème case $\implies$ reste 1+7 cases vides. Donc $g(1)= {\color{green}1}$ et $g(7)={\color{green}1}$,
$\implies g(1) \oplus g(7) = {\color{green}1} \oplus {\color{green}1} = [001]b_2 \oplus [001]b_2 = [000]b_2 = {\color{red}0}$

    O X O            

4ème possibilité: mettre X dans la 4ème case $\implies$ reste 2+6 cases vides. Donc $g(2)=1$ et $g(6)=1$,
$\implies g(2) \oplus g(6) = {\color{red}0}$.

      O X O          

5ème possibilité: mettre X dans la 5ème case $\implies$ reste 3+5 cases vides. Donc $g(3)=2$ et $g(5)=3$,
$\implies g(2) \oplus g(6) = {\color{red}1}$.

        O X O        

6ème possibilité: mettre X dans la 6ème case $\implies$ reste 4+4 cases vides. Donc $g(4)=0$,
$\implies g(4) \oplus g(4) = {\color{red}0}$.

Les possibilités s'arrêtent ici car les suivantes sont symétriques à celles que nous venons de montrer.

Donc par Eq.(5):

(8)
\begin{align} g(11)= mex({\color{red}3},{\color{red}0},{\color{red}0},{\color{red}0},{\color{red}1},{\color{red}0})={\color{blue}2} \end{align}

Remarques

  • D'après Kayles, il y a une périodicité dans la séquence des 34 premières valeurs (x=0 à x=33).
  • Il y a par contre quelques exceptions comme illustrées dans le tableau 2.
Kyles_per.png

Tab. 2 Périodicité de la sequence S.G. reprise de [3]

Bibliography
1. Cour MA.2703 - Mathématiques I pour BSc_SI, semestre SA2013, donné par Prof. hc.rfinu|regrebneuel.hpotsirhc#hpotsirhC regrebneueL, assistent (hc.rfinu|iwik.vel#hc.rfinu|iwik.vel Lev Kiwi).
2. Text, document ou image produit par nous: hc.rfinu|idinitnatsnok.anitsirhc#idinitnatsnoK anitsirhC, hc.rfinu|reissor.ahtnamas#reissoR ahtnamaS, hc.rfinu|atreb.onafets#atreB onafetS, hc.rfinu|elavenrac.acul#elavenraC acuL.
3. E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for Your Mathematical Plays, Volume 1, A K Peters, 2001.
4. Site cut-the-knot.org page dédié aux jeux d'échecs de Dawson visité le 12 novembre 2013 - http://www.cut-the-knot.org/Curriculum/Games/DawsonChess.shtml
5. Site cut-the-knot.org page dédié aux théorèmes de jeux de Grundy visité le 12 novembre 2013 - http://www.cut-the-knot.org/Curriculum/Games/Grundy.shtml
6. Site lkozma.net page de à la resolution d'algorithme des jeux combinatoire de moc.liamg|amzokl#amzoK olzsaL visité le 12 novembre 2013 - http://www.lkozma.net/game.html
7. Site math.ucia.edu page dédié a une demo du jeux online visité le 12 novembre 2013 - http://www.math.ucla.edu/~tom/Games/dawson.html
8. Site wikipedia exclusive or - XOR visité le 14 novembre 2013 - http://en.wikipedia.org/wiki/Exclusive_or

Etant à l'université de Fribourg, nous avons réalisé cette page dans le cadre de notre cours de bachelor de mathématiques.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License