Jeux de Nim

Cette animation a été réalisée par Ouest INSA, à partir de l’applet réalisée dans le cadre d’un projet étudiant de l’École Polytechnique de l’Université de Tours, par Li Yifang, encadrée par Yannick Kergosien et Jean-Charles Billaut.

Dans l’animation que nous vous proposons, trois niveaux de difficulté sont disponibles lorsque vous affrontez l’ordinateur :

• le joueur débutant joue aléatoirement à chaque coup ;
• le joueur maître joue un coup sur deux aléatoirement, un coup sur deux avec la stratégie gagnante ;
• et le joueur expert joue avec la stratégie gagnante à chaque coup.

Historique

Les origines des jeux de Nim remontent très loin dans le temps, si bien qu’il est impossible d’indiquer avec certitude leur provenance. Ils sont signalés en Chine sous le nom de fan-tan et connus en Afrique sous le nom de tiouk-tiouk. Leur nom actuel nous vient de l’allemand nimm qui signifie prends !, et leur a été donné par le mathématicien américain Charles Leonard Bouton en 1901.

Un peu de théorie des jeux

Avant de préciser la stratégie des jeux de Nim, il convient d’aborder plus généralement la théorie des jeux. Vaste domaine de recherche à la frontière de l’économie et des mathématiques, la recherche opérationnelle envisage les problèmes d’aide à la décision par une approche mathématique. La théorie des jeux peut être vue comme l’une de ses branches, qui s’attache plus particulièrement à définir des algorithmes de calcul des solutions, de recherche de stratégie.

Un jeu se joue à plusieurs, au minimum deux adversaires. Ce qu’étudie la théorie des jeux, ce sont les choix de chaque joueur et les conséquences de ces choix sur l’ensemble du jeu. Voir à ce sujet le document Les jeux dynamiques, du combat aérien à l’écologie comportementale.

On distingue deux grandes catégories de jeux :

• les jeux à somme nulle : dans un jeu à somme nulle, le total des gains et des pertes des différents joueurs s’équilibre. Les jeux de Nim en sont un cas particulier à deux joueurs, où il y a toujours un vainqueur et un perdant, sans égalité possible. Le jeu de Morpion (ou TicTacToe) est un exemple dans lequel au contraire il n’est pas rare qu’aucun des deux joueurs ne gagne ;
• les jeux à somme non-nulle : un exemple classique de jeu à somme non-nulle est le dilemme du prisonnier. Deux personnes ayant commis un forfait sont arrêtées, et sans que les deux prisonniers puissent se concerter, on leur propose un marché. Si tous deux avouent, ils seront condamnés. Si tous deux nient, ils seront relâchés faute de preuve. Mais si l’un des deux avoue et que l’autre nie, celui qui coopère bénéficiera d’une remise de peine alors que l’autre sera condamné plus lourdement. On montre que dans ces circonstances, les deux prisonniers vont avouer, pour espérer une remise de peine et ne pas risquer une peine plus lourde.

Stratégie gagnante

Afin de montrer à quoi correspond la stratégie gagnante d’un jeu de Nim, nous allons prendre l’exemple du « jeu des allumettes », dont la règle est simple. Au départ il y a n allumettes, chaque joueur prend à tour de rôle une, deux ou trois allumettes, et le joueur qui prend la dernière allumette a perdu. Celui qui laisse une seule allumette a donc gagné.

Dans tous les jeux, le nombre de situations possibles est fini. Par exemple, dans le jeu des allumettes avec n = 12, il existe douze situations : il reste 12, 11, 10… ou 1 allumette. Il existe donc une stratégie gagnante pour chaque jeu, basée sur la connaissance de ces situations. Dans le cas des allumettes, la stratégie dépend du nombre d’allumettes restantes. Les schémas suivants expliquent comment gagner à tous les coups.

Imaginons que je joue contre vous, si la situation 1 est la suivante et que c’est à vous de jouer :

Vous prenez la dernière allumette et vous avez perdu.

Si nous sommes maintenant dans cette situation 2 et que c’est encore à vous de jouer :

Vous perdez, car je vais toujours vous ramener dans la situation 1 : si vous prenez une allumette, j’en prends trois ; si vous prenez deux allumettes, j’en prends deux ; si vous prenez trois allumettes, j’en prends une.

Maintenant, si nous sommes dans cette situation 3 avec encore quatre allumettes de plus et que c’est encore à vous de jouer :

Vous perdez encore, car je vais vous ramener de la même manière que précédemment dans la situation 2, et dans cette situation vous perdez.

Il est possible de continuer comme ça en ajoutant autant de fois que l’on veut quatre allumettes. Ainsi, par exemple, dans un jeu d’allumettes avec n = 12 :

C’est le joueur qui commence qui gagne, à condition de connaître la stratégie gagnante. Ici, il faut que le premier joueur prenne trois allumettes pour être sûr de gagner.

Dans les jeux de Nim, quelle que soit la stratégie gagnante utilisée, elle peut être implémentée dans un ordinateur. Les algorithmes qui représentent une stratégie gagnante utilisent la théorie des graphes et plus particulièrement la définition du noyau d’un graphe.

Graphe associé à un jeu de Nim

Dans la grande majorité des cas, l’ensemble des situations, même s’il est très grand, est fini. Il est alors possible de constituer un graphe de leur enchaînement, traduisant l’ensemble des coups possibles à jouer.

