計算機圍棋/識別非法走棋
< 計算機圍棋
一個非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;
}