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 in the field of computer chess and its victory over world chess champion Garry Kasparov, the move to challenge other difficult board games is natural. Recently Go has attracted A.I. experts from all 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.
| Contents |
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. This fact has been reinforced by a number of papers converting difficult (even NP-complete) combinatorial problems into Go problems.
In 2002, the 5x5 game of Go was completely solved, with black winning by 25 points (the entire board). To date, this is the largest game of Go that has been solved. The name of the computer program that found the solution is MIGOS (MIni GO Solver).
The future
Novices often learn a lot from the game records of old games played by master players. There is a strong hypothesis 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)
New approaches to the problem
Historically, GOFAI (Good Old Fashioned AI) techniques have been used to approach the problem of Go AI. More recently, Neural Networks and Genetic algorithms are being looked at as an alternative approach.
These approaches bypass the problems of the game of Go having a high branching factor and numerous other difficulties.
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. Regular, less formal, competitions between programs occur on the Computer Go Ladder.
Prominent go-playing programs include Michael Reiss's Go++ and David Fotland's Many Faces of Go. As of 2004, GNU Go is considered the strongest free program.
See also
External links
Reference and further reading
- Müller, Martin. Computer Go, Artificial Intelligence 134 (2002): 145-79.
- Kinger, Tim and Mechner, David. An Architecture for Computer Go (http://www.cns.nyu.edu/~mechner/compgo/acg/) (1996)
- Online Computer Go bibliography (http://www.markus-enzenberger.de/compgo_biblio.html).
- All systems Go (http://www.cns.nyu.edu/~mechner/compgo/sciences/) by David A. Mechner, discusses the game where professional go player Janice Kim won a game against program Handtalk after giving a 25-stone handicap.
- Two Representative Computer Go Games (http://www.cs.ualberta.ca/~mmueller/cgo/survey/twogames.html), an article about two computer go games, the one with two computers players, and the other, a 29-stone handicap human-computer game
- Computer Go (http://senseis.xmp.net/?ComputerGoProgramming) and Computer Go Programming (http://senseis.xmp.net/?ComputerGoProgramming) pages at Sensei's Library (http://senseis.xmp.net)
- The Computer Go Room on the Kiseido Go Server (http://kgs.kiseido.com) (KGS) for online discussion and running "bots".
Computer programs
- Go++ (http://www.goplusplus.com)
- GNU Go (http://www.gnu.org/software/gnugo)
- Smart Go (http://www.smartgo.com/)
- The Many Faces of Go (http://www.smart-games.com/manyfaces.html)
- 5x5 Go is solved (http://www.cs.unimaas.nl/~vanderwerf/5x5/5x5solved.html)ja:コンピュータ囲碁