MiniMax算法深度大于2时失效，国际象棋Bot最佳走法异常

我正在实现一款国际象棋Bot，目前在以下MiniMax函数的实现上遇到问题：

int MiniMax(Board board, int depth, bool maximizingPlayer, int alpha, int beta) {

    if (depth == 0 || IsTerminalState(board))
        return Evaluate(board);
        
    Move[] allMoves = board.GetLegalMoves();

    if (maximizingPlayer) {
        int maxEval = int.MinValue;
        foreach (Move move in allMoves) {
            board.MakeMove(move);
            int eval = MiniMax(board, depth - 1, false, alpha, beta);
            board.UndoMove(move);
            if(eval > beta) {
                break;
            }
            alpha = Math.Max(eval, alpha);
            if (eval >= maxEval) {
                maxEval = eval;
                bestMove = move;
            }
        }
        return maxEval;
    }
    else {
        int minEval = int.MaxValue;
        foreach (Move move in allMoves) {
            board.MakeMove(move);
            minEval = Math.Min(minEval, MiniMax(board, depth - 1, true, alpha, beta));
            board.UndoMove(move);
            if(minEval < alpha) {
                break;
            }
            beta = Math.Min(beta, minEval);
        }
        return minEval;
    }
}

当以深度3或更大值调用该函数（如MiniMax(board, 3, true, int.MinValue, int.MaxValue);）时，全局变量bestMove（初始化为空走法）有时会变成当前局面下的非法走法。我怀疑问题出在走法的撤销方式上，因为board.UndoMove()要求走法必须按相反顺序撤销，例如执行走法A、B、C后，需按C、B、A的顺序撤销。

问题分析与解决方案 #

1. 全局变量bestMove的赋值逻辑错误

这是导致非法走法的核心原因：所有递归层级的MiniMax函数都会修改同一个全局bestMove变量。当递归进入深层（比如depth=1或depth=2的层级）时，此时的move是基于中间局面的合法走法，但并非初始调用层（depth=3）的合法走法，这些深层的赋值会直接覆盖顶层的bestMove，最终得到非法走法。

解决方法：
移除全局变量，改用局部变量管理最佳走法，仅在顶层递归层级记录最佳走法。可以拆分出一个对外的入口函数，内部调用MiniMax时传递引用参数保存最佳走法，示例如下：

// 对外入口函数
Move FindBestMove(Board board, int depth) {
    Move bestMove = Move.Empty;
    MiniMax(board, depth, true, int.MinValue, int.MaxValue, ref bestMove);
    return bestMove;
}

// 内部MiniMax函数，添加ref参数传递最佳走法
int MiniMax(Board board, int depth, bool maximizingPlayer, int alpha, int beta, ref Move bestMove) {
    if (depth == 0 || IsTerminalState(board))
        return Evaluate(board);
        
    Move[] allMoves = board.GetLegalMoves();
    if (maximizingPlayer) {
        int maxEval = int.MinValue;
        Move currentBestMove = bestMove; // 记录当前层级的最佳走法
        foreach (Move move in allMoves) {
            board.MakeMove(move);
            int eval = MiniMax(board, depth - 1, false, alpha, beta, ref currentBestMove);
            board.UndoMove(move);
            
            if (eval > maxEval) {
                maxEval = eval;
                currentBestMove = move; // 仅更新当前层级的最佳走法
            }
            
            alpha = Math.Max(alpha, maxEval);
            if (alpha >= beta) {
                break; // Alpha-Beta剪枝
            }
        }
        bestMove = currentBestMove; // 仅当当前是顶层时，最终赋值到传入的引用中
        return maxEval;
    } else {
        int minEval = int.MaxValue;
        foreach (Move move in allMoves) {
            board.MakeMove(move);
            int eval = MiniMax(board, depth - 1, true, alpha, beta, ref bestMove);
            board.UndoMove(move);
            
            minEval = Math.Min(minEval, eval);
            
            beta = Math.Min(beta, minEval);
            if (beta <= alpha) {
                break; // Alpha-Beta剪枝
            }
        }
        return minEval;
    }
}

2. Alpha-Beta剪枝的逻辑顺序错误

原代码中剪枝判断和参数更新的顺序颠倒，会导致剪枝逻辑失效，甚至引发错误的评估值传递：

• max玩家分支：先判断eval > beta再更新alpha和maxEval，正确顺序是先更新评估值和alpha，再判断剪枝条件。
• min玩家分支：先判断minEval < alpha再更新beta，正确顺序是先更新minEval和beta，再判断剪枝条件。

修正后的剪枝逻辑已在上述示例代码中体现，核心是先更新当前层级的评估值和alpha/beta参数，再判断是否满足alpha >= beta的剪枝条件。

3. 走法撤销的验证

从代码逻辑看，每个走法的递归调用后都执行了UndoMove，递归内部也遵循同样的Make/Undo流程，理论上走法撤销顺序是正确的。但需要确认Board类的MakeMove和UndoMove实现是否完整处理了状态回滚——比如是否记录了被吃棋子、兵升变、王车易位状态等信息，若状态回滚不完整，会导致后续局面错误，进而生成非法走法。

内容的提问来源于stack exchange，提问作者Gioloh