计算机围棋/识别非法走棋
< 计算机围棋
一个非Pass的棋步是合法的，如果该点是空的，该点不违反Ko规则，并且该棋步不是自杀。如果以下任一条件成立，则该棋步不是自杀
- 任何相邻的点都是空的
- 任何相邻的点都是相同颜色，并且拥有超过一个自由
- 任何相邻的点都是不同颜色，并且只有一个自由
从我们目前的代码来看，我们可以确定一个点是否为空，以及一个点是否违反Ko规则。现在我们需要的是循环遍历某个点的相邻点的代码，以及确定给定棋组自由数的代码。
第一个是微不足道的
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;
}
确定给定棋组的自由数有点困难。由于任何给定棋组的自由数都是重要的信息，并且会被频繁访问，所以大多数程序会存储棋盘上所有棋组（及其自由数）的列表，并对其进行增量更新，而不是每次需要时都重新计算。我们首先使用一种更简单的方法： 洪泛填充.
该算法从目标点开始，将其更改为相反颜色，然后递归地在原始颜色的所有相邻点上执行该算法。通过记住所有相邻的空点，我们可以确定该棋组的自由数。
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;
}
不幸的是，该算法会改变棋盘，所以我们需要确保我们只在棋盘的副本上执行它。
private boolean inAtari(Point p) {
return clone().getLiberties(p).size() == 1;
}
现在我们拥有了确定给定棋步是否合法的所有资源。
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;
}