Jeux de Nim

Les jeux de Nim voient s'affronter deux joueurs qui jouent à tour de rôle. Il existe de nombreuses variantes de ces jeux très connus, avec des allumettes, des pièces, des graines, des billes, etc. Il s'agit de prendre, de déplacer ou de poser un certain nombre d'objets ; selon les variantes, le dernier à jouer gagne ou perd. Il y a forcément un gagnant, et donc un perdant.

Pour les jeux de stratégie pure, ne laissant aucune part au hasard, les règles sont importantes, car il en découle une stratégie. Pour les jeux de Nim en particulier, il existe toujours une stratégie gagnante. Quand on la connaît, et si les conditions sont réunies (choix de la personne qui commence par exemple), on peut toujours gagner... mais encore faut-il la trouver.

Pourquoi l'informatique s'est-elle intéressée aux jeux de Nim ? Définir des approches mathématiques pour résoudre des problèmes de stratégie, c'est l'objet du domaine de recherche appelé la théorie des jeux. Les jeux de Nim ont été beaucoup étudiés afin d'implémenter des algorithmes qui mettent en œuvre la stratégie gagnante. La théorie des graphes a permis de concevoir de tels algorithmes rapides.

Voici quatre exemples de jeux de Nim, vous pouvez y jouer contre l'ordinateur ou avec un ami.

Cette applet a été réalisée dans le cadre d'un projet étudiant de l'École Polytechnique de l'Université de Tours document externe au site, par Li Yifang, encadrée par Yannick Kergosien et Jean-Charles Billaut.
 

Dans l’applet 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 anglais 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 autre document Interstices.

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 où 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 1, 2 ou 3 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 12 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 à chaque coup.

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 1 allumette, j’en prends 3; si vous prenez 2 allumettes, j’en prends 2; si vous prenez 3 allumettes, j’en prends 1.

Maintenant, si nous sommes dans cette situation 3 avec encore 4 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 4 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 3 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 12 allumettes.

graphe pour 12 allumettes
Graphe correspondant à un jeu de 12 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 1, 2 ou 3 allumettes. Les 3 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 12 allumettes, il est assez facile de vérifier que le noyau du graphe est l’ensemble des sommets 1, 5 et 9.

graphe pour 12 allumettes
Graphe correspondant à un jeu de 12 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 3 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.

graphe pour 12 allumettes - exemple de partie

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 definition, 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.

Tags