The Game of Go

Game of Go
Game of Go

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 10700. This number is almost definitely an overestimate considering that the estimated number of particles in the Universe, when I last checked, was 1091!! 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 :

Minimax Example

Minimax Example

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.


Bookmark and Share

Advertisements

6 thoughts on “The Game of Go

  1. I look forward to seeing more articles about Go. It’s been an interest of mine for nearly two decades now, though I have to admit that I’m not very good at it, haha.

    I’ve been intensely interested in the progress of Go software for that entire period, and it often seems to me as if creating a strong Go program is one of the few pathologically difficult problems remaining in software development. I may be overstating that somewhat, but you have to admit that even the ‘best of the best’ in Go software is ridiculously naive compared to human players, and unlike Chess and other games it’s very difficult to identify and weight potential patterns.

    I’ve subscribed (having found your blog through a link on AIGameDev), and hope to see more on this topic in the future 🙂

  2. The number 10^700 is the complexity of the game of Go as measured by the number of possible non-redundant games. The number of particles in the universe does not impose a limitation that would require this number to be scaled down because while the rules of the game need to be explained with a certain minimum number of bits, the game possibilities are theoretical and do not have to be recorded in order to define the game according to its rules. Because of this, the number 10^700 should not be considered an overestimate merely because the number of particles in the universe is less. In fact, genetic algorithms in particular use their rules as an efficient way to find an ideal solution in a relatively complex possibility space. A simpler definition of the problem facilitates the acquisition of an answer.

    • [Edited]
      The comparison with the number of particles in the Universe was meant as pop-science note. The direct implication was that a brute force min-max approach to solving the game would be futile. ( Although there is a school who believe its possible ) Therefore, an indirect representation such as those used in GAs would be a good option. I found a paper on a Roving Eye ANN developed using NeuroEvolution that plays smaller boards. I don’t how well it would scale though.

  3. Pingback: Computer Go (….continued) « The Green Destiny

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s