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上提供的问题是...好...不完整（图片丢失），但已足够完整。这也是可以验证的，但并不是最小的。如果遵循指导方针，您将很快得到答案。