Computer Go/Recognizing Illegal Moves
Recognizing Illegal Moves edit
A non-passing move is legal if the point is unoccupied, the point is not illegal due to the Ko rule, and the move is not suicide. A move is not suicide if any of the following conditions holds true:
- any neighboring point is empty
- any neighboring point is the same color and has more than one liberty
- any neighboring point is a different color and has only one liberty
From the code we currently have, we can determine if a point is unoccupied and if a point is illegal due to the Ko rule. What we need now is code to loop through the neighbors of a particular point, as well as code that will determine the number of liberties of a given group.
The first is trivial:
private List<Point> getNeighbors(Point p) {
List<Point> neighbors = new ArrayList<Point>();
if (p.x > 0) neighbors.add(new Point(p.x - 1, p.y));
if (p.x < boardSize - 1) neighbors.add(new Point(p.x + 1, p.y));
if (p.y > 0) neighbors.add(new Point(p.x, p.y - 1));
if (p.y < boardSize - 1) neighbors.add(new Point(p.x, p.y + 1));
return neighbors;
}
Determining the number of liberties of a given group is a little more difficult. Because the number of liberties of any given group is important information that is accessed frequently, most programs store a list of all groups on the board (and their liberties) and update it incrementally, rather than calculate it every time it is needed. We'll start out using a much simpler method: flood fill.
This algorithm starts at the point in question, changes it to the opposite color, and then recursively performs the algorithm on every neighboring point of the original color. By remembering all neighboring empty points, we can determine the number of liberties of the group.
private Set<Point> getLiberties(Point p) {
Set<Point> liberties = new HashSet<Point>();
Color myColor = getColor(p);
Color floodfillColor = myColor.opposite();
setColor(p, floodfillColor);
List<Point> neighbors = getNeighbors(p);
for (Point neighbor : neighbors) {
if (getColor(neighbor) == myColor) {
liberties.addAll(getLiberties(neighbor));
} else if (getColor(neighbor) == EMPTY) {
liberties.add(neighbor);
}
}
return liberties;
}
Unfortunately this algorithm changes the board, so we need to make sure that we only ever perform it on a copy of the board.
private boolean inAtari(Point p) {
return clone().getLiberties(p).size() == 1;
}
Now we have all the resources required to determine if a given move is legal.
public boolean isLegal(Point p, Color c) {
// Is the point already occupied?
if (getColor(p) != EMPTY) {
return false;
}
// Is the move ko?
if (p.equals(koPoint)) {
return false;
}
// Is the move suicide?
boolean suicide = true;
for (Point neighbor: getNeighbors(p)) {
if (getColor(neighbor) == EMPTY) {
// if any neighbor is VACANT, suicide = false
suicide = false;
} else if (getColor(neighbor) == c) {
// if any neighbor is an ally
// that isn't in atari
if (!inAtari(neighbor)) {
suicide = false;
}
} else if (getColor(neighbor) == c.opposite()) {
// if any neighbor is an enemy
// and that enemy is in atari
if (inAtari(neighbor)) {
suicide = false;
}
}
}
if (suicide) {
return false;
}
// If the point is not occupied, the move is not ko, and not suicide
// it is a legal move.
return true;
}