Computer Go

Computer go is the field of artificial intelligence (AI) dedicated to creating a computer program that plays go, an ancient board game.
Note: 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 and will not be discussed in this page.

Performance

Computer go has long been considered a strong challenge in the field of AI. Since the results of Deep Blue and Deep Fritz, computer chess has lost much of its significance as a big challenge for AI. Go, however, is a much harder problem. Amongst the reasons for this is the size of the board and that the average number of legal moves in a game is much greater than in chess. In computer go, much more sophisticated algorithms need to be used to create a program, which can be compared to the strongest human players (9 dan professional). It is also thought that the algorithms solving the main challenge of computer go should be of a different kind, and that they can shed more light on human intelligence than computer chess did.

Ranks

In recent years, enormous progress has been made, with a computer beating the best human player.

Endgame

Since the number of possible moves in endgame is much less, one may think the endgame should be much easier than other parts of the game since the number of possibilities is reduced. A computer should be able to tackle it. In chess, a computer can handle all different endgame situations flawlessly due to the use of endgame tablebases.

One possible kind of game analysis was pioneered by John H. Conway, who invented surreal numbers to analyze games and go endgames in particular. This idea was much further developed by Elwyn R. Berlekamp and David Wolfe. It is outlined in their book, Mathematical Go (ISBN 1-56881-032-6). While not of general utility in most play, it greatly aids in the analysis of certain classes of positions.

Nevertheless, although elaborate study has been conducted, go endgames are proved to be PSPACE-hard. There are many reasons why they are harder than others, such as chess endgames:

• Although each local endgame area is isolated, the whole endgame is not. Even if a computer can play each local endgame area flawlessly, we cannot conclude that it can play flawlessly when they are put all together. Some additional areas to deal with include Sente & Gote relationships, prioritization of different local endgames, as well as territory counting & estimation
• endgame may involve many other aspects of go, including life and death which are also known to be NP-hard.
• each local endgame area may affect one another to form a global relationship. In other words, they are dynamic in nature although visually isolated. This makes it much more difficult for computers to deal with. This nature leads to some very complex situations like Triple Ko, Quadruple Ko & Moonshine Life.

After consideration of all the above, it is very unlikely to be able to find a reasonably fast algorithm for playing go endgames flawlessly, let alone the whole go game.

Challenges

Computer go is not like computer 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 marginally 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 learned 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.

Board size

A large board (e.g. the full-size go board at 19×19) 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 to the extent that it prevents an alpha-beta searcher without significant search extensions or pruning heuristics from achieving deep look ahead.

So far, the largest game of go being completely solved is just 5×5 board. It was achieved in 2002, with black winning by 25 points (the entire board), by a computer program called MIGOS (MIni GO Solver).

Algorithms

The fact that computer go programs were significantly weaker than computer chess programs served to generate research into many different programming techniques. The techniques which proved to be the most effective in computer chess have generally shown to be mediocre at 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.

Formerly, the most success was made by programs which utilize large amounts of expert knowledge, but new techniques are continually being researched, developed, and improved. Most recently, the most effective method has been brute-force learning: the computer plays enormous numbers of games against itself.

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.

Evaluation function

Another problem comes from the difficulty of creating a good evaluation function for go. More than one move can be regarded as the best depending on how you use that stone and what your strategy is. In order to choose a move, the computer must evaluate different possible outcomes and decide which is the 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.

Combinatorial problems

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.

Tactical search

One of the main concerns for a go player is which groups of stones can be kept alive and which can be captured. This general class of problems is known as life and death. The most direct strategy for calculating life and death is to perform a tree search on the moves which potentially affect the stones in question, then record the status of the stones at the end of the main line of play.

However, within time and memory constraints, it is not generally possible to determine with complete accuracy which moves could affect the life of a group of stones. This implies that some heuristic must be applied to select which moves to consider. The net effect is that for any given program, there is a trade-off between playing speed and life and death reading abilities.

Data storage

A problem that all go programs must solve is how to represent the current state of the game. For programs that use extensive searching techniques, this representation needs to be copied and modified for each new hypothetical move considered. This need places the additional constraint that the representation should either be small enough to be copied quickly or flexible enough that a move can be made and undone easily.

The most direct way of representing a board is as a 1 or 2-dimensional array, where each space in the array represents a point on the board, and can take on a value corresponding to a white stone, a black stone, or an empty space. Additional data is needed to store how many stones have been captured, whose turn it is, and which spaces are illegal due to Ko rule.

