Analyse du Jeu de Rex

Analyse du Jeu de Rex

L’objet de cette analyse est de donner la solution du Jeu de Rex (Jeu d’Hex à qui perd gagne) pour un Hexiquier H n, quelle que soit la valeur de l’ordre n de l’hexiquier.

Cette étude a été réalisée en utilisant des notions très simples de la théorie des graphes, ce qui n’aurait certainement pas déplu à Claude Berge. Elle nous a permis de mettre en évidence 2 types de solutions. La première solution, solution géométrique, déjà connue mais n’utilisant pas la théorie des graphes, permet de donner la solution des hexiquiers H n, n inférieur ou égal à 5, sans permettre cependant de faire une analyse exhaustive de ces hexiquiers. On notera ici que jusqu’à présent personne n’a donné la solution du Jeu de Rex pour des hexiquiers H n, n supérieur à 5. La seconde solution, solution analytique, que nous avons créée, permet de donner la solution des hexiquiers H n, n supérieur ou égal à 2.

Les graphes que nous utilisons peuvent être répartis en 2 groupes. Les graphes fermés, qui sont une généralisation des solutions utilisées pour les hexiquiers H n , n inférieur ou égal à 5, et les graphes ouverts, que nous avons créés pour résoudre à la main le Jeu de Rex pour un hexiquier H n , n supérieur ou égal à 2. On notera que sans les graphes ouverts il n’aurait pas été possible de résoudre le Jeu de Rex. Tous les graphes fermés sont créés à partir d’une même définition. Il en est de même pour tous les graphes ouverts. Il a par conséquent été possible de les analyser grâce à une même technique de gain, ce qui a permis de les analyser une fois pour toutes.

Ainsi que nous l’avons fait pour le Jeu d’Hex nous avons commencé par définir quelques positions types pour le Jeu de Rex.

La méthode d’analyse que nous utilisons est la même que celle que nous avons créée pour le Jeu d’Hex, à savoir : on analyse un seul coup du camp qui gagne, chaque fois qu’il a le trait, et tous les coups du camp qui perd, chaque fois qu’il a le trait. De plus on arrête l’analyse d’une ligne de jeu dès que le dernier coup du camp qui perd permet de créer un graphe fermé ou ouvert, car nous savons que dans ce cas le reste de l’analyse n’est plus qu’une affaire de technique.

Pour un hexiquier H n la stratégie de gain du camp qui gagne est simple. Il ne doit jouer que sur la couronne comprise entre l’hexiquier H n et l’hexiquier H n-2 situé en son centre. Bien évidemment chaque coup du camp qui gagne doit lui permettre de créer une position gagnante, quel que soit le coup que vient de jouer le camp qui perd, c’est-à-dire une position qui, tôt ou tard, permet de créer un graphe fermé ou ouvert.

Nous montrons que lorsque les 2 camps ont occupé toutes les cases de la couronne (H n – H n-2) les Blancs, avec le trait, doivent jouer les premiers sur l’hexiquier central H n-2. Si on a déjà fait une analyse exhaustive de cet hexiquier central l’analyse de l’hexiquier H n est alors terminée.

Il n’y a pas à imaginer des stratégies et des tactiques pour le camp qui perd puisque l’on analyse tous ses coups possibles chaque fois qu’il a le trait. En revanche nous montrons que le camp qui gagne doit choisir avec le plus grand soin les coups qu’il joue sur les 2 colonnes (rangées) extrêmes ainsi que sur certaines cases des 2 rangées (colonnes) extrêmes si ce camp est celui qui joue avec les pions blancs (noirs) s’il ne veut pas être contraint de jouer sur l’hexiquier central H n-2. Si un tel cas se présente au cours d’une analyse c’est la preuve que le camp qui gagne a commis une faute en jouant un de ses précédents coups qu’il doit alors corriger.

Les meilleurs coups du camp qui perd résultent directement de la méthode d’analyse. Pour le camp qui gagne la situation est différente. Puisqu’à la fin d’une partie toutes les cases de l’hexiquier sont couvertes de pions il serait erroné de conclure pue tous les coups du camp qui gagne sont équivalents. Nous rappelons en effet qu’il est possible d’arrêter l’analyse d’une ligne de jeu dès qu’un graphe fermé ou ouvert est créé. Par conséquent il est possible de dire qu’un coup du camp qui gagne est meilleur qu’un autre coup s’il conduit à la création d’un graphe fermé ou ouvert en un plus petit nombre de coups.

Grace à la solution analytique nous avons pu faire une analyse exhaustive des hexiquiers Hn, n inférieur ou égal à 5 ; puis pour l’hexiquier H6 , une analyse exhaustive de la position obtenue après 1. (6,1)
[Nous donnons en annexe l’analyse exhaustive de la variante 1 (6,1), (1,6)] ; ensuite, pour l’hexiquier H7, une analyse exhaustive des positions obtenues après les premiers coups 1. (4,3) ; 1. (4,4) ; 1. (5,3) ; 1. (5,4) ; 1. (3,3) et 1. (2,2) ; enfin pour l’hexiquier H8 nous donnons en annexe une analyse de la position obtenue après 1. (8,1), (4,4), analyse que nous avons arrêtée dès qu’elle nous a paru suffisamment avancée pour permettre de comprendre comment on résout les quelques difficultés qui peuvent se présenter.

Remarquons enfin que les analyses qui précèdent prouvent bien que pour un hexiquier Hn , d’ordre n pair, les Blancs gagnent et que pour un hexiquier H n , d’ordre n impair, les Noirs gagnent.

De même que pour le Jeu d’Hex, la solution de l’hexiquier H n, n supérieur ou égal à 6, s’obtient à partir des hexiquiers

H n-1 , H n-2 , …… , H8 et H 6.

Après avoir résolu à la main le Jeu d’Hex, problème NP complet, nous venons de résoudre à la main le Jeu de Rex dont, à notre connaissance, le degré de complexité n’a pas encore été étudié. Nous estimons cependant que ce degré de complexité est supérieur à celui du Jeu d’Hex.

Qu’il nous soit permis de reposer la question : n’aurait –on pas l’égalité P=NP ?

Accédez aux études: