Go Artificial Intelligence
By ai-depot | June 30, 2002
The Rules
Before we delve into the difficutlies and challenges of playing computer Go, a brief overview of the rules would probably be a good idea. If you are familiar with the game then feel free to move right along to the next section.
The Rules
The rules that govern Go are very simple. It is essentially a territorial game, with each player trying to claim areas of the board as their own. There is only one type of piece, known as a stone, one player plays white, and the other uses black.
The board is a 19×19 grid made from intersections of horizontal and vertical lines (a smaller board of size 9×9 or 13×13 is used for teaching and beginners).
The game starts with an empty board and at each turn players may either place one of their stones onto an intersection, or they can pass. Once a stone has been placed onto the board it cannot be moved. Individual stones can be joined to form groups, or strings, and it is with these that players surround and capture territory.
Image 2: One liberty on the left of the black stone.
A stone, or group of stones, has a number of liberties. (A liberty being an empty, adjacent intersection). If a player succeeds in capturing all of a group’s liberties, the captured string is removed from the board and count toward that player’s prisoners. For example, if White where to play at point A in the diagram on the right, he would have taken the black stone’s remaining liberty and it would be removed from the board. Capturing stones is the only possible way in which stones that have been played can move.
The game ends when both players pass in succession, meaning the game finishes when both players decide there are no more moves that would be advantagous. That is to say a player should pass when adding a stone to the board will either lessen their own territory, or give an unnecessary prisoner to their opponent.
Apart from ko, a rule which forbids a move to be made that would repeat an earlier board configuration (in order to prevent infinite loops), these are the only rules Go has. If that wasn’t a good enough explanation, or you’d like to find out more, there are many websites around, but I’d recommend this one.
Game Stages
There are three stages in a game of Go; the opening-game, the middle-game and the end-game. Each requires different move strategies. The opening game usually consists of moves made to try and stake a claim for areas of the board and results in individual stones spread about the board.
The middle-game consists of extending the lone stones into groups in order to defend the territory you want, or to threaten the opponent’s areas. This results in many small battles all over the board.
Image 3: A finished game with white ending up on top.
The end-game involves moves that are used to ensure territory will remain yours, and moves that have been delayed due to their inevitability. The Figure on the left shows a finished game, with territory marked out.
Since there are three stages of game playing, each with their own strategies, good and bad moves, each should be viewed differently when teaching a machine to play the game, and we shall see this is one of the major difficulties in Computer Go.
A great feature of Go is that there is a very good handicap system enabling players of varying standards to play an evenly matched game. The weaker player receives a number of handicap stones, determined by the difference in skill levels of the players, which are placed on the board, in pre-defined positions, before the game begins.
This means that playing against weaker or stronger players also requires different strategies: if playing with handicap stones the main objectives become to defend the territory you have already staked a claim to by playing defensively. Whereas if playing against someone with handicap stones the strategy should more of an attacking one in order to to reduce the territory the opponent will have in the endgame.
Now that everyone hopefully knows enough of the game to understand its complexity lets move onto discussion the problems that popular game AI methods have in playing Go.
Tags: none
Category: essay |
March 2nd, 2008 at 9:22 pm
Very interesting, thanks.