Games - Computer Go

Home > Listing Index > Games > Computer Go

	Games - 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. Computer Go is typically restricted to programs which actually play moves; programs which only allow replay of expert games or play against opponents across the internet are not considered computer go programs in this sense.

Go is unlike chess, where the massive computing power of modern computer systems (and in particular dedicated chess machines like Hydra) together with relatively simple search and evaluation heuristics have proven superior to the best of human players. The effort to construct a Go-playing machine capable of competing even with strong amateur players has so far been unsuccessful. It is a widespread opinion that techniques learnt in the course of developing a strong Go program would transfer, to a greater degree, to more general problems in artificial intelligence, than has been the case with chess.

Although the rules of the game are simple to state, it is not trivial even to write a program capable of automatically determining the winner of a finished game. The number of research efforts made, for a dozen years, is comparable to that researching many other board games, although the development effort going into computer chess systems continues to be at least an order of magnitude larger: this is evidenced for example by the existence of literally hundreds of freely available and about a dozen relatively successful commercially sold chess engines as well as by the fact that computer chess unlike computer go still sometimes manages to get access to supercomputing hardware.

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. This point alone is however not terribly convincing in light of the fact that other games, such as Amazons, feature branching factors significantly larger than Go without sharing with Go the apparent difficulty of writing a strong computer player. Still, the large board size is a problem insofar as it prevents an alpha-beta-searcher without significant search extensions or pruning heuristics from achieving deep lookahead.

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.

Sometimes it is mentioned in this context that various difficult combinatorial problems (in fact, any NP-complete problem) can be converted to Go problems; however, the same is the true for other abstract board games, including chess when suitably generalized to a board of arbitrary size. NP-complete problems do not tend in their general case to be easier for unaided humans than for suitably programmed computers: it is doubtful that unaided humans would be able to compete successfully against computers in solving for example instances of the subset sum problem. Hence, the idea that we can convert some NP-complete problems into Go problems does not help in explaining the present human superiority in Go.

The widespread idea that in chess, a simple material counting evaluation will be sufficient for decent play is also wrong: writing a good chess evaluation function is not a trivial job. However, many more subtle considerations like isolated pawns, rooks on open verticals, pawns in the center of the board etc. can be formalized easily, providing a reasonably good evaluation function which can be calculated in short time. Comparing chess and go, it is also worth noting that there exist chess positions which presently existing chess programs tend to handle badly, in particular fortress-type positions. As the type of reasoning that enables human players to recognize fortresses is more important in Go than in chess, it is not unnatural to expect Go to be harder than chess to implement.

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)

[ Visit the complete Wikipedia entry for Computer Go ]

Searches on eBay

computer go