History and AI

In many classical AI games, tree search is all that is needed and it can be viewed as a black box that when provided with an evaluation function, will search the game tree and give out the optimal move. As we've seen with Go though, things will never be that simple. The global game tree is too large to search, and more-over there is no good evaluation function to use.

A Brief History

Dispite all we've seen so far on the complexity, there have been some reasonable successful programs developed. One of the best Computer Go players is The Many Faces of Go which is rated on the Go handicap system at 6 kyu (the same as an average humn player with about 1 year experience). Lets take a brief look at how the modern day approaches to playing Go have evolved.

Influence Functions

Very early on came the concept of a stones influence on its surrounding intersections. In fact the very first Go programs solely used an influence function in order to generate possible moves. Unfortunately these programs could only beat an absolute beginner at Go.

Another major contribution made by one of the first Go programmers, Zobrist, was to devise a general and efficient method of hashing a board position. This was to be used in some form in every Go program developed since. In a nut shell, he associated a random hash value with every possible move in a game, and the hash for a certain board configuration is the XOR of all the moves made to reach it.

Machine Learning

Another important part of Go programs which was introduced at an early stage was that of learning. Like many game AI's, getting a program to try to teach itself an evaluation function is much easier, and often results in a better function than hand-coding one.

a game in progress

In true computer science manner, people have been trying to divide and conquer the overall task of playing Go, in order to make the domain of a learner much smaller, and hence the complexity much lower. They have worked on sub-problems of the game such as either playing on a smaller board, or on localised problems such as the life and death of a group.

Abstract Representations

Bruce Wilcox designed the first program which played better than an absolute beginner. It used abtract representations of the board, and tried to reason about groups of stones rather than just individuals. He also divided the board into zones, and reasoned about these zones seperately. Once divided into zones Wilcox could start to apply some of the techniques people used in their sub-problems enabling him to solve local taks before attempting to make a global assement of the game.

Pattern Matching

Although pattern matching had been used to some extent in the early influence based programs, it was now that the real breakthough came. People began to use patterns intensively to suggest moves rather than make them. Typical situations could be matched without any game tree search and one a particular pattern had been seen a sequence of moves known to defeat that particular attack, or an attack garuenteed to capture stones can be recognised without great complexity. This requires databases of moves and patterns to be stored of course, and this soon became standard in a Go program. There is a database available to all known as the Joseki database. This contains thousands of endgame positions and optimal plays for each. Many human Go masters know most of them so to that end it doesnt seem like cheating to store them in a Computer player (except a computer has perfect recall).

The Present

Current programs use all of the above techniques, most of them relying on rapid tactial searches, slower searches involving smaller subgames, and eventually a small search on the global tree. They invariably use patterns and abstract representations of the game. They normally have an evaluation module which breaks the game down and suggests possible moves with an associated priority, and an overall tacital move maker which looks at each suggested move and checks it won't lead to immediate disaster using a small lookahead on the global tree. The Many Faces of Go uses several local game tree searches in order to determine whether a group of stones is alive (cannot be captured) or dead (cannot avoid being captured) for example.

Read on for a taster of what's to come in Computer Go

Remember you can visit the Message Store to discuss this essay. Comments are always welcome!. There are already replies in the thread, why not join in?