Le jeu de Hex

Voulez-vous jouer à Polygon ? Piet Hein a inventé un jeu que les mordus du jeu d’échecs pratiqueront avec autant de plaisir que ceux qui savent tout juste tenir un crayon.

Ces lignes, parues dans le journal danois Politiken daté du 26 décembre 1942, marquent la naissance d’un jeu, qui sera plus tard popularisé sous le nom de Hex. Les règles sont en effet d’une simplicité enfantine. On joue à deux sur un plateau en forme de losange pavé par des hexagones. A tour de rôle, chaque joueur place un pion de sa couleur sur n’importe laquelle des cases encore libres. Deux des côtés opposés du plateau sont blancs et les deux autres noirs. Pour gagner, il faut relier les deux côtés à sa couleur par une chaîne ininterrompue de pions. On peut jouer sur des losanges de taille variable ; la récente édition du jeu par le Comité International des Jeux Mathématiques contient par exemple des plateaux de taille 9x9, 11x11, 14x14 et 19x19.
Les photos ci-dessous montrent les huit premiers coups d’une partie, et la situation finale après la victoire des blancs.

Comment gagner à Hex ?

On réalise vite qu’il n’est pas toujours judicieux de placer un nouveau pion juste à côté des pions précédents. Si deux pions blancs ont deux cases voisines vides en commun, comme sur la troisième photo ci-dessus, alors les noirs ne pourront pas empêcher la connexion. Une telle configuration s’appelle un maillon. Les maillons sont très efficaces pour former de longues chaînes : dans notre exemple, après le troisième coup des blancs, la connexion du pion central avec le bord blanc en bas à droite est assurée. En généralisant cette technique, on s’aperçoit assez facilement que les blancs (qui commencent le jeu) ont une façon de gagner immanquablement lorsque le plateau est de taille 4x4 ou 5x5. Une telle stratégie gagnante est détaillée dans le bloc dépliant qui suit.

Comment gagner sur un petit plateau

Sur un plateau 4x4, les blancs ont une stratégie gagnante qui commence en B3, à la suite de quoi les noirs ne peuvent empêcher les blancs de compléter l’un des chemins victorieux indiqués en pointillés. Les blancs procèdent de la façon suivante. A tout moment, si les noirs jouent dans l’une des deux cases rouges, les blancs répliquent dans l’autre case rouge, assurant ainsi la connexion avec le bord en bas à droite. Si les noirs jouent leur premier coup dans la zone verte, les blancs répondent dans la zone bleue, dans la case marquée d’une pastille blanche, ce qui assure la victoire par le principe des maillons. Inversement, si les noirs jouent dans la zone bleue, les blancs gagnent en jouant dans la zone verte.

Le principe est le même sur un plateau 5x5 : en jouant dans la case centrale C3, les blancs peuvent assurer leur connexion aux deux bords quoiqu’il arrive, grâce à des ensembles disjoints de cases dans lesquels ils peuvent, en un seul coup, sécuriser un chemin.

Jin Yang, informaticien à l’université du Manitoba au Canada, a réussi à détailler des stratégies gagnantes pour les blancs jusqu’à la taille 9x9, mais cette dernière requiert la description de 715 « tactiques locales ». Au delà, personne ne semble savoir comment gagner à coup sûr. Les parties sur un plateau de taille 19x19 sont souvent acharnées, et la chaîne qui finit par l’emporter aussi sinueuse que les méandres de la Seine... L’attrait du jeu réside dans ce contraste entre des règles simples et des stratégies complexes, que recherchait le mathématicien-poète Piet Hein lorsqu’il inventa le jeu.

Pourquoi la recherche d’une stratégie gagnante devient-elle si difficile à mesure que la taille du plateau augmente ? Intuitivement, ceci est dû à la croissance exponentielle du nombre de parties possibles. Pour décrire précisément la difficulté de ce type de problèmes, les informaticiens ont défini toute une hiérarchie de classes de complexités, dont la fameuse classe des problèmes NP.
Stefan Reisch a montré en 1981 que la recherche d’une stratégie gagnante pour le jeu de Hex sur un plateau de taille $n$ est au moins aussi difficile que tous les problèmes de la classe NP. Lorsque $n$ augmente, on conjecture que le temps de résolution nécessaire doit augmenter plus vite que toutes les puissances de $n$ ; c’est une conséquence de la célèbre conjecture « P $\neq$ NP ». En pratique, ceci signifie que vous ne pourrez pas programmer un ordinateur pour qu’il gagne à coup sûr avec les blancs sur un grand plateau si vous voulez qu’il ne mette pas des années avant de vous indiquer la case où il veut jouer.

