Flutter中Minimax算法在4/5/6格井字棋中无限运行问题求助

我在Flutter中实现了一款简易井字棋游戏，采用Minimax算法计算AI玩家的走法。该算法在3x3棋盘上运行完全正常，但适配到4x4、5x5、6x6棋盘时，即便添加了alpha-beta剪枝优化，Minimax函数仍会无限运行，无法返回有效走法。以下是核心代码：

核心函数 #

Minimax算法实现 #

int minimax(List<List<String>> board, bool isMaximizing, BuildContext context, int alpha, int beta) {
  // 检查终端状态
  if (checkWin(board, 'O', context)) {
    return 1;
  } else if (checkWin(board, 'X', context)) {
    return -1;
  } else if (checkDraw(board)) {
    return 0;
  }

  // 递归遍历游戏树
  if (isMaximizing) {
    int bestScore = -1000;
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {
        if (board[i][j].isEmpty) {
          board[i][j] = 'O';
          int score = minimax(board, false, context, alpha, beta);
          board[i][j] = '';
          bestScore = max(score, bestScore);

          alpha = max(alpha, score);
          if (beta <= alpha) {
            break; // 剪枝子树
          }
        }
      }
    }
    return bestScore;
  } else {
    int bestScore = 1000;
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {
        if (board[i][j].isEmpty) {
          board[i][j] = 'X';
          int score = minimax(board, true, context, alpha, beta);
          board[i][j] = '';
          bestScore = min(score, bestScore);

          beta = min(beta, score);
          if (beta <= alpha) {
            break; // 剪枝子树
          }
        }
      }
    }
    return bestScore;
  }
}

胜负判断函数 #

bool checkWin(List<List<String>> board, String player, BuildContext context) {
  for (int i = 0; i < 4; i++) {
    // 横向/纵向四连判断
    if ((board[i][0] == player && board[i][1] == player && board[i][2] == player && board[i][3] == player) || 
        (board[0][i] == player && board[1][i] == player && board[2][i] == player && board[3][i] == player)) {
      // 获胜格子着色逻辑
      if(context.read<SharedPrefProvider>().hardLevel % 2 != 0) {
        checkWinColors(board, player, i, context);
      }
      return true;
    }
  }
  // 对角线四连判断
  if ((board[0][0] == player && board[1][1] == player && board[2][2] == player && board[3][3] == player) ||
      (board[0][3] == player && board[1][2] == player && board[2][1] == player && board[3][0] == player)) {
    if(context.read<SharedPrefProvider>().hardLevel % 2 != 0) {
      checkWinColors(board, player, 0, context);
    }
    return true;
  }
  return false;
}

平局判断函数 #

bool checkDraw(List<List<String>> board) {
  // 检查所有格子是否填满
  for (var row in board) {
    for (var cell in row) {
      if (cell.isEmpty) {
        return false; // 存在空格子，不是平局
      }
    }
  }
  return true; // 所有格子填满，平局
}

AI走法调用函数 #

void makeAIMove(board) {
  int bestScore = -1000;
  int bestMoveRow = -1;
  int bestMoveCol = -1;

  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
      if (board[i][j].isEmpty) {
        board[i][j] = 'O';
        int score = minimax(board, false, context, -1000, 1000);
        board[i][j] = '';

        if (score > bestScore) {
          bestScore = score;
          bestMoveRow = i;
          bestMoveCol = j;
        }
      }
    }
  }

  // 执行AI走法
  if (bestMoveRow != -1 && bestMoveCol != -1) {
    setState(() {
      board[bestMoveRow][bestMoveCol] = "O";
    });
  }
}

问题排查与修复方案 #

1. 硬编码棋盘大小导致适配失败 #

所有函数中均直接使用4作为棋盘的行列数，当切换到5x5/6x6棋盘时：

• 循环仅遍历前4行/列，剩余格子未被处理，导致递归无法覆盖所有可能状态
• checkWin函数仅检查固定位置的4连，无法适配大棋盘的获胜判断逻辑

修复方式：将所有硬编码的4替换为动态获取的棋盘尺寸：

// 循环时使用board.length获取行数，board[i].length获取列数
for (int i = 0; i < board.length; i++) {
  for (int j = 0; j < board[i].length; j++) {
    // ... 原有逻辑
  }
}

2. 递归中混入UI逻辑导致性能异常 #

