Le jeu de Hex

mardi 19 octobre 2021
par  Alain BUSSER

Les bleus essayent de créer un chemin bleu de haut en bas ; les rouges essayent de créer un chemin rouge de gauche à droite. On ne se rappelle plus si c’est aux bleus ou aux rouges de jouer mais on voit bien qui va gagner :

Histoire du jeu

En 1942, Piet Hein (physicien) (inventeur du cube soma) a décrit à un colloque organisé par Niels Bohr un jeu mathématique qu’il considérait comme exemplaire du genre (pas d’intervention du hasard, règle du jeu courte, durée d’une partie pas trop longue...). Hein était danois et comme tous les habitants de Copenhague, passait beaucoup de temps dans les couloirs du métro à cause des bombardements. Les habitants lisaient alors la revue Politiken où se trouvaient des jeux pour occuper les danois durant les bombardements. Le 26 décembre 1942, dans la revue Politiken, Hein a décrit le jeu connu aujourd’hui sous le nom de Hex mais alors appelé Polygon. Hein décrivait le plateau comme ayant toute dimension entre 5×5 et 11×11 mais le dessin du journal Politiken est un 11×11 :

Un des plus anciens problèmes de Hex a été publié dans le même journal fin 1942. Le prochain joueur gagne :

Qui est-il ? Comment gagne-t-il ?

En 1948, John Forbes Nash découvre, à Princeton, go (jeu). Il y invente une variante de Go où, en plus des lignes verticales et horizontales du goban [1], il imagine des diagonales dans chaque carré [2]. Le jeu est alors connu à Princeton sous le nom de « Nash ».

En 1951, Claude Shannon invente un jeu basé sur une compétition entre construction et destruction d’un graphe. En fait, comme couper une arête revient au même que créer une arête dans le graphe dual, le jeu de Shannon généralise Hex (dont le graphe est autodual). Au passage, Shannon crée un réseau électronique (page 5) permettant de jouer à Hex.

En 1952, les frères Parker commercialisent ce jeu, sous le nom de Hex. Puis (en partie sous l’impulsion de Martin Gardner en juillet 1967) le jeu est commercialisé au Danemark sous le nom de Con-Tac-Tix en 1968.

Le jeu dessiné par Nash :

Depuis, le jeu n’est plus guère commercialisé, mais on peut y jouer avec relativement peu de matériel, de surcroît instructif à créer.

Matériel nécessaire

Pour jouer à Hex, il faut une grille et des jetons. Pour les jetons, des tranches de bouchons de liège peintes en bleu et rouge conviennent (attention toutefois à ce que les élèves ne les mettent pas dans la bouche). De plus, comme après avoir posé un pion, on ne le bouge plus, Hex est de facto un jeu de coloriage. Les joueurs peuvent donc jouer avec des crayons de couleur ce qui présente l’avantage double, de faire travailler la psychomotricité par le coloriage et de permettre après coup d’analyser la partie, par exemple pour voir qui a gagné. Si on veut réutiliser le plateau de Hex, des pierres de go (jeu) font également l’affaire.

Voici des plateaux [3] au format pdf, à imprimer, pour jouer avec des jetons rouges et bleus ou en coloriant :

Voici un exemple de partie jouée entre un joueur de CE1 et son frère de petite section :

En petite section, jouer consiste essentiellement à placer les jetons (rouges ici) dans les cases. C’est plus facile qu’une boîte de formes mais c’est plat et bien placer le jeton au centre de la case est ludique.

Ici les rouges (petite section) ont déjà gagné mais aucun des deux joueurs ne s’en aperçoit. Il vaut donc mieux laisser jouer les élèves jusqu’à remplissage du plateau :

Et seulement après cela, poser la question : qui a gagné ? Cela prend du temps de trouver ! On peut même donner des exercices en distribuant des images similaires à celle ci-dessus et demander qui est le gagnant (par exemple en encerclant les hexagones donnant le chemin gagnant). Ici il y a 49 jetons à placer ce qui dure plusieurs minutes. Temps auquel il faut ajouter l’analyse du jeu.

Qui a gagné ?

