Minimax算法递归异常：我的井字棋实现未遍历所有状态

问题概述 #

你的MiniMax函数能够返回包含index和score的对象，但无法遍历井字棋的所有可能游戏状态，示例执行后仅输出6行内容，递归未正常遍历所有分支。

核心错误原因 #

问题出在直接修改了传入的gameLayout数组且未做回溯处理。由于数组是JavaScript中的引用类型，在循环中修改数组后，后续的循环迭代和递归调用都会基于被修改后的数组执行，导致大量潜在的游戏状态被跳过——原本空的单元格被提前填充，后续emptyCells函数无法识别这些位置，自然不会探索对应的分支。

修复方案 #

有两种可行的修复方式，核心都是保证每个递归分支基于独立的游戏状态执行：

方式1：创建数组副本（推荐） #

每次循环时创建原游戏布局的副本，修改副本而非原数组，这样不会影响后续分支的状态：

function miniMax (gameLayout, player) {
  const empty = emptyCells(gameLayout)
  if (checkWin(gameLayout) === 1) {
    return { score: 10 }
  } else if (checkWin(gameLayout) === -1) {
    return { score: -10 }
  } else if (empty.length === 0) {
    return { score: 0 }
  }
  const moves = []
  for (let i = 0; i < empty.length; i++) {
    const move = {}
    move.index = empty[i]
    // 创建原数组的副本，避免修改原布局
    const newLayout = [...gameLayout]
    newLayout[empty[i]] = player === 'O' ? 'O' : 'X'
    // 递归调用时传入副本，保证分支独立性
    move.score = player === 'O' ? miniMax(newLayout, human).score : miniMax(newLayout, ai).score
    moves.push(move)
  }
  let bestMove
  if (player === 'O') {
    bestMove = moves.reduce((acc, curr, i) => moves[acc].score > curr.score ? acc : i, 0)
  } else {
    bestMove = moves.reduce((acc, curr, i) => moves[acc].score < curr.score ? acc : i, 0)
  }
  console.log(JSON.stringify(moves))
  return moves[bestMove]
}

方式2：回溯恢复原数组 #

如果不想创建副本，可以在递归调用完成后，将修改的单元格恢复为空（回溯），还原原数组状态：

function miniMax (gameLayout, player) {
  const empty = emptyCells(gameLayout)
  if (checkWin(gameLayout) === 1) {
    return { score: 10 }
  } else if (checkWin(gameLayout) === -1) {
    return { score: -10 }
  } else if (empty.length === 0) {
    return { score: 0 }
  }
  const moves = []
  for (let i = 0; i < empty.length; i++) {
    const move = {}
    move.index = empty[i]
    // 修改原数组
    gameLayout[empty[i]] = player === 'O' ? 'O' : 'X'
    // 递归调用
    move.score = player === 'O' ? miniMax(gameLayout, human).score : miniMax(gameLayout, ai).score
    // 回溯：将单元格恢复为空，不影响后续分支
    gameLayout[empty[i]] = ''
    moves.push(move)
  }
  let bestMove
  if (player === 'O') {
    bestMove = moves.reduce((acc, curr, i) => moves[acc].score > curr.score ? acc : i, 0)
  } else {
    bestMove = moves.reduce((acc, curr, i) => moves[acc].score < curr.score ? acc : i, 0)
  }
  console.log(JSON.stringify(moves))
  return moves[bestMove]
}

修复效果 #

采用上述任意一种方式后，MiniMax算法会正确遍历所有可能的游戏状态，控制台输出的内容数量会对应所有分支的探索结果，递归逻辑恢复正常。

内容的提问来源于stack exchange，提问作者Дмитрий Орлов