Cette difficulté théorique n’empêche évidemment pas de concevoir des programmes pour jouer à Hex. Le programme Hexilla, disponible en ligne, utilise la règle d’échange décrite plus bas ; je n’ose avouer le nombre de parties que j’ai perdues contre lui...

Stratégies Gagnantes

Bien que personne ne sache comment faire pour gagner, on sait de façon certaine qu’il existe une stratégie gagnante pour les blancs, quelle que soit la taille du plateau. Si la phrase précédente peut paraître paradoxale, c’est parce que le raisonnement qui conduit à l’existence de cette stratégie gagnante est un raisonnement par l’absurde, qui n’est pas constructif. La partie la plus élégante du raisonnement, qu’on appelle le « vol de stratégie », est due au mathématicien John Nash. John Nash a ré-inventé le jeu de Hex, indépendamment de Piet Hein et quelques années après lui, comme le cadre idéal où appliquer ce type de raisonnement. L’argument du vol de stratégie permet de montrer que les noirs ne peuvent pas avoir de stratégie gagnante. Comme nous allons le voir, il repose fondamentalement sur le fait qu’à Hex, un pion n’est jamais handicapant pour celui qui l’a joué [1].

Supposons donc qu’il existe une stratégie gagnante pour les noirs. Cette stratégie gagnante peut être assimilée à un programme informatique qui gagne infailliblement lorsqu’il joue en second. Imaginons que je me sois procuré ce logiciel, que nous fassions une partie, vous et moi, et que je joue avec les blancs. J’aimerais m’aider du logiciel pour gagner, mais il ne sait jouer qu’avec les noirs ; comment faire ? L’idée est de faire jouer le logiciel à ma place, en lui faisant croire que j’ai les noirs. En pratique, je commence par échanger en deux coups de pinceau les couleurs blanches et noires sur les côtés du plateau de jeu (ça ne devrait pas vous déranger, le plateau étant symétrique). Je place ensuite mon premier pion n’importe où, et vous jouez à votre tour un pion noir. Je reproduis dans le logiciel votre premier coup, mais avec un pion blanc. L’ordinateur répond un coup pour les noirs, et je place sur le plateau un pion blanc sur la case correspondante. La partie se poursuit de cette façon, la situation sur le plateau étant reproduite à tout moment à l’écran avec une inversion des couleurs, et un pion en moins (celui que j’ai joué au tout début). Il peut arriver que le logiciel me demande justement de jouer sur la case occupée par mon premier pion, dont il ignore l’existence : dans ce cas, je place un nouveau pion sur n’importe quelle case libre du plateau. Au bout d’un certain temps mon logiciel finit par annoncer qu’il a gagné (vous vous souvenez, il gagne toujours) : sur le plateau affiché à l’écran, je vois une chaîne de pions noirs qui relie les deux côtés noirs. Sur le vrai plateau, je vois la même configuration avec les couleurs inversées, et un pion blanc en plus quelque part. Il y a donc une chaîne de pions blancs qui relie les deux côtés blancs : j’ai gagné.

Autrement dit, à l’aide d’un logiciel gagnant immanquablement avec les noirs, on pourrait fabriquer un autre logiciel qui gagnerait immanquablement avec les blancs. Ceci
est bien sûr impossible : si l’on faisait jouer ces deux programmes l’un contre l’autre, tous deux devraient gagner. Nous avons montré par l’absurde qu’il n’existe pas de stratégie gagnante pour les noirs.

Peut-on vraiment en déduire que les blancs en ont une ? Oui, essentiellement parce qu’il ne peut pas y avoir de partie nulle. L’impossibilité d’une partie nulle est presque évidente : comment les noirs peuvent-ils barrer le chemin aux blancs autrement qu’en formant une chaîne continue de pions reliant les côtés noirs ? Voici un argument (un peu) plus précis.
Une partie nulle ne pourrait arriver qu’avec un plateau dont toutes les cases sont occupées par des pions, comme sur cet exemple.

