Variation sur un concept d’Aviezri Fraenkel

Dans cet article, on va s’intéresser à des jeux impartiaux, dont l’archétype est le jeu de Nim. Dans ce jeu, on dispose de jetons, disposés en tas comme ici (jeu de Nim à deux tas) :

Ci-dessous ce jeu sera noté (3,2) car il y a un tas de 3 jetons et un tas de 2 jetons. Un coup du jeu de Nim consiste à

• choisir un tas (par exemple celui de droite),
• en retirer autant de jetons qu’on souhaite (par exemple un seul) :

Celui qui prend le dernier jeton gagne le jeu. Ci-dessus ce sera celui qui a joué en premier, parce qu’il dispose maintenant d’une stratégie gagnante (jouer dans un tas ce que son adversaire vient de jouer dans l’autre tas). Mais dans le cas général, on calcule ce qu’on appelle nombre de Grundy du jeu, et ce nombre (un entier résumant le jeu) se calcule récursivement sur le graphe du jeu. Pour construire ce graphe, on assimilera la position

avec la position

car l’emplacement des tas importe peu pour la stratégie gagnante, tout ce qu’il faut connaître, c’est la hauteur de chacun des tas. Les deux positions ci-dessus seront toutes deux notées (2,1) : on convient de mettre dans l’ordre décroissant les hauteurs des tas de jetons. De plus, on ne note pas les tas devenus vides. Avec ces conventions le graphe du jeu est :

Le calcul des nombres de Grundy de chaque sommet donne la valeur 1 pour le sommet qui est en haut. Ce nombre de Grundy étant différent de 0, il y a une stratégie gagnante consistant à viser un sommet dont le nombre de Grundy est nul, et ce sommet est (2,2). L’idée fondamentale de Fraenkel est d’utiliser ce graphe, non pour modéliser le jeu, mais pour jouer, par le biais d’un pion, commun aux deux joueurs, et qu’à chaque tour de jeu on glisse le long d’une flèche, jusqu’à ce que ce ne soit plus possible (parce que le pion est tombé dans un puits en bas), auquel cas le dernier à avoir bougé le pion (le joueur qui a fait tomber le pion dans le puits) a gagné le jeu. Quelques définitions :

• un graphe orienté est connexe s’il est d’un seul tenant (on ne peut pas le séparer en deux morceaux sans enlever un sommet ou un arc),
• un cycle est un chemin permettant d’aller d’un sommet à lui-même en suivant des flèches,
• un graphe n’ayant pas de cycle est un graphe acyclique,
• un sommet où n’arrive aucune flèche est une source,
• un sommet dont ne part aucune flèche est un puits.

Les jeux de Fraenkel se jouent sur des graphes orientés connexes et acycliques. De tels graphes ont au moins une source et au moins un puits. Pour savoir où mettre le pion au départ, il faut qu’ils n’y ait qu’une source, et le jeu est plus facile à jouer s’il n’y a qu’un puits, comme sur ce graphe d’enfant (dont le nombre de Grundy est 2) :

On énonce alors le

Théorème de Fraenkel : tout jeu impartial est équivalent à un jeu où on déplace un pion sur un graphe orienté connexe acyclique ayant une source et un puits, le pion étant placé au départ sur la source et le gagnant étant celui qui amène le pion dans le puits.

Atelier de création de jeux impartiaux

Un atelier de création de jeux impartiaux revient à un atelier de dessins de graphes orientés, ce qui suggère ce genre de tournoi :

• chaque enfant se voit remettre du papier et un crayon, et dessine un graphe orienté,
• si le graphe comporte un cycle, il est disqualifié,
• s’il comporte plusieurs sources ou plusieurs puits, il est pénalisé,
• les graphes restants sont alors classés par nombre de Grundy, et le graphe ayant le plus grand nombre de Grundy est gagnant du tournoi.

La récompense pour le gagnant est l’organisation d’un tournoi de jeu impartial sur son graphe. Un outil d’aide à la conception de graphes orientés est disponible en ligne sur Nirina974. Un bêta-test a permis à une enfant de 8 ans de rapidement produire ce graphe dont le nombre de Grundy est 3 :

(le départ est en bas à gauche). Et voici un graphe créé par Aviezri Fraenkel (il a deux puits, coloriés en vert ; son nombre de Grundy est 0) :

Autres concepts d’Aviezri Fraenkel

Fraenkel s’est beaucoup intéressé au calcul de nombres de Grundy sur certains graphes ayant un ou plusieurs cycles comme

dont le nombre de Grundy est aussi égal à 0.

Conway et Fraenkel ont classé les interactions possibles entre pions sur un graphe orienté connexe (avec ou sans cycle) :

• Les pions peuvent être des bosons, auquel cas il n’y a pas de limite supérieure au nombre de pions présents sur un sommet du graphe.
• Les pions peuvent s’exclure mutuellement comme des fermions, ce qui occasionne des blocages ; Conway attribue à un certain Welter la création d’un cas particulier de ce genre de jeu, où le graphe est formé de sommets alignés, chacun étant relié à tous les sommets qui sont à sa gauche.
• Les pions peuvent se comporter comme des antiparticules : lorsqu’un pion arrive sur un sommet déjà occupé, les deux pions sont retirés du jeu.
• les pions peuvent être de deux couleurs, et avoir un comportement mixte : un pion ne peut pas aller sur un sommet où se trouve un pion de la même couleur, mais peut occuper un sommet où se trouve un pion de l’autre couleur, auquel cas il va le clobber, c’est-à-dire qu’il prend sa place en le retirant du graphe, comme aux échecs.

