A Graph Theory Explanation

Go is traditionally played on a 19 by 19 grid, but we can make a more general definition and consider the 19 by 19 version as a special case. Specifically, we define a Go-board to be a graph $G$ whose verticies can take on three values; empty, black, and white. A Go-game then can be an ordered quadruple $(G_{cur}, S, P_b, P_w)$ , where $G_{cur}$ is the current board, $S$ is the set of past boards² $\{G_0, G_1, \ldots , G_{n-1}\}$ , and $P_b$ and $P_w$ are the amounts of prisoners possessed by each of black and white.

Implementing the rules on this structure requires a formal definition of the lifting and coe rule checking processes. For the former we first note that we have a nice property of lifting: if any pieces are to be lifted at all they must be or border the piece just played, or else they would have been lifted on a previous turn. We then only have to branch our recursion out from the piece just played.

Figure 1: Algorithm Lift

This algorithm is implemented in figure 1 as Lift. It uses two subroutines, the first of which, isSafe, determines recursively if a block of pieces of like color is safe from lifting. If any piece within the block borders an empty space then the whole block is declared safe. The second is removeBlock, a procedure that gets invoked once we decide that a block of pieces should be lifted. It does the actual removal from the board and updates the prisoner counts. It would be possible to combine these two routines into one procedure for an algorithm faster by a constant, but that would give messier code.

The main routine uses isSafe to check each opposite color piece adjacent to the one that was just played to see if it forms a block that should be lifted, using removeBlock on any that should be. Then it looks at the piece just played to see if it is in a block of same color pieces that should be lifted. If so, it goes ahead and lifts them. This leaves us with updated board and prisoner counts.