Minimax算法异常求助：首步固定选择、搜索深度适配错误

我在开发棋类AI时遇到以下Minimax算法异常问题：

• 当己方棋子无威胁时，算法总是选择首个可用走法，导致行为可预测
• 调整搜索深度后出现新问题：深度设为4时maxEval恒为9999，深度为3时算法会选择极小化玩家的棋子作为最优走法

以下是相关代码：

Min Max方法 #

int minMax(List<String> piecesPos, int depth, bool isMaximizing, int alpha, int beta) {
    // Base case: if depth is 0 or the game is over, return the evaluation
    if (depth == 0 || isGameOver(piecesPos)) {
      return evaluateBoard(piecesPos);
    }

    if (isMaximizing) {
      int maxEval = -9999; // Initialize to a very low value
      for (int i = 0; i < piecesPos.length; i++) {
        if (piecesPos[i][0] == "B" || piecesPos[i][0] == "O") {
          List<int> possibleMoves = getPossibleMoves(piecesPos, i);
          for (int move in possibleMoves) {
            // Save the current state
            List<String> saveState = List.from(piecesPos);

            // Make the move
            makeMove(piecesPos, i, move);

            // Recursive call
            int eval = minMax(piecesPos, depth - 1, false, alpha, beta);

            // Restore the state
            piecesPos = List.from(saveState);

            // Update maxEval
            maxEval = max(maxEval, eval);
            alpha = max(alpha, eval);

            // Alpha-Beta Pruning
            if (beta <= alpha) {
              break;
            }
          }
        }
      }
      return maxEval;
    } else {
      int minEval = 9999; // Initialize to a very high value
      for (int i = 0; i < piecesPos.length; i++) {
        if (piecesPos[i][0] == "W" || piecesPos[i][0] == "Q") {
          List<int> possibleMoves = getPossibleMoves(piecesPos, i);
          for (int move in possibleMoves) {
            // Save the current state
            List<String> saveState = List.from(piecesPos);

            // Make the move
            makeMove(piecesPos, i, move);

            // Recursive call
            int eval = minMax(piecesPos, depth - 1, true, alpha, beta);

            // Restore the state
            piecesPos = List.from(saveState);

            // Update minEval
            minEval = min(minEval, eval);
            beta = min(beta, eval);

            // Alpha-Beta Pruning
            if (beta <= alpha) {
              break;
            }
          }
        }
      }
      return minEval;
    }
  }

最优走法调用逻辑 #

void playBestMove(List<String> piecesPosCopy, int depth) {
    int bestEval = -9999;
    int bestMovePrev = -1;
    int bestMoveIndex = -1;
    // Save the current state before call
    List<String> defaultState = List.from(piecesPos);

    for (int i = 0; i < piecesPos.length; i++) {
      if (piecesPos[i][0] == "B" || piecesPos[i][0] == "O") {
        List<int> possibleMoves = getPossibleMoves(piecesPos, i);
        for (int move in possibleMoves) {
          // Save the current state
          List<String> saveState = List.from(piecesPos);

          // Make the move
          makeMove(piecesPos, i, move);

          // Evaluate the move
          int eval = minMax(piecesPos, depth - 1, false, -9999, 9999);

          // Restore the state
          piecesPos = List.from(saveState);

          // Update best move
          if (eval > bestEval) {
            bestEval = eval;
            bestMovePrev = i;
            bestMoveIndex = move;
          }
        }
      }
    }
    print("BBB The best max is $bestEval prev is $bestMovePrev and index is $bestMoveIndex");
    //Restored state to original State before making best move
    piecesPos = List.from(defaultState);

    // Play the best move
    if (bestMovePrev != -1 && bestMoveIndex != -1) {
      //makeMove(piecesPos, bestMovePrev, bestMoveIndex);
      recentlyCrowned = false;
      if(animatePieceMovement){performMultitakeAnim = true;}
      if(!vsComputer){
        undoMove = List.from(piecesPos);
        saveMovesState.add(undoMove);
      }
      //Allow to check for Win, loose and draw.
      checkForWinLooseDraw = true;
      //MakeMove
      makeBotMove(bestMovePrev, bestMoveIndex);
    }
  }