Most programs, however, use more than just the raw board information to evaluate positions. Data such as which stones are connected in strings, which strings are associated with each other, which groups of stones are in risk of capture and which groups of stones are effectively dead is necessary to make an accurate evaluation of the position. While this information can be extracted from just the stone positions, much of it can be computed more quickly if it is updated in an incremental, per-move basis. This incremental updating requires more information to be stored as the state of the board, which in turn can make copying the board take longer. This kind of trade-off is very indicative of the problems involved in making fast computer Go programs.

System design

New approaches to problems

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 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 . Combinatorial Game Theory, a branch of applied mathematics, is a topic relevant to computer Go .

Language choice

Several languages have been used to make successful computer Go playing software, and each language has its own advantages and disadvantages. C and C++ are generally considered to result in faster executables than many other languages, and for this reason programs which perform extensive searches, or have other large performance bottlenecks will often be programmed in C or C++. Examples include GnuGo, Many Faces of Go, and Go++. Handtalk was originally written in even lower-level assembly language.

Java has also been a popular choice for Go software as it provided speeds close to that of C and C++, but takes away some of the technical details such as memory management, that C and C++ programs have to deal with. It also offers an (arguably) cleaner OOP syntax than C++ and, due to its platform independent nature can be run on nearly any platform (or in browsers in the form of applets). This language has been used for several online Go playing applets as well stand-alone projects. The program Gosharp is programmed in C#, which also compiles to speeds close to that of C and C++ and provides memory management assistance.

Several other languages have been used for making Go programs, especially when speed is not as large a concern. Lisp, and Prolog were both designed for AI tasks and are especially well suited for rule based systems.

Design philosophies

The only choice a program needs to make is where to place its next stone. However, this decision is made difficult by the wide range of impacts a single stone can have across the entire board, and the complex interactions various stones groups can have with each other. Various architectures have arisen for handing this problem. The most popular are using some form of tree search, the application of Monte-Carlo methods, the creation of knowledge-based systems, and the use of machine learning. Few programs use only one of these techniques exclusively; most combine portions of each into one synthetic system.

Minimax tree search

One traditional AI technique for creating game playing software is to use a minimax tree search. This techniques involves playing out all hypothetical moves on the board up to a certain point, then using an evaluation function to estimate the value of that position for the current player. The move which leads to the best hypothetical board is selected, and the process is repeated each turn. While tree searches have been very effective in computer chess, they have seen less success in Computer Go programs. This is partly because it has traditionally been difficult to create an effective evaluation function for a Go board, and partly because the large number of possible moves each side can make each leads to a high branching factor. This makes this technique very computationally expensive. Because of this, many programs which use search trees extensively can only play on the smaller 9×9 board, rather than full 19×19 ones.

There are several techniques, which can greatly improve the performance of search trees in terms of both speed and memory. Pruning techniques such as Alpha-beta pruning, Principal Variation Search, and MTD-f can reduce the effective branching factor without loss of strength. Likewise, caching techniques, such as transposition tables can reduce the amount of repeated effort, especially when combined with an iterative deepening approach. In order to quickly store a full sized Go board in a transposition table, a hashing technique for mathematically summarizing is generally necessary. Zobrist hashing is very popular in Go programs because it has low collision rates, and can be iteratively updated at each move with just two XORs, rather than being calculated from scratch. Even using these performance-enhancing techniques, full tree searches on a full sized board are still prohibitively slow. Searches can be sped up by using large amounts of domain specific pruning techniques, such as not considering moves where your opponent is already strong, and selective extensions like always considering moves next to a groups of stones which are about to be captured. However, both of these options introduce a significant risk of not considering a vital move which would have changed the course of the game.

Results of computer competitions show that pattern matching techniques for choosing a handful of appropriate moves combined with fast localized tactical searches (explained above) are sufficient to produce a competitive program. For example, GNU Go is competitive, yet does not have a full-board search.

Monte-Carlo methods

One major alternative to using tree searches is the use of Monte-Carlo methods. This is done by generating a list of potential moves, and for each move playing out hundreds of games at random on the resulting board. The move which leads to the best set of random games for the current player is chosen as the best move. The advantage of this technique is that it requires very little domain knowledge, or expert input. However, because the moves used for evaluation are generated at random it is possible that a move which would be excellent except for one specific opponent response would be mistakenly evaluated as a good move. The result of this are programs which are strong in an overall strategic sense, but are weak tactically. This problem can be mitigated by adding a greater level of search depth on top of the random evolution. Two programs which use Monte-Carlo techniques are Olga and Gobble.

Knowledge-based systems

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."

