MinMax生成游戏树

Question

我试着用Java编写一个连接-4游戏的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;
}

板类是板状态的表示形式。

move 类保存要执行的移动(tic为整数0-8，连接4为0-6 )。

Node类保存移动，并评估给定移动的好坏。还有，抱着它所有的孩子。

在代码中，我使用如下方法：

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方法(感谢上帝，顺便说一句)已经检查游戏是否已经结束，所以如果是的话，就不会产生任何移动。(检查分数的最佳时机)。

错误#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:玩家在耍你，

一旦我改变了所有这一切，我花了片刻与调试器，以了解为什么它仍然不能工作。

最后一个错误不是您在问题中提供的代码。(以你为耻！)

原来这是您的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()方法是非常有帮助的，因为这将给您提供一种很好而且简单的方法来查看调试器中的板。你甚至可以用它再次旋转它，所以你看，不必看它躺在一边;)
• 当我们在董事会讨论的时候.这只是我但是..。我总是试着先点击油漆表面，然后必须记住:哦，是的，有按钮:我的意思是.为什么不直接将图像放在按钮上或实现一个MouseListener，这样您就可以实际单击绘制的表面了？
• 当提供代码和/或示例图像时，请取出测试输出。当然，我说的是Player 1 won! ;)
• 下一次在StackOverflow上提问时，请了解一个完整的、可验证的和最小的例子是什么。你问题中的那个不是完整的或可验证的，你在github上提供的那个是.好吧..。不完整(图像丢失)，但足够完整。它也是可核查的，但并不是最低限度的。如果你遵循指导方针，你会很快得到答案的。