java - 在围棋棋盘游戏中捕获石头

Question

我正在尝试用 Java 重新创建棋盘游戏“go”。我目前正在研究捕获系统。基本上，一旦一块石头在所有四个侧面都被敌方石头包围（对角线不算在内），您就可以移除该石头。就像在下面的屏幕截图中一样。

或者，如果连接了多个相同的石头，则必须围绕所有开放的边。就像在下面的屏幕截图中一样。

在这两种情况下，此时都应移除黑色石头。这个链接解释了更多关于捕获石头的规则。社会.cam。交流。英国 /cugos/go/rules_03.html

有人告诉我最好使用递归来做到这一点。在对递归进行了一些研究之后，我设法编写了一些代码。但它不起作用。它似乎只在游戏的第二步检测到敌人的石头。每次将一块石头放在我的 mouseReleased 中时，我都会调用我的方法。

public static boolean checkCapture(int x, int y)
{
    {
        if ((board[x][y + 1] != move) && (board[x][y + 1] != 0)) //bellow
        {
            System.out.println("enemy is bellow");
            if (checkCapture(x, y + 1))
                board[x][y] = 0;
        } else if (board[x][y + 1] == 0)
        {
            return false;
        }

        if ((board[x][y - 1] != move) && (board[x][y - 1] != 0)) //above
        {
            System.out.println("enemy is above");
            if (checkCapture(x, y - 1))
                board[x][y] = 0;
        } else if (board[x][y - 1] == 0)
        {
            return false;
        }

        if ((board[x + 1][y] != move) && (board[x + 1][y] != 0)) // right
        {
            System.out.println("enemy is right");
            if (checkCapture(x + 1, y))
                board[x][y] = 0;
        } else if (board[x + 1][y] == 0)
        {
            return false;
        }

        if ((board[x - 1][y] != move) && (board[x - 1][y] != 0)) //left
        {
            System.out.println("enemy is left");
            if (checkCapture(x - 1, y))
                board[x][y] = 0;
        } else if (board[x - 1][y] == 0)
        {
            return false;
        }
    }
    return true;
}

我的 int x 是我的列，我的 int y 是我的行，move 是我的变量，轮到谁了（1 = black，2 = white） board 是我的二维数组，它保存了棋盘上所有棋子的位置。

Answer 1

I think that recursion complicates this solution more than necessary. If I were to implement something like this, I would take the following steps:

1. Find connected groups of stones. You can limit this to just dragons if you can detect if a group is alive because it has two eyes.

2. For each group of connected stones, count the liberties vertically and horizontally. (Liberties are unoccupied locations adjacent to a connected group of stones.) If the number of liberties is 0, then the group is captured.

If you are checking for a capture after a move has been made, then you really only need to check the connected groups which are adjacent to the most recent move, not all connected groups.

Answer 2

首先，首先要明确您的函数的作用。

/**
 *  Checks to see if the grid point passed in is captured.
 *  @param...(you should say what your params are here
 **/
public static boolean checkCapture(int x, int y) {
   //some code
}

这很重要：如果此函数检查网格点是否正在捕获其他任意点怎么办？此外，我们立即看到一个问题……被谁捕获了？每当解决递归问题时，您都需要了解基本情况：这里没有未被敌人占领的垂直或水平相邻区域。

因此，我们必须检查以查看特定颜色：

/**
 *  Checks to see if the grid point passed in is captured.
 *  @param...(you should say what your params are here
 **/
public static boolean checkCapture(int x, int y) {
   if (!isOccupied(x,y)) {//writing this function should be trivial
     return false;//can't be captured; no one is there!
   }

   Color color = getColor(x,y);//similarly, get the color of whoever is there.
   Status status = checkFlanked(x, y, color);
   if (status = Status.FLANKED) {
     return true;
   }
}

private static Status checkFlanked(int x, int y, Color color) {
   //check to see that this location is valid for the board
   //check to see if this square is occupied at all
     //if it is not, return LIBERTY (an empty space means no capture, right?)
     //if it is, is it occupied by the opposite color? --> Return a FLANKED result!
     //if it is, is it occupied by the same color? --> recurse!
}

现在我们已经分解了我们的问题！并且很容易看出基本情况是如何解决的：如果正方形未被占用，则它不能在侧翼......所以它返回一个LIBERTY结果。如果它被相反的颜色占据，那么这个方块就在你最初检查的人的两侧。然后唯一困难的部分是检查，在被原始颜色占据的情况下，任何其他位置是否具有自由。

 //get all valid adjacent locations
 //call checkFlanked on those locations.
 //If any return LIBERTY, return LIBERTY. Otherwise return FLANKED.

（注意：为了清楚起见，我假设LIBERTY并被FLANKED定义为枚举。）

我希望这可以帮助您以更明智的方式解决问题。请记住：当您使用递归时，您关心两种情况：基本情况和“+1 迭代”情况。请注意，即使使用上述方法，您也必须解决一些问题：

• 您需要智能地不递归回您已经访问过的广场。（研究尾递归，但您也可以只传递其他状态，指示已经检查过的方块。）
• 你需要确保你不会从板上掉下来，如果你掉下来的话，你需要返回一个适当的结果。基本上，您需要解决“什么是有效位置？” 问题。

其他一些有趣的问题是：

• 你是按广度还是按深度搜索？
• 这是否适合作为静态方法，还是应该在类中捕获？

Answer 3

我有一些代码可以让你玩和捕获石头。看到这个答案：https ://gamedev.stackexchange.com/questions/23291/go-game-placing-stones-on-grid-intersections/23406#23406

诀窍是跟踪连续的石头块，然后在每次移动后检查该移动是否捕获了块。

还有ko要担心。

Answer 4

在这种情况下，递归的问题是很容易陷入无限循环。检查两块石头，检查右边的石头会检查左边的石头会再次检查右边等等。你需要跟踪你已经检查过的石头。您将需要通过您已经检查过的石头的一些状态。