Oh yeh, the Rules!

Well ok, so now we can detect some nice geometrical shapes, but we haven't really related it to the game of Go as such.  To do that we need to teach the computer a bit about the rules, so that it can at least process the effects of a move, and determine whether a proposed move is legal or not.

Fortunately Go has very few rules - all the complexity flows from their application.

So, here are the basics:

1) The game has two players, one taking the black stones, the other the white. 
2) Players take alternating turns, beginning with black.  On each turn a player places one stone of his or her own colour on a vacant intersection of the board.  A player may choose to pass rather than play if they wish to.
3) Stones are captured if they have no liberties.  To define what this means we need to talk a bit about some basic concepts.  I'll do that in a moment.  First lets quickly finish up on the remaining rules
4) It is illegal to play a stone in such a way that it would immediately have no liberties unless by doing so it captures one or more opposing stones and thus gains one or more liberties in the resulting position (no suicide)
5) It is illegal to play in such a way as to repeat a previous position (strictly this is a generalised variant of a slightly harder-to-state rule called the 'ko' rule, but we'll just go with the easier-to-understand generalisation (which means we'll be playing what are called 'Chineese rules'))
6) The game terminates after 3 consecutive passes, after which the winner is determined by adding up the territory owned by each player + any captured stones they have gained during play (more on territory below)

So this all boils down to two concepts, which need better definition:

Liberties

A 'liberty' is a vacant intersection adjacent (directly - no diagonals) to a connected set of stones.  You'll find rule books tend to talk about liberties of a 'group' but I'm going to reserve that term for a more general concept that better equates to the way Go players use it when talking about positions.  Instead I will henceforth use the term cluster for a connected set of stones.  The highlighted stones in the diagram below are all examples.

The vacant intersection directly adjacent to the stones of each cluster are its liberties.  These are illustrated below:

So the cluster of a single stone (left) has 4 liberties, the 2-stone cluster 6 and so on.  Now we can examine what rule (3) (Stones are captured if they have no liberties) means.  In the position below the black stones would be captured if white played at the highlighted point, as this is their only remaining liberty:

Captured stones are removed from the board, and each counts as one point when the scores are determined at the end of the game.

Territory

The final concept we need then is territory.  At the end of the game players agree which stones that have not actually been captured are anyway  'dead' (what this boils down to is stones which both players agree would be captured regardless of anything the owning player could do if they chose to play things out locally).  A simple example of  a dead stone is shown below - because it is obviously futile for white to play further stones (each of which will ultimately be one more point for his opponent when eventually captured) he will not do so.  In the event of a disagreement between the players over what is dead, the onus is on the player claiming they are not to demonstrate he can forms two eyes (see below) and thus avoid capture).

Because of rule (4) (It is illegal to play a stone in such a way that it would immediately have no liberties unless by doing so it captures one or more opposing stones and thus gains one or more liberties in the resulting position) it is possible to create uncapturable clusters by creating what are known as eyes (which are essentially enclosed vacant intersections).  Consider this position:

White can never capture the black stones because to do so he would have to play at both marked points, but each of them is illegal to play at because of the no-suicide rule.  These marked points are examples of what are known as eyes. Any cluster that can makes 2 eyes is therefore immune to capture.

Once all dead stones are removed each vacant point entirely surrounded by one colour is a point of territory for the player enclosing it.  A player's territory + captures is their final score.  The white player often (though this is more an adjunct than a rule really) is also awarded what is known as a komi, or extra points to compensate for black's advantage in having the first move.  A typical komi (which may vary from tournament to tournament) is 5.5 points (thus avoiding draws).

Finally to illustrate rule (5) (no repeated positions) take a look at this position:

If it is black's move he may play the marked vacant point, capturing the white stone (this is not illegal by the suicide rule because by playing there he captures  a stone and so winds up with a liberty).  However, the result is this:

Which is symmetrical and at first sight could be responded to just by white playing the marked point and recapturing again.  This shape is what is called a ko.  White cannot immediately recapture, because to do so would produce a repeated position.  Instead he must play elsewhere, possibly intending to recapture on his next turn (when the intervening moves will mean the position is not repeated).  If the result of this ko is important (and sometimes games hinge on them) white will play what is called a ko threat elsewhere - this is a move that threatens something dire and must be responded to.  At some point one or other player will run out of threats that their opponent deems severe enough to outweigh winning the ko, and it will be resolved (usually by black filling in the marked point in the last position above, or white in the symmetrical position).

Ok, so I've gone on long enough about the rules.  What about implementing them?

The main thing needed is to track liberties, either dynamically (so evaluate when a stone is played to see if it is a capture) or iteratively (keep track of all the clusters and their liberties so you only have to update those adjacent to the played move each time).  Which will ultimately be more efficient depends on how often you need to ask about the liberties of a cluster, but since it not only underpins legality validation, but also informs position evaluation and move choice I went for an iterative approach to minimise recalculation.  There's no rocket science here so I'm not going to dwell on the details.  The main thing is that the result is a Go-policing game surface (it isn't a player yet) that will perform captures, count captured stones and prevent illegal moves.

As a detail, we can use Zobrist checksums to check for repeated positions, which is well-known technique for games like this to hash a position.  We retain a list of previous position hashes and check that after each move we have a new one.  This technique was invented by Albert Zobrist, who also devised the concept of influence functions for Go programs, which I'll be coming back to in a future post.