极小极大值问题 - Java

Question

我到处寻找修复我的代码的答案，但在花了很长时间尝试调试它之后，我发现自己无可救药地陷入困境。问题是我的 minimax 函数不会 return 最佳可能移动的正确值，我什至试图通过存储最佳第一步来修复它（当深度 = 0 时），但如果解决方案不明显，那么该算法就会严重失败。我还尝试修改基本案例中的 return 值，以便优先考虑较早的胜利，但这并没有解决问题。

目前我正在 TicTacToe 棋盘和助手类上测试该功能（例如 getMoves() 或 getWinner 工作正常），我知道我的风格不是最有效的，但我需要代码来相当明确。通过添加一堆打印语句，我意识到在某些情况下我的 bestFinalMoves ArrayList 没有被修改，所以这可能与问题有关。另一个相关的问题是，除非算法找到直接获胜（在下一步中），否则它不会选择可能导致未来获胜或平局的移动，而是通过阻止导致立即阻止的方块，它只会产生 space 最小化玩家获胜。

例如在黑板上：

aBoard= new int[][] {
                {0,1,0}, // 1 is MAX (AI), -1 is MIN (Human)
                {-1,0,0},
                {-1,0,0}
        };

产生错误的结果 2,0，显然它应该是 0,0，因此它阻止了最小化玩家的获胜，并且 bestFinalMoves ArrayList 为空。

 private result miniMaxEnd2(Board tmpGame, int depth){
    String winner =  tmpGame.whoWon();
    ArrayList<Move> myMoves = tmpGame.getMoves();

    if (winner == 'computer'){ //Base Cases
        return new result(1000);
    }else if (winner == 'human'){
        return new result(-1000);
    }
    else if (winner == 'tie'){
        return new result(0);
    }
        if (tmpGame.ComputerTurn) {//MAX
            bestScore = -99999;
            for (Move m : tmpGame.getMoves()){
                Board newGame = new Board(tmpGame,!tmpGame.ComputerTurn, m);
                result aScore = miniMaxEnd2(newGame, depth+1);
                if (aScore.score > bestScore) {
                    bestScore = aScore.score;
                    bestMove = m;
                        if (depth == 0) {
                            bestFinalMoves.add(m);
                        }
                }
            }
            return new result(bestScore, bestMove);
        } else {//MIN
            bestScore = 99999;
            for (Move m : tmpGame.getMoves()) {
                Board newGame = new Board(tmpGame,!tmpGame.ComputerTurn, m);
                result aScore = miniMaxEnd2(newGame, depth + 1);
                if (aScore.score < bestScore) {
                    bestScore = aScore.score;
                    bestMove = m;
                }

            }
            return new result(bestScore,bestMove);

        }

}

我知道这很长 post，但非常感谢您的帮助。可以在 https://github.com/serch037/UTC_Connect

访问完整代码

Answer 1

bestScore 和 bestMove 变量必须在 miniMaxEnd2 方法内声明为局部变量，此逻辑才能正常工作。这些变量的值正在被递归调用替换。

极小极大值问题 - Java

Minimax value issue - Java

java

artificial-intelligence

minimax