Computer go programming: Encyclopedia II - Computer go programming - Design philosophies

Computer go programming - 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.

Computer go programming - Tree search

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.

Computer go programming - 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.

Computer go programming - 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.

Computer go programming - 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.

Adapted from the Wikipedia article "Design philosophies", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki