Information AboutComputer Go |
| CATEGORIES ABOUT COMPUTER GO | |
| computer gocomputer go | |
| go | |
| game artificial intelligence | |
| video board games | |
|
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 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. The international rating for chess expressed in ELO points shows an approximately linear relationship between ELO score and search depth for any given program over quite a range of strengths. The much higher levels of pruning used for Go, required by the high branch factor, limits the effectiveness of increasing the search depth in Go. 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 Algorithm s are being looked at as an alternative approach. These approaches attempt to mitigate 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 2006 , GNU Go is considered the strongest free program. SEE ALSO EXTERNAL LINKS Reference and further reading
Computer programs
Other links
|
|
|