井字棋AI的JavaScript Minimax函数运行过慢求助

兄弟，我看你这井字棋的Minimax跑起来慢得离谱——1-1.5分钟确实完全不正常，正常情况下哪怕没做极致优化，井字棋的AI走棋也应该是瞬间出结果的。既然你已经确认终止状态都能正确返回分数，那大概率是踩了这几个常见的性能坑：

1. 没实现Alpha-Beta剪枝 #

这是Minimax算法提速最核心的优化，没有剪枝的话，算法会毫无必要地遍历所有可能的分支，哪怕有些分支已经不可能影响最终决策了。比如当AI已经找到一个必胜的走法，就没必要再去计算其他更差的走法分支了。

给你一个基础的Alpha-Beta剪枝实现示例，你可以对照着修改你的代码：

function minimax(board, depth, isMaximizing, alpha = -Infinity, beta = Infinity) {
  // 先检查终止状态（赢/输/平局）并返回对应分数
  const gameResult = checkGameStatus(board);
  if (gameResult) {
    return calculateScore(gameResult, depth);
  }

  if (isMaximizing) {
    let bestScore = -Infinity;
    for (let i = 0; i < 9; i++) {
      if (board[i] === '') {
        // 模拟落子
        board[i] = 'ai';
        // 递归调用，切换为极小化玩家
        const currentScore = minimax(board, depth + 1, false, alpha, beta);
        // 回溯，撤销落子
        board[i] = '';
        
        bestScore = Math.max(bestScore, currentScore);
        alpha = Math.max(alpha, currentScore);
        
        // Alpha剪枝：如果当前极大值已经大于等于极小值，直接终止循环
        if (beta <= alpha) break;
      }
    }
    return bestScore;
  } else {
    let bestScore = Infinity;
    for (let i = 0; i < 9; i++) {
      if (board[i] === '') {
        board[i] = 'human';
        const currentScore = minimax(board, depth + 1, true, alpha, beta);
        board[i] = '';
        
        bestScore = Math.min(bestScore, currentScore);
        beta = Math.min(beta, currentScore);
        
        // Beta剪枝：如果当前极小值已经小于等于极大值，直接终止循环
        if (beta <= alpha) break;
      }
    }
    return bestScore;
  }
}

2. 没有缓存重复状态（备忘录模式） #

井字棋的很多棋盘状态是重复出现的（比如不同的落子顺序导致完全相同的棋盘），如果每次遇到相同状态都重新计算一遍，会浪费大量的计算资源。你可以用一个Map或者普通对象来缓存已经计算过的棋盘状态的分数，下次遇到直接读取缓存即可。

比如把棋盘转换成字符串作为缓存的键：

const memo = new Map();

function minimax(board, depth, isMaximizing, alpha, beta) {
  const boardKey = board.join(',');
  // 先检查缓存，如果有直接返回
  if (memo.has(boardKey)) {
    return memo.get(boardKey);
  }

  // ... 原有终止状态检查和递归逻辑 ...

  // 计算完成后存入缓存
  memo.set(boardKey, bestScore);
  return bestScore;
}

3. 状态表示过于复杂且拷贝开销大 #

你代码里用的是state对象，如果每次递归都要深拷贝这个对象（比如用JSON.parse(JSON.stringify(state))），那会带来巨大的性能开销。建议简化棋盘状态的表示，比如用一个简单的数组（['', 'X', 'O', ...]），然后通过回溯的方式修改状态，避免深拷贝——也就是在递归前修改数组元素，递归结束后再改回去，这样完全不需要拷贝整个状态。

4. 递归中存在不必要的额外操作 #

比如你提到用日志输出排查问题，如果日志输出是放在递归函数内部的，那每一次递归都会触发一次DOM操作或者控制台输出，这也会拖慢整体速度。建议把日志输出移到递归函数外部，或者只在顶层调用时输出关键信息。

先从Alpha-Beta剪枝开始优化，这应该能直接把运算时间从分钟级压缩到毫秒级。如果还是有问题，再检查状态拷贝和缓存的问题。

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