帮助我实现MinMax

Question

我一直在尝试为一个简单的游戏实现minMax算法(稍后会尝试alphabeta剪枝)……我看过很多伪代码和教程，但我就是不能让它工作……

如果您能提供一点帮助，我们将不胜感激:)

下面是相关的类...(为清晰起见删除了实现)

class Board { //Stores board state, Immutable

    Board playMove(Move m); //generates new Board after playing "Move m"

    List<Move> nextMoves(Move m); // generates all possible moves, previous move is required to decide the validity of the next moves

    boolean isTerminal(); //board at terminal state?
}


class Move { //stores positions played and score gained from that move

}

这是我的最小最大Implementation...Can，有人能指出我做错了什么吗？谢谢。

private Move bestMove = null; // field variable

private int maxMove(Board board, Move prevMove, int myScore, int oppnScore) {
    out("maxMove " + board );
    if(board.isTerminal()) {
        return myScore - oppnScore;
    }
    int mx = Integer.MIN_VALUE;
    for(Move nxtMove: board.nextMoves(prevMove)) {
        int k = minMove(board.playMove(nxtMove),
                        nxtMove,
                        myScore + nxtMove.score,
                        oppnScore);
        if(k > mx) {
            mx = k;
            bestMove = nxtMove;
        }
    }
    return mx;
}

private int minMove(Board board, Move prevMove, int myScore, int oppnScore) {
    if(board.isTerminal()) {
        return myScore - oppnScore;
    }
    out("minMove " + board );
    int mn = Integer.MAX_VALUE;
    for(Move nxtMove: board.nextMoves(prevMove)) {
        int k = maxMove(board.playMove(nxtMove),
                        nxtMove,
                        myScore,
                        oppnScore + nxtMove.score);
        if(k < mn) {
            mn = k;
            bestMove = nxtMove;
        }
    }
    return mn;
}

编辑:游戏的简要描述如下，你面前有一定数量的不同面额的硬币。你和另一个玩家轮流从任一侧(左或右)取出一枚硬币。硬币的面额表示你在这一步中得到的分数。某些硬币有特殊的含义，比如拾取X意味着你将跳过一轮，或者Y意味着你将获得更多一轮。你的目标是比你的对手得到更多的分数。

Answer 1

我只看到了一个错误:你不记得你为给定的棋盘状态选择了哪个转弯，所以你计算了很多次，算法变得很慢。或者速度不是你的问题？

Answer 2

我想我不太明白游戏规则，但看起来你的病情不太好。

您将返回玩家之间的分数差值。这意味着一个玩家想要最大化这个值(与对手的最大差异)，而另一个玩家想要最小化这个值(他试图获得与对手最接近的分数)。这看起来真的不像任何真正的游戏的目标。

我想你想要的是得分最高的玩家获胜。因此，您只需检查是否为myScore>oppScore，并相应地返回1,0和-1。这意味着第一个玩家想要最大化回报(即他试图使其为1-他赢了)，而对手试图最小化回报(即如果回报为-1他就赢了)。如果不能获胜，他们宁愿选择0(平局)。

另外，为什么需要prevMove来生成下一步操作？难道board没有关于游戏当前状态的所有信息(即硬币剩余)吗？