Trois jeux de Nim (ou analogue) seront décrits ici, et simulés sur un échiquier :
- 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 ;
- 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 ;
- 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 :
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 :
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 :
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 :
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 :
if jouable()
$(".l#{ligne}.c#{colonne}").text ""
[ligne, colonne] = [ll, cc]
$(".l#{ligne}.c#{colonne}").text "♕"
riposte()
Voici le jeu en html :
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