Re: hex game

Le 03/08/2024 à 16:38, robby a écrit :

Pour info: JP Delahaye m'a donné ces refs. ça à l'air de parler de Dijkstra aussi. miam !

J'ai retrouvé l'article de SVM sur archive.org: https://tinyurl.com/3pyt5c6y
(https://archive.org/details/science-et-vie-micro-049/page/93/mode/1up?view=theater)
C'est pas exactement comme dans mon souvenir (le programme n'était pas qu'en Pascal), mais pas loin :)
Le bon coté est qu'il a été OCRisé, et bingo! ca parle de Dijkstra.
------8<------------------------------------------------------------------
SCIENCE & VIE MICRO N°49 - AVRIL 1988
HEX, LE JEU DE CONNEXION
Maintenir la liaison entre des positions avancées et les lignes arrières a toujours été la règle de base de toute stratégie. Certains jeux dits : de connexion : l'érigent en principe fondamental : relier ses positions et empêcher l'adversaire d'en faire autant. Hex est l'archétype des jeux de ce type. Un peu de théorie des jeux, un soupçon de théorie des graphes et une dose de programmation sont les ingrédients nécessaires pour que votre ordinateur puisse devenir un rival convenable à ce jeu à la fois simple et riche. Notre programme est en version Basic Microsoft standard et en Turbo Pascal pour Macintosh. Il constitue une base de départ pour réaliser vous-même un adversaire de première force. Envoyez-nous votre méthode avant le 15 mai : les meilleurs programmes seront publiés dans un prochain numéro.
UN PAVAGE, HEXAGONAL BIEN sur, et deux couleurs, une pour chaque joueur, suffisent pour jouer à Hex. Sur le losange de n sur n hexagones, chacun colorie alternativement une case. Il s'agit d'établir une ligne continue d'hexagones d'une même couleur entre deux des côtés opposés du losange. L'un joue avec les côtés nord et sud, et l'autre avec les côtés est et ouest. Sans qu'il soit nécessaire de le démontrer mathématiquement, il semble évident que dès que l'un des deux joueurs a relié ses deux côtés, nord et sud, par exemple, il coupe définitivement toute possibilité de connexion à son adversaire (l'est et l'ouest sont définitivement isolés par la liaison nord-sud). Celui qui réalise le premier cette connexion est donc déclaré vainqueur.
Dans le jeu de Hex, inventé dans les années cinquante par le mathématicien amateur Piet Hein, celui qui joue le premier coup bénéficie d'un avantage incontestable. Il a même été mathématiquement prouvé, peu de temps après l'invention de Hein, que cet avantage devait en fait assurer la victoire. Ce que ne dit malheureusement pas la démonstration, c'est la façon dont il faut s'y prendre pour gagner à tous les coups. Hormis sur des terrains de très petites dimensions (3 x 3 ou 4 x 4) où l'analyse exhaustive est possible, il n'existe pas, à notre connaissance, de stratégie infaillible pour gagner. L'avantage dont bénéficie le premier joueur peut alors se comparer à l'avantage que possèdent les blancs aux échecs : pour le transformer en victoire, il faut être bon tacticien et fin stratège.
La fonction d'évaluation
Lorsque l'on programme un jeu sur ordinateur, deux cas de figures peuvent se présenter : ou bien il existe une recette numérique permettant d'obtenir une victoire mathématique (c'est le cas du jeu de Marienbad, voir : Jouez avec des allumettes », SVM n°21) et il suffit de l'appliquer, ou bien il n'y en a aucune de connue et les choses se corsent. Il faut alors transposer les raisonnements du joueur, et plus délicat encore, son intuition, dans un algorithme chargé de décider quels coups sont bons. Ceci est valable pour des jeux de réflexion classiques comme les échecs, les dames, le go, le bridge.
La méthode employée dans tous ces programmes repose sur deux étapes fondamentales : l'exploration des coups à venir et l'évaluation des positions qui en résultent. La première de ces deux étapes est souvent purement combinatoire, il suffit de simuler ce qui ce produira si chaque joueur joue tel ou tel coup, jusqu'à une profondeur donnée. Toute: l'intelligence : du programme est donc souvent concentrée dans sa manière d'évaluer les positions, qui seule lui permet de décider si un coup est meilleur qu'un autre, puisque la position qui en résulte lui est plus favorable. Les programmes que nous vous proposons sont presque uniquement centrés sur ce type d'évaluation : ils n'explorent pas du tout l'arbre du jeu, mais se contentent d'évaluer avec précision la position actuelle et la valeur des différents coups possibles. Nous laissons aux lecteurs le soin d'appliquer les règles d'évaluation que nous allons décrire (et aussi celles qu'ils inventeront) à une analyse en profondeur des divers coups. Notre jeu est basé sur la connexion. Or dès que l'on parle de connexion, le mathématicien qui sommeille en nous pense : graphe » C'est pourquoi la méthode d'évaluation des positions de Hex que nous allons décrire repose sur la théorie des graphes, et plus particulièrement sur le calcul de la plus courte distance d'un point à un autre dans un graphe. Pour fixer les idées, il n'est peut être pas inutile de rappeler qu'un graphe est un ensemble de points dont certains sont reliés les uns aux autres par des arêtes. Ici, les points du graphe sont les hexagones. Au début de la partie, ces hexagones sont reliés à leurs six voisins (sauf ceux qui se situent sur les bords ou dans les coins et qui n'ont que quatre ou deux voisins). Le graphe évolue ensuite à mesure que les joueurs colorient les cases. Les hexagones occupés par l'adversaire deviennent des obstacles infranchissables coupant les connexions, tandis que les vôtres transformés en stalactites et stalagmites accrochées aux bords, raccourcissent la distance séparant les deux côtés à relier.
Le principe de la méthode employée par le programme pour évaluer l'état d'avancement consiste à mesurer la distance minimale qui sépare ces deux côtés, c'est-à-dire le nombre minimum de cases qu'il lui reste à colorier, pour que sa connexion soit établie. Il est évident que plus cette distance est faible, plus le joueur concerné est proche du but, et donc sa position d'autant plus favorable. Mais le programme ne doit pas seulement optimiser sa propre position, il doit aussi mettre des bâtons dans les roues de son adversaire, ce qui l'oblige à prendre en compte la position de ce dernier. La véritable fonction d'évaluation est donc la différence entre le nombre de coups que le programme doit encore jouer pour connecter ses bords et le nombre de coups que doit jouer son adversaire humain pour en faire autant. Si ce chiffre est négatif, c'est l'ordinateur qui a l'avantage, s'il est positif, il est au contraire en difficulté.
Le chemin le plus court
L'algorithme de calcul des distances que nous emploierons est dérivé d'un procédé classique dit « algorithme de Dijkstra ». Il fournit en réalité plus d'informations que ce que nous venons de décrire. Non seulement il calcule la longueur du plus petit trajet entre les deux bords, mais il indique aussi quelles cases permettent de réaliser cette connexion minimale. Pour fixer les idées, considérons la situation du joueur qui doit relier les côtés nord et sud du losange. Dans un premier temps, on calcule la distance minimale qui sépare les hexagones libres du bord sud, en tenant compte de ceux déjà coloriés. Le principe consiste à propager les valeurs de la distance à partir du bord sud (qui est à une distance nulle de lui-même) en remontant vers le nord : chaque case a pour distance au bord sud, le minimum des distances de tous ses voisins augmenté de un. Ainsi les cases adjacentes au bord sud en sont à une distance de 1, celles qui touchent ces dernières à une distance de 2, et ainsi de suite jusqu'au bord nord. Toute case occupée par l'adversaire n'est pas prise en compte dans le calcul du minimum et, à l'inverse, si l'on rencontre l'une de ses propres cases, sa distance est calculée à partir du minimum des distances de ses voisines, sans avoir besoin d'y ajouter un.
Pour évaluer une position, le programme effectue cette opération deux fois symétriquement, en calculant d'abord la distance nord-sud, puis la distance sud-nord. Le résultat en terme de distance nord-sud étant le même, quel en est l'intérêt ? Ceci permet de calculer pour chaque case sa distance au bord nord et sa distance au bord sud, et donc en effectuant la somme des deux, la longueur minimale d'un chemin joignant les deux bords et passant par cette case. Ainsi, on évalue non seulement la distance minimale, mais aussi les cases qui permettent d'obtenir un chemin de cette longueur, à savoir celles dont la somme des distances au bord nord et au bord sud est minimale. Pour compléter l'analyse du programme, il faut également lui faire évaluer les meilleures cases pour une connexion est-ouest, afin qu'il tienne compte de la position de l'adversaire. Le programme somme les distances obtenues pour les trajets est-ouest et nord-sud, et choisit son coup parmi ceux qui obtiennent le plus petit score. En effet, ceux-ci ont le double avantage d'optimiser sa position tout en privant l'adversaire d'une de ses cases les plus favorables.
La méthode que nous venons de décrire est appliquée par nos deux programmes à la profondeur zéro, c'est-à-dire sans explorer l'arbre des coups. Ceci permet d'obtenir des performances moyennes avec un temps de calcul très court (quelques secondes en Basic, instantanément en Pascal avec un terrain 6 x 6). L'horizon limité de l'analyse ne permet cependant pas au programme de décider parmi plusieurs coups possibles obtenant le même score, lequel est le plus favorable. Une exploration à deux ou trois demi-coups de profondeur doit suffire pour pallier ce défaut (un demi-coup est un mouvement opéré par l'un des deux joueurs seulement, par opposition au coup complet qui serait constitué par l'attaque de l'un et la riposte de l'autre).
Nous laissons aux lecteurs courageux le soin d'adapter les programmes présentés pour les rendre très performants, soit en améliorant la méthode d'évaluation, soit en donnant une certaine profondeur d'analyse au programme. L'attribution de scores aux divers coups permet de les classer a priori et éventuellement de n'étudier que les meilleurs, ce qui permet d'élaguer considérablement l'arbre du jeu et donc de réduire le temps de calcul. L'évaluation finale des positions résultantes étant la différence des distances nord-sud et est-ouest.
Pour notre part, nous vous proposons deux programmes identiques, l'un en Basic Microsoft standard et l'autre en Turbo Pascal pour Macintosh. Les instructions y apparaissent dans le même ordre et ont été mises face à face. Les lecteurs peu familiers avec le Pascal pourront confronter les deux listages, et comparer les similitudes et les différences. II va sans dire que le programme en Pascal est très sensiblement plus performant que le programme en Basic, même compilé.
Frédéric NEUVILLE
(c) SCIENCE & VIE MICRO N°49 - AVRIL 1988