在Go棋盤遊戲中捕獲棋子

Question

我正在嘗試在Java中重新創建棋盤遊戲「go」。我目前正在研究捕捉系統。基本上，一旦一塊石頭四面都被敵人的石頭包圍（對角線不計算在內），你就會移除那塊石頭。就像下面的截圖一樣。

或者，如果同樣的石頭多個連接，你必須圍繞所有打開的側面。就像下面的截圖一樣。

在這兩種情況下，黑寶石應在此時被刪除。這個鏈接更詳細地解釋了捕捉石塊的規則。 societies.cam。 AC。 uk /cugos/go/rules_03.html

我被告知最好使用遞歸來做到這一點。在對遞歸進行一些研究之後，我設法編寫了一些代碼。但它不起作用。它似乎只是在遊戲的第二步中發現敵人的石頭。每次在我的鼠標放置一塊石頭時，我都會打電話給我的方法。

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是我的行，此舉是我的變量保持輪到誰（1 =黑，2 =白色）板是我保存的位置的二維陣列棋盤上的所有石塊。

Answer 1

我認爲遞歸複雜化這個解決方案超過了必要的。如果我要實現這樣的事情，我會採取以下步驟：

1. 查找關聯的羣組。如果您可以檢測到一個組是否存在，因爲它有兩隻眼睛，您可以將其限制爲只有龍。

2. 對於每組相連的寶石，計算垂直和水平的自由度。 （自由人是與相連的一組寶石相鄰的空閒位置。）如果自由度數爲0，則該組被捕獲。

如果你檢查捕獲的舉動作出後，那麼你真的只需要檢查其鄰近的最新舉動，並非所有的連接組連接組。

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

在這種情況下遞歸的問題是它很容易陷入無限循環。檢查兩塊石頭，檢查右邊的石頭將檢查左邊的石頭再次檢查右邊等等。你需要跟蹤你已經檢查過的石頭。你將需要通過你已經檢查過的寶石狀態。

Answer 4

我有一些代碼，可以讓你玩和捕捉寶石。看到這個答案：https://gamedev.stackexchange.com/questions/23291/go-game-placing-stones-on-grid-intersections/23406#23406

訣竅是跟蹤連續的石頭塊，然後檢查每一步之後，看看該移動是否捕獲塊。

還有ko擔心。