theme: fancy
原文链接 Tic Tac Toe AI with a Depth-First Search -- 作者 Ofek Gila
深度优先搜索是种深度优先遍历树的算法，这意味着它递归地遍历树，在继续下一个分支前，遍历完当前分支。
图片来源 Wikipedia
它可以用来处理游戏，找到最佳移动位置或者简单实现谁赢得游戏的理想玩法。这种游戏 AI 最容易去实现，因为它不需要构建树。这种算法自下而上工作，无需重新检测任何结点，它通常使用递归函数和检查游戏是否结束的函数。
译者加：AI -> 人工智能（Artificial Intelligence）
对于井字棋，我们可以考虑下面方法：
代码语言：javascript复制/**
* @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 做了以下这些工作：
- 检查游戏是否结束 - 如果不是玩家赢或者棋盘被填满，返回游戏的结果
- 遍历所有的棋盘格子
- 如果格子被使用，跳过
- 根据当前玩家的颜色，设置格子为
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
打个比方，你移动一根（正常）头发的长度，完全解决了井字棋，然后移动另一个头发并重复，这时有人解决四目游戏，他在你移动距离时，完成了从地球到月球往返一千次移动。换言之，我们不能单纯使用深度优先搜索，去尝试解决四目或者其他复杂的游戏。
这个故事的寓意是：虽然深度优先搜索可以被用来解决井字棋的游戏，但在更复杂的游戏中将会失败 - 我不信在玩四目游戏的时候，你会愿意让计算机思考很多年。这就是为什么 AI 要使用极大极小值或者Monte Carlo tree 搜索去寻找更好移动的下一步位置。虽然找到的位置并非完美，但是它们可以在数秒内完成评估计算，这很棒且很重要。
如果你想查看我的Connect Four AI（它比你在网上找到的任何其他的 AI 都要强大），请查看。
一个完整的井字棋深度优先搜索的简单 AI 案例，请戳这里。
译者加：如果你应用在五子棋这种稍微复杂的游戏中，深度优先搜索 AI 可能就会卡死你的电脑，读者可以通过更改下面的代码体验
代码片段
本文正在参加「金石计划 . 瓜分6万现金大奖」
