/* chomp.txt - jeu de chomp (the David Gale's game of chomp)
Copyright 2004 Jean-Paul Davalan jpdvl@wanadoo.fr
mise à jour le 27/04/2014
http://jm.davalan.org/index.html
http://jm.davalan.org/jeux/nim/chomp/chomp.txt
http://jm.davalan.org/jeux/nim/chomp/chp.js
http://jm.davalan.org/jeux/nim/chomp/index.html
http://jm.davalan.org/liens/liens_nim.html
*/
QUESTION : Comment peut-on programmer une stratégie gagnante au jeu de chomp ?
==============================================================================
A - Le premier à jouer gagne (jeu m x n )
********************************************
Une étude a été faite pour les jeux de chomp ayant 1, 2 ou 3 lignes ou colonnes.
Pour 3 lignes voir
Three-Rowed CHOMP de Doron Zeilberger
(ancienne page : http://www.math.temple.edu/~zeilberg/mamarim/mamarimhtml/chomp.html=
http://www.math.rutgers.edu/~zeilberg//mamarim/mamarimhtml/chomp.html
Outre l'étude des jeux à 3 lignes on trouve aussi la très courte démonstration due à David Gale de la propriété suivante :
Si un jeu de Chomp débute par un rectangle A de dimensions m x n (m et n >= 1) complet, alors il existe un mouvement gagnant pour le premier joueur.
démonstration (pour m*n > 1) :
J'enlève un seul carreau en (m, n), il reste m * n - 1 carreaux (état B du jeu). Soit ce mouvement est gagnant et c'est bien, soit il ne l'est pas et mon adversaire saura effectuer un mouvement gagnant.
Or toute position atteignable à partir de l'état B, l'était déjà à partir de A et donc je pouvais aussi me placer directement sur cette position.
On reviendra sur cette démonstration un peu plus loin, ce sera alors peut-être plus clair.
B - Où l'on voit qu'il s'agit seulement de trouver le noyau ...
****************************************************************
PRÉCISION : Cette explication est prévue pour les jeux de NIM en général, même si, pour fixer les idées, les figures correspondent au jeu de Chomp
Où l'on voit qu'il s'agit seulement de trouver le noyau d'un graphe, un peu - très peu - de théorie des graphes s'impose :
Pour bien comprendre les jeux de Nim, et en particulier le jeu de Chomp, et pouvoir en parler clairement, il est sans doute préférable de connaître un peu de théorie des graphes, de savoir ce qu'est un ensemble stable, un ensemble absorbant, un noyau et pour certains jeux connaître aussi les fonctions de Grundy, mais ici on n'a pas besoin de fonction de Grundy.
Comme je ne sais pas du tout à quel niveau placer mes explications, je vais me permettre de donner quelques définitions sur les graphes et si certaines vous paraissent simplistes j'espère que vous ne m'en tiendrez pas rigueur.
------------------------
Les graphes finis G dont nous avons besoin sont très simples, lorsqu'on les dessine on a des points et des flèches qui relient un point à un autre :
Les graphes finis G sont formés d'un ensemble fini S de sommets (points) et d'un ensemble A fini d'arcs orientés (flèches du schéma) entre ces sommets.
arc
a -->-- b (b est un successeur de a)
Pour les jeux de Nim, que ce soit le jeu de Chomp ou un autre, les sommets a, b, ... sont les états différents du jeu.
Par exemple pour le jeu de Chomp, le sommet 'a' sera, pour fixer les idées, l'état 6x5 soit : 6 colonnes et 5 lignes
XXXXXX
XXXXXX
XXXXXX
XXXXXX
et le sommet 'b' correspondra par exemple à ceci
XXXXX.
XXXXX.
XXXXXX (attention j'ai malencontreusement inversé le jeu haut/bas par rapport à la page html)
XXXXXX
l'arc a -->-- b symbolise donc la possibilité, pour un même joueur, dans le jeu de Chomp, de passer en jouant un seul coup de l'état 'a' à l'état 'b'
Si on appelle 'c' l'état de jeu ci dessous, on voit qu'un joueur peut passer s'il le désire de 'b' à 'c'
mais pas directement de a à c
X.....
XXXXX.
XXXXXX
XXXXXX
une partie du graphe est donc a -->-- b -->-- c
(et sans flèche de a vers c)
Un état particulier est l'état 'f' vide ci-dessous, celui où il ne reste plus aucun carreau
......
......
......
......
Essayez de trouver tous les sommets et tous les arcs en partant d'une configuration initiale trés simple comme 3x2 - juste pour voir ! -
a b c d u v w r s f (vérifiez qu'il n'en manque pas)
xxx xx. x.. ... xx. x.. ... x.. ... ...
xxx xxx xxx xxx xx. xx. xx. x.. x.. ...
------------------------
Le graphe obtenu en déterminant tous les sommets et tous les arcs du jeu de Chomp (en partant par exemple d'un rectangle m x n initial) est particulier, il possède quelques propriétés :
c'est un 1-graphe :
-------------------
il y a au plus un arc d'un sommet vers un autre. (Contrairement au plan d'une ville où plusieurs voies existent parfois d'un carrefour 'a' vers un autre 'b' proche !)
il est antiréflexif :
---------------------
il n'y a aucune boucle - une boucle est un arc qui va d'un sommet 'a' vers le même sommet 'a' - (un joueur ne peut pas dire 'passe', il est obligé de passer d'un état à un autre état différent)
2) il est antisymétrique :
--------------------------
s'il y a une flèche a -->-- b, alors il ne peut y avoir de flèche b -->-- a (pas de retour possible : dans Chomp on enlève des carreaux, on n'en remet pas).
3) il n'a aucun circuit :
-------------------------
en partant d'un sommet a, le jeu ne reviendra jamais en a (dans Chomp on enlève des carreaux ...)
4) Il existe au moins un sommet sans successeur.
------------------------------------------------
Comme le graphe est fini (on a supposé que l'ensemble des sommets et l'ensemble des arcs sont finis), on finira par arriver sur un sommet f sans successeur (aucun arc ne part de f vers un autre sommet)
(Certains autres jeux, au contraire, se jouent sur des graphes infinis)
Dans le cas de Chomp, un seul sommet a cette propriété, c'est le rectangle vide final.
On a deux possibilités, considérer comme on va le faire que << arriver en f est gagnant pour le joueur >> ou le contraire, qu'arriver en f est perdant.
Dans le jeu de Chomp, l'un des choix de la règle finale est inintéressant, ce n'est pas toujours le cas pour les autres NIM.
Sous-ensemble stable.
=====================
Un sous-ensemble A de sommets est dit stable si tout sommet x de A n'a aucun successeur dans A
Sous-ensemble absorbant.
========================
Un sous-ensemble A de sommets est dit absorbant si tout sommet n'appartenant pas à A possède au moins un successeur dans A.
Noyau
=====
Un sous-ensemble A de sommets est un noyau du graphe s'il est à la fois stable et absorbant.
Connaître le jeu de Chomp c'est connaître un noyau K contenant la position finale gagnante f, en effet :
Vous laissez la position f à votre adversaire, ou toute position répertoriée dans K, et vous êtes certain alors de gagner (en supposant que vous ne l'avez pas fait par pur hasard et que vous savez ce que sont les positions répertoriées dans K).
Vous laissez la position k de K à votre adversaire, or K est stable : votre adversaire va ensuite laisser une position p n'appartenant pas à K.
C'est à nouveau à vous de jouer, vous partez de la position p n'appartenant pas à K, or K est absorbant, c'est donc que p a un successeur k' dans K (au moins un successeur), vous laissez donc la position k' à votre adversaire ... et ainsi de suite jusqu'à arriver finalement à la position finale f où vous gagnerez.
On montre la propriété suivante :
---------------------------------
Un 1-graphe sans circuits admet un noyau ; en outre ce noyau est unique.
Elle nous assure de l'existence d'une solution au jeu de Chomp et d'une seule (le noyau).
------------------------
C - Programmation
*****************
Point de vue de celui qui veut programmer Chomp :
j'affecte la valeur 0 aux éléments du noyau (à commencer par la position finale f) et 1 aux éléments qui ne sont pas dans le noyau.
fonction valeur(sommet s) {
pour x prenant toutes les valeurs des successeurs {
si valeur(x) == 0 // c'est-à-dire si x est dans le noyau
alors retourner 1 // s n'est pas dans le noyau car x l'est
}
retourner 0 // s est alors dans le noyau (en particulier si s==f on arrive ici)
}
Retour à la première propriété et à sa démonstration
----------------------------------------------------
A est le rectangle m x n et B est le rectangle sauf un carreau : m x n-1
A : B :
XXXXXXX XXXXXX.
XXXXXXX XXXXXXX
XXXXXXX XXXXXXX
XXXXXXX XXXXXXX
XXXXXXX XXXXXXX
TOUS les successeurs de B sont aussi des successeurs de A
1) si valeur(B) = 1 alors valeur(A)=1
en effet B a alors un successeur de valeur 0 qui est donc aussi un successeur de A
2) Si valeur(B) = 0 alors valeur(A)=1 car B est un successeur de A.
Conclusion : dans tous les cas, valeur(A)=1, le premier à jouer sera le gagnant (s'il sait bien jouer, s'il sait trouver une position dans le noyau et ne fait jamais d'erreur).
Programmation de la recherche du noyau
--------------------------------------
J'ai donné plus haut une définition récursive de la fonction valeur(s).
Lorsque des démonstrations, comme celle vue plus haut, donnent les valeurs 0 ou 1 de certaines positions, on peut les utiliser dans la fonction 'valeur(s)'.
Dans mon implémentation en javascript j'utilise :
un tableau 'noyau[pos]' qui
- soit ne contient rien lorsque la position 'pos' n'est pas connue (n'a pas été étudiée)
- soit contient 0 ou 1 selon que 'pos' est connu comme étant ou non dans le noyau K.
une fonction 'gagne(pos)' qui correspond à la fonction 'valeur(s)' plus haut
mais qui plus intelligemment (gain de temps, pas d'espace) commence par regarder si noyau[pos] est ou non connu.
- si 'pos' est connu elle retourne sa valeur 'noyau[pos]'
- sinon, elle cherche récursivement sa valeur et l'inscrit dans le tableau noyau[] avant de la retourner.
De plus, il faut penser à jouer réellement, lorsqu'une position gagnante est trouvée comme successeur à 'pos', on la place dans un tableau : suivt[pos] = n,
par contre si pos est gagnant, on place suivt[pos] = pos et on laisse la possibilité à une autre fonction de choisir aléatoirement ou non la position (perdante) où aller.
Pour résumer,
- si gagne(pos) retourne 1 (hors noyau) vous trouvez la position où aller en prenant 'suivt[pos]' (qui vaut 0 et qui est dans le noyau)
- si gagne(pos) retourne 0 (dans le noyau) vous êtes perdu et vous pouvez aller où vous voulez, ce n'est pas 'suivt[pos]' qui vous dira où.
Codage des états, ou positions ou sommets du graphe.
----------------------------------------------------
Une particularité du programme est la manière de coder les sommets du graphe, c'est-à-dire les diverses positions du jeux
............. 0
XXX.......... 2
XXXXX........ 5
XXXXXXXX..... 8
XXXXXXXX..... 8
XXXXXXXXXXX.. 11
les colonnes les valeurs 5, 5, 5, 4, 4, 3, 3, 3, 1, 1, 1, 0, 0
de gauche à droite, ou
0 0 1 1 1 3 3 3 4 4 5 5 5 de droite à gauche,
les lignes valent 0, 2, 5, 8, 8, 11 de haut en bas ...
dans un jeu de dimensions 13 x 6 au départ
On peut choisir de coder un sommet par l'une ou l'autre de ces listes, moi j'ai décidé de considérer l'une de ces listes de nombres (je ne sais plus laquelle) comme l'écriture dans une certaine base, par exemple :
0 0 1 1 1 3 3 3 4 4 5 5 5 serait l'écriture d'un nombre en base 7 (la valeur maxi d'une colonne peut être égale à 6 mais pas plus).
11133344555(base 7) = 331478915 en base 10
on retrouve les nbres d'éléments des colonnes en prenant les restes de divisions successives par 7, on n'a à le faire qu'une fois.
En javascript ce serait encore plus simple de noter tout simplement la position par une chaîne de caractères :
position ="5 5 5 4 4 3 3 3 1 1 1 0 0"
on récupère alors tous ces nombres dans un tableau : colonnes=position.split(/\s/)
Recherche des successeurs
-------------------------
à chacun des carreaux marqués X va correspondre un successeur
.............
XXX..........
XXXXX........
XXXXXXXX.....
XXXXXXXX.....
XXXXXXXXXXX.. "5 5 5 4 4 3 3 3 1 1 1 0 0"
je choisis un carreau (que j'indique par une * en (3, 2))
.............
XXX..........
XXXXX........
XXX*XXXX..... 2 (3, 2)
XXXXXXXX.....
XXXXXXXXXXX.. 0
0 3
et j'obtiens le successeur
.............
XXX..........
XXX..........
XXX......... à partir de la position 3, on érase à 2 :
XXXXXXXX.....
XXXXXXXXXXX.. "5 5 5 2 2 2 2 2 1 1 1 0 0"
==============================================================================
QUESTION :
vous avez écrit : « On a deux possibilités, considérer comme on va
le faire que << arriver en f est gagnant pour le joueur >> ou le contraire,
qu'arriver en f est perdant. »
Primo, cela me paraît ambigu (l'état vide final f est-il gagnant ou perdant
pour celui qui le donne ou pour celui qui le reçoit ?).
Secundo, il n'y a qu'une éventualité intéressante à étudier : celle où l'état
f est perdant pour celui qui le donne et gagnant pour celui qui le reçoit.
-----------------------------------------------------------------------------
REPONSE :
Comme dans les autres jeux de Nim on doit choisir la règle du jeu qui est de
définir les déplacements autorisés et de dire si
"celui qui prend la dernière allumette" ou "le dernier carreau de chocolat"...
est le gagnant ou est le perdant.
Il y a donc évidemment une contradiction !
Mais bien entendu vous choisissez l'une ou l'autre des règles, pas les deux.
Même à "qui perd gagne", il n'y a qu'un gagnant et ce n'est pas le perdant
du jeu alternatif.
Il est préférable de prendre la règle qui est utilisée sur le site, l'autre règle
serait inintéressante !
==============================================================================
QUESTION :
je trouve étonnant qu'en théorie des graphes on considère comme
stable un ensemble S de sommets ssi tout sommet de S n'a aucun successeur dans
A.
Dans d'autres contextes on qualifie de stable etc.
-----------------------------------------------------------------------------
REPONSE :
Un ensemble S de sommets d'un graphe G est dit stable s'il n'existe pas dans S
deux sommets adjacents.
Si cette définition ne vous convient pas ou vous choque, je n'y peux
malheureusement pas grand chose, la définition n'est pas de moi et je n'ai pas
la possibilité de la changer car elle se trouve dans tous les cours de théorie
des graphes.
==============================================================================