Avons-nous des tables de fin de partie de Go, comme pour les échecs ?

Question

Je suis relativement novice en matière de Go et plus intéressé par les aspects de programmation de la conception d'un moteur Go.

Les moteurs de go utilisent-ils une liste systématique de positions de fin de partie avec des victoires connues, comme le font les moteurs d'échecs ? Et les joueurs de go de niveau professionnel mémorisent-ils une liste de positions de fin de partie dans le cadre de leur entraînement ?

Quelques recherches en ligne ont permis de trouver cet article de Wikipedia y papier d'informatique suggérant que Résoudre les fins de partie de Go par ordinateur est un problème très difficile, qui prend beaucoup de temps. C'est peut-être la raison pour laquelle les tables de fin de partie de Go n'existent pas / ne sont pas largement utilisées ?

Answer 1

Je connais beaucoup plus le Go que les échecs, donc je ne sais pas à quel point mes suppositions sur les fins de parties d'échecs seront précises, mais... Je pense que les échecs ont tendance à être à leur plus simple dans la finale (comme le Go), et il y a peu d'informations dans la finale sur la façon dont le reste de la partie a progressé (contrairement au Go). De plus, il existe des algorithmes pour gagner (dans certains cas) qui se généralisent à un grand nombre de positions. Par exemple, si les Blancs ont une Dame et un Roi, et que les Noirs n'ont qu'un Roi, à moins que le Roi ne soit sur le point d'être capturé, les Blancs gagneront, quelle que soit leur position.

Au Go, la finale est également la partie la plus simple du jeu, dans la mesure où c'est la seule partie du jeu dans laquelle le score et la valeur de chaque coup peuvent être calculés très précisément, cependant la position est tout, et vous ne verrez jamais deux parties se terminer avec la même position sur le plateau. Aux échecs, vous pouvez généraliser de nombreuses positions en fonction des pièces restantes, mais au go, la seule généralisation est le décompte des points et le nombre de points restant à prendre.

Il serait tout à fait impraticable de se baser sur des tableaux de niveau de plateau entier au Go, mais de nombreuses petites zones du plateau correspondent à des modèles communs, qui sont mémorisés par les joueurs de Go et programmés dans les ordinateurs. Un exemple de niveau moyen serait bent four dans le coin est mort mais vous verrez que cette position relativement courante n'est pas du tout évidente pour un débutant et qu'elle s'accompagne de plusieurs réserves (pas de menace de ko-inamovible, le groupe environnant doit être vivant et avoir deux yeux), et bien qu'elle soit relativement courante, elle constitue en quelque sorte un cas particulier.

Quelque chose comme savoir où jouer pour tuer (ou sauver !) volumineux cinq (et bien d'autres formes encore) devrait être automatique pour un humain ou un ordinateur.

Programmer un ordinateur pour qu'il joue bien yose est un problème très difficile, mais c'est l'un des rares aspects du Go pour lequel les ordinateurs peuvent battre les joueurs de Go professionnels, car il s'agit d'un calcul et, bien que difficile, la théorie est bien comprise. Pour être efficace, le programme doit être capable d'estimer le score actuel, d'identifier les coups restants sur le plateau qui valent des points, et de les trier par ordre de valeur - ce qui n'est pas trivial. Cet article pourrait être un bon point de départ.

Résumé : Il y a une place pour les listes systématiques de positions dans les programmes de Go, mais elles ne seront pas utiles pour les positions de l'ensemble du plateau. Le programme doit être capable d'évaluer le statut de vie ou de mort de chaque groupe sur le plateau, et c'est dans ces positions d'un ou deux groupes que les listes seront les plus utiles - et elles le seront tout au long de la partie. En essayant d'attaquer les groupes de l'adversaire, le but de votre programme ne sera pas seulement de reconnaître les formes de la liste, mais plutôt de forcer l'adversaire à utiliser des formes dont il sait qu'elles sont mort tout en maintenant formes vivantes même. Voir aussi Formes d'angle courantes .

Pour écrire un programme de Go, je vous donnerais le même conseil qu'à une personne apprenant le Go : commencez sur un petit plateau, même aussi petit que 5x5 jusqu'à ce que vous ayez compris les règles. Passez ensuite à 7x7, puis restez longtemps sur 9x9 avant de penser à essayer 13x13.

Bonne chance !

Answer 2

Il n'existe pas de bases de données de fin de partie sur l'ensemble du plateau, car il y a trop de permutations possibles à la fin. Une telle approche ne pourrait pas être traitée par les systèmes informatiques les plus modernes.

La bonne nouvelle est que les bases de données de fin de partie pour les situations confinées et locales ont un sens et peuvent être vraiment bien appliquées, plus la fin de partie a progressé. Après avoir analysé le résultat de chaque situation locale confinée, vous pouvez calculer la meilleure façon de la traiter en trouvant le bon ordre des coups. Bien sûr, il n'est pas si facile de trouver une solution parfaite, parce que vous devez chronométrer des coups sente "gratuits" qui détruisent vos propres menaces ko- et ainsi de suite, mais la finale de l'IA au Go est plutôt bonne comparée au milieu de partie.

Pour comprendre le concept de fin de partie, les schémas communs, l'importance de sente/gote et ainsi de suite, je peux vous recommander le livre La fin de la partie si vous êtes intéressés.

Answer 3

Il y a une théorie de fin de partie pour le Go utilisant Des chiffres surréalistes . La théorie est exposée dans le livre "Mathematical Go : Chilling Gets the Last Point" par Berlekamp et Wolfe.

Une IA utilisant cette théorie joue de manière optimale et bat généralement un joueur professionnel humain en finale. La lecture de ce livre reste amusante pour un joueur de go moyen et vous apprend beaucoup sur la stratégie des fins de partie.