井字棋Minimax算法问题：状态估值异常与测试方法咨询

我在大学课程作业中实现井字棋（Tic-Tac-Toe）的Minimax算法时碰到了问题：首步落子后得到两种状态，算法给出的Minimax值均为0，但实际一种状态（状态1）会被对手100%击败，另一种（状态2）能保证Bot（操控O）赢或平局。我尝试加重失败惩罚但无效果，不确定算法是否有误，想了解测试任意井字棋状态Minimax值的方法。

规则说明 #

X先手，Bot操控O；获胜得+10，平局得0，失败得-10。当前算法会选择状态1，但该状态必败，更优的状态2却未被选中。

相关状态 #

状态1（必败） #

X . O
. . .
. . .

状态2（可保证不败） #

X . .
. O .
. . .

实现的Minimax算法代码 #

private int minimaxValue(BoardTree state, bool minimising)
{
    // Minimise means opt for lowest score, noughts win = +10, draw = 0, cross win = -10
    if (state.successiveMoves.Count == 0)
    {
        if (state.Board.gameDrawnFlag) return DRAW_VAL;
        switch (state.Board.winner)
        {
            case TicTacToeBoard.Player.Cross: return LOSE_VAL;
            case TicTacToeBoard.Player.Nought: return WIN_VAL;
        }
    }
    
    if (minimising)
    {
        int lowestValue = minimaxValue(state.successiveMoves[0], !minimising); // Get an initial value
        
        for (int i = 1; i < state.successiveMoves.Count; i++) 
        {
            int val = minimaxValue(state.successiveMoves[i], !minimising); // Check each state, maximised this time
            if (val < lowestValue)
            {
                lowestValue = val; // Find the lowest value from the list
            }
        }
        
        return lowestValue;
    }
    else // Maximising
    {  
        int highestValue = minimaxValue(state.successiveMoves[0], !minimising); // Initial base comparison value

        for (int i = 1; i < state.successiveMoves.Count; i++)
        {
            int val = minimaxValue(state.successiveMoves[i], !minimising); // Check each state, minimised this time
            if (val > highestValue)
            {
                highestValue = val;
            }
        }
        
        return highestValue;
    }
}

算法问题排查方向 #

1. 角色与minimising参数对应错误：Bot操控O（最大化玩家，目标是+10），X是最小化玩家（目标是让O得-10）。需确认递归时minimising参数是否正确对应当前走棋的玩家——比如O走棋时应该触发最大化逻辑，X走棋时触发最小化逻辑，若对应反了会导致评估完全错误。
2. 缺少步数权重：当前算法对所有赢/输的得分都是固定值，没有考虑步数。比如同样是输，晚输比早输更有价值；同样是赢，早赢比晚赢价值更高。可以修改得分公式为WIN_VAL - depth、LOSE_VAL + depth（depth为当前递归深度），这样算法会优先选择最快获胜或避免最快失败的路径。
3. BoardTree状态生成错误：检查successiveMoves是否正确生成了当前状态下所有可能的合法走棋，若遗漏了关键走法（比如X的必胜步），会导致算法错误评估状态。
4. 胜负判断逻辑错误：验证gameDrawnFlag和winner的判断是否准确，比如状态1中X走中间后是否被正确识别为X的获胜威胁。

测试任意状态Minimax值的方法 #

• 手动递归验证：选取简单状态（比如只剩1-2步的终局前状态），手动计算Minimax值，与算法输出对比，验证基础逻辑是否正确。
• 添加递归日志：在minimaxValue方法中，每次递归时打印当前棋盘状态、minimising参数、计算得到的值，追踪每一步的递归路径，定位状态1和状态2的评估差异点。
• 编写单元测试：针对已知结果的状态编写测试用例：
  • 必赢状态（O只差一步获胜）：验证算法返回+10
  • 必败状态（X只差一步获胜）：验证算法返回-10
  • 平局状态：验证算法返回0
• 可视化递归树：将BoardTree的结构和每个节点的Minimax值打印为树形结构，直观查看算法对每个分支的评估过程。

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