Hex

Le jeu de Hex est un jeu de société combinatoire abstrait pour deux joueurs. Il se joue sur un tablier en forme de losange dont les cases sont hexagonales. Toutes les dimensions du côté du losange sont possibles, la plus traditionnelle est celle composée par 11 hexagones, mais on trouve aussi les valeurs 13 ou 19. L'un des inventeurs du jeu, John Nash, préconise un tablier de taille 14 × 14. Ce jeu possède des similarités avec le go.

Ce jeu, inventé par des mathématiciens fait uniquement appel à la logique, à l'image du go ou des échecs. Son étude est source d'inspiration, non seulement en théorie des jeux, mais aussi pour d'autres branches des mathématiques comme la topologie ou la géométrie algébrique.

Si l'on sait qu'il existe une stratégie gagnante pour le premier joueur, cette stratégie est inconnue si le tablier n'est pas de petite taille (de côté strictement plus petit que 9). La recherche de stratégies efficaces, à défaut d'une stratégie gagnante, est l'objet d'études en intelligence artificielle.

Histoire 
Le premier énoncé de la règle du jeu est l'œuvre de Piet Hein lors d'une conférence en 1942 au Parenthesis, l'association des mathématiciens de l'Université de Copenhague. L'auteur cherchait alors à imaginer un jeu équitable, progressif, fini, clair, stratégique et décisif. Le jeu porte alors le nom de Polygone la stratégie Sr, en oubliant qu'il a commencé et joué A1. Le deuxième coup de Bleu est donc le premier coup de la stratégie Sr après celui qu'a joué Rouge. Bleu prolonge cette stratégie jusqu'au moment éventuel où il est amené à jouer A1. Il joue alors n'importe quoi, noté α. Il imagine alors que le premier coup oublié était α et qu'il vient de jouer A1. Bleu n'a pas quitté le scénario Sb, consistant à voler la stratégie gagnante. Comme Sr est une stratégie gagnante, la victoire est assurée pour Bleu.

Un tel raisonnement montre qu'une stratégie gagnante Sr ne peut exister. Ce qui montre que quelle que soit la stratégie de Rouge, il est possible pour Bleu d'éviter la défaite, et donc de gagner.

Assurer la victoire 

Le paragraphe précédent est un raisonnement de Nash. En 1948, il avait aussi montré l'existence d'une stratégie gagnante pour Bleu. La démonstration proposée ici n'est néanmoins pas de lui mais de David Gale, un camarade de Nash à l'université de Princeton. Elle possède l'avantage d'être plus simple.

On suppose maintenant que Bleu suit la stratégie Sd. Une fois la partie finie, si le tablier n'est pas entièrement recouvert de pions, l'un des adversaires a nécessairement gagné. Comme cela ne peut être Rouge, c'est Bleu et le résultat est démontré. Sinon, le tablier est entièrement recouvert de pions bleus et rouges et une fois encore, Bleu a nécessairement gagné la partie. Pour s'en rendre compte, on ajoute à chacun des quatre côtés du tablier, un jeu d'hexagones, de la couleur de son joueur. Ces hexagones sont illustrés en clairs sur la figure de droite. Les quatre sommets du nouveau losange sont notés A, B, C et D. Le principe est de construire une ligne, illustrée en vert sur la figure, qui montre la victoire de Bleu. Cette ligne démarre au sommet A, et plus exactement au sommet P1 commun uniquement à deux hexagones ajoutés et de couleurs distinctes.

La ligne verte suit l'arête partagée par deux hexagones de couleurs distinctes. Elle se termine sur un autre sommet P2. On prolonge cette ligne par une nouvelle arête, différente de P1P2 et une fois encore partagée par deux hexagones de couleurs distinctes. On remarque qu'il n'existe qu'un unique choix possible. On répète alors cette même démarche, jusqu'à ce que cela ne soit plus possible.

Cette ligne verte dispose de quatre propriétés qui montrent la victoire de Bleu. Il est impossible à la ligne verte de faire une boucle, un sommet ne peut être atteint qu'une unique fois par la ligne verte. Le seul motif d'arrêt est que la ligne verte a atteint un sommet extérieur, commun à deux hexagones ajoutés (en clairs sur la figure). Ces deux hexagones sont nécessairement de couleurs différentes, c'est-à-dire qu'ils se trouvent sur un sommet du losange. Comme le sommet A est déjà pris, cette fin se situe sur l'un des sommets B, C ou D. Si l'on parcourt la ligne verte, depuis A jusqu'à sa fin, sur la proximité droite de la ligne, on ne trouve que des hexagones bleus (clairs ou foncés). Sur la proximité gauche, on ne trouve que des hexagones rouges. Cette propriété est illustrée sur la figure.

