Tic-Tac-Toe游戏Minimax算法AI未选最优落子问题咨询

问题场景 #

玩家先手，依次选择位置2、4、6（井字棋位置编号如下）时，AI未选择位置9直接获胜，反而落子到位置3，且在freeCodeCamp同款示例中测试相同策略也得到类似结果。

1 | 2 | 3
---------
4 | 5 | 6
---------
7 | 8 | 9

原因分析 #

这并非算法实现错误，而是Minimax算法在存在多个最优解时的遍历顺序导致的选择差异：

1. 当前代码的Minimax得分规则为：AI获胜得1分，玩家获胜得-1分，平局得0分。
2. 当玩家下完位置2、4、6后，AI存在多个能直接获胜的落子位置（比如位置3和位置9），这些位置的评估得分均为1（最优得分）。
3. 在aiMove函数中，遍历顺序是从第一行到第三行、从左到右依次检查每个空位。位置3（对应数组索引(0,2)）会比位置9（对应数组索引(2,2)）更早被遍历到，因此算法会优先选择第一个遇到的最优位置，而非我们直觉认为的位置9。

优化方案 #

如果希望AI在多个最优解中随机选择落子，可修改aiMove函数，收集所有得分等于最优得分的位置，再随机挑选一个：

function aiMove() {
  let bestScore = -2;
  let score;
  let bestMoves = [];

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (board[i][j] == ' ') {
        board[i][j] = ai;
        score = miniMax(board, false);
        board[i][j] = ' ';
        if (score > bestScore) {
          bestScore = score;
          bestMoves = [{i, j}];
        } else if (score === bestScore) {
          bestMoves.push({i, j});
        }
      }
    }
  }
  // 从所有最优落子中随机选择一个
  let moveSpot = random(bestMoves);
  board[moveSpot.i][moveSpot.j] = ai;
}

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