0

我正在尝试实现一种算法来清除围棋游戏中的死子。

我听说 Floodfill 是实现这一目标的最佳方法，因为递归使用它会最有效且更容易实现。

我在我的代码中使用它时遇到了麻烦，我想知道我应该如何去实现它。

这是我的一门课，很容易解释。

import java.io.*;

public class GoGame implements Serializable {

    int size;
    char[][] pos; // This is the array that stores whether a Black (B) or White (W) piece is stored, otherwise its an empty character.

    public GoGame(int s){
        size = s;
    }

    public void init() {
        pos = new char[size][size];
        for (int i=0;i<size;i++) {
            for (int j=0;j<size;j++) {
                pos[i][j] = ' ';
            }
        }
    }

    public void ClearAll() {
        for (int i=0;i<size;i++) {
            for (int j=0;j<size;j++) {
                pos[i][j] = ' ';
            }
        }
    }

    public void clear(int x, int y) {
        pos[x][y]=' ';
    }

    public void putB(int x, int y) { //places a black stone on the board+array
        pos[x][y]='B';
        floodfill(x,y,'B','W');

    }

    public void putW(int x, int y) { //places a white stone on the board+array
        pos[x][y]='W';
        floodfill(x,y,'W','B');

    }

    public char get(int x, int y) {
        return pos[x][y];
    }

    public void floodfill(int x, int y, char placed, char liberty){


        floodfill(x-1, y, placed, liberty);
        floodfill(x+1, y, placed, liberty);
        floodfill(x, y-1, placed, liberty);
        floodfill(x, y+1, placed, liberty);

    }

}

x和y是正方形的坐标，placed是放下石头的字符，liberty是另一个字符

任何帮助都会很棒！

4

4 回答 4

2

虽然其他答案在技术上是正确的，但您也缺少更多与 go 相关的逻辑。你需要做的是，我认为（在 B 移动）：

for each W neighbour of the move:
   check that W group to see if it has any liberties (spaces)
       remove it if not

洪水填充对于查找一组石头的范围很有用，但是您的例程需要的远不止这些（我在这里进行了简化，并且还试图猜测该例程的用途 - 请参阅此答案下方的评论）。

鉴于上述情况，识别组中所有石头的洪水填充将是这样的（请注意，它使用第二个数组进行填充，因为您不想pos仅仅为了找到一个组而进行更改）：

public void findGroup(int x, int y, char colour, char[][] mask) {
    // if this square is the colour expected and has not been visited before
    if (pos[x][y] == colour && mask[x][y] == ' ') {
        // save this group member
        mask[x][y] = pos[x][y];
        // look at the neighbours
        findGroup(x+1, y, colour, mask);
        findGroup(x-1, y, colour, mask);
        findGroup(x, y+1, colour, mask);
        findGroup(x, y-1, colour, mask);
    }
}

您可以调用它来识别单个组（并将其复制到掩码中），因此它将帮助您识别与 B 移动相邻的 W 组的成员（例如），但这只是整个逻辑的一小部分你需要。

最后，请注意，如果您想对组中的每一块石头做某事，您有两种选择。你可以像上面那样调用一个例程，然后循环mask查找组，或者你可以将你想要做的动作直接放在例程中（在这种情况下你仍然使用mask控制洪水填充的程度测试&& mask[x][y] == ' '，但您没有使用它作为结果 - 所有工作都在例程返回时完成）。

（按照所有规则编程要正确处理的东西实际上非常复杂 - 你还有很多工作要做......：o）

于 2012-04-10T11:21:08.877 回答
1

我会为此使用虚假证据。以下是我如何找到捕获的石头： 

private static final int SIZE = 8;
private static final int VACANT = 0;       //empty point
private static final int MY_COLOR = 1;     //Black
private static final int ENEMY_COLOR = 2;  //White
private static final int CHECKED = 50;     //Mark for processed points
private static final int OUT = 100;        //points out of the board

private static boolean isCaptured(int col, int row, int[][] board) {
    boolean result = !isNotCaptured(col, row, board);
    cleanBoard(board);
    return result;
}

private static boolean isNotCaptured(int col, int row, int[][] board) {
    int value = board[col][row];
    if (!(value == MY_COLOR || value == CHECKED))
        return true;

    int top = row < SIZE - 1 ? board[col][row + 1] : OUT;
    int bottom = row > 0 - 1 ? board[col][row - 1] : OUT;
    int left = col > 0 ? board[col - 1][row] : OUT;
    int right = col < SIZE - 1 ? board[col + 1][row] : OUT;

    if (top == VACANT || right == VACANT || left == VACANT || bottom == VACANT)
        return true;

    board[col][row] = CHECKED;

    return (top == MY_COLOR && isNotCaptured(col, row + 1, board))
            || (bottom == MY_COLOR && isNotCaptured(col, row - 1, board))
            || (left == MY_COLOR && isNotCaptured(col - 1, row, board))
            || (right == MY_COLOR && isNotCaptured(col + 1, row, board));
}

private static void cleanBoard(int[][] board) {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            if (board[i][j] == CHECKED)
                board[i][j] = MY_COLOR;
        }
    }
}

然后你可以像这样调用方法：

isCaptured(5, 4, board)
于 2016-09-17T09:09:49.690 回答
0

我认为 BFS 对于这种情况会更好，因为你需要先探索邻居，这样如果他们中的任何一个被捕获，那么这个点就会被捕获。

于 2017-02-10T17:37:05.370 回答
0

正如其他人指出的那样，围棋中还有一个“ko规则”，大致意思是当你捕获一块石头时，你不能立即夺回（简化）。总之，您可能希望为此使用现有的库。

我推荐brugo存储库，它在 maven 中可用。

<!-- https://mvnrepository.com/artifact/be.brugo/brugo -->
<dependency>
    <groupId>be.brugo</groupId>
    <artifactId>brugo</artifactId>
    <version>0.1.0</version>
</dependency>

它大致是这样工作的。（警告：代码未经测试）

// create a starting position
Position position = new Position(boardSize, komi);

// play a move
Intersection whereToPlay = Intersection.valueOf(4,4);
IntStatus colorToPlay = IntStatus.BLACK;
Position position2 = position.play(whereToPlay, colorToPlay);

// watch the result.
IntStatus[][] matrix = position2.getMatrix()

它还包含要导出到加载/保存 SGF 的对象。SGF 文件的加载不仅支持UTF-8亚洲编码，还支持亚洲编码。这是一个屏幕截图，显示了实现自己的难度：

部分代码图片

如果您还计划使用 javafx，请运行此演示：brugo.go.ui.javafx.goban.GobanComponentDemo

足以让您入门。

于 2019-04-12T07:27:35.567 回答