Jeu de Cram

Le jeu de Cram est un jeu mathématique, étudié dans le cadre de la théorie des jeux combinatoires. Le jeu se joue sur un damier que l'on remplit progressivement de Dominos. Il a été connu sous plusieurs noms différents dans le monde anglo-saxon, notamment plugg et dots-ands-pairs, avant d'être popularisé sous le nom de Cram par Martin Gardner dans la revue Scientific American, en 1974[1].

Un exemple de partie du jeu de Cram. Dans la version normale, le joueur bleu gagne car il a joué en dernier.

Pour les articles homonymes, voir CRAM.

Règles

Le jeu se déroule sur un quadrillage, habituellement rectangulaire, mais on peut généraliser à des formes de quadrillage irrégulières, comme des polygones.

Les joueurs disposent d'un ensemble commun de dominos, en nombre suffisant pour recouvrir l'ensemble du quadrillage. Ils placent un domino sur la grille à tour de rôle, horizontalement ou verticalement. Contrairement au jeu très proche du Domineering, les joueurs disposent donc des mêmes coups possibles à tout moment de la partie, et le Cram est donc un jeu impartial.

Comme pour tous les jeux impartiaux, deux conventions de victoires sont possibles :

  • dans la version normale du jeu, le joueur qui ne peut plus jouer a perdu.
  • au contraire, dans la version dite misère, celui qui ne peut plus jouer a gagné.

Jeu par symétrie

Dans le cas du Cram en version normale, il existe une stratégie gagnante simple pour les plateaux de taille pair × pair (la hauteur et la largeur du plateau sont paires, par exemple 2 × 2, 4 × 6, etc.) et de taille impair × pair (une dimension paire et l'autre impaire, par exemple 3 × 6, 4 × 5, etc). Dans le cas pair × pair, le second joueur peut gagner en jouant par symétrie. Cela signifie qu'à chaque fois que le Joueur 1 effectue un coup, le Joueur 2 peut répondre avec un coup symétrique par rapport au point central du plateau. En imitant ainsi chaque coup de son adversaire, le Joueur 2 est certain d'effectuer le dernier coup, et donc de gagner la partie.

Dans le cas pair × impair, c'est cette fois le premier joueur qui gagne en effectuant des coups symétriques. Le joueur 1 commence par placer son premier domino sur les deux cases centrales du plateau (parallèlement à la direction de dimension paire). Il peut ensuite imiter les coups de son adversaire en jouant le symétrique par rapport à ce domino central, ce qui lui assure de jouer le dernier coup et de remporter la partie.

Il est à noter que cette stratégie utilisant des coups symétriques ne fonctionne pas en version misère, parce que dans ce cas-là elle assurerait au joueur l'appliquant uniquement une défaite, et non pas une victoire. En version misère, aucune stratégie simple de ce type n'est connue.

Version normale

Nimbers

Puisque le Cram est un jeu impartial, le théorème de Sprague-Grundy indique que, dans la version normale du jeu, toute position est équivalente à un certain nimber, c'est-à-dire à un tas d'une certaine taille du jeu de Nim. Les valeurs de nimbers de plusieurs positions remarquables sont données dans Winning Ways for your Mathematical Plays, avec en particulier une solution complète des damiers de taille 2 × n, dont le nimber est 0 si n est pair et 1 si n est impair[2].

La stratégie de symétrie décrite pour les plateaux de taille pair × pair implique que ceux-ci ont un nimber de 0, mais dans le cas des plateaux de taille pair × impair, elle implique seulement que le nimber est supérieur ou égal à 1, sans donner la valeur exacte.

Valeurs connues
Nimbers des grands plateaux
n × m456789
4 020301
5 -0211≥1
6 --0>30≥1
7 ---≥1≥1 ?

En 2009, Martin Schneider a calculé les valeurs de nimbers des plateaux allant jusqu'à des tailles de 3 × 9, 4 × 5 et 5 × 7[3]. Puis, en 2010, Julien Lemoine et Simon Viennot ont appliqué au jeu de Cram des algorithmes développés initialement pour le jeu de Sprouts[4]. Cela leur a permis de calculer les valeurs de nimbers jusqu'aux plateaux de taille 3 × 18, 4 × 9 et 5 × 8. Ils ont également pu calculer que les plateaux 5 × 9 et 7 × 7 sont gagnants pour le premier joueur (mais sans obtenir la valeur complète du nimber)[5].

Les valeurs connues de nimbers pour les plateaux 3 × n, de n=1 à n=18, sont: 1, 1, 0, 1, 1, 4, 1, 3, 1, 2, 0, 1, 2, 3, 1, 4, 0, 1. Aucune régularité apparente n'est connue.

La table de droite montre les nimbers connus pour des plateaux dont les dimensions sont supérieures à 4 cases. Le nimber d'un plateau n × m est le même que celui d'un plateau m × n.

Version misère

Valeur de Grundy misère

La valeur de Grundy misère d'un jeu G est définie par Conway dans On Numbers and Games comme l'unique nombre n tel que G+n (la somme de G et d'un jeu de Nim de taille n) soit une victoire pour le second joueur en version misère[6]. Même si la valeur de Grundy misère se définit d'une façon similaire au nimber (aussi appelé valeur de Grundy) en version normale, elle ne possède pas autant de priorités. En particulier, il n'est pas possible de déduire la valeur de Grundy misère d'une somme de jeux à partir des valeurs de Grundy misère des composantes de la somme.

Valeurs de Grundy misère
n × m456789
4 000111
5 -211 ? ?
6 --1 ? ? ?

Valeurs connues

En 2009, Martin Schneider a calculé les valeurs de Grundy misère jusqu'à des plateaux de tailles 3 × 9, 4 × 6, et 5 × 5[3]. En 2010, Julien Lemoine et Simon Viennot ont étendu le calcul des valeurs jusqu'à des plateaux de taille 3 × 15, 4 × 9 et 5 × 7, ainsi qu'au plateau de taille 6 × 6[5].

Les valeurs de Grundy misère connues pour les plateaux 3 × n, de n=1 à n=15, sont : 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1. Cette suite est conjecturée périodique, de période 3[5].

La table de droite montre les valeurs connues pour les plateaux dont l'une des dimensions est supérieure à 4.

Références
  1. (en) Martin Gardner Mathematical Games: Cram, crosscram and quadraphage: new games having elusive winning strategies Scientific American, vol. 230, 1974, pages 106–108.
  2. (en) Elwyn R. Berlekamp, John H. Conway et Richard K. Guy, Winning ways for your mathematical plays, vol. 3, Natick, Mass, A.K. Peters, , 2e éd. (1re éd. 1982), 275 p. (ISBN 978-1568811437 et 1568811438).
  3. (de) Das Spiel Juvavum, Martin Schneider, thèse de Master, 2009
  4. (en) Nimbers are inevitable, Julien Lemoine, Simon Viennot, arxiv (2010)
  5. (en) Résultats de calculs de Cram, Julien Lemoine, Simon Viennot
  6. (en) Conway John H., On Numbers and Games, A K Peters, Ltd., , 2e éd., 256 p. (ISBN 1568811276 et 978-1568811277)
  • Portail des jeux
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.