Le jeu de Hex se joue à deux sur un tablier en forme de losange dont les cases sont hexagonales. Chaque paire de côtés opposés du losange est identifiée à une couleur. À tour de rôle, BLEU et ROUGE colorent une case de leur couleur. Le but du jeu est de joindre les deux côtés opposés de leur couleur par une chaîne de cases colorées adjacentes de la même couleur.
Le jeu de Hex a été introduit indépendamment par deux mathématiciens, une première fois par Piet Hein en 1942, et une deuxième fois par John Nash1 en 1947.
Voici un tablier de jeu de Hex. Les cases colorées ne font pas partie du jeu. Elles servent à identifier la couleur des côtés opposés du losange. Le losange peut être arbitrairement grand. Dans la figure il a 6 × 6 = 36 cases.
BLEU et ROUGE jouent à tour de rôle et colorent une case de leur couleur et BLEU commence. Voici une partie où BLEU gagne après avoir joué 12 coups.
Et voici une partie où ROUGE gagne après avoir joué 12 coups.
Bien sûr, après un nombre fini de coups toutes les cases sont rouges ou bleues.
Peut-on avoir une partie nulle ?
John Nash a montré que non : soit BLEU, soit ROUGE gagne à chaque partie.
Remarquons que tant que personne n’a gagné, BLEU et ROUGE continuent de jouer jusqu’à remplir toutes les cases. Supposons que BLEU n’ait pas gagné. Intuitivement, c’est parce que ROUGE lui a barré le chemin d’un côté à l’autre du tablier. C’est cette barrière qui garantit que ROUGE a alors gagné. Dans l’encadré, on explique comment écrire rigoureusement cette idée.
Il n’y a pas de partie nulle
Regardons les flèches d’entrée et de sortie sur la figure. Elles sont orientées pour que le bleu se trouve du côté gauche.
Rentrons par la flèche inférieure et continuons le chemin le long des arêtes en laissant toujours le bleu à gauche et le rouge à droite. Il n’y a qu’une seule manière de le faire.
Ce chemin ne peut pas avoir d’auto-intersection, ni faire une boucle car il est ouvert à une extrémité. Donc, il doit ressortir par une des deux sorties du tablier. Sur la figure ci-dessus il sort à droite. À gauche du chemin se trouve une trajectoire qui montre que BLEU a gagné.
L’autre possibilité est que le chemin ressorte à gauche (figure ci-dessous).
C’est maintenant à droite du chemin qu’on trouve une trajectoire qui montre que ROUGE a gagné.
Y a-t-il une stratégie gagnante ?
Y a-t-il un avantage pour BLEU ou pour ROUGE?
Aussi, rappelons que le tablier peut être arbitrairement grand. S’il y a un avantage, est-il toujours du même côté ? Ou bien dépend-il de la taille du tablier ?
John Nash a montré que BLEU a une stratégie gagnante. Ce qui veut dire que si BLEU ne commet pas d’erreur, BLEU gagne toujours. Pourtant, la stratégie gagnante est inconnue dès que le tablier est plus grand que 9 × 9.
Comment est-ce possible ? C’est que la preuve de Nash est existentielle : John Nash a montré qu’il existe une stratégie gagnante pour BLEU. Pour cela, il suppose qu’il n’en existe pas. Ceci signifie que, quoi que joue BLEU, ROUGE va pouvoir répliquer et gagner. Donc, cela veut dire que ROUGE a une stratégie gagnante. Et John Nash en déduit une contradiction. C’est ce qu’on appelle une preuve par l’absurde, elle ne nous apprend rien sur la stratégie. Le détail de l’argument se retrouve dans l’encadré.
BLEU a une stratégie gagnante
Supposons que BLEU n’ait pas de stratégie gagnante. Cela veut dire que ROUGE qui joue en second a une stratégie gagnante appelée \(S_R\). Remarquons qu’on peut interchanger les couleurs ROUGE et BLEU. Et alors, cette stratégie gagnante de \(S_R\) donne une stratégie gagnante \(S_B\) pour BLEU si c’est ROUGE qui commence. Cette stratégie \(S_B\) signifie que si ROUGE commence et si BLEU réplique à chaque coup de ROUGE par la stratégie \(S_B\), alors BLEU va construire une trajectoire bleue qui traverse le tablier.
Au premier coup, BLEU joue n’importe quelle case, appelée \(A_1\). Ensuite ROUGE joue son premier coup selon \(S_R\). À chaque coup de ROUGE selon \(S_R\), BLEU réplique par la stratégie \(S_B\). Si la stratégie \(S_B\) commandait de jouer \(A_1\), alors BLEU joue n’importe quelle case vide, appelée \(A_2\). Etc.
Donc, en pratique, toutes les cases que la stratégie \(S_B\) commandait de colorer en bleu seront bleues. Et ces cases donnent une trajectoire gagnante pour BLEU et forment une barrière empêchant ROUGE de gagner.
Contradiction avec l’hypothèse que ROUGE a une stratégie gagnante. Donc, BLEU a une stratégie gagnante.
On voit bien que cette preuve ne nous apprend rien de la stratégie gagnante pour BLEU.
- John Nash (1928-2015) s’est mérité le prix Nobel d’économie en 1994 pour ses contributions à la théorie des jeux. ↩