Computer Go

Computer Go is a computer program that plays Go, an ancient board game.

After the remarkable success of Deep Blue, computer chess, the course to challenge other difficult board games seems a natural move and one among them is Go, but the trouble is that Go is different. An attempt to make computer go is in line with creation of board games such as chess in the past, which is mostly a snap now. In these decades and Go has attracted computer scientists of artificial intelligence over the world because of its difficulty of making a strong computer program playing the game as they have attained successful results in other board game.

Remarkable achievements made so far are very few. Its complication is due to that rules of the game are deceptively simple, which makes the game mathematically beautiful but causing a huge number of legitimate possibility, and that developers of computer go have failed to figure out decent ways to represent on the computer human knowledge used for playing the game. Quite a number of researching efforts have been made for dozen years; the number is as much as that to other board games such as chess. The accomplishment made to date, although, is awfully little. Not a single method that is agreed effective has been found, strongest players are as weak as players that have learned the game for months and a very few experts on computer go predict the future programs cannot be far better, if little.

The simplicity of go makes the game mathematically beautiful but causes huge complexities on making of computer go and the explanation of difficulties involves the reason human players can take advantage of being human (Muller 150). A huge size (19x19) of the board used in Go is often noted as one of primary reasons why strong computer go is hard to make because the size seems to cause a far more number of possible legitimate moves in one game than other board games. While it is true that the number is huge, this claim is rather a misconception; even with the board size of 9x9, a number of branches are far more than those in chess. In short, the size of the board seems to matter little. This fact importantly suggests simple improvements are not much use; if a huge number of possibilities is an origin of problems, speeding up the computer helps adequately for the strength and even some sophisticated mathematical algorithm can reduce the possible number dramatically, and those are cases that happened in computer chess.

The significant difference between go game and other board game, in turn, is that complex situations appearing in games of go and distinct trade-offs to consider due to them, that is, games in go involve local tactics and global strategies in sense of human. In go, local situations overwhelmed by changes at global level. The speed of computer helps little to evaluate moves correctly and understanding human intelligence is the key.

This complication is a nightmare for developers of computer go because techniques they have are quite ineffective in go. Evaluation functions are excessively used in computer board games to judges which board is favorable to one and disadvantageous to the opponent. The effectiveness of evaluation function is a key component of the computer go because it is a main criteria to choose the best moves among any a huge number of legal moves yielded from brute force computation (Muller 151). However, "the situation on a Go board can be extremely chaotic, leaving exhaustive analysis as the only known method of solution" except in endgame because in endgame typical good moves are rather regular. In short, evaluation functions tell a clue about paths the computer should seek. Local games including life and death judgment of territories, require the computer to see correct evaluation situations quite further.

Another problem is complexity representing Go knowledge, including pattern recognition, in digitalized form (Muller 151). The computer always has trouble seeing concepts such as 'light' and 'heavy' stones. It is well-known that a strong professional go players instantly see a decisive move and those can tell a situation is favorable to which players momentally and correctly and even estimate scores in the end of game with surprising precision, which is done by evaluation functions on the computer side. Novices often learn a lot from the game records of old games played by master players. There is strong hypotheses that acquiring go knowledge is a key to make a strong computer go. For example, Tim Kinger and David Mechner argue that "it is our belief that with better tools for representing and maintaining Go knowledge, it will be possible to develop stronger Go programs."; they proposes two ways: recognizing common configuration of stones and their positions and concentrating on a local battle. Pattern recognition is one of problems that the computer has and that human beings are surprisingly good at. "[...] Go programs are still lacking in both quality and quantity of knowledge." (Muller 151)

Although there is no effective way to measure it precisely, the performance of computer go until today is shameful for AI researchers. There are some incremental improvements but no groundbreaking works yet. Most of relatively successful results come from individual skills at go and their personal conjectures about go, but not from formal mathematical assertions; they are trying to mimic the way they play a go on the computer. "Most competitive programs have required 5-15 person-years of effort, and contain 50-100 modules dealing with different aspects of the game." (Muller 148) Surprisingly adding knowledge of go sometimes weakening the program because some superficial knowledge might bring mistakes; "the best programs usually play good, master level moves. However, as every games player knows, just one bad move can can ruin a good game. Program performance over a full game can be much lower than master level." (Muller 148) In short, the complications seen in computer go is difficulty seeing the root of human intelligence. The results of research of computer go is also applied to other similar fields such as cognitive science, pattern recognition and machine learning (Muller 150). Combinatorial game theory, a branch of mathematics applying, is often relevant topic to computer go (Muller 150).

Several annual competitions take place between Go computer programs, the most prominent being the 21st Century Championship Cup and the Go event at the Computer Olympiad.

Prominent go-playing programs include Michael Reiss's Go4++ and David Fotland's Many Faces of Go.

Reference and Further reading

• Muller, Martin. "Computer Go" Artificial Intelligence 134 (2002): 145-79.
• Kinger, Tim Kinger and Mechner, David. "An Architecture for Computer Go" 1996 <http://http://www.cns.nyu.edu/~mechner/compgo/acg/>