Game Of Kayles

Explication du jeu de Kayles

les%20quilles%202.png

A la base du jeu de Kayles se trouve en fait une sorte de jeu de quilles modifié. Dans celui-ci, deux joueurs ont devant eux 13 quilles, dont la 2ème est déjà tombée. Les joueurs sont capables de faire tomber une quille, ou alors, deux quilles côte à côte. On part du principe que le joueur qui fait tomber la dernière quille est le gagnant.

Règles du jeu

Dans le jeu de Kayles, qui peut se jouer sur une table, les quilles sont remplacées par des jetons, mais le principe est le même. Il peut y avoir un nombre quelconque, mais fini, de jetons. Chacun son tour, le joueur peut enlever soit un, soit deux jetons placés l'un à côté de l'autre. Celui qui fait le dernier mouvement est le gagnant.

Capture%20d%E2%80%99%C3%A9cran%202013-11-10%20%C3%A0%2021.03.04.png

Si le joueur choisit d'enlever son ou ses deux pions dans un bord, il restera une ligne, comme au départ. Par contre, si le joueur décide d'enlever un (ou deux) pions au milieu de la ligne, alors celle-ci sera séparée en deux.

Capture%20d%E2%80%99%C3%A9cran%202013-11-10%20%C3%A0%2021.04.13.png

Dans le jeu de Kayles normal, c'est le joueur qui enlève le dernier jeton qui gagne.

Dans la variante misère du jeu, c'est le joueur qui enlève le dernier jeton qui perd. Dans ce cas-là, pour gagner, il faut faire en sorte de finir par laisser un jeton à l'autre adversaire.

Le jeu de Kayles est intéressant à analyser avec la théorie des jeux, car il a les propriétés suivantes:

  • Il a deux joueurs qui jouent en alternance.
  • Il est fini. Le jeu s'arrête toujours après un nombre fini de mouvements.
  • Il n'y a pas d'informations cachées. Les deux joueurs ont accès aux mêmes informations.
  • Il est déterministe, c'est-à-dire qu'il n'y a pas de hasard. Chaque mouvement donne lieu à une position unique.
  • Il est impartial, c'est-à-dire que les coups autorisés ne dépendent pas du joueur, mais de la position dans laquelle le joueur se trouve.
  • Il suit la règle "le dernier joueur qui fait un mouvement gagne".

Stratégie gagnante

La stratégie gagnante du jeu de Kayles est de laisser un nombre pair de groupes similaires de jetons, de manière à pouvoir copier exactement les mouvements de l'autre joueur. Par exemple, après avoir atteint la symétrie, si le joueur enlève un jeton parmi un groupe de quatre, alors il faudra aussi en enlever un parmi l'autre groupe de quatre jetons. Au final, cela vous garantit d'enlever le ou les deux derniers jetons, et donc de gagner.
Bien sûr, il est aussi intéressant de savoir, dans le cas où les deux joueurs auraient une stratégie gagnante, si c'est le premier ou le deuxième joueur qui gagne.
Pour un jeu de Kalyes avec n jetons, c'est le premier qui gagne à condition de savoir jouer parfaitement. Si n est pair, il faut enlever deux jetons consécutifs au centre afin d'atteindre la symétrie. Si n est impair, il faut enlever un jeton en réfléchissant de la même manière. Ensuite, il ne reste plus qu'à reproduire les mouvements du joueur 2 de manière symétrique jusqu'à ce qu'il ne reste plus qu'un ou deux jetons qu'il peut retirer, et ainsi gagner.

Capture%20d%E2%80%99%C3%A9cran%202013-11-10%20%C3%A0%2021.06.26.png

Prenons par exemple un jeu Kayles avec 13 jetons. Puisque le jeu commence avec un arrangement impairs de jetons, il faut que le premier joueur enlève un jeton au centre de la ligne de jeton. Ensuite, il ne lui restera plus qu'à copier exactement les mouvements du second joueur.
Ainsi, si le premier joueur à la stratégie, il gagnera toujours.

Valeurs de Sprague-Grundy

Somme des valeurs de Sprague-Grundy - Somme NIM

Pour additionner des valeurs de Sprague-Grundy, il faut transformer ces valeurs en nombre binaire ("nimber"). Ensuite, on peut les addtionner sous cette forme (somme NIM) et transformer le résultat obtenu à nouveau en nombre décimal.
Remarque: Si on additionne deux valeurs de Sprague-Grundy identiques, le résultat sera toujours de 0. Donc, par exemple, la valeur Sprague-Grundy de g(1)+g(1) est égale à 0.

