深度优先搜索实现 AI 井字游戏

theme: fancy

原文链接 Tic Tac Toe AI with a Depth-First Search -- 作者 Ofek Gila

深度优先搜索是种深度优先遍历树的算法，这意味着它递归地遍历树，在继续下一个分支前，遍历完当前分支。

Depth-first-tree.svg

图片来源 Wikipedia

它可以用来处理游戏，找到最佳移动位置或者简单实现谁赢得游戏的理想玩法。这种游戏 AI 最容易去实现，因为它不需要构建树。这种算法自下而上工作，无需重新检测任何结点，它通常使用递归函数和检查游戏是否结束的函数。

译者加：AI -> 人工智能（Artificial Intelligence）

对于井字棋，我们可以考虑下面方法：

/**
 * @param board 棋盘的当前状态
 * @param xTurn 当前方
 * @return 返回游戏结果 - 1 表示 X 赢, -1 表示 Y 赢,  0 表示平局
 */
public int getGameResult(char[][] board, boolean xTurn) {
  // 如果游戏已经结束，返回游戏结果
  if (gameOver(board)) return gameResult(board);
  
  // 如果游戏继续，检查所有的可能的移动
  // 然后为玩家选择最优的一步
  int result = xTurn ? -1:1;
  for(int i = 0; i < board.length; i++) {
    for(int a = 0; a < board[i].length; a++) {
      if(board[i][a] != ' ') continue;
      // 下棋，然后递归运行函数
      // 然后撤销上一步棋子
      board[i][a] = xTurn ? 'X' : 'O';
      int tempResult = getGameResult(board, !xTurn);
      board[i][a] = ' ';
      
      // 检查结果是否对玩家有力
      if((xTurn == tempResult > result) || (!xTurn &amp;&amp; tempResult < result)) {
        result = tempResult;
      }
    }
  }
  return result;
}

上面递归方法 getGameResult 做了以下这些工作：

1. 检查游戏是否结束 - 如果不是玩家赢或者棋盘被填满，返回游戏的结果
2. 遍历所有的棋盘格子

• 如果格子被使用，跳过
• 根据当前玩家的颜色，设置格子为 X 或 O
• 通过递归获取游戏结果，调用相同的方法更新棋盘，并交换 xTurn 的布尔值
• 更新当前分支的最佳结果，尝试最大化当前玩家的结果。

简而言之，假设最大化两个玩家的结果。需要注意的是，可以简单应用这个算法去玩 Misère or Anti Tic Tac Toe游戏，这个游戏很类似井字棋游戏，不过它的目标是求输。

这个方案很简单，因此它在井字棋上运行可能需要将近半秒的时间而已，尽管可以实现不到百分之一秒的运行（参考Kesav Viswanadha’s implementation）。当然，对于大型的游戏，比如四目和五目游戏，这将花费很长的时间。因为深度有限搜索的时间复杂度是**O(b^d)**，其中 b 是分支因子（在任意棋盘位置的平均可能移动的位置），d 是游戏结束前的平均深度或者移动数。

如果运行井字棋（思考）所需的时间是 1，那么不同的游戏相关运行时间大致如下：

• 四目：1.80 * 10^16
• **Othello (黑白棋)**：3.81 * 10^52
• 五目 - 五子棋：1.77 * 10^64
• 国际象棋：1.28 * 10^118
• **围棋 (Weiqi)**：1.87 * 10^354

打个比方，你移动一根（正常）头发的长度，完全解决了井字棋，然后移动另一个头发并重复，这时有人解决四目游戏，他在你移动距离时，完成了从地球到月球往返一千次移动。换言之，我们不能单纯使用深度优先搜索，去尝试解决四目或者其他复杂的游戏。

earthmoon_near_big.jpeg

这个故事的寓意是：虽然深度优先搜索可以被用来解决井字棋的游戏，但在更复杂的游戏中将会失败 - 我不信在玩四目游戏的时候，你会愿意让计算机思考很多年。这就是为什么 AI 要使用极大极小值或者Monte Carlo tree 搜索去寻找更好移动的下一步位置。虽然找到的位置并非完美，但是它们可以在数秒内完成评估计算，这很棒且很重要。

如果你想查看我的Connect Four AI（它比你在网上找到的任何其他的 AI 都要强大），请查看。

一个完整的井字棋深度优先搜索的简单 AI 案例，请戳这里。

译者加：如果你应用在五子棋这种稍微复杂的游戏中，深度优先搜索 AI 可能就会卡死你的电脑，读者可以通过更改下面的代码体验

代码片段

本文正在参加「金石计划 . 瓜分6万现金大奖」