It is amazing how simple rules can result in breathtaking complexity. This post is about such another game :

Go

Chances are, you have already seen people play the game. I had seen it first in ‘Fist of Legend‘, Jet Li’s adaptation of the ‘Fist of Fury‘.

It is so old that it was mentioned in the ‘*Analects of Confucius*‘( 479 B.C ). In fact, the American Go Association cites this is as one of the top ten reasons to play Go.

When you play go, you are doing something that billions of people have done for thousands of years. Many centuries ago, people were doing the exact same thing, in the exact same way.

What an absurd reason to give a promising player to choose the game!!!

Crisply, the rules as specified here:

- Go-board(Goban):19 x 19 intersections.
- Back and White play alternatively.
- Black starts the game.
- Adjacent stones ( of the same colour ) are called a string.
- Liberties are the empty intersections next to the string.
- Stones do not move, they are only added and removed from the board.
- A string is removed if its number of liberties is 0.
- Score: Territories(number of occupied or surrounded intersections).

Plain and simple. There is also a large set of terms associated with the game which you will nedd to know if you are playing / coding a player. All of them, Japanese. I strongly agree with the subject of this post, so try to play a few games before you get coding. I would suggest GNUGo, with Quarry to make a good beginning.

However, Computer Science considers a human level Computer Go player an open problem. It belongs to the same class of problems as the ` P = NP ` and ` The Church Turing Hypothesis `.

A comparison with Chess, ought to bring more light on the subject.

- Computer Chess Programs have defeated Chess Grandmasters, and have become so good, that are now competing among themselves for Chess Supremacy.
- An average Go program, on the other hand, are routinely trounced by Asian school children.
- At any stage of the game, Chess, on average, has 37 possible moves, decreasing as the game progresses. ( Lesser coins, lesser moves )
- Go, on the other hand, averages 250 possible replies per move.
- There are terms in Go, look here, each of which needs a representation in the program.
- Chess has very little such terms, en passe, fortress, and the like, and provides lesser challenge to a programmer who has little knowledge of the game.

If you cannot truly assess the complexity of the problem, here’s one more trivia, Go, is associated with the number 10^{700}. This number is almost definitely an overestimate considering that the estimated number of particles in the Universe, when I last checked, was 10^{91}!! However, more reasonable estimates aren’t too far from this number either.

## A brief Intro on how computers play ( board ) games:

Computers, play games by searching in a state space tree. Many use a theorem called the Minimax Theorem. Chess, Go and most other board games are said to be complete-information deterministic games in that both players know everything there is to be known from the beginning to the end of the game. There is no role for chance here. In 1928, Von Neumann proved that such games are always zero sum. In non formal terms, a zero-sum game is a game in which one player’s winnings equal the other player’s losses. It is pretty much like cake cutting. So a good move means that the opponent has got only worse moves, all of them in all variants leading to favourable positions which are therefore unfavourable for the opponent.

An example of the minimax algorithm should be very useful here :

Consider a two-player game, where each player takes alternate turns ( which is the vast majority of the board games today ). Now as shown in the figure, you have three options, to each which your opponent has three options in reply. The tree’s root indicates that you’ll choose the move that lands you in the best position possible when you are to play next. The numbers in the circle indicates your position after that move. Level 2 is your opponent’s move. Initially, the tree is constructed with empty circles, and evaluation is done from the leaf to the root.

Some evaluation function, say f(x), evaluates the board position and returns the values at the leaf level. You take the minimum of the points your opponent’s move left you and put it in the corresponding higher level. Then, you take the maximum of all the points your move will leave you and put it in the higher level. What has happened? You are left with a guarantee that you’ll get at least +1 no matter what your opponent’s response is. IN simpler terms, you have maximised your minimum profit. And hence the term minimax.

** A minimax tree is generally more than 2 ply( 1 ply is a single player’s turn, turn itself being an ambiguous term, to be used across multiple games ) deep.

Here is more on zero-sum games. A wiki minimax example.

Here is an article that shows why MInimax Theorem is not always practically optimal.

Many optimizations have been made to this approach the prominent of them being, Alpha-Beta pruning.

Naturally, it is important how deep your tree is. The evaluation of the game state is also just as crucial if not more, in the grand scheme of things. A good evaluation function can reduce how deep you need to look.

All of the most famous Chess engines of our time use this technique. For a game like Chess, with an average branching factor of 35~50, specialised hardware with pre-calculated open-game and end-game tables is enough to beat a Chess Grandmaster. In fact it even defeated the highest graded Grandmaster in history.

Such an approach becomes immediately inadequate in the game of Go. No hardware can search in such large a state space. Also, an accurate evaluation function is also very difficult to arrive at. Well, then how do today’s programs approach Go?

### A look at the current Computer Go Scenario :

The most powerful computer Go programs in the world today are :

- GNUGo
- MoGo
- CrazyStone
- Go++
- NeuroGo

A rough analysis of these five should be of great interest. Updates on this post and further posts will be regarding this.