Exemple: g(1)+g(3)

On note en binaire les chiffres 1 et 3:
1: [0 0 1]2
3: [0 1 1]2
On additonne ces nombres avec la somme de NIM: [0 0 1] ⊕ [0 1 1] = [0 1 0], qui vaut 2 en chiffre décimal.
Donc, g(1)+g(3) donc la valeur SG 2.

Valeurs de Sprague-Grundy du jeu de Kayles

Dans le but de trouver la fonction Sprague-Grundy du jeu de Kayles, il faut commencer par chercher quelques valeurs.
Tout d'abord, il y a la solution triviale

(1)
\begin{equation} g(0)=0 \end{equation}

En effet, s'il n'y a pas de jetons sur la table, le premier joueur ne peut pas jouer. Donc, selon les règles du jeu, il est perdant. Ceci implique une valeur de Sprague-Grundy égale à 0. Une valeur de Sprague-Grundy égale à 0 correspond à une position P. Toutes les autres valeurs (c'est-à-dire celles différentes de 0) correspondent à des positions N.
Pour

(2)
\begin{equation} g(1)=1 \end{equation}

le seul mouvement possible est d'enlever le seul pion présent. Donc, la valeur de Sprague-Grundy est de 1, puisqu'elle correspond au MEX (minimum exludent) de la valeur 0.

(3)
\begin{equation} g(2)=2 \end{equation}

En effet, il y a deux mouvements possibles: enlever un jeton ou enlever les deux jetons. A nouveau, on prend les MEX des positions dans lesquelles nous pouvons jouer, donc MEX(0,1)=2.

(4)
\begin{equation} g(3)=3 \end{equation}

car il y a trois mouvements possibles: enlever un ou deux jetons à l'une des extrémités, ou alors, enlever le pion central. On a ainsi la possibilité d'arriver dans les positions, g(1), g(2) ou g(1)+g(1), ce qui correspond à une valeur Sprague-Grundy de 0. Donc le MEX de tout cela est de 3.
Expliquons maintenant comment obtenir

(5)
\begin{equation} g(4)=1 \end{equation}

Il y a quatre mouvements possibles: enlever un ou deux jetons à l'une des extrémités, ou alors, enlever un ou deux pions au centre de la ligne de jetons. On peut se trouver dans les positions g(2), g(3), g(1)+g(2) qui donne une valeur SG de 3, ou g(1)+g(1), qui donne une valeur SG de 0. Le MEX de 0, 2, 3 vaut 1.
Par les mêmes méthodes, on trouve

(6)
\begin{equation} g(5)=4 \end{equation}
(7)
\begin{equation} g(6)=3 \end{equation}

Et ainsi de suite, pour les valeurs suivantes.

Capture%20d%E2%80%99%C3%A9cran%202013-11-11%20%C3%A0%2015.35.26.png

Puisque toutes les valeurs de Sprague-Grundy, ormi la première, sont différentes de 0, donc correspondent à des positions N, le joueur qui commence gagne automatiquement, à condition qu'il connaisse et suive la stratégie gagnante.

Généralisation de la fonction de Sprague-Grundy

Pour généralisier la formule de la fonction à un nombre de jetons n, tel que n < infini, il faut considérer deux cas:

Si n est pair:

(8)
\begin{gather} g(n)= MEX\{g(n-1); g((n-1)-1) + g(1); g((n-1)-2) + g(2); ...; g((n-1)-\frac {n-2}{2}) + g(\frac {(n-1)-1}{2}); \\ g(n-2); g((n-2)-1) + g(1); g((n-2)-2) + g(2); ... ; g((n-2)-\frac {n-2}{2}) + g(\frac {n-2}{2})\} \end{gather}

Si n est impair:

(9)
\begin{gather} g(n)= MEX\{g(n-1); g((n-1)-1) + g(1); g((n-1)-2) + g(2); ...; g((n-1)-\frac {n-1}{2}) + g(\frac {n-1}{2}); g(n-2); \\ g((n-2)-1) + g(1); g((n-2)-2) + g(2); ... ; g((n-2)-\frac{(n-2)-1}{2}) + g(\frac {(n-2)-1}{2})\} \end{gather}

Voici une explication plus claire de l'obtention de ces deux formules:

Capture%20d%E2%80%99%C3%A9cran%202013-11-09%20%C3%A0%2018.21.11.png

Exemple vidéo du Jeu de Kayles

Vous trouvez ici une vidéo comprenant quatre exemples du Jeu de Kayles avec 13 et 16 jetons consécutifs.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License