3.1 博弈
在第一章中，我们讨论了搜索问题以及如何高效且最优地解决它们——使用强大的通用搜索算法，我们的智能体可以确定最佳计划，然后简单地执行它以到达目标。现在，让我们转变思路，考虑这样的场景：我们的智能体有一个或多个对手，他们试图阻止智能体达到目标。我们的智能体不能再运行之前学过的搜索算法来制定计划，因为我们通常无法确定性地知道对手会如何计划对抗我们以及如何响应我们的行动。相反，我们需要运行一类新的算法来解决对抗搜索问题，更常见的叫法是博弈。
博弈有许多不同的类型。博弈的行动可以有确定性或随机结果，可以有任意数量的玩家，并且可能是或不是零和博弈。我们首先要讨论的是确定性零和博弈，其中行动是确定性的，我们的收益直接等于对手的损失，反之亦然。最简单的理解方式是：博弈由一个单一变量值定义，一个团队或智能体试图最大化它，而对方团队或智能体试图最小化它，使他们处于直接竞争中。在 Pacman 游戏中，这个变量是你的分数，你试图通过快速有效地吃豆子来最大化分数，而幽灵试图通过先吃掉你来最小化你的分数。许多常见的桌面游戏也属于这一类博弈：
- 国际跳棋 — 第一个国际跳棋计算机程序创建于 1950 年。此后，国际跳棋已成为一个已解决的博弈，这意味着在双方都采取最优策略的情况下，任何局面都可以被确定性地评估为赢、输或平局。
- 国际象棋 — 1997 年，Deep Blue 成为第一个在六局比赛中击败人类国际象棋冠军加里·卡斯帕罗夫的计算机智能体。Deep Blue 使用极其复杂的方法每秒评估超过 2 亿个局面。现在的程序甚至更强，尽管不那么具有历史意义。
- 围棋 — 围棋的搜索空间比国际象棋大得多，大多数人认为围棋计算机智能体在未来几年内不可能击败人类世界冠军。然而，由 Google 开发的 AlphaGo 在 2016 年 3 月历史性地以 4:1 击败了围棋冠军李世石。
所有上述世界冠军级别的智能体都至少在某种程度上使用了我们即将介绍的对抗搜索技术。与返回完整计划的普通搜索不同，对抗搜索返回一个策略或policy，它简单地推荐在智能体和对手的某个配置下的最佳移动。我们很快会看到，这样的算法具有通过计算产生行为的美妙特性——我们运行的计算在概念上相对简单且广泛通用，但却能够天然地产生同一团队智能体之间的合作以及对对手智能体的“策略思考”。
标准的博弈形式化由以下定义组成：
- 初始状态， \(s_0\)
- 玩家， \(Players(s)\) 表示轮到谁
- 行动， \(Actions(s)\) 玩家的可用行动
- 转移模型 \(Result(s, a)\)
- 终止测试， \(Terminal-test(s)\)
- 终止值， \(Utility(s, player)\)