Quels sont les principaux résultats en théorie des jeux combinatoires concernant Go ?

Question

Quels sont les principaux résultats mathématiques concernant Go?

Go est un jeu avec des règles simples mais une complexité de jeu élevée. Il est inefficace d'appliquer des méthodes primitives d'intelligence artificielle aux échecs (telles que la force brute de position et les fonctions d'estimation de position empirique) à un jeu de Go.

Je suis intéressé par les résultats dans l'application de la théorie des jeux mathématiques au Go. Y a-t-il de bons résultats dans ce domaine?

Answer 1

Sur les nombres

Le grand résultat général en mathématiques Go commence par l'utilisation des nombres surréels pour évaluer les positions sur le plateau. Les nombres surréels sont une classe de nombres comprenant les nombres réels ainsi que de nombreux nombres infinis et infinitésimaux.

Les nombres surréels sont définis de manière récursive ; un nombre surréel est une paire d'ensembles de nombres surréels précédemment définis, appelés l'ensemble de gauche et l'ensemble de droite, où chaque nombre de l'ensemble de gauche est inférieur à chaque nombre de l'ensemble de droite. En Go, l'ensemble de gauche représente les coups possibles du joueur Blanc, et l'ensemble de droite ceux du joueur Noir ! Le nombre surréel ainsi défini est considéré comme étant entre tous les nombres de son ensemble de gauche et tous les nombres de son ensemble de droite. ("Inférieur" est également défini de manière récursive.) Zéro est le premier nombre surréel,

0 = ({},{})

c'est-à-dire, son ensemble de gauche est vide et son ensemble de droite est vide. Une notation plus courante pour cela est

0 = {|}

En Go, 0 représente une situation où les joueurs ont atteint une égalité. En utilisant 0, nous pouvons définir d'autres nombres surréels :

 1 = {0|}
-1 = {|0}

C'est-à-dire, 0 est à gauche de 1, et 0 est à droite de -1. En Go, 1 représente une situation où la partie s'est terminée et que Noir est en tête d'un point, et -1 Blanc est en tête d'un point. En utilisant -1, 0 et 1, nous pouvons définir

2    = {1 |  }
1/2  = {0 |1 }
-1/2 = {-1|0 }
-2   = {  |-1}

Déjà, les nombres surréels deviennent utiles de manière non négligeable pour parler de Go ! 1/2 représente une situation où Noir est en tête d'un demi-point. Remarquez que le contenu de 1/2 est 0 à gauche et 1 à droite, ce qui signifie que si c'est au tour de Blanc, Blanc peut changer la position en un 0, et si c'est au tour de Noir, Noir peut changer la position en un 1. Ainsi, ce qui suit au milieu d'un plateau de Go pourrait avoir la valeur 1/2 :

$$Wcm31
$$ X X X O
$$ X . . O
$$ X X X O

La grande chose à propos des nombres surréels est que puisqu'ils sont des nombres, vous pouvez les additionner. Les additionner correspond à avoir des situations dans des parties distinctes du plateau de Go. Ensuite, vous pouvez voir quelle est la valeur totale de la partie (c'est-à-dire, combien Noir va gagner). Bien sûr, cela n'est pratique que pendant l'endgame. Consultez cette page du Sensei pour un exemple d'une situation valant -10 31/32. Et jetez un œil à ce pdf ou à ce livre de Knuth pour vous initier aux nombres surréels.

Et les jeux

Lorsque nous rejetons la condition selon laquelle "chaque nombre de l'ensemble de gauche est inférieur à chaque nombre de l'ensemble de droite", et laissons simplement apparaître n'importe quoi qui a été précédemment défini dans l'un ou l'autre ensemble, nous obtenons des choses telles que

* = {0|0}

où la situation n'est pas techniquement zéro, mais soit Blanc soit Noir peuvent se déplacer vers une position où la situation est zéro. Par exemple, * est la valeur d'une égalité avec un seul "dame" restant dans un ensemble de règles où nous sommes obligés de remplir les "dames".

Tout ce que nous obtenons de cette manière est appelé un jeu. Remarquez ensuite que le livre de Conway On Numbers and Games utilise "nombre" pour désigner un nombre surréel, et "jeu" pour désigner ceci. Suivez les liens sur la page du Sensei sur la Théorie des Jeux Combinatoires pour en savoir plus.

Les résultats principaux

Je dirais que "l'élimination des options dominées et réversibles" est l'un des résultats principaux de la théorie des jeux combinatoires applicable au Go. Les pages 17-19 de cet article de Brit C. A. Milvang-Jensen l'expliquent bien. Malheureusement, comme la page du Sensei sur la Forme Canonique le souligne, le fait qu'une certaine position puisse être considérée comme une menace de ko peut être perdu lorsque nous éliminons les options dominées et réversibles, donc l'application du résultat n'est pas formellement directe.

Le concept le plus saillant de la théorie des jeux combinatoires dans le Go est probablement celui de température, ou valeur miai, et de refroidissement. La température est de combien Noir gagnerait plus en jouant dans une position que en passant, et le refroidissement est une méthode de calcul dans laquelle on imagine devoir payer un certain nombre de prisonniers pour le privilège de jouer dans une certaine position.

Le livre le plus complet sur le Go mathématique est probablement Mathematical Go: Chilling Gets the Last Point de Berlekamp et Wolfe. Cette page du Sensei à ce sujet inclut un exemple d'une situation pour laquelle il est facile d'appliquer la théorie si vous la connaissez bien, mais les 9-dans professionnels peuvent s'y casser la tête en vain.