Les jeux de Nim déguisés en jeux d’échecs

dimanche 27 septembre 2015
par  Alain BUSSER

Un chapitre du livre « winnings ways for your mathematical plays » où les auteurs semblent particulièrement s’amuser est celui où ils décrivent des stratégies gagnantes du jeu d’échec de Dawson et du jeu de dame de Wythoff en ramenant ces jeux à des jeux de Nim (ou variantes).

Trois jeux de Nim (ou analogue) seront décrits ici, et simulés sur un échiquier :

  1. le jeu d’échec de Dawson ou hexapawn, qui se joue avec des pions, qui prennent en diagonale. On prouve qu’aucun pion n’est jamais promu reine parce que la prise est obligatoire ;
  2. le jeu de tiouk-tiouk, où on avance et recule des pions, verticalement seulement ; il peut être comparé à un jeu de Nim à plusieurs tas où on peut aussi ajouter des objets ;
  3. le jeu de Wythoff, une variante du jeu de Nim à deux tas, où les tas sont représentés comme coordonnées d’une dame sur l’échiquier.

Tiouk tiouk

Conway attribue ce jeu à Northcott mais il existe depuis longtemps en Afrique de l’Ouest sous le nom de tiouk tiouk ; ici il se joue sur un échiquier ; traditionnellement l’un des joueurs pousse des jetons et l’autre des bâtons, mais avec des pions de couleur différente on peut y jouer aussi.

La variante proposée ici ne se joue pas sur un échiquier de forme carrée mais sur un échiquier de 8 lignes et d’un nombre quelconque de colonnes :

jeu de tiouk tiouk
ouvrir dans un autre onglet pour jouer ; on réinitialise le jeu en actionnant un curseur

Un tour de jeu consiste à bouger un pion, verticalement, d’autant de cases que l’on veut, et dans le sens que l’on veut. Le but du jeu est de bloquer l’adversaire puisque le premier joueur qui ne peut plus bouger de pion a perdu.

Par exemple, ci-dessus, si c’est au joueur vert de commencer, il ne peut que reculer un de ses pions, que le joueur marron peut ensuite coincer en avançant un pion, et ensuite, reculer l’autre pion, qui sera alors aussi coincé par le joueur marron : Le joueur vert perd. Par contre, avec la même position de jeu, si c’est au joueur marron de jouer, le joueur vert peut gagner, par exemple en coinçant systématiquement le pion que vient de jouer le joueur marron.

Avec 6 colonnes, le jeu est équivalent à un jeu de Nim à 6 tas de 6 objets chacun, le nombre d’objets sur le tas étant représenté par le nombre de cases vides entre les deux pions. Si on peut reculer, c’est qu’il est possible de rajouter des objets sur un tas, en respectant la limite de 6 objets. Cependant, l’usage du théorème de Sprague-Grundy permet de trouver une stratégie gagnante pour le joueur qui commence.

Hexapawn

Ce jeu, sorte de jeu d’échecs simplifié, a été inventé par Thomas Dawson en 1935 :

le jeu d’échecs de Dawson
ouvrir dans un autre onglet pour jouer ; on réinitialise le jeu en actionnant un curseur

En fait l’échiquier n’a que 3 lignes, et au début de la partie, seule celle du milieu est vide : Les pions sont alignés (les verts en haut, les marron en bas), et chaque joueur, à son tour, joue un pion comme aux échecs, à ceci près que la prise est obligatoire. Le premier joueur qui ne peut plus jouer parce qu’il est bloqué, a perdu.

Par exemple, ci-dessus, on dirait que le joueur vert a avancé un pion tout à gauche pour bloquer le joueur marron, mais ce genre de mouvement n’est possible que si la colonne était isolée ; en fait

  • le joueur vert a bien avancé le pion qui était en a1 (pour le mettre en b1) ;
  • mais une fois en b1, ce pion menaçait le pion marron en c2 ; celui-ci était donc obligé de prendre (en diagonale) le pion vert en b1 ;
  • du coup, le pion marron en b1 menaçait le pion vert en a2, qui a donc dû prendre le pion marron en a2.

Petit rappel des coordonnées pour se situer dans cet échiquier :

a1 a2 a3
b1 b2 b3
c1 c2 c3

Il s’est passé quelque chose de similaire dans la colonne 4, sauf que là, c’était à l’initiative du joueur marron, et que ça a fait le ménage sur les deux colonnes voisines. Maintenant, si le joueur marron (qui doit jouer) joue l’une des colonnes 6 ou 8, le joueur vert joue l’autre dès qu’il peut et gagne. Par contre si le joueur marron joue la colonne 7, après le massacre habituel, il bloque le pion restant en 7 et gagne.