checkWin函数中在递归过程中调用context.read<SharedPrefProvider>()和checkWinColors，属于UI层操作：

• 递归过程中频繁操作上下文会大幅降低性能，甚至引发状态异常
• Minimax算法仅需判断胜负状态，无需处理UI着色逻辑

修复方式：分离算法与UI逻辑，将着色操作移到AI走法完成后执行，修改后的checkWin仅保留胜负判断：

bool checkWin(List<List<String>> board, String player) {
  int boardSize = board.length;
  int winLength = 4; // 根据游戏规则设定获胜所需的连续棋子数

  // 横向检查
  for (int i = 0; i < boardSize; i++) {
    for (int j = 0; j <= boardSize - winLength; j++) {
      bool win = true;
      for (int k = 0; k < winLength; k++) {
        if (board[i][j + k] != player) {
          win = false;
          break;
        }
      }
      if (win) return true;
    }
  }

  // 纵向检查
  for (int j = 0; j < boardSize; j++) {
    for (int i = 0; i <= boardSize - winLength; i++) {
      bool win = true;
      for (int k = 0; k < winLength; k++) {
        if (board[i + k][j] != player) {
          win = false;
          break;
        }
      }
      if (win) return true;
    }
  }

  // 正对角线检查
  for (int i = 0; i <= boardSize - winLength; i++) {
    for (int j = 0; j <= boardSize - winLength; j++) {
      bool win = true;
      for (int k = 0; k < winLength; k++) {
        if (board[i + k][j + k] != player) {
          win = false;
          break;
        }
      }
      if (win) return true;
    }
  }

  // 反对角线检查
  for (int i = winLength - 1; i < boardSize; i++) {
    for (int j = 0; j <= boardSize - winLength; j++) {
      bool win = true;
      for (int k = 0; k < winLength; k++) {
        if (board[i - k][j + k] != player) {
          win = false;
          break;
        }
      }
      if (win) return true;
    }
  }

  return false;
}

3. 大棋盘状态空间过大导致无限递归 #

4x4棋盘的状态数为16!（约2e13），远超出计算机实时计算能力，即使有alpha-beta剪枝也无法遍历所有状态，导致递归无法终止。

修复方式：添加递归深度限制+启发式评分函数：

// 修改Minimax函数，加入深度参数和启发式评分
int minimax(List<List<String>> board, bool isMaximizing, int depth, int alpha, int beta) {
  int boardSize = board.length;
  int winLength = 4;

  // 终端状态判断
  if (checkWin(board, 'O')) {
    return 1000 + depth; // 深度越深，得分越低（鼓励尽快获胜）
  } else if (checkWin(board, 'X')) {
    return -1000 - depth;
  } else if (checkDraw(board) || depth == 6) { // 限制最大递归深度为6
    return evaluateBoard(board, winLength); // 启发式评分
  }

  if (isMaximizing) {
    int bestScore = -1000;
    for (int i = 0; i < boardSize; i++) {
      for (int j = 0; j < boardSize; j++) {
        if (board[i][j].isEmpty) {
          board[i][j] = 'O';
          int score = minimax(board, false, depth + 1, alpha, beta);
          board[i][j] = '';
          bestScore = max(score, bestScore);
          alpha = max(alpha, score);
          if (beta <= alpha) break;
        }
      }
    }
    return bestScore;
  } else {
    int bestScore = 1000;
    for (int i = 0; i < boardSize; i++) {
      for (int j = 0; j < boardSize; j++) {
        if (board[i][j].isEmpty) {
          board[i][j] = 'X';
          int score = minimax(board, true, depth + 1, alpha, beta);
          board[i][j] = '';
          bestScore = min(score, bestScore);
          beta = min(beta, score);
          if (beta <= alpha) break;
        }
      }
    }
    return bestScore;
  }
}

// 启发式评分函数：评估当前棋盘对AI的有利程度
int evaluateBoard(List<List<String>> board, int winLength) {
  int score = 0;
  // 可根据横向、纵向、对角线的连续棋子数加权评分，例如：
  // 3连未被阻挡得10分，2连得2分，以此类推
  // 具体逻辑可根据游戏规则调整
  return score;
}

4. alpha-beta剪枝的break逻辑优化 #

原代码中仅在内层列循环break，外层行循环仍会继续，这本身没问题，但可优化遍历顺序（优先检查角落、中心等关键位置），进一步提升剪枝效率。

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