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 , mais on trouve aussi les valeurs 13 ou 19. L'un des inventeurs du jeu, John Nash, préconise un tablier de taille S. Nasar, A Beautiful Mind: A Biography of John Forbes Nash, Simon & Schuster (1998) .. Ce jeu possède des similarités avec le go.

Inventé par des mathématiciens, ce jeu 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 PolygoneT. Maarup, Hex par l'auteur d'une thèse sur le jeu de Hex...

En 1948, et de manière indépendante, un jeune mathématicien de l'université de Princeton du nom de John Nash réinvente le jeu et le diffuse au , une salle commune aux élèves et aux professeurs du département de mathématiques. Il en perçoit l'intérêt en théorie des jeux et démontre l'existence d'une stratégie gagnante pour le premier joueur. Cependant, sa preuve est non constructive, c’est-à-dire qu'elle n'indique pas de stratégie gagnanteCette preuve est rapportée pour la première fois par M. Gardner dansConcerning the game of hex, which may be played on the tiles of the bathroom floor, Scientific American vol. 197, (1957).. En 1952, la société Parker Brothers commercialise le jeu aux États-Unis.

Règles du jeu

thumb|left|Tablier de Hex 11×11. thumb|Configuration gagnante pour Bleu. Au début de partie, un tablier vide, illustré sur la figure de gauche, sépare deux joueurs. Ce tablier représente un losange formé par des hexagones réguliers. Chaque joueur est représenté par une couleur, bleu et rouge dans l'article, noir et blanc en général.

Les joueurs possèdent des pions à leur couleur qu'ils disposent tour à tour sur une case de leur choix et un par un. Le tablier se remplit ainsi progressivement. L'objectif d'un joueur, par exemple Bleu, est de relier les deux côtés opposés du losange symbolisés par la couleur bleue. Si la configuration des pions bleus permet la création d'une ligne continue (en blanc sur la figure) reliant un côté bleu à l'autre, Bleu a gagné et le jeu s'arrêteThe Rules of Hex, par l'université de Newcastle (Australie)..

Une règle supplémentaire, la règle du gâteau, est parfois appliquéeLa règle décrite ici est en vigueur sur le site de Hex game.wtanaka.com., en particulier lors des compétitions. Si Bleu commence, il joue le premier coup. Rouge a alors le choix entre jouer à son tour ou intervertir les couleurs. Dans le , le joueur qui a commencé devient Rouge et joue alors son premier coup en tant que Rouge, le jeu continuant ensuite normalement. Cela impose de jouer un premier coup ni trop fort (car il donnerait un avantage au joueur adverse qui se l'approprierait) ni trop faible (il serait alors laissé par l'adversaire) et réduit l'avantage de commencer.

Stratégie Un jeu de Hex est nécessairement fini. Dans la configuration illustrée sur les figures, il existe sur le tablier. Au bout de joués d'une part et de 60 de l'autre, le losange est rempli. La suite de l'article montre qu'indépendamment de la manière d'avoir joué, il existe toujours un vainqueur. Le match nul n'existe pas au Hex. La preuve de ce résultat est l'œuvre de NashV. V. Anshelevich, Hex information par le site International Computer Games association.. Pour contrebalancer l'avantage du premier joueur, on peut imaginer un tablier tel que les distances séparant les deux côtés opposés du losange ne soient pas égales. Il est alors simple de montrer que le joueur ayant la plus petite distance à parcourir gagne toujours, et cela indépendamment du fait qu'il commence ou nonB. Enderton, Answers to infrequently asked questions about the game of Hex par le site de Carnegie Mellon School of computer science..

Il existe de nombreux textes sur les différentes stratégies possibles pour gagnerVoir par exemple : R. Hayward, Berge and the art of Hex, University of Alberta.. Cependant les stratégies gagnantes ne sont connues que si le tablier est de dimension restreinte, c'est-à-dire jusqu'à . Une autre piste consiste à rechercher des heuristiques sur ordinateur pour jouer le mieux possible, sans rechercher des stratégies nécessairement gagnantes, procédant ainsi comme pour le jeu d'échecs, à l'aide de techniques de programmation issues de l'intelligence artificielleH. J. Van den Herik, J. W. H. M. Uterwijk et J. Van Rijswick, Games solved: Now and in the future, in (vol. 134), 2002, .. Ces programmes sont sources de versions électroniques du jeuUn jeu en ligne par R. Kirkland : Un jeu de Hex7 en ligne, par le site Web Mazeworks..