Dans ce dernier cas, Fraenkel a conçu un jeu impartial :

et même un jeu partisan (chaque joueur ayant ses propres 7 pions) sur un graphe pas entièrement orienté :

Ce jeu a été commercialisé dans les années 1970 sous le nom de on the line, puis dans les années 2000 sous le nom de arrows. Dans ce dernier cas, le plateau de jeu était en bois, avec des creux pour les pions, lesquels étaient des billes, transparentes pour un joueur, et métalliques pour l’autre joueur. Sur le site https://mathpickle.com/ (consacré à l’enseignement des maths par la ludologie), des jeux similaires ont été proposés sur des graphes plus simples :

https://mathpickle.com/wp-content/uploads/2015/08/Arrows-Game.pdf

Certains de ces graphes semblent permettre d’introduire la notion de parité (apparemment en cycle 2).

Variation sur un thème de Fraenkel

Revenons un peu en arrière, là où Fraenkel suggère de mettre plusieurs pions sur un graphe orienté connexe acyclique, le mode d’interaction des pions faisant partie de la règle du jeu. La carte des cartes donne envie d’explorer cette variante :

Avant de jouer, on place un pion sur l’unique source de chaque composante connexe d’un graphe orienté acyclique. Un tour de jeu consiste à choisir un des pions qui n’est pas encore bloqué, puis le bouger suivant une flèche. Le premier qui ne peut plus bouger a perdu le jeu.

Les composantes connexes

En vrai, avant de jouer, on construit les composantes connexes du graphe, par exemple en les puisant d’une collection établie lors de l’activité décrite dans la partie atelier de création de jeux impartiaux plus haut, ou comme modèles de jeux impartiaux connus comme par exemple le jeu de Sowing impartial (graphes simplifiables en mettant ensemble tous les puits et en tenant compte des symétries) :

ou alors des graphes orientés connexes acycliques créés sans chercher à modéliser un autre jeu impartial, juste en dessinant le graphe, comme par exemple le graphe d’enfant vu en début d’article, que voici rendu en Python :

ou, enfin, des graphes qui ont été créés spécialement pour cette activité cartes des cartes impartiales :

Le jeu est à deux joueurs :

• les deux joueurs choisissent des graphes orientés connexes acycliques ayant une source et un puits parmi la collection (iles choisissent des cartes dans le jeu de cartes),
• puis posent ces cartes sur la carte des cartes (la table : ils construisent le plateau de jeu avant de jouer),
• puis posent un pion à chaque départ d’une carte,
• et, enfin, jouent : chacun son tour, déplace un des pions en lui faisant suivre une flèche.
• Le premier qui ne peut plus bouger (parce que tous les pions sont dans des puits) a perdu.

Application au jeu de Nim

On rappelle que pour le jeu de Nim à deux tas (3,2), le graphe possède 9 sommets :

Mais la version à deux composantes connexes n’en a plus que 7 (par contre il y a deux pions) :

et on peut simplifier encore : comme la composante connexe de gauche a un nombre de Grundy égal à 3 (c’est un tas de 3 jetons) et celle de droite a un nombre de Grundy égal à 2 (c’est un tas de 2 jetons), le jeu est, d’après les théorèmes de Sprague-Grundy et de Fraenkel, LE jeu de nombre de Grundy 1 (Nim-somme de 3 et 2), c’est-à-dire ce jeu (à seul pion pour le coup) :

Comment jouer/faire jouer

Comme il s’agit de jeux à deux joueurs, chaque table de jeu occupe deux joueurs. Mais en plus il y a une table centrale où se trouvent posées des cartes, dont chacune porte un graphe orienté connexe acyclique avec une source et un puits. Les joueurs d’une table de jeu commencent par choisir quelques cartes de la table centrale (en essayant de ne pas frustrer les joueurs d’autres tables) puis les posent sur leur table de jeu, en mettant un pion au départ de chaque carte.

Puis ils jouent au jeu qu’ils ont créé, c’est-à-dire que chacun son tour bouge un pion le long d’une flèche. Lorsque le jeu est terminé (plus aucun pion ne peut bouger, donc celui qui devait jouer a perdu), ils notent les nombres de Grundy des cartes choisies et leur Nim-somme.

Ensuite ils préparent un autre jeu, en choisissant parmi ces opérations :

• enlever une carte jugée inintéressante,
• ajouter une carte qui semblait manquer,
• échanger une carte peu intéressante contre une carte plus intéressante (comme au poker) au niveau de la table centrale.

Après quelques tours de ce métajeu, on compare les jeux les plus intéressants, et les nombres de Grundy obtenus. La version sans nombres de Grundy est plus simple mais fait appel au jugement humain pour ranger les jeux construits par qualité subjective.