Game theory

Game Theory is a branch of mathematics which studies games in general. There are several branches of game theory, and we consider two of them here.

The two branches of game theory

The first one (which is confusingly usually just called "Game Theory") is not interesting to treat games like go. It goes back to John von Neumann and considers games where two or more players do turns at the same time. An example is the Prisoners Dilemma. The most famous theorem is the von Neumann's MinMax Theorem, and John Nash's generalization of it (Nash Equilibrium). In this theory, go is quite a boring game, because it only considers optimal play, and either black or white wins under optimal play, which is basically all to be said about it. An introduction to this theory can be found here.

The second one (Combinatorial Game Theory) is much more interesting for go-players. Combinatorial Game Theory treats two-player full information games like go in general. Such a game consists in two players making alternating moves, and the player who cannot make more moves lose. It is not extremely difficult to see that go can be treated as such a game.

Combinatorial Game Theory is mainly interested in what happens if a combination of two or more such games is played: the players take alternating turns in moving, but they both have the additional choice of which of the games to move in (i.e., one only makes one move in one of the games in one turn).

Since go is a full information two player game, it can be treated by combinatorial game theory (up to kos, which are not really treated by the theory). However, in most positions the theory does not really simplify the game, or help in deciding which is the best move. On the other hand, in the endgame, it is often possible to treat different positions on the board completely independent. In this case, they are just multiple games played in combination, which is exactly what CGT was designed for. It is therefore not so surprising that using CGT it is possible to find optimal endgame moves which are hard to find if one does not know the theory.

Go in game theoretical terms

Go is a 2-person zero-sum game with perfect information. In the end game it tends to decompose into more or less independent regions, each of which is a game. Combinatorial games add and subtract. Games with kos do not add and subtract, and are not, strictly speaking, combinatorial games. For instance, a zero game may be a ko threat. Adding a zero game to a combinatorial game does not change it, just as adding zero to a score does not change it. But adding a ko threat to a ko may change it, even if the threat is a zero game.

However, much of combinatorial game theory can be applied to go, particularly thermography, a method that determines the count and size of plays in a position. Thermography has been extended to cover kos by Professor Berlekamp and myself. A related concept, temperature, is useful in thinking about go.

Go is a zero-sum game. One person loses and one person wins. But are individual local battles zero-sum?

This is a question to pose; but the standard answer by means of the exchange concept leaves no mystery. If one player gains locally, that says just the same as the other player losing. Characteristic of go is the trade-off for'assets' of different kinds: typically territory against influence. There will be, in all cases, a number based on a 'best play' continuation after that, which tells one how many points were gained or lost in a local sequence. In most cases outside the endgame we aren't likely to be able to give that number exactly.

(Sebastian:) Let's look at it this way: With a simple mathematical operation we can, instead of looking at the scores for B and W individually, look at B+W and B-W. Go as a game only regards B-W. What would be the use of tallying up B+W at every instant if you disregard it in the end?

RafaelCaetano: Just make up a few examples yourself and see what it turns out. Tip: use area rules.

One person wins and one person loses? 99% of the time sure, but there's several other phenomena that may occur. There may be a draw (assuming integer komi), no result (assuming there isn't a superko rule), "both lose" rule in some cases (i.e. a group status is unsettled but whoever asks for a continuation goes second), etc. ~srn347

Related Pages

See game theory interface for comments on how to approach combinatorial game theory as a go player.

A Beautiful Mind for a discussion on Nash and applicability of game theory to Go.

Go belongs to the class of games of partisan combinatorial games, whose general mathematical treatment did not come until John Conway saw go being played.

For more information see the books: On Numbers and Games^[1] by John Conway. Also Mathematical Go: Chilling Gets the Last Point by Elwyn Berlekamp and David Wolfe.