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 :

HTML - 20.7 ko
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 :

HTML - 23.3 ko
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 :

Zip - 4.4 ko
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 :

HTML - 7 ko
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 :

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

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 :

        if ligne==1 and colonne==1
                $("#sortie").text "Ah, tu as gagné ! Félicitations"
                fini = true
        else
                if accessible(5,8)
                        [ll,cc] = [5,8]
                else if accessible(6,4)
                    [ll,cc] = [6,4]
                else if accessible(4,6)
                    [ll,cc] = [4,6]
                else if accessible(3,2)
                    [ll,cc] = [3,2]
                else if accessible(2,3)
                    [ll,cc] = [2,3]
                else if accessible(1,1)
                    [ll,cc] = [1,1]
                else if colonne>2
                    [ll,cc] = [ligne, colonne-1]
                else if ligne > 2
                    [ll,cc] = [ligne-1, colonne]
                else
                    [ll,cc] = [1,colonne]

Voici le jeu en html :

HTML - 3.5 ko
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
PDF - 318.2 ko
LaTeX - 66.9 ko

Commentaires

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 3 mai 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mardi 13 juin 2017, 14h-18h, campus du Tampon
- Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6


Brèves

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

Quand les chercheurs mettent au point des modèles d’optimisation et de recherche de plus court chemin qui s’inspirent du comportement de masse de colonies de fourmis...
À écouter : Sur les Épaules de Darwin, émission diffusée sur France Inter samedi 31 août 2013.

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

Les RMLLd se dérouleront pour la 2e fois à Saint-Joseph du 22 au 25 août.
C’est une opportunité pour les élèves qui suivent la spécialité ISN et les passionnés d’informatique.

Voici pour le samedi et le dimanche quelques interventions choisies :
- http://2013.d.rmll.info/Raspberry-votre-ordinateur-au-format-carte-de-credit?lang=fr
- http://2013.d.rmll.info/Materiel-libre-et-DIY?lang=fr
- http://2013.d.rmll.info/Arduino-de-l-electronique-libre?lang=fr

Noter aussi les conférences Art et Culture du dimanche, ainsi qu’une conférence plus engagée.

Le programme complet se trouve ici. Une radio sera ouverte pour l’occasion.
Des plaquettes à distribuer se trouvent ici.

Hyper-vidéos pour l’algorithmique au lycée

dimanche 19 août 2012

Olivier Roizès, à la demande de l’ADIREM, a réalisé une collection d’hyper-vidéos de présentation de logiciels et environnements de programmation. Ces hyper-vidéos, c’est-à-dire des vidéos contenant des éléments clicables, devraient être utiles aux enseignants désireux de se familiariser avec Python, CaRMetal, R, Rurple, Scilab ou Xcas.

Ouverture du SILO

mardi 1er novembre 2011

Le SILO (Science Informatique au Lycée : Oui !) est un espace collaboratif documentaire de partage et de formation collégiale, à destination des professeurs appelés à enseigner l’informatique au lycée.

Une initiative du CNDP, de l’INRIA et de Pasc@line, à laquelle se sont associés SPECIF, fuscia, EPI et ePrep.

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

Le CRDP de Paris publie le premier ouvrage destiné aux professeurs chargés d’enseigner la nouvelle spécialité « Informatique et sciences du numérique » en Terminale S à la rentrée 2012. Cet ouvrage a été coordonné par Gilles Dowek, directeur de recherche à l’INRIA.

Sur la création de la spécialité ISN, on pourra également consulter l’interview donnée au Café pédagogique par l’inspecteur général Robert Cabanne.

Sur le Web : CRDP de Paris

Deux publications sur l’algorithmique

samedi 17 octobre 2009

L’IREM d’Aix-Marseille publie une brochure de 73 pages, téléchargeable librement, intitulée Algorithmes et logique au lycée. Ces notions sont illustrées et déclinées sur des exercices du programme de spécialité mathématique en série L, mais sont adaptables aux programmes à venir.

Le hors série thématique n° 37 du magazine Tangente, disponible actuellement en kiosque, s’intitule « Les algorithmes. Au cœur du raisonnement structuré ». Extrait de l’éditorial : « La rédaction de Tangente a conçu la quasi-totalité de ce hors série thématique pour qu’il puisse être lu par des élèves de Seconde ».

Une carte mentale pour l’algorithmique

jeudi 10 septembre 2009

Sur son site, Jean-Jacques Dhénin a publié une carte mentale géante qui renvoie vers plus de 30 documents en ligne sur l’algorithmique. Tout ce qu’il faut — et même davantage — pour faire face au nouveau programme de Seconde !

Un catalogue libre d’algorithmes pour le lycée

dimanche 30 août 2009

Guillaume Connan, de l’IREM de Nantes, publie un catalogue libre de 119 pages d’algorithmes pour le lycée. Sur son site très riche, on trouvera d’autres documents en rapport avec l’algorithmique, notamment sur l’utilisation des langages fonctionnels au lycée et sur la comparaison programmation fonctionnelle/programmation impérative.

L’algorithmique à l’IREM de Lille

vendredi 26 juin 2009

Le groupe AMECMI de l’IREM de Lille vient de mettre en ligne des ressources importantes au service des professeurs de Seconde :

- Algorithmique et programmation (Emmanuel Ostenne)
- Bibliographie amoureuse de l’algorithmique (Alain Juhel)

Statistiques

Dernière mise à jour

dimanche 28 mai 2017

Publication

746 Articles
Aucun album photo
131 Brèves
11 Sites Web
127 Auteurs

Visites

227 aujourd'hui
838 hier
2025775 depuis le début
24 visiteurs actuellement connectés