Computer Go/Processing a Move

Processing a MoveEdit

Now that we have the ability to detect legal moves, the next step is to actually process legal moves by adding the new piece to the board, removing any captured pieces, and updating the ko point. We are already able to detect when captures take place:

} else if (getColor(neighbor) == c.opposite()) {
        // if any neighbor is an enemy
        // and that enemy is in atari
        if (inAtari(neighbor)) {
                suicide = false;
        }
}

All we need to do now is update this code to remove the captured stones. By now it should be obvious that a way of representing chains would be considerably useful. Let's modify our previous getLiberties() code to return a chain rather than a set of liberties.

private Set<Point> getChainPoints(Board b, Point p) {
        Set<Point> stones = new HashSet<Point>();
        stones.add(p);
        
        Color myColor = b.getColor(p);
        Color floodfillColor = myColor.opposite();
        b.setColor(p, floodfillColor);
        
        List<Point> neighbors = b.getNeighbors(p);
        for (Point neighbor : neighbors) {
                if (b.getColor(neighbor) == myColor) {
                        if (!stones.contains(neighbor)) {
                                stones.addAll(getChainPoints(b, neighbor));
                        }
                }
        }
        
        return stones;
}

Given the set of stones that make up a particular chain, we can also easily obtain the set of empty points adjacent to the chain, and construct an object that contains both sets.

private Chain getChain(Point p) {
        Set<Point> stones = getChainPoints(clone(), p);

        Set<Point> liberties = new HashSet<Point>();
        for (Point stone : stones) {
                for (Point point : getNeighbors(stone)) {
                        if (getColor(point) == EMPTY) {
                                liberties.add(point);
                        }
                }
        }
        
        return new Chain(stones, liberties);
}

The modified code to remove captured stones from the board now becomes quite straightforward:

} else if (getColor(neighbor) == c.opposite()) {
        // if any neighbor is an enemy
        // and that enemy is in atari
        
        Chain enemy = getChain(neighbor);
        if (enemy.inAtari()) {
                suicide = false;

                // remove the enemy stones from the board
                for (Point point : enemy) {
                        setColor(point, EMPTY);
                        capturedStones.add(point);
                }
        }
}

By saving the captured stones in a set, we can now easily update the ko point.

// If this move captured exactly one stone, that stone is the new ko point
if (capturedStones.size() == 1) {
        koPoint = capturedStones.iterator().next();
} else {
        koPoint = null;
}

If you would like a copy of all the source code used in this chapter in a format ready to compile and run, you can download a copy of the sample code here.

Last modified on 24 June 2006, at 09:32