MinMax - 生成遊戲樹

Question

我嘗試在Java中編寫一個用於連接四遊戲的MinMax程序，但該程序也應該適用於其他遊戲。但是，我遇到了一個問題，我幾天無法通過。節點的值設置不正確。我分享我負責生成樹的代碼片段。

也許你會注意到我犯了一個錯誤。

如果有人能幫助我，我會很高興。

public Node generateTree(Board board, int depth) { 
    Node rootNode = new Node(board); 
    generateSubtree(rootNode, depth); 
    minMax(rootNode, depth); 
    return rootNode; 
} 

private void generateSubtree(Node subRootNode, int depth) { 
    Board board = subRootNode.getBoard(); 

    if (depth == 0) { 
     subRootNode.setValue(board.evaluateBoard()); 
     return; 
    } 

    for (Move move : board.generateMoves()) { 
     Board tempBoard = board.makeMove(move); 
     Node tempNode = new Node(tempBoard); 
     subRootNode.addChild(tempNode); 
     generateSubtree(tempNode, depth - 1); 
    } 
} 

public void minMax(Node rootNode, int depth) { 
    maxMove(rootNode, depth); 
} 

public int maxMove(Node node, int depth) { 
    if (depth == 0) { 
     return node.getValue(); 
    } 
    int bestValue = Integer.MIN_VALUE; 
    for (Node childNode : node.getChildren()) { 
     int tempValue = minMove(childNode, depth - 1); 
     childNode.setValue(tempValue); 
     if (tempValue > bestValue) { 
      bestValue = tempValue; 
     } 
    } 
    return bestValue; 
} 

public int minMove(Node node, int depth) { 
    if (depth == 0) { 
     return node.getValue(); 
    } 
    int bestValue = Integer.MAX_VALUE; 
    for (Node childNode : node.getChildren()) { 
     int tempValue = maxMove(childNode, depth - 1); 
     childNode.setValue(tempValue); 
     if (tempValue < bestValue) { 
      bestValue = tempValue; 
     } 
    } 
    return bestValue; 
} 

局類是板狀態的表示。

移動類執行移動（整數[0-8]爲井字遊戲，[0-6]爲連接四）。

節點類擁有移動和價值移動是多好。並且，擁有所有的孩子。

在我用這個方法這樣的代碼：

Node newNode = minmax.generateTree(board, depth, board.getPlayer()); 
Move newMove = new TicTacToeMove(board.getPlayer(), newNode.getBestMove().getMove(), depth); 
board = board.makeMove(newMove); 

當很明顯，鑑於此舉是敗着（或獲獎），我沒有收到這個舉動。

Answer 1

好吧，你確實犯了一些錯誤。大約3-4，取決於你如何計數;）我花了一些調試，以弄清楚這一切，但我終於得到了一個答案給你：D

錯誤＃1：你所有的父母總是得到雙胞胎那可憐的母親）

這僅僅是你上傳的代碼，而不是你的問題中的代碼，所以也許我們把它算作是一個錯誤？ 既然你的樹還沒有那麼大，它不會破壞你的算法，反正這是最不重要的。不過，這是值得注意的。 在您上傳的代碼，你在你的generateSubtree方法做到這一點：

Node tempNode = new Node(tempBoard, move, subRootNode); 
subRootNode.addChild(tempNode); 

由於該構造函數已經增加了孩子的subRootNode，第二行總是添加它第二次。

錯誤＃2：織補深度

如果你還沒有達到所需的深度還，但遊戲已經決定，你完全忽略這一點。所以在你提供的例子中，如果 - 例如 - 你看到的是移動7而不是3（這將是'正確的'移動），然後對手移動3，你不會把它算作-10分，因爲你還沒有達到你的深度。它仍然不會得到任何孩子，所以即使在你的minmax，它也不會意識到這是一個錯誤的方式。

這就是爲什麼在這種情況下每一個動作都是'可能的'，並且你只是得到第一個返回。

在之前的動作中，幸運的是總是有一種方法可以讓對手第三步移動（又名第五步），這就是爲什麼這些被正確調用的原因。

好的，那麼我們如何解決它？

