Computer Go
Computer Go is the field of artificial intelligence (A.I.) dedicated to creating a computer program that plays Go, an ancient board game.
After the remarkable success of Deep Blue and its mastery of computer chess, the move to challenge other difficult board games is natural. Recently Go has attracted A.I. experts from over the world because of the difficulty of making a strong Go-playing program.
There are few remarkable achievements as of yet. The task is complicated due to the deceptively simple rules of the game. This makes the game mathematically easy to represent, but also allows for a huge number of legal moves. Quite a number of research efforts have been made for a dozen years; the number is comparable to that of other board games such as chess. Researchers have not found a single effective method. The strongest programs are as weak as players that have played the game for months. Few experts predict rapid improvement in the field.
Difficulties
A large board (e.g. the full-size go board at 19x19) is often noted as one of the primary reasons why a strong program is hard to create. A large board size causes a larger number of possible legal moves than with other board games. Even with the smaller board size of 9x9, the number of game tree branches is far more than that with a game such as chess. This makes lookahead harder to implement in Go.
Another problem comes from the difficulty of creating a good evaluation function for Go. In order to choose a move, the computer must evaluate different possible outcomes and decide which is best. This is difficult due to the delicate trade-offs present in Go. For example, it may be possible to capture some enemy stones at the cost of strengthening the opponent's stones elsewhere. Whether this is a good trade or not can be a difficult decision even for humans.
The future
Novices often learn a lot from the game records of old games played by master players. There is a strong hypotheses that suggests 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 propose two ways: recognizing common configurations of stones and their positions and concentrating on local battles. "... Go programs are still lacking in both quality and quantity of knowledge." (Muller 151)
Most of the relatively successful results come from programmers' individual skills at Go and their personal conjectures about Go, but not from formal mathematical assertions; they are trying to make the computer mimic the way they play Go. "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 weakens 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 ruin a good game. Program performance over a full game can be much lower than master level." (Muller 148)
Computer Go research results are being applied to other similar fields such as cognitive science, pattern recognition and machine learning (Muller 150). Combinatorial game theory, a branch of applied mathematics, is a topic relevant 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 Go++ and David Fotland's Many Faces of Go. As of 2003, GNU Go is considered the strongest free program.
Reference and Further reading
- Muller, Martin. Computer Go, Artificial Intelligence 134 (2002): 145-79.
- Kinger, Tim and Mechner, David. An Architecture for Computer Go (1996)