Why Go? After Deep Blue won a series of games against Garry Kasparov in 1997, programmers had to search elsewhere for games. Shogi programs can play at the level of 1-dan, while the strongest Go program is only 8-kyu (for more information about ranks visit Hanging out at Dan's). It is hard to find the strength of Go programs because human players will find their weaknesses and in subsequent games take advantage of them. No strong Go computers have the ability to learn, so a rank is difficult to determine. Since Go programs are still at the amateur level, I had to go and find out why.

Go and computers Picture courtesy of Kirsty Healey/BGA

I found Nick Wedd 1-dan, arbiter of the Computer Go Olympiad, and asked him what the troubles were coding computer Go players. He explained that many thought that Shogi would be as hard for computers to play as Go, but this proved to be false as well. Nick told me that the evaluation function is the key aspect of writing a computer Go program. An evaluation function is the way a computer determines which side is currently winning. In most games like Chess or Shogi, a computer can easily compute simple formulas to determine who is winning by simply counting the pieces remaining on the board and they can make moves based on these evaluation functions.

In the game of Go, it is usually difficult to tell who is winning simply by looking at the board. In Chess, someone could count the number of pieces based on their values to adequately perceive who is winning. Shogi could follow similar principles, but in Go, an accurate evaluation formula is almost impossible to discover. Most of the work surrounding Artificial Intelligence and Game Theory requires an accurate evaluation formula.

Another problem is the incredibly large branching factor in Go. On the first move of the game there are 361 (19x19) possible moves and there are 129,960 possible combinations after the second move! For a computer search tree, the amount of memory and processing power would quickly exhaust. These numerous problems make writing strong Go programs hard to code.

Often, when mathematicians and computer scientists attempt to write strong computer programs, they first examine how the game would be played on a smaller board and see if any of the strategies on the smaller boards would be applicable on the larger board. I asked Nick if Go was solved on a 4x4-sized board.

He said the major problem with smaller boards is that there are numerous rulesets from Japan to China on how to score a game of Go, so if it were "solved" in one ruleset, then it would not necessarily be solved in another one.

An interesting fact to note about Go is that it is solved to be a draw by definition. In an even game of Go, a komi indicates what should be added to the white's score, because black has an advantage by going first. In theory, experts estimate seven to be a good value for komi. However, if Go were solved as a win for the first player, the komi could just be adjusted to ensure a fair game. Of course, if the komi were adjusted based on hypothetically perfect play, then it would be adjusted to the perfect komi, making the game a draw by definition!

Michael Reiss 1-kyu, programmer of Go 4++, had more insights into the difficulties of writing computer Go programs. He started by explaining that the middlegame is the hardest part to write. In the opening, chess computers have a fairly easy time because the opening book can be used with almost certainty that the computer is playing adequately well, just by following database moves.

In Go, the opening is not as important because the board is so much larger and openings in different areas of the board affect the play in other areas of the board. Also, Nick Wedd commented that the opening is not all that important because on the first four moves of the game, one could easily play on the star points and have a good game.

The middle-game is generally the most difficult to program because the opening can be covered by a database and then the endgame can be solved because it is simpler than the rest of the game (especially in Chess).

In Chess, computers get to the point where the end of the game is solved and then they play mechanically, but Go endings are not so simple. One easy programming trick is to fill in the largest Dame first because this area could eventually turn into territory for yourself. Michael Reiss' program Go4++ finished second in the Computer Go Olympiads this year and is published as Go Professional 3 in Europe by Oxford Softworks.