Jump to content

Computer Go programming

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by 206.69.212.103 (talk) at 16:14, 6 April 2006 (→Problems that arise in Computer-Computer games). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Computer Go programming has long been considered a strong challenge in the field of AI. The fact that computer Go programs are significantly weaker than computer chess programs has 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. So far, the most success has been made by programs which utilize large amounts of expert knowledge, but new techniques are continually being researched, developed, and improved.

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.

One traditional AI technique for creating game playing software is to use a 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 9x9 board, rather than full 19x19 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 speed 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.

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

The use of expert knowledge has been very effective in programming Go software. Hundreds of guidelines and rules of thumbs 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. 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 Geomate, Handtalk, The Many Faces of Go, and Go Plus Plus, each of which has at some point been considered the world's best go program.

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.

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.

State representation

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

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

Java as well has been a popular choice for Go software as it provided speeds close to that of C and C++, but offers more memory management support and platform independency. 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. C#, like Java, also has the benefit of a wide variety of standard libraries to assist in programming.

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.

Problems that arise 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.

See also

General Computer Go Information

Computer programs

References

  1. [1] AI-oriented survey of Go
  2. [2] Monte-Carlo Go
  3. [3] Monte-Carlo Go
  4. [4] Life and Death
  5. [5] Co-evolution and Neural Networks
Retrieved from "https://en.wikipedia.org/w/index.php?title=Computer_Go_programming&oldid=47267810"