生成游戏树

我尝试用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);

而且很明显,给定的举动是失败的举动(或胜利),我不会收到这一举措。


好的,你确实犯了一些错误。 大约3-4,取决于你的数量;)我花了一些调试来弄清楚这一切,但我终于得到了一个答案给你:D

错误#1:你所有的父母总是得到双胞胎(那个可怜的母亲)

这仅仅是你上传的代码的情况,而不是你的问题中的代码,所以也许我们把它算作是一个错误? 由于你的树还没有那么大,它不会破坏你的算法,所以这是最不重要的。 不过,这是值得注意的。 在您上传的代码中,您可以使用generateSubtree方法执行此操作:

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

由于该构造函数已将子项添加到子引导节点,因此第二行始终会再次添加该子节点。

错误#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;
}

自从你打电话

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

TicTacToeMainWindowmakeMove方法中,你总是从错误的玩家开始。

您可能会猜到自己,您只需将其更改为:

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

它应该做的伎俩。

也:

在这一点上,我想说几句话:

  • 清理你的进口! 您的TicTacToe实际上仍然导入您的ConnectFour类! 没有理由。

  • 您的电路板在您的电路板阵列中旋转并镜像。 为什么? 你知道这是多么烦人的调试? 我的意思是,我想你可能会这样做:D另外,如果你的代码有问题,而且你需要调试它,覆盖你的主板toString()方法是非常有用的,因为这会给你一个非常好的和简单的方法在调试器中查看您的电路板。 你甚至可以用它来再次旋转它,所以你不必看着它躺在一边;)

  • 虽然我们在董事会的主题......这只是我,但是......我总是先试着点击彩绘表面,然后必须记住:哦,是的,有按钮:DI的意思是......为什么不只需将图像放在按钮上或者实现一个MouseListener以便实际上只需单击所绘的表面?

  • 提供代码和/或示例图像时,请取出您的测试输出。 我说的是Player 1 won! 当然;);)

  • 请了解下一次在StackOverflow上提出问题时,完整,可验证和最低限度的示例。 您的问题中的问题并不完整或无法验证,您在github上提供的问题是...好...不完整(图片丢失),但已足够完整。 这也是可以验证的,但并不是最小的。 如果遵循指导方针,您将很快得到答案。

  • 链接地址: http://www.djcxy.com/p/56373.html

    上一篇: generating game tree

    下一篇: MinMax with Alpha