private void generateSubtree(Node subRootNode, int depth, int player) { 
    Board board = subRootNode.getBoard(); 
    List<Move> moveList = board.generateMoves(); 

    if (depth == 0 || moveList.isEmpty()) { 
     subRootNode.setValue(board.evaluateBoard(player)); 
     return; 
    } 

    for (Move move : moveList) { 
     Board tempBoard = board.makeMove(move); 
     Node tempNode = new Node(tempBoard, move, subRootNode); 
     generateSubtree(tempNode, depth - 1, player); 
    } 
} 

只需事先獲得移動列表，然後看它是否是空的（你的Board類（感謝上帝的generateMoves()方法，您提供的的方式;））已檢查，如果遊戲結束，因此，如果是，不會有任何動作產生。完美的時間來檢查分數）。

錯誤＃3：再次

織補深入我們不是剛去了呢？

不幸的是，你的Min Max算法本身也有同樣的問題。如果您已達到所需的深度，它甚至只會查看您的值。你需要改變它。

但是，這有點複雜，因爲你沒有一個很好的方法來檢查遊戲是否已經完成。

您可以檢查是否設置了您的值，但問題可能在於：它可能設置爲0，您也需要考慮這一點（因此您不能僅僅執行if (node.getValue() != 0)）。

我只是將每個節點的初始值設置爲-1，而不是對-1進行檢查。這不是......你知道......漂亮。但它的工作。

public class Node { 
    private Board board; 
    private Move move; 
    private Node parent; 
    private List<Node> children = new ArrayList<Node>();; 
    private boolean isRootNode = false; 

    private int value = -1; 
    ... 

這在maxMove：

public int maxMove(Node node, int depth) { 
    if (depth == 0 || node.getValue() != -1) { 
     return node.getValue(); 
    } 
    int bestValue = Integer.MIN_VALUE; 
    for (Node childNode : node.getChildren()) { 
     int tempValue = minMove(childNode, depth - 1); 
     childNode.setValue(tempValue); 
     if (tempValue > bestValue) { 
      bestValue = tempValue; 
     } 
    }    
    return bestValue; 
} 

它的工作原理相同的，當然minMove。

錯誤＃4：播放器擰你

有一次，我改變了這一切，我花了一個時刻與調試明白爲什麼它仍然是行不通的。

這最後一個錯誤不是你在問題提供的代碼btw。真丟臉！ ;）

原來這是您的TicTacToeBoard類這個美好的一段代碼：

@Override 
public int getPlayer() { 
    // TODO Auto-generated method stub 
    return 0; 
} 

而且因爲你在你的TicTacToeMainWindowmakeMove方法稱爲

 MinMax minmax = new MinMax(); 
     Node newNode = minmax.generateTree(board, (Integer) spinner.getValue(), board.getPlayer()); 

，你總是會開始了與錯誤的球員。

正如你可能已經猜到了自己，你只是需要將其更改爲：

public int getPlayer() { 
    return this.player; 
} 

它應該做的伎倆。

另外：

只是一對夫婦的事情，我想在這一點上備註：

• 清理進口！您的TicTacToe實際上仍然導入您的ConnectFour類！沒有理由。

• 您的電路板在您的電路板陣列中旋轉並鏡像。爲什麼？你知道這是多麼煩人的調試？我的意思是，我想你可能會這樣做：D另外，如果你的代碼有問題，而且你需要調試，它會覆蓋你的主板toString()方法非常有用，因爲這會給你一個非常好的和簡單的方法來看待您的電路板在調試器中。你甚至可以用它來再次旋轉它，所以你不必看着它躺在一邊;）

• 雖然我們在董事會的主題......這只是我，但是， ...我總是嘗試點擊畫面，然後必須記住：哦，是的，有按鈕：DI的意思是......爲什麼不把圖像放在按鈕上或實現一個MouseListener，所以你實際上只需點擊漆面？

• 當提供代碼和/或示例圖像時，請取出您的測試輸出。我正在談論Player 1 won!當然;）

• 請您瞭解什麼是一個完整的，可驗證的和最小的例子是下一次你問一個關於StackOverflow的問題。您的問題中的問題並不完整或無法驗證，您在github上提供的問題是...好...不完整（圖片丟失），但已足夠完整。這也是可以驗證的，但並不是最小的。如果遵循指導方針，您將很快得到答案。