Take the 2-minute tour ×
Board & Card Games Stack Exchange is a question and answer site for people who like playing board games, designing board games or modifying the rules of existing board games. It's 100% free, no registration required.

What are the main mathematical results concerning Go?

Go is a game with simple rules and big 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 they any good results in this field?

share|improve this question
    
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 Nov 22 '11 at 13:36
    
Note that usually the area of mathematics applied to go is "combinatorial game theory". Standard game theory talks about different types of games, and is often applied to economics. –  Max Feb 27 '12 at 8:49
    
Game theory is about applying mathematics to human decisions - it actually has little to do with board games. The results you seem to be looking for would fall under AI and combinatorics. –  BlueRaja - Danny Pflughoeft Mar 12 '12 at 17:07
add comment

1 Answer

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.

share|improve this answer
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 Nov 22 '11 at 19:33
1  
youtube.com/watch?v=rNvP6a8sTnI&feature=youtu.be i found this description of temperatures particularly helpful –  magnetar Nov 22 '11 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 Nov 22 '11 at 20:03
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.