30

What are the main mathematical results concerning Go?

Go is a game with simple rules but high game complexity. It is inefficient to apply primitive chess AI methods (such as position brute force and empirical position estimation functions) to a Go game.

I am interested in results in the application of mathematical game theory to Go. Are there any good results in this field?

1
  • i don't have a full answer, but you might check out j.h. conway's stuff on go endgames, which is game-theoretic. i once asked him if he played go, and he said no. despite that, he (and some students) did originally invent the game of life on the go board.
    – magnetar
    Commented Nov 22, 2011 at 13:36

1 Answer 1

33

On Numbers

The one big overarching result in mathematical Go starts with the use of surreal numbers to evaluate positions on the board. The surreal numbers is a class of numbers including the real numbers as well as many, many, infinite and infinitesimal numbers.

The surreal numbers are recursively defined; a surreal number is a pair of sets of previously defined surreal numbers, called the left set and the right set, where each number in the left set is less than each number in the right set. In Go, the left set represents White's possible moves, and the right set Black's! The surreal number thus defined is thought of as being between all the numbers in its left set and all the numbers in its right set. ("Less than" is recursively defined as well.) Zero is the first surreal number,

0 = ({},{})

that is, its left set is empty and its right set is empty. A more usual notation for this is

0 = {|}

In Go, 0 represents a situation where the players have reached a draw. Using 0, we can define more surreal numbers:

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

That is, 0 is to the left of 1, and 0 is to the right of -1. In Go, 1 represents a situation where the game has ended and Black is up one point, and -1 White is up one point. Using -1, 0, and 1, we can define

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

Already the surreal numbers become nontrivially useful for talking about Go! 1/2 represents a situation where Black is up a half a point. Notice that the contents of 1/2 are 0 on the left and 1 on the right, which means that if it's White's turn, White can change the position to a 0, and if it's Black's turn, Black can change the position to a 1. Thus the following in the middle of a Go board might have value 1/2:

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

The great thing about surreal numbers is that since they're numbers, you can add them. Adding them corresponds to having situations in distinct parts of the Go board. Then you can see what the whole game's worth (i.e., how much Black will win by). Of course, this is only practical in the endgame. See this Sensei's page for an example of a situation worth -10 31/32. And check out this pdf or this book by Knuth to get an introduction to surreal numbers.

And Games

When we throw away the condition that "each number in the left set is less than each number in the right set," and just let anything at all that was previously defined show up in either set, we get things such as

* = {0|0}

where the situation is not technically zero, but either White or Black can move to a position where the situation is zero. For instance, * is the value of a draw with one dame left in a ruleset where we are obligated to fill in dame.

Everything that we obtain in this way is called a game. Notice that then Conway's book On Numbers and Games uses "number" to mean surreal number, and "game" to mean this. Follow the links on The Sensei's page on Combinatorial Game Theory to find out more specifics.

The Main Results

I would have to say the "elimination of dominated and reversible options" is one of the main results within combinatorial game theory applicable to Go. Pages 17-19 of this paper by Brit C. A. Milvang-Jensen explain it well. Unfortunately, as the Sensei's page on Canonical Form points out, the fact that a certain position may count as a ko threat may be lost when we eliminate dominated and reversible options, so the application of the result is not formally straightforward.

The most salient concept from combinatorial game theory in Go is probably that of temperature, or miai value, and cooling. Temperature is how much more Black would gain from playing in a position than from passing, and cooling is a method of reckoning in which one imagines having to pay a tax of a certain number of prisoners for the privilege of playing in a certain position.

The most thorough book on mathematical Go is probably Mathematical Go: Chilling Gets the Last Point by Berlekamp and Wolfe. This Sensei's page about it includes an example of a situation to which it's easy to apply the theory if you know it well, but professional 9-dans may puzzle over it to no avail.

4
  • 1
    +1 for an excellent answer. last time i checked the SL page about that book was about 2 years ago, and the board diagram showing that fascinating problem was not there.
    – magnetar
    Commented Nov 22, 2011 at 19:33
  • 1
    youtube.com/watch?v=rNvP6a8sTnI&feature=youtu.be i found this description of temperatures particularly helpful
    – magnetar
    Commented Nov 22, 2011 at 19:38
  • 2
    see also library.msri.org/books/Book29/files/kim.pdf for a formal description of the temperature-reading process by Berlekamp, along with some very nice diagrams showing the use of surreal numbers
    – magnetar
    Commented Nov 22, 2011 at 20:03
  • 1
    Great answer! I seem to recall Berlekamp analyzing endgames in Go, fairly early in the field. Here is his official Go page: math.berkeley.edu/~berlek/cgt/go.html
    – DukeZhou
    Commented Aug 11, 2017 at 20:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .