likes
comments
collection

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

作者站长头像
站长
· 阅读数 26

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

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

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

图片来源 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 && tempResult < result)) {
        result = tempResult;
      }
    }
  }
  return result;
}

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

  1. 检查游戏是否结束 - 如果不是玩家赢或者棋盘被填满,返回游戏的结果
  2. 遍历所有的棋盘格子
  • 如果格子被使用,跳过
  • 根据当前玩家的颜色,设置格子为 XO
  • 通过递归获取游戏结果,调用相同的方法更新棋盘,并交换 xTurn 的布尔值
  • 更新当前分支的最佳结果,尝试最大化当前玩家的结果。

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

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

如果运行井字棋(思考)所需的时间是 1,那么不同的游戏相关运行时间大致如下:

  • 四目:1.80 * 101610^161016
  • Othello (黑白棋):3.81 * 105210^521052
  • 五目 - 五子棋:1.77 * 106410^641064
  • 国际象棋:1.28 * 1011810^11810118
  • 围棋 (Weiqi):1.87 * 1035410^35410354

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

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

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

如果你想查看我的Connect Four AI(它比你在网上找到的任何其他的 AI 都要强大),请查看

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

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

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