Go Artificial Intelligence
By ai-depot | June 30, 2002
Search Space Complexity
As the last section showed, there are few rules to Go, and it is the game’s simplicity that, for me anyway, makes it so elegant and fascinating. However, despite the simplicity of the rules compared to chess, the complexity of trying to solve or at least play the game well, is absolutely huge.
Complexity
Although in the same category of games as chess (i.e two player, rule-based, perfect information, zero sum games), Go is too difficult a game for ordinary game AI techniques (namely minimax with alpha-beta pruning) to be enough. This is mainly due to the shear enormity of the game tree.
Seach Space
The search space for Go’s game tree is both wider and deeper than that of chess. It has been estimated to be as big as ~10170 compared to ~1050 for chess, making the normal brute-force game tree search algorithms much less effective. As we’ll see later-on there is also very little pruning that can be done on the move tree as a whole, since there is, as yet, no good evaluation function to use as a heuristic.
Some of the factors responsible for the game tree’s enormity are shown below. (A comparison to chess is shown in brackets)
- the size of the board : 19×19 (8×8)
- the average number of moves per game is around 300 (80)
- the average branching factor at each turn is around 235 (35)
- players can pass
Evaluation Function
In Chess there exist several evaluation functions used to give an estimate of the relative merit of a board configuration. These functions allow tree-search algorithms to prune the search tree, and to help pick the optimal move.
A simple material evaluation for chess that works well, where each type of piece is given a value (see diagram on the right), and each player recieves a score depending on his/her remaining pieces. The player with the higher score is deemed to be ‘winning’ at that stage of the game.
Image 4: Weighting the importance of pieces in chess.
However, Chess programmers innocently asking Go players for an evaluation function would be met with disbelief! For no such simple evaulation has been found yet. Since there is only a single type of piece only the number each player has on the board could be used for a simple material heuristic, and there is almost no disernable correlation between the number of stones on the board and what the end result of the game will be.
The lack of such an evaluation function provides another challenge to Computer Go, without a simple heuristic other methods more varied than modified, enhanced minimax are going to have to be used.
Human Factors
If a computer program is going to be developed to play Go and beat Humans, then some of the curiousities that occur when we play should be taken into account.
Lookahead
Even beginners in Go can achieve lookahead of around 60 moves in specific cases such as ladders, while you’d have to be a grandmaster at chess to be able to look a meagre 10 moves ahead. Should a computer be able to search the game tree very deeply down specific branches, and merely a few moves down others? Of course it should, but achieving this is easier said than done.
Horizon Effect
When searching a game tree to a depth n, the horizon effect occurs when searhing to depth n+1 would result in the evaluation of a move being drastically different. Examples of this include Queen exchanges in Chess, and ladders in Go. Another major difference between the games is that in many occasions only grandmasters of Chess have full grasp over the horizon effect, whereas beginners at Go quickly pick up the concept. This adds to the problem of lookahead.
Psychological Gouping
A psychological study was undertaken in which the aim was to find out how players of Chess and Go viewed the board internally, how they made links between groups of pieces. The major outcome of this research was that for Chess players find it very easy to assign each piece to a single group, wheras for Go stones bore no relation to each other until the very end of the game. It was almost impossible to see which group an individual stone belonged to, and in fact players mentally placed stones in more than one group. This bears heavily on the representation of the game in an AI player. How should it determine which stones belong to which groups? If we have so much trouble, how can we expect a computer to be able to do it!
Next we’ll look at how the current Go programs have evolved, and how they perform.
Tags: none
Category: essay |
March 2nd, 2008 at 9:22 pm
Very interesting, thanks.