mardi 25 novembre 2008
Hex
Par Didier Müller, mardi 25 novembre 2008 à 08:18 - Jeux / Théorie des jeux
Le jeu de Hex est un jeu de société abstrait pour deux joueurs. Il se joue sur un plateau en forme de losange dont les cases sont hexagonales. On peut choisir plusieurs dimensions pour le plateau mais la plus intéressante semble être 11 x 11. Au début de la partie, aucun pion n'est sur le plateau. Les joueurs posent tour à tour un de leur pion sur une case de leur choix et le plateau se remplit ainsi progressivement. Deux côtés opposés du plateau sont noirs et les deux autres sont blancs. Chaque joueur doit réussir à relier les deux côtés avec les pions qui portent sa couleur. Le jeu s'arrête dès qu'un joueur y est parvenu. Ci-dessous, les noirs ont gagné. Il ne peut pas y avoir de match nul.
Ce jeu a été inventé indépendamment par Piet Hein (Danemark, 1942) puis John Forbes Nash (USA, 1948). J. Nash a démontré que le premier joueur peut toujours gagner : il n'y a pas de hasard, juste de la stratégie. Cependant, sa preuve est non constructive, c’est-à -dire qu'elle n'indique pas la stratégie gagnante et celle-ci est sans doute beaucoup trop complexe pour être décrite !
Sur tout plateau rempli, un des deux joueurs et un seul possède une chaîne gagnante. Cela peut être démontré par exemple en utilisant le fait qu'une partie de hex puisse être vue comme une partie particulière de Y, et en se référant alors à la démonstration dans le cas du Y.
Ce jeu suscite d'importantes réflexions en mathématiques et notamment :
- en logique (des stratégies gagnantes ont été découvertes pour des dimensions jusqu'à 9 x 9 mais le problème de trouver une stratégie gagnante générale semble relié à des problèmes ouverts parmi les plus importants à l'heure actuelle)
- en intelligence artificielle (on cherche à programmer des ordinateurs à jouer le mieux possible au Hex, sans chercher à proprement parler de stratégie gagnante)
lu 7306 fois
