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.

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 :

Les bleus (CE1) ayant déjà réussi un alignement allant du bleu au bleu ont déjà gagné :

Mais aucun des deux joueurs ne s’en est rendu compte, aussi entendent-ils continuer à jouer :

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.

Le réflexe des rouges était de créer un alignement de rouges parallèle à la ligne bleue, ce qui est perdant (une ligne rouge allant du bleu au bleu n’est pas gagnante). Après ça, les joueurs créent spontanément une diagonale à couleurs alternées, puis des diagonales de couleurs unies :

Ils continuent à jouer jusqu’à remplissage du plateau :

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 bleus.

Cela montre que les bleus 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 :

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 au 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é.

Comme on l’a vu, la perception des lignes n’est pas encore assez performante en petite section, pour permettre aux élèves de savoir qui a gagné. Ils jouent donc au hasard et à la fin, c’est à quelqu’un de plus âgé qu’eux, de dire qui a gagné. Mais ils adorent adouber (échecs), c’est-à-dire dans le cas présent, replacer bien au centre de l’hexagone, un jeton décalé. On le voit sur l’animation ci-dessus, l’adoubement ayant lieu par les rouges (PS) alors même que les bleus (CE1) sont en train de jouer le coup suivant.

On voit sur cet exemple la volonté de faire un alignement, les bleus essayant de créer une ligne bleue :

Mais celle-ci allant d’un bord rouge à l’autre bord rouge, ne peut être gagnante pour les bleus. De fait ce sont les rouges qui ont gagné :

Voici un autre exemple de partie, jouée entre les rouges (PS) et les bleus (CE1) :

Les bleus ont joué en premier :

Les rouges réussissent à compléter une ligne, mais celle-ci joint un bord rouge et un bord bleu :

Les bleus aussi ont réussi à compléter une ligne mais celle-ci joint deux bords rouges :

Pendant ce temps les rouges ont réussi à compléter une deuxième ligne (toujours joignant un bord bleu à un bord rouge).

Les bleus essayent ensuite de compléter une diagonale bleue (qui est gagnante). Mais les rouges interrompent cette ligne bleue en y insérant un jeton rouge.

Alors les bleus trichent en déplaçant ce jeton rouge discrètement dans un coin pour insérer à la place un jeton bleu :

C’est d’autant plus surprenant que les bleus avaient un coup gagnant en plaçant un jeton à droite de ce jeton rouge.

Au final les bleus ont gagné en trichant :

La version avec crayons de couleur (un rouge, un bleu) présente l’avantage d’interdire cette façon de tricher, en plus d’assurer une certaine pérennité à la partie : elle permet de reporter à un autre jour (ou à une autre classe) la question de savoir qui avait gagné. Il suffit pour cela de noter en rouge et en bleu les prénoms des deux joueurs, avant même qu’ils jouent (sauf s’ils appliquent la règle du gâteau).

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 :

Mais en imaginant chacune des arêtes du graphe ci-dessus comme une résistance électrique (de 2,2 kΩ), on peut construire une copie du graphe sous forme de réseau électronique :

Les sommets du graphe sont des prises. Jouer consiste, pour les bleus, à brancher dans une prise libre de son choix, un câble noir. Il y en a 3 déjà branchés ci-dessus. Si les rouges essayent de jouer systématiquement en branchant un câble rouge dans la prise de plus petit potentiel (ci-dessus, 1,8 V) alors cela les amène à créer une ligne rouge allant du noir au noir (ou du bleu au bleu).

Si par contre les rouges jouent le potentiel le plus élevé (ci-dessous 2,28 V) ils peuvent gagner :

Mais ce n’est pas là la stratégie décrite par Nash à propos de Shannon : on cherche à minimiser le potentiel sur une ligne passant par le sommet de potentiel maximum. Et là, au premier essai, les noirs (joués par la machine) gagnent :

Voici une variante du jeu à 5×5 cases (ci-dessous, l’original) :

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 ?

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) :

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