Pour le savoir, on fait parcourir (virtuellement) le plateau de jeu par un robot de type tortue qui part d’un bord puis,

  • s’il a une dalle rouge à sa gauche et une dalle bleue à sa droite, s’arrange pour toujours avoir une dalle rouge à sa gauche et une dalle bleue à sa droite,
  • s’il a une dalle bleue à sa gauche et une dalle rouge à sa droite, s’arrange pour toujours avoir une dalle bleue à sa gauche et une dalle rouge à sa droite.

De tels robots, sur l’exemple ci-dessus, laisseront ces traces vertes :

On voit que parmi ces tracés verts, un seul joint deux bords opposés : il sépare un chemin rouge et un chemin bleu joignant tous deux les deux bords rouges.

Cela montre que les rouges ont gagné. Mais ce n’est pas tout : comme un chemin vert joignant les deux bords rouges et un chemin vert joignant les deux bords bleus ne peuvent se croiser, ils ne peuvent exister tous les deux sur le même plateau. Ce qui signifie qu’à Hex, il n’y a pas de différence entre un jeu défensif et un jeu offensif : essayer d’empêcher l’adversaire de faire un chemin, revient à essayer de faire son propre chemin.

Et ce n’est pas tout : puisque les parties nulles n’existent pas en Hex, il y a une stratégie gagnante pour l’un des deux joueurs. Or cela ne peut pas être le second joueur, car sinon le premier disposerait de cette stratégie gagnante :

  • jouer n’importe quelle case ;
  • laisser le second joueur jouer ;
  • appliquer chaque fois que c’est possible, la stratégie gagnante du second joueur. Quand ce n’est pas possible (car la stratégie gagnante consisterait à jouer la case jouée en premier), jouer n’importe quelle case restante ;
  • etc.

Ce vol de stratégie montre que s’il y a une stratégie gagnante, ce ne peut être que pour le premier joueur. Or il existe une stratégie gagnante (puisque les parties nulles sont impossibles) donc elle est pour le joueur qui joue en premier.

Ce résultat est connu depuis sa publication par Nash, dans cet article de RAND :

La règle du gâteau

Même si on ne connaît pas la preuve de Nash, la pratique du jeu de Hex finit par faire pressentir l’avantage qu’il y a à jouer en premier. Pour rétablir une certaine équité, deux astuces existent parmi les joueurs de Hex :

  1. Le jeu de Rex (Reverse Hex) est identique à Hex, à ceci près que le premier qui a joint ses bords opposés par un chemin de sa couleur, est le perdant. C’est donc la version « qui perd gagne » de Hex [4].
  2. La règle du gâteau est un algorithme classique pour approcher l’équité. Dans le cas de Hex, elle consiste à laisser le second joueur, au début du jeu, un choix :
  • ou bien il joue en plaçant un de ses jetons sur une case de son choix (autre que celle déjà jouée)
  • ou bien il change d’identité avec son adversaire, de sorte que celui-ci rejoue mais dans une autre couleur, qu’il gardera jusqu’à la fin du jeu.

Il peut être intéressant de voir combien d’élèves de l’école maternelle réinventent cet algorithme, ou inventent leur propre algorithme de recherche d’équité.

Jouer en ligne

Ce fichier permet de jouer en ligne, en cliquant sur une case blanche pour la colorier en rouge ou en bleu :

Toutefois, il n’est pas très facile de voir les chemins. Par exemple ci-dessus, Rouge a gagné, et cela se voit moins que sur la version classique :

Graphes

Voici une variante en ligne du jeu à 5×5 cases (ci-dessous, carrées) :

On fait en quelque sorte rétrécir les cases pour qu’elles deviennent les sommets d’un graphe, dont chaque joueur essaye de joindre (par des sommets de sa couleur) les deux sommets déjà coloriés dans sa couleur :

C’est sur ce genre de graphe que Shannon a créé son jeu de connexion et sa stratégie au Hex : il suffit de remplacer chaque arête du graphe par une résistance (toutes les résistances étant de la même valeur) et les sommets bleus sont reliés à la masse, les sommets rouges au plus de l’alimentation (le rôle de Rouge est en fait d’essayer d’établir un court-circuit).

