Cracking GO

Dead or Alive?

To play any board game well you have to assess the situation on the board astutely, over and over again. For go, doing this involves determining whether a group of connected, like-colored stones (yours or your opponent’s) is “alive” or “dead.” Stones that cannot be captured are alive; spaces that are surrounded by living groups of the first side that cannot sustain living groups of the second side belong to the first side. the game ends when both sides agree on the final disposition of territory.

The challenge of go comes from the fact that analyzing whether a group of like-colored stones is likely to live or die can be a hugely tricky affair. In the figure below, the black stones are unconditionally alive as they have two “eyes,” indicated by A and B. the liberties A and B cannot be occupied by white (for a white stone placed in either spot would itself be dead), and therefore black stones cannot be captured no matter what.

However, the situation is usually more complicated, and to judge whether a group is alive or dead the program must search many moves ahead. In the figure below, if black places a stone on C, then the black stones will live, but not unconditionally. that is, black may have to make additional moves to keep the stones alive if white plays nearby. For instance, if white plays on any of the points marked in red, then black will have to respond appropriately—and immediately—to keep the black group alive.

Consider the black stone labeled D. If the nearby green spaces are occupied by white and black doesn’t react right away, then white can kill black by playing on the space to the right of stone D. If black captures the new stone, then white plays on the space above stone D and destroys the eye. If black connects by playing on the space above stone D, then white captures the four newly connected stones, killing the entire group.

A program would have to follow these branching possibilities to see whether the black stones are alive or dead, a far more arduous job than simply counting up men and positional features, as in chess.