JAVA - Go游戏算法

Question

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

我听说洪水填充是最好的，因为递归使用它将是最有效和更容易实现的。

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

这是我的课程之一，它非常自我解释。

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是另一个角色

任何帮助都会很棒！

Answer 1

虽然其他答案在技术上是正确的，但你也缺少与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）

Answer 2

我会用假证明。以下是我如何找到捕获的石头：

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)

Answer 3

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

Answer 4

正如其他人所指出的那样，Go中也有一个“ko规则”，大致意味着当一块石头被捕获时（简化），你不能立即捕获。总之，您可能希望使用现有库。

我推荐使用maug中的brugo存储库。

<!-- 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()

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

如果您还打算使用javafx，那么运行此演示：brugo.go.ui.javafx.goban.GobanComponentDemo

足够让你入门。

Some background about Brugo

http://www.brugo.be是一个在2008年左右创建的PHP网站，这是一个在线joseki字典，显然需要一些代码来处理Go职位。所以，所有这些都是用PHP编写的。大约一年后，它开始使用一些Java小程序（当时仍然“正常”），这样可以更容易地浏览位置。因此，go逻辑的代码被移植到Java。

后来有一些努力也将它用于AI和客户端/服务器应用程序，但没有成功。大约在这个时候，Java代码得到了大量改进，以支持不同的文件编码。

但是在2015年左右，代码被移植到javascript，并在2017年左右移动到打字稿，试图升级布鲁戈网站。再次没有直接的成功。

在2018年左右，有计划将Java代码用于特定的开源项目（AI再次相关），但从未实现过。但是当时它集中在maven中。

在那段时间里，由于LeeLa Zero的成功，开源Go项目大幅增加。这也是为什么brugo的java代码是开源的动机。

2019年初http://www.zbaduk.com推出（现在非正式），重新使用BruGo的打字代码，并使用LeeLa Zero项目进行人工智能。