Le nom d’hexapawn (6 pions) vient de Martin Gardner, qui a étudié le cas particulier du jeu de Dawson où l’échiquier est carré (3 par 3). Dans ce cas le premier joueur a une stratégie gagnante : Jouer au centre.

Pour gagner du temps, on peut considérer que les prises (obligatoires) sont automatiques, et jouer à une sorte de tic-tac-toe monodimensionnel :

Dawson en version tic-tac-toe
Cliquer sur une case pour la cocher

Pour joueur une case, on clique dessus, et on obtient une croix bleue et aussi, sur les cases voisines, un rond rouge, qui représente le vide créé par les prises de pion. Il s’agit donc d’un déguisement du jeu d’échecs de Dawson. Or sur ce déguisement, on voit qu’il s’agit d’un jeu octal, qui est une généralisation du jeu de Nim.

Le jeu ci-dessus est dans un dossier zip parce qu’il utilise des images (le O et le X) au format gif. Pour mettre le tout dans un seul fichier html, on peut représenter les signes par des lettres (O et X), comme dans ce jeu de Tic-Tac-Toe en html :

Le jeu de Tic-Tac-Toe en html
ne pas hésiter à regarder le source, surtout si on enseigne le codage en collège

Wythoff

Pour en savoir plus sur ce jeu, voir l’article de Lisa Rougetet sur MathemaTICE.

Le jeu est théoriquement défini sur un échiquier de taille illimitée, ce qui pose rapidement la question de la façon dont la complexité dépend de la taille.

Une dame de jeu d’échecs est posée sur un échiquier, et ne peut bouger que vers la gauche, vers le bas ou en diagonale (à la fois vers la gauche et le bas). Les joueurs déplacent la dame à tour de rôle (en tout bien tout honneur), et celui qui amène la dame en bas à gauche a gagné.

Techniquement, il s’agit juste de trouver comment on peut dessiner une dame dans une des cases du tableau/échiquier : le caractère unicode numéro 2655 convient ; on l’écrit donc comme texte dans la case de l’échiquier choisie. Déplacer la dame se fait alors en remplaçant le texte actuel par un texte vide et en rajoutant à la nouvelle case (l’arrivée) le texte formé du seul caractère unicode 2655 :

  1.     if jouable()
  2.         $(".l#{ligne}.c#{colonne}").text ""
  3.         [ligne, colonne] = [ll, cc]
  4.         $(".l#{ligne}.c#{colonne}").text "♕"
  5.         riposte()

Télécharger

calcul de la case de destination

La stratégie de jeu consiste à chercher si une case gagnante peut être atteinte depuis la position actuelle de la dame ; si oui on y va, si non on va au bord :

  1.         if ligne==1 and colonne==1
  2.                 $("#sortie").text "Ah, tu as gagné ! Félicitations"
  3.                 fini = true
  4.         else
  5.                 if accessible(5,8)
  6.                         [ll,cc] = [5,8]
  7.                 else if accessible(6,4)
  8.                     [ll,cc] = [6,4]
  9.                 else if accessible(4,6)
  10.                     [ll,cc] = [4,6]
  11.                 else if accessible(3,2)
  12.                     [ll,cc] = [3,2]
  13.                 else if accessible(2,3)
  14.                     [ll,cc] = [2,3]
  15.                 else if accessible(1,1)
  16.                     [ll,cc] = [1,1]
  17.                 else if colonne>2
  18.                     [ll,cc] = [ligne, colonne-1]
  19.                 else if ligne > 2
  20.                     [ll,cc] = [ligne-1, colonne]
  21.                 else
  22.                     [ll,cc] = [1,colonne]

Télécharger

Voici le jeu en html :

jeu de Wythoff

Un aspect sympathique de ce jeu est que, par coloriage des cases gagnantes, on peut dessiner l’arbre du jeu sur le plateau de jeu.


Post-scriptum

Pour en savoir plus, voici un article en pdf, abondamment illustré, qui propose d’aller un peu plus loin (Welter à plusieurs lignes, Chomp, mélange de Nim et de jeu de la soustraction, et même le jeu des grenouilles et des crapauds, qui n’est pas un jeu de Nim) ; le source, au format Latex, est libre, et joint à l’article :

l’article en pdf le source en Latex

Commentaires