Un graphe est une structure mathématique définie par un ensemble de sommets et un ensemble d’arcs orientés reliant deux sommets. Dans le graphe associé à un jeu de Nim, les sommets représentent les situations et les arcs sortant d’un sommet et entrant dans un autre représentent les coups qui font passer d’une situation à une autre. Partant d’une situation initiale, représentée dans le graphe par un sommet sans arc entrant, le jeu évolue vers une situation finale représentée par un sommet sans arc sortant, un « puits » dans le langage de la théorie des graphes.

Dans l’exemple du jeu des allumettes, chaque sommet est renseigné par le nombre d’allumettes qui restent dans cette situation et chaque arc est renseigné par le nombre d’allumettes retirées lors du coup correspondant. Voici par exemple le graphe correspondant à un jeu de douze allumettes.

Graphe correspondant à un jeu de douze allumettes
L’état initial porte le nombre d’allumettes présentes en début de partie, donc ici 12. De ce sommet partent trois arcs, selon que le joueur enlève une, deux ou trois allumettes. Les trois sommets suivants possibles sont donc étiquetés respectivement 11, 10 et 9. Dans la situation terminale, il reste une seule allumette (elle est étiquetée 1). Le joueur qui arrive dans cette situation a gagné, puisqu’il ne laisse pas d’autre choix à son adversaire que de prendre la dernière allumette.

Le jeu ne peut évoluer que dans un sens, puisqu’on retire des allumettes et qu’on n’en ajoute jamais. Le graphe d’enchaînement des situations a donc la particularité d’être sans circuit, c’est-à-dire qu’il est impossible en suivant les arcs de partir d’un sommet et d’y revenir.

Pour chaque jeu de Nim, un tel graphe sans circuit peut être dessiné suivant les principes énoncés.

De l’importance du noyau du graphe

Le problème à résoudre est maintenant le suivant : comment assurer à un joueur que ce sera lui qui arrivera dans le sommet étiqueté 1, situation finale et gagnante ?

La solution repose sur la notion de noyau d’un graphe. Un noyau est un sous-ensemble de sommets particuliers : quel que soit le sommet du graphe, il existe toujours un arc qui relie ce sommet à un sommet du noyau (on dit que le noyau est un ensemble absorbant) et il n’existe pas d’arc reliant deux sommets du noyau entre eux (on dit que le noyau est un ensemble stable). Selon les graphes, il existe ou non un ou plusieurs noyaux. Dans le cas d’un graphe sans circuit, il existe toujours un noyau unique. Dans notre exemple des douze allumettes, il est assez facile de vérifier que le noyau du graphe est l’ensemble des sommets 1, 5 et 9.

Graphe correspondant à un jeu de douze allumettes. Le noyau du graphe comprend les sommets 9, 5 et 1.

C’est ce noyau qui va déterminer la stratégie gagnante : si le joueur se trouve dans une situation telle que le sommet correspondant est dans le noyau, il sera gagnant. En effet, l’autre joueur, dont c’est le tour de jouer, sera obligé de sortir du noyau (en raison de la stabilité) et notre joueur pourra toujours revenir dans le noyau (qui est absorbant) au coup d’après. Étant donné que la situation gagnante, le sommet 1, est dans le noyau, notre joueur est assuré de pouvoir l’atteindre, à condition bien sûr qu’il ait la possibilité de se placer dans le noyau. Ce qui lui est garanti s’il joue en premier, et que le sommet correspondant au nombre initial d’allumettes n’est pas dans le noyau. Il est en effet facile de voir que, partant du sommet initial, le joueur qui joue en premier peut toujours entrer dans le noyau, puisque celui-ci est absorbant. Sur notre exemple, il lui suffit d’enlever trois allumettes, ce qui fait passer du sommet 12 au sommet 9, qui appartient au noyau.

La détermination du noyau du graphe associé au jeu fournit donc la stratégie gagnante : il s’agit de jouer en premier et de retirer à chaque coup le nombre d’allumettes qui fait entrer dans le noyau, et terminer ainsi par le « puits » du graphe, qui est à l’intérieur du noyau : la situation où il ne reste qu’une allumette.

Trouver le noyau dans un graphe quelconque est un problème qui a beaucoup été étudié. Il a été démontré qu’il fait partie de l’ensemble des problèmes, appelés NP-complets, dont la complexité, évaluée en nombre d’opérations élémentaires à effectuer, croît exponentiellement en fonction de la taille, ici le nombre de sommets du graphe. Cependant, dans un graphe sans circuit, le problème est plus facile : sa complexité est polynomiale en fonction de la taille du graphe.

Le noyau d’un graphe n’est qu’un moyen, parmi d’autres de la théorie des jeux, d’approcher mathématiquement les jeux. Cependant, dans le cas des jeux de Nim, c’est la meilleure approche. De plus, la théorie des graphes fournit suffisamment d’outils pour résoudre tous ces types de jeux.

La théorie des jeux est encore plus vaste. Elle a pour but de mettre en place la meilleure stratégie possible en fonction de l’analyse des situations actuelles et antérieures du jeu et des comportements des individus. Suivant le type de jeux (coopératif, de compétition, avec hasard…), différents outils mathématiques peuvent être utilisés pour aider à trouver la meilleure stratégie. Ces outils sont nombreux et très spécifiques : programmation linéaire, théorie combinatoire, théorie des graphes… et même l’intelligence artificielle.