java - 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]）。

节点类保存Move，并评估给定的移动程度。此外，还保留所有孩子。

在代码中，我使用这种方法：

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分，因为您尚未达到深度。它仍然不会有任何孩子，因此即使在您的最低要求下，它也永远不会意识到这是一个糟透了的路。

这就是为什么在这种情况下每一步都是“可能的”，而您只得到第一个返回的原因。

幸运的是，在之前的举动中，总是有一种方法可以使对手的第三招（即第5招）达到失败的举动，这就是为什么正确地调用对手的原因。

好了，那么我们该如何解决呢？

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);
    }
}

只需事先获取移动列表，然后查看它是否为空（您的 generateMoves()类的 Board方法（顺便说一句，谢天谢地，您好吗；））已经检查了游戏是否结束，因此，是否存在不会产生任何动作。完美的时间来检查分数）。

错误三：那该死的深度又来了

我们不只是解决这个问题吗？

可悲的是，您的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也是一样的。

错误四：玩家在跟你拧

一旦改变了所有这些，我花了一些时间在调试器上意识到为什么它仍然无法正常工作。

最后一个错误不在问题btw中提供的代码中。你太无耻了！ ;）

原来这是您的 TicTacToeBoard类中的这段美妙的代码：

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

既然你打电话

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

在 makeMove的 TicTacToeMainWindow方法中，您总是会从错误的播放器开始。

您可能会猜到自己，只需将其更改为：

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

它应该可以解决问题。

也：

现在，我只想指出几件事：


清理您的进口！您的TicTacToe实际上仍然会导入ConnectFour类！而且没有理由。
您的电路板被旋转并镜像到您的电路板阵列中。为什么？您知道调试有多烦人吗？我的意思是，我想您可能是：D另外，如果您的代码有问题并且需要调试，则覆盖板 toString()方法将非常有帮助，因为这将为您提供一种非常简便的方法在调试器中查看您的电路板。您甚至可以使用它再次旋转它，因此您不必看它放在侧面；）
虽然我们只是董事会的主题，但那只是我自己，但是...我总是尝试首先单击绘画表面，然后不得不记住：哦，是的，有按钮：DI表示...为什么不呢？只需将图像放在按钮上或实现 MouseListener，实际上就可以单击绘制的表面？
提供代码和/或示例图像时，请取出测试输出。我说的当然是 Player 1 won!;）
下次您在StackOverflow上提问时，请了解什么是完整，可验证的最小示例。您问题中的一个不完整或不可验证，而您在github上提供的一个是...好...不完整（图像丢失），但足够完整。它也是可验证的，但并非最小。如果遵循指南，您将很快得到很多答案。