棋盘评估方法 #

int evaluateBoard(List<String> piecesPos) {
    // Implement the evaluation function
    // This function should return a score based on the current state of the board
    // For example, the difference in the number of pieces between the two players
    int totalMyPiece = 0;
    int totalOppPiece = 0;

    //Piece Weight
    for (int i = 0; i < piecesPos.length; i++) {
      if (piecesPos[i][0] == "W"){
        totalOppPiece = totalOppPiece + 10;
      }else
      if(piecesPos[i][0] == "Q"){
        totalOppPiece = totalOppPiece + 20;
      }else
      if (piecesPos[i][0] == "B"){
        totalMyPiece = totalMyPiece + 10;
      }else
      if(piecesPos[i][0] == "O"){
        totalMyPiece = totalMyPiece + 20;
      }
    }
    // center control
    for(int b = 0; b < centerControlArea.length; b++){
      if (piecesPos[centerControlArea[b]][0] == "W" || piecesPos[centerControlArea[b]][0] == "Q"){
        totalOppPiece = totalOppPiece + 3;
      }
    }
    // Threats (pieces under attack)
    totalOppPiece = totalOppPiece - squaresWithTakes_OPP.length * 5;

    // center control
    for(int b = 0; b < centerControlArea.length; b++){
      if (piecesPos[centerControlArea[b]][0] == "B" || piecesPos[centerControlArea[b]][0] == "O"){
        totalMyPiece = totalMyPiece + 3;
      }
    }
    // Threats (pieces under attack)
    totalMyPiece = totalMyPiece - squaresWithTakes.length * 5;

    print("VVV $totalMyPiece");
    print("VVV $totalOppPiece");

    return totalMyPiece - totalOppPiece;
  }

问题分析与修复方案 #

1. 无威胁时固定选择首个走法

原因：playBestMove中仅当eval > bestEval时更新最优走法，多个走法评估分值相同时，只会保留第一个遇到的走法。
修复：将判断条件改为eval >= bestEval，或在分值相同时随机选择走法增加多样性：

// Update best move
if (eval >= bestEval) {
  // 分值相同时随机替换，避免固定行为
  if (eval == bestEval && Random().nextBool()) {
    bestEval = eval;
    bestMovePrev = i;
    bestMoveIndex = move;
  } else if (eval > bestEval) {
    bestEval = eval;
    bestMovePrev = i;
    bestMoveIndex = move;
  }
}

2. 深度4时maxEval恒为9999

排查方向：

• 检查isGameOver函数，确认深度4递归时是否错误判定游戏结束，且对应结束状态的评估分值为9999
• 检查evaluateBoard是否存在未处理的边界情况，导致返回极端值9999
• 补充无合法走法的处理逻辑：当max玩家无走法时，应返回极低分而非初始值：

if (isMaximizing) {
  int maxEval = -9999;
  bool hasValidMoves = false;
  for (int i = 0; i < piecesPos.length; i++) {
    if (piecesPos[i][0] == "B" || piecesPos[i][0] == "O") {
      List<int> possibleMoves = getPossibleMoves(piecesPos, i);
      for (int move in possibleMoves) {
        hasValidMoves = true;
        // 原有逻辑...
      }
    }
  }
  // 无合法走法时返回极低分，表示己方劣势
  return hasValidMoves ? maxEval : -9999;
}

3. 深度3时选择极小化玩家棋子

原因：评估函数中威胁计算逻辑可能混淆了己方与对方的威胁状态
修复：确认squaresWithTakes是己方被威胁的棋子集合，squaresWithTakes_OPP是对方被威胁的棋子集合，调整评估逻辑：

// 己方棋子被威胁，扣分
totalMyPiece = totalMyPiece - squaresWithTakes.length * 5;
// 对方棋子被威胁，己方加分（或对方扣分）
totalOppPiece = totalOppPiece - squaresWithTakes_OPP.length * 5;

同时验证minMax中玩家角色对应关系：isMaximizing=true对应己方（B/O），需最大化totalMyPiece - totalOppPiece；isMaximizing=false对应对方（W/Q），需最小化该值。

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