Variantes de Hex

Plusieurs variantes de Hex ont été étudiées. Notamment la variante Qui-perd-gagne est gagnante pour le premier joueur seulement si le tablier est de dimension paire., tandis que sur les variantes où le tablier est de taille infinie, une partie jouée parfaitement se solde par une partie nulle. Les variantes asymétriques où l'un des bords du tablier est plus long que l'autre voient quant à elle la victoire du joueur ayant à construire le chemin le plus court, qu'il ait commencé ou non.

Jeu de Hex et mathématiques Stratégie et théorie des jeux left|200px|thumb|Si les rouges ne jouent pas B1 à leur premier coup, ils ne peuvent éviter une défaite en trois coups. right|200px|thumb|Jouer B1 pour les rouges en deuxième coup ne fait que retarder d'un coup l'inévitable défaite. En théorie des jeux, le terme de stratégie possède une signification particulière. Une stratégie pour Bleu, s'il commence, indique le premier coup joué, puis le deuxième coup, en fonction du premier coup de Rouge, etc. Une stratégie gagnante assure la victoire quels que soient les choix que fait la partie adverse.

Illustrons ceci par un exemple sur un hex . Le tablier est numéroté de la manière indiquée sur la figure de gauche. Bleu commence et joue A3 (voir la figure de gauche). On suppose le coup B2 interdit pour commencer, sinon la victoire est trop aisée. Si Rouge ne joue, pour son premier coup, aucune des cases A1, B1 et A2, Bleu joue au deuxième tour A2. Il est alors à un coup de la victoire et il faudrait bloquer deux cases A1 et B1 pour l'en empêcher, ce qui est impossible à réaliser en un coup pour Rouge. Bleu a alors gagné. Le même raisonnement est réalisable sur les cases B1, C1 et B2 : si Rouge joue à son premier coup A1 ou A2, Bleu joue B2 et dispose encore d'une victoire assurée au troisième coup.

L'unique case à jouer en premier coup de Rouge, qui empêche la victoire en trois coups de Bleu, est B1, l'intersection des deux ensembles {A1, B1, A2} et {B1, C1, B2}. Dans ce cas, Bleu joue pour son deuxième coup C1, comme illustré sur la figure de droite. Rouge est maintenant menacé de défaite en un coup. S'il ne joue pas B2 en deuxième coup, Bleu joue B2 en troisième coup et a gagné. Si Rouge joue B2 pour le deuxième coup, Bleu joue C2 pour son troisième coup. Au prochain coup, les cases B3 et C3 lui assurent la victoire. Rouge ne peut bloquer en un unique coup deux cases, il a nécessairement perdu.

Éviter la défaite La première partie du raisonnement montre que le joueur qui commence (supposé Bleu dans cet article) dispose d'une stratégie évitant systématiquement la défaite. La démonstration proposée ici est dite par l'absurde. On suppose le résultat faux, c'est-à-dire que Rouge dispose d'une stratégie gagnante Sr. Bleu construit alors une stratégie Sb qui lui assure la victoire. La stratégie Sb montre que Sr, ne peut être gagnante (il faudrait qu'elle le soit quelle que soit la stratégie adverse). On en déduit que Rouge ne dispose pas d'une stratégie gagnante.

La stratégie Sb consiste à jouer un premier coup à vide, par exemple A1. Ensuite, Bleu voleLe terme « voler » correspond à une traduction de l'expression anglaise utilisée par Nash : T. Maarup, Hex, thèse de l'University of Southern Danemark (2005) . 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, donc de gagnerCet argument est détaillé de la thèse de T. Maarup, Everything You Always Wanted to Know About Hex But Were Afraid to Ask, University of Southern Denmark..

Assurer la victoire 250px|right 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 GaleCette preuve vient de ., un camarade de Nash à l'université de PrincetonT. Maarup, Everything You Always Wanted to Know About Hex But Were Afraid to Ask, University of Southern Denmark (2005).. 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 représentés en teintes claires 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.