After implementation, the use of expert knowledge has been proved very effective in programming Go software. Hundreds of guidelines and rules of thumb for strong play have been formulated by both high level amateurs and professionals. The programmer's task is to take these heuristics, formalize them into computer code, and utilize pattern matching and pattern recognition algorithms to recognize when these rules apply. It is also important to have a system for determining what to do in the event that two conflicting guidelines are applicable.

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."

This method has to date been the most successful technique in generating competitive Go programs on a full sized board. Some example of programs which have relied heavily on expert knowledge are Handtalk (later known as Goemate), The Many Faces of Go, and Go++, each of which has at some point been considered the world's best go program.

Nevertheless, 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."

Machine learning

While knowledge-based systems have been very effective at Go, their skill level is closely linked to the knowledge of their programmers and associated domain experts. One way to break this limitation is to use machine learning techniques in order to allow the software to automatically generate rules, patterns, and/or rule conflict resolution strategies.

This is generally done by allowing a neural network or genetic algorithm to either review a large database of professional games, or play many games against itself or other people or programs. These algorithms are then able to utilize this data as a means of improving their performance. Machine learning techniques can also be used in a less ambitious context to tune specific parameters of programs which rely mainly other techniques.

Competitions among computer Go programs

Several annual competitions take place between Go computer programs, the most prominent being the Go event at the Computer Olympiad and the Gifu Challenge in Japan. Regular, less formal, competitions between programs occur on the Kiseido Go Server and the Computer Go Ladder.

Prominent go-playing programs include ZhiXing Chen's Handtalk, Michael Reiss's Go++ and David Fotland's Many Faces of Go. As of 2006, GNU Go is considered the strongest free program.

History

The first computer Go competitions were sponsored by USENIX. They ran from 1984-1988. These competitions introduced Nemesis, the first competetive go program from Bruce Wilcox, and G2.5 by David Fotland, which would later evolve into Cosmos and The Many Faces of Go.

One of the early drivers of computer go research was the Ing Prize, a relatively large money award sponsored by Taiwanese computer magnate Ing Chang-ki of Acer, offered annually between 1985 and 2000 at the World Computer Go Congress (or Ing Cup). The winner of this tournament was allowed to challenge young professionals at a handicap in a short match. If the computer won the match, the prize was awarded and a new prize announced: a larger prize for beating the professionals at a lesser handicap. The series of Ing prizes was set to expire either 1) in the year 2000 or 2) when a program could beat a 1-dan professional at no handicap for 40,000,000 NT dollars. The last winner was Handtalk in 1997, claiming 250,000 NT dollars for winning an 11-stone handicap match against three 8-9 year old professionals. At the time the prize expired in 2000, the unclaimed prize was 550,000 NT dollars for winning a 9-stone handicap match.

Many other large regional Go tournaments ("congresses") had an attached computer Go event. The European Go Congress has sponsored a computer tournament since 1987, and the USENIX event evolved into the US/North American Computer Go Championship, held annually from 1988-2000 at the US Go Congress.

Surprisingly, Japan has only recently started sponsoring its own computer Go competitions. The FOST Cup was held annually from 1995-1999 in Tokyo. That tournament has been supplanted by the Gifu Challenge, which has been held annually since 2003 in Ogaki City.

Problems in computer-computer games

When two computers play a game of Go against each other, the ideal is to treat the game in a manner identical to two humans playing. However, this can be difficult especially during the end game. The main problem is that Go playing software has no capacity to communicate in a dialog with its opponents. So if there is a disagreement about the status of a group of stones, there is no general ways for two different programs to “talk it out” and resolve the conflict. One method for resolving this problem is to have an expert human or well-crafted piece of software judge the final board. However, this introduces subjectivity into the results and the risk that the expert would miss something the program saw. An alternative method is to send a special command to the two programs that indicates they should continue placing stones until there is no question about the status of any particular group. The main problem with this system is that some rules sets (such as the traditional Japanese rules) penalize the players for making these extra moves. Additionally this introduces the risk that a program which was in a winning position at the traditional end of the game (when both players have passed), could be penalized for poor play that is made after the game was technically over.

Notes and references

General references

1. AI-oriented survey of Go
2. Monte-Carlo Go, presented by Markus Enzenberger, Computer Go Seminar, University of Alberta, April 2004
3. Monte-Carlo Go, written by B. Bouzy and B. Helmstetter from Scientific Literature Digital Library
4. Static analysis of life and death in the game of Go, written by Ken Chen & Zhixing Chen, 20 February 1999
5. Co-Evolving a Go-Playing Neural Network, written by Alex Lubberts & Risto Miikkulainen, 2001