|
| Questions sur le jeu de HEX (Mathématiques et Deep Learning) par Julo62 le
[Aller à la fin] |
| Informatique | |
J'ai découvert, récemment le jeu de HEX.
https://fr.wikipedia.org/wiki/Hex
Rapidement, au sujet du jeu :
- Le jeu se joue sur un plateau en losange composé d’hexagones (d'où le nom, hihi!).
- Blancs et Noirs jouent alternativement en posant un pion sur une case vide.
(Les joueurs disposent de suffisamment de pions pour remplir complètement le plateau.)
- Blanc débute la partie.
- Un pion, une fois placé sur le plateau ne bougera plus et ne pourra être pris.
L'objectif est de relier par une série de pions, dans des hexagones contigus, 2 côtés opposés du losange.
Chaque joueur a comme objectif l'une des deux paires de côtés opposés.
Particularités :
De prime abord, les distances sur le plateau sont "inégales" :
De part la composition du plateau il n'y a pas équidistance entre 2 angles opposés.
Pour un losange composé de 2x2 = 4 hexagones, on a 2 angles contigus, et 2 angles séparés par 1 case.
On a donc 4 cases (chacune formant 1 des angles), 2 sont contiguës des 3 autres cases, et les 2 autres ne sont contiguës que de 2 autres cases...
Le jeu ne peut se finir par un résultat nul.
Dans le cas d'un losange composé de 2x2 = 4 losanges, on se rend compte, facilement, que Blanc, s'il pose un pion sur 1 des cases contiguës des 3 autres, Noirs ne peut pas l'empêcher de gagner au coup suivant.
On peut aussi se rendre compte facilement que :
- Avec un losange de 3x3 = 9 hexagones, contrairement au jeu du morpion, en plaçant son 1er pion sur la case centrale, Blanc est obligatoirement gagnant.
Si on passe à un losange de 4x4 = 16 hexagones, il existe 2 coups gagnants pour blanc, en occupant 1 des 2 cases médianes de la petite diagonale.
Je n'ai pas beaucoup de connaissances en mathématiques, aussi, je ne sais pas si cette "preuve" sur les premiers cas suffit, ou non, à affirmer, en l'extrapolant, que les blancs sont toujours gagnants, quelque soit la taille du plateau, sur un jeu parfait.
Mais je sais que le jeu ayant été conçu, par des mathématiciens, pour cette particularité, elle est admise (mais par un autre raisonnement que je ne maîtrise pas).
Mes questions :
1) Le jeu reste amusant, en l'absence de "théorie" dès qu'on agrandit le plateau.
Quelqu'un sait-il, jusqu'à quelle taille de plateau, le jeu est-il résolu ?
2) Est-ce que quelqu'un a connaissance d'études utilisant cette règle pour faire fonctionner un système de Deep Learning (type Alpha Zéro) ?
3) Existe-t-il un corpus de règles et de principes pour s'approcher du jeu parfait, quelque soit la taille du plateau ?
(Le petit logiciel, sur le net que j'ai trouvé pour jouer me semble assez faible, du genre des ordinateur d'échecs des années 80.)
J'espère que le sujet est intéressant.
Merci d'avoir lu.
|
|
|
"Le jeu ne peut se finir par un résultat nul"
Ah, intéressant, je n'y avais jamais songé.
"Je n'ai pas beaucoup de connaissances en mathématiques, aussi, je ne sais pas si cette "preuve" sur les premiers cas suffit, ou non, à affirmer, en l'extrapolant, que les blancs sont toujours gagnants, quelque soit la taille du plateau, sur un jeu parfait"
Non, l'étude des premiers cas ne suffit pas. Wikipedia donne une réponse partielle : il existe une stratégie gagnante, mais elle ne peut pas être explicitée. Résolution "ultra-faible" donc (mais valable pour toute taille de plateau).
Aucune idée pour les questions 2) et 3). Par contre j'avais lu une façon de rendre le jeu plus équilibré : les blancs jouent, puis les noirs peuvent choisir de changer les couleurs. Ça force à jouer un premier coup a priori ni trop bon ni trop mauvais (cf. "pie rule" sur la page Wikipedia).
|
|
|
Pour faire une démonstration basée sur la taille du plateau, il faudrait avoir un argument qui permette de passer d'une taille du plateau à une autre plus petite et on pourrait alors conclure (raisonnement par récurrence).
Malheureusement tu n'exhibes pas cet argument.Pas sur qu'il existe.
La preuve de John Nash pour montrer que le premier joueur gagne sur un plateau NxN est différente (strategy stealing argument) et vient du fait que dans ce jeu, un coup supplémentaire ne peut être qu'un avantage. C'est assez bien expliqué dans la version anglaise de Wikipedia, deuxième partie: https://en.wikipedia.org/wiki/Hex_(board_game)#Determinacy
La démo de John Nash montre donc que le jeu est résolu, mais de manière faible car il ne dit pas comment jouer.
Toujours sur la page en Anglais on voit que certains se sont attelés à le résoudre en donnant une stratégie de gain jusqu'à 10x10 apparemment...
|
|
|
Merci pour vos réponses et désolé de n'avoir pu intervenir plus tôt.
J'avais, à peu près, les mêmes conclusions que vous. À savoir cette résolution faible.
J'ai vu aussi pour la règle du swap.
En effet, mais encore une fois, c'est tout empirique, et basé sur quelques dizaines de parties seulement, je pense qu'il est impossible, sans cette règle de swap, d'éviter un gain facile du joueur en 1er s'il prend le centre.
Il peut développer sa chaîne vers les bords non défendus en instaurant des doubles menaces de raccordement de chaînes.
Du coup, le jeu ne pouvant être nul, "il se résume à savoir" s'il existe des coups, selon la taille du plateau, suffisamment mauvais pour que le joueur en second n'ait pas intérêt à switcher, mais à prendre lui-même le centre avec un coup de moins.
J'ai trouvé quelques contenus sur le net d'explication des règles et de tactiques basiques. Mais effectivement, rien de "théorique".
|
|
|