Il s’agit donc de montrer que lorsque toutes les cases sont occupées, il y a forcément un chemin de pions blancs reliant les deux côtés blancs ou un chemin de pions noirs reliant les deux côtés noirs.
Pour voir ceci, on considère l’ensemble $B$ des cases de pions blancs reliés au côté blanc en haut à gauche par un chemin de pions blancs (les mathématiciens parleraient d’une « composante connexe » de l’ensemble des pions blancs). Si l’un des pions de $B$ touche l’autre côté blanc, les blancs ont gagné. Sinon, l’ensemble $B$ est bordé par un chemin de pions noirs reliant les deux côtés noirs, et les noirs ont gagné. Nous avons ainsi démontré qu’il n’y a pas de partie nulle à Hex, et on peut en déduire qu’une stratégie gagnante doit exister pour l’un ou l’autre des deux joueurs. L’argument du vol de stratégie a montré qu’il n’en existe pas pour les noirs, on conclut que les blancs possèdent une stratégie gagnante.

Lorsque la taille du plateau est supérieure à 9x9, on ne sait presque rien dire de cette stratégie gagnante des blancs. En raffinant l’argument du vol de stratégie, Anatole Beck a montré qu’aucune stratégie gagnante des blancs ne commence par la case A1 située à l’angle aigu du jeu [2]. Le raisonnement est très élégant mais l’information est d’une bien maigre utilité pratique !

En l’absence de partie nulle, l’un ou l’autre des deux joueurs a une stratégie gagnante. Cette affirmation paraît probablement très raisonnable au lecteur, ou peut-être pas : les lecteurs ne sont pas tous identiques ! En tout cas, on peut l’etayer en donnant quelques détails : c’est l’objet de notre deuxième bloc dépliant.

Stratégies gagnantes et arbre du jeu

Les mathématiciens aiment modéliser le jeu de Hex sous la forme d’un arbre représentant toutes les parties possibles. L’arbre commence avec la position initiale, un plateau vide. De cette racine partent autant de branches qu’il y a de possibilités pour le premier coup du premier joueur, et chaque branche aboutit à un noeud de l’arbre représentant la position obtenue, le plateau contenant un unique pion blanc. De chacun de ces noeuds partent à nouveau autant de branches que de réponses possibles pour le second joueur, et ainsi de suite. La figure ci-dessous représente l’arbre des parties pour le jeu de Hex 2x2. Cette taille de plateau est bien sûr particulièrement inintéressante à jouer, et cependant l’arbre occupe déjà une place respectable avec ses 52 branches ! Pour les plateaux plus grands on ne peut pas vraiment dessiner l’arbre sur une feuille de papier, il s’agit plutôt d’un objet abstrait qui est utile pour le raisonnement.

L’arbre va nous aider à nous convaincre qu’il y a bien une stratégie gagnante pour l’un ou l’autre des deux joueurs (sans nous dire lequel : cette partie du travail incombe à l’argument du « vol de stratégie » raconté plus haut). Le principe consiste à colorier tous les noeuds de l’arbre en blanc ou en noir, chaque noeud colorié correspondant à une position à partir de laquelle le joueur de la couleur correspondante possède une stratégie gagnante.

 L’arbre se termine par des noeuds d’où ne partent aucune branche, qu’on appelle des feuilles ; chaque feuille représente une fin de jeu, avec la victoire de l’un des deux joueurs, puisqu’il n’y a pas de partie nulle possible. Nous commençons par colorier en blanc les feuilles représentant une fin de partie gagnée par les blancs, en noir celles correspondant à la victoire du joueur noir.

Le reste du coloriage se fait progressivement. À un moment donné, on veut attribuer une couleur à un noeud qui n’en a pas encore, mais dont toutes les branches descendantes mènent à des noeuds déjà coloriés. Supposons que ce noeud représente une position à partir de laquelle c’est aux blancs de jouer. Si l’une au moins des branches issues du noeud mène à un noeud blanc, alors on colorie le noeud en blanc. Dans le cas contraire, c’est-à-dire si toutes les branches mènent à des noeuds coloriés en noir, on le colorie en noir. On procède de façon symétrique si c’est aux noirs de jouer.
De proche en proche, on colorie ainsi tous les noeuds de l’arbre, jusqu’à la racine représentant la position initiale. Si celle-ci est finalement coloriée en blanc, le mode de coloriage utilisé assure que le joueur blanc pourra à chaque coup emprunter une branche menant à un noeud blanc, et que le joueur noir, au contraire, n’aura jamais le choix qu’entre des branches menant toutes à un noeud blanc. Ainsi, la stratégie des blancs consistant à rester sur les noeuds blancs est possible et gagnante. Si la racine est noire, par contre, ce sont les noirs qui ont une stratégie gagnante.

Variantes

Puisque les blancs ont un avantage, au moins théorique, il est tentant d’amender les règles pour réduire cet avantage, et de nombreuses variantes du jeu ont ainsi vu le jour. La règle d’échange est l’une des plus intéressantes : selon cette variante, après le premier coup des blancs, le deuxième joueur a la possibilité d’échanger les couleurs (le mieux pour bien comprendre est d’essayer ici). Cette règle incite donc les blancs à éviter un premier coup trop avantageux, comme de jouer au centre, puisque l’échange des couleurs permet alors au second joueur de détourner cet avantage à son profit. Au plan théorique, cette variante renverse la situation : ce sont maintenant les noirs qui ont une stratégie gagnante...

Une deuxième variante interdit au premier joueur de poser son premier pion sur la case centrale. Ceci n’empêche pas l’un ou l’autre des deux joueurs d’avoir une stratégie gagnante, mais cette fois-ci l’argument du vol de stratégie échoue, et nul ne sait si cette stratégie est au bénéfice des blancs ou des noirs !

L’impossibilité d’une partie nulle dans le jeu sans variante correspond à un théorème de topologie combinatoire du plan. Certaines variantes sont basées sur d’autres résultats topologiques. Claude Shannon a ainsi imaginé un plateau triangulaire, toujours pavé par des hexagones, le but de chaque joueur étant de relier les trois côtés par un ensemble connexe de pions à sa couleurs ; cette variante a été baptisée « Y », et les parties nulles y sont tout aussi impossibles.
On pourrait aussi imaginer un jeu torique, basé sur le fait que deux courbes qui font le tour de la surface d’une bouée, l’une dans le sens vertical et l’autre dans le sens horizontal, doivent nécessairement se rencontrer.

Terminons par une variante en forme d’énigme, à nouveau basée sur une idée de Claude Shannon. Je prétends que sur le plateau suivant, les noirs ont une stratégie gagnante particulièrement simple.

L’énigme est double, la première partie, la plus simple, consistant à découvrir en quoi le jeu est différent du jeu de base. La seconde partie est, au choix, un exercice purement intellectuel, ou bien une énigme à résoudre sur le Net en utilisant les moteurs de recherche...

Références

• Martin Gardner, The Game of Hex, initialement paru en 1959 dans Scientific American. Ré-édité dans
  Hexaflexagons, probability paradoxes, and the Tower of Hanoi : Martin Gardner’s first book of mathematical puzzles and games. Cambridge University Press, 2008. L’article qui a popularisé le jeu en dehors du Danemark.

• Anatole Beck, The Game of Hex, dans Excursions in Mathematics, ed. Anatole Beck, Michael Bleicher and Donald Crowe. Worth, 1969. Ré-édition : A. K. Peters, the Millenium edition, 2000.

• Stefan Reisch. Hex ist PSPACE-vollständig. Acta Informatica, 15:167–
  191, 1981.

• Jing Yang. Hex 9x9 solution, 2003. La page web de Jing Yang a disparu, et cet article ne semble pas être disponible sur internet.

• Thomas Maarup, Hex : Everything You Always Wanted to Know About Hex But Were Afraid to Ask, mémoire de Master au Department
  of Mathematics and Computer Science, University of Southern Denmark, 2005. Une mine d’informations.

• Broderick Arneson, Ryan B. Hayward, Philip Henderson, Solving Hex : beyond human. 7th International Conference on Computers and Games, 2011.
  « Solving Hex » (« Résoudre Hex ») signifie ici décrire toutes les ouvertures qui font partie d’une stratégie gagnante. L’ordinateur met 31 heures à résoudre le jeu de Hex 8x8, et résout partiellement le jeu 9x9 après plusieurs dizaines de jours de calculs.

• Livret du jeu de Hex édité par le CIJM, 2011. Très bien fichu...

• Garikai Campbell, The game of Hex. On y trouve notamment l’explication des stratégies gagnantes en 4x4 et 5x5.