D’autres graphes que le jeu classique de Hex peuvent être coloriés. Par exemple ce jeu inédit, avec ce célèbre graphe :

Ce dernier jeu possède une stratégie gagnante, laquelle ?

Autres jeux de connexion

Un cas particulier du jeu de Shannon a été créé à la fin des années 1950 par David Gale. Il s’appelle bridg-it et a fait l’objet d’une expérimentation à l’école Decroly de Saint-Mandé dans les années 1970. Les points à relier étaient peints sur des ardoises sur lesquelles les élèves jouaient avec des craies de couleurs différentes. On peut aussi y jouer avec une planche à clous et des bâtons calibrés de deux couleurs pour être placés entre deux clous.

Les jeux de connexion suivants nécessitent un matériel relativement facile à fabriquer : des cartes de forme carrée ou hexagonale montrant des morceaux de chemins à assembler pour des chemins plus longs.

L’un des plus anciens est le Black path game comportant les trois types de cartes suivantes :

En fait, il n’y a que deux cartes possibles, les deux premières ci-dessus étant deux versions de la même carte tournées différemment.

Comme aux dominos, les joueurs placent alternativement des pièces parmi les 3 ci-dessus, de manière que la pièce touche une pièce déjà posée (la première pièce est posée sur un bord de la grille). Au fur et à mesure que les pièces sont posées, il se forme un chemin. Lorsque ce chemin joint deux bords de la grille (ou un bord à lui-même), le joueur qui vient de poser une pièce a perdu le jeu :

Le second des jeux de Lewthwaite utilise uniquement cette carte (dans deux orientations différentes) :

Mais là, on ne pose pas les cartes (on les fait glisser comme au taquin). Et le but du jeu est cette fois-ci d’être le premier à constituer un chemin de longueur pas trop courte.

Ni le Black path game, ni le second jeu de Lewthwaite, n’ont été jusqu’ici, semble-t-il, pratiqués à l’école maternelle. Leur pratique pourrait éventuellement développer la vision des lignes.

Un autre jeu de connexion est trax. Il se joue avec des pièces de forme carrée :

Le but du jeu est d’être le premier à faire un chemin suffisamment long, ou une boucle.

Il en est de même avec le jeu tantrix dont les dalles sont hexagonales :

Trax est annoncé pour des joueurs d’au moins 8 ans, Tantrix pour des joueurs d’au moins 6 ans. Autant dire que leur pratique à l’école maternelle n’est pas fréquente...

Voici un jeu de cartes pour Trax, à imprimer en noir et rouge :

Et voici un jeu de cartes pour Trantrix (un seul exemplaire de chaque carte par couple de joueurs) :

L’abeille et la chenille

Cette activité non plus n’a pas encore, semble-t-il, été expérimentée à l’école maternelle.

Le jeu de Hex est intéressant à jouer à tout âge, car

  • dès la petite section, il mobilise la phase de manipulation (placer les jetons au bon endroit, colorier correctement les sommets d’un graphe,
  • en grande section (voire avant) il mobilise la perception des lignes (chemin gagnant rouge ou bleu) ce qui pourrait constituer une aide à l’apprentissage de la lecture et du dessin par la suite,
  • il pose des questions (cruciales pour beaucoup d’enfants) sur l’équité, et mène à une réflexion intéressante sur la règle du gâteau (en ce sens il contribue à socialiser les élèves),
  • une partie de Hex ne dure pas très longtemps (c’est trouver qui a gagné, qui peut être plus long),
  • il familiarise avec la structure en nid d’abeille et le fait qu’un losange est un parallélogramme,
  • plus tard il permet de réaliser un projet électronique avec la machine de Shannon,
  • etc !

[1C’est peut-être sur les mêmes goban de Princeton, que par la suite, John Conway a inventé le football des philosophes.

[2voir le début du 3 page 6 (ou 822 sur le papier) de ce document.

[3dessinés sur alcoffeethmique avec ce script :

[4Là aussi, il y a une stratégie gagnante, mais elle est parfois pour le second joueur. Cela dépend de la parité du nombre de cases.


Commentaires