On suppose que le sommet atteint finalement par la ligne verte est celui noté D. Considérons une deuxième ligne rejoignant par des segments les centres des hexagones constituant le flanc droit de la ligne verte. Cette ligne est intégralement dans la zone bleue. Elle démarre dans la zone bleu clair située entre A et B et finit encore dans le camp bleu, mais cette fois dans la zone claire située entre C et D. Considérons la portion de cette ligne comprise entre le dernier hexagone bleu clair situé entre A et B et le premier hexagone bleu clair situé entre C et D. Cette portion de ligne est illustrée en blanc. Elle est la preuve que Bleu a gagné.

Si d'aventure, la ligne verte se termine sur le sommet B, le même raisonnement que le précédent montre que Rouge a gagné la partie. Cette configuration est impossible avec la stratégie choisie. Cela permet néanmoins de démontrer un résultat un peu plus fort que celui annoncé en début de paragraphe. Si les stratégies de Rouge et Bleu sont quelconques, il existe toujours un vainqueur. Autrement dit, le nul n'existe pas au Hex.

Le sommet C ne peut être atteint par la ligne verte. Pour s'en rendre compte, il suffit d'imaginer que l'hexagone du tablier connexe au sommet C est bleu foncé, illustré sur la figure de gauche. Cet hexagone est nécessairement à gauche de la ligne verte (parcourue dans le sens A vers C), ce qui est impossible car les hexagones situés à gauche de la ligne sont tous rouges. Si le même hexagone est rouge foncé, il est à droite de la ligne verte, ce qui est encore impossible.

Cette démonstration termine la preuve du fait qu'il existe nécessairement une stratégie gagnante pour le premier joueur. En revanche, comme elle utilise un raisonnement par l'absurde, elle ne décrit pas directement de manière de s'y prendre pour effectivement jouer et toujours gagner si l'on commence. Nash exprimait cette idée à D. Gale en 1948 qui le rapporte ainsi : . Il s'avère en fait que le jeu est PSPACE-complet, ce qui modulo certaines hypothèses de théorie de la complexité, signifie que de toute façon la recherche d'une stratégie gagnante devient très rapidement impraticable quand la taille du jeu augmente.

Autres champs mathématiques 
Le jeu de Hex est source de démonstrations dans des branches mathématiques éloignées de la théorie des jeux. Le théorème du point fixe de Brouwer indique qu'une fonction continue d'un disque dans lui-même possède toujours un point fixe. Ce résultat se généralise aux dimensions supérieures. Autrement dit, quand on remue son café, il existe toujours un point de la surface qui n'a pas quitté sa position initiale. La démonstration de l'absence de possibilité d'un match nul au jeu de hex est une manière élégante de prouver ce résultat, ce qui constitue l'objet de l'article de David Gale de 1979. Pour être plus précis, ce que David Gale appelle le théorème du jeu de Hex et qui indique l'absence de possible match nul est un résultat équivalent au théorème du point fixe de Brouwer.

Ce théorème a des conséquences amusantes en topologie algébrique, puisqu'on peut l'utiliser pour démontrer le théorème de Jordan, qui indique qu'un lacet simple dans le plan, c'est-à-dire une boucle sans point double, divise l'espace en deux parties connexes, celle intérieure à la boucle qui est bornée et celle extérieure qui ne l'est pas. Ce théorème intuitivement évident est difficile à démontrer rigoureusement. Une conséquence de ce théorème est celui de Poincaré-Bendixson, qui indique qu'une équation différentielle autonome définie par une fonction dérivable à valeurs dans un plan ne peut engendrer de situation chaotique. Cela implique que si un étang est parcouru par un courant qui ne varie pas au cours du temps, un bouchon flottant sur cet étang finit par s'immobiliser ou tourner indéfiniment dans un tourbillon.

Annexes

Notes et références

Bibliographie 
  C. Browne, Hex Strategy—Making the Right Connections, A. K. Peters, 2000

Liens externes 

 T. Maarup Everything You Always Wanted to Know About Hex But Were Afraid to Ask University of Southern Denmark
 Un wiki dédié au Hex.
 Little Golem un site où l'on peut jouer par correspondance au Hex ainsi qu'à d'autres jeux (go, échecs…)
 R. Kirkland ''Un jeu de Hex7 en ligne par le site Mazeworks
 Étude sur le jeu d'hex Une approche mathématique par Edouard Rodrigues
Hexy programme à télécharger permettant de jouer contre l'ordinateur sous Windows (4 niveaux de difficulté).

Jeu de société
Jeu de stratégie combinatoire abstrait
Jeu par arrangement
Jeu mathématique
Jeu de papier et crayon
Jeu de connexion