技术博客
首页 所有文章 标签 分类 关于
技术博客

目录

人工智能学习四对抗搜索

 收录于 人工智能基础
   约 3980 字   预计阅读 8 分钟 
https://bing.ee123.net/img/rand?artid=124935765

人工智能学习（四）：对抗搜索

目录

3.1 引言

对于多 https://latex.csdn.net/eq?Agent 环境，其中每个 https://latex.csdn.net/eq?Agent 需要考虑到其他 https://latex.csdn.net/eq?Agent 的行动及其对自身的影响。其他 https://latex.csdn.net/eq?Agent 的不可预测性可能导致该 https://latex.csdn.net/eq?Agent 问题求解过程中的偶发性。

竞争环境 ：

竞争环境中每个 https://latex.csdn.net/eq?Agent 的目标之间是有冲突的，这就引出了对抗搜索问题通常被称为博弈。

博弈 ：

人工智能中“博弈”通常专指博弈论专家们称为 有完整信息的 、 确定性的 、 轮流行动的 、 两个游戏者的零和游戏 。

术语中，这是指在确定的、完全可观察的环境中两个 https://latex.csdn.net/eq?Agent 必须轮流行动，在游戏结束时效用值总是相等并且符号相反。正是 https://latex.csdn.net/eq?Agent 之间效用函数的对立导致了环境是对抗的。

博弈游戏中的状态很容易表示， https://latex.csdn.net/eq?Agent 的行动数目通常受限，而行动的输出都有严谨的规则来定义。博弈要求具备在无法计算出最优决策的情况下也要给出某种决策的能力。博弈对于低效率有严厉的惩罚。

3.2 游戏的分类

四个维度：

确定性的 和 非确定性的

  • 确定性的 ：跳棋，国际象棋，围棋。
  • 非确定性的 ：西洋双陆棋（使用了骰子确定下一步的行为）。

玩家的数量

  • 一名玩家：纸牌。
  • 两名玩家：跳棋，国际象棋，围棋，西洋双陆棋。
  • 更多玩家：扑克。

是否零和

  • 零和：玩家都是在互相对抗。
  • 非零和：玩家并不是都在互相对抗。

信息是否完整

  • 信息完整：当玩家决定一步时，他了解游戏当前状态的所有信息。例子：国际象棋，跳棋，围棋。
  • 信息不完整：当玩家决定一步时，他不能了解游戏当前状态的所有信息。例子：扑克（不知道其他玩家的牌）。

3.3 形式化游戏问题

首先考虑两人参与的游戏： https://latex.csdn.net/eq?MAX 和 https://latex.csdn.net/eq?MIN 。 https://latex.csdn.net/eq?MAX 先行，两人轮流出招，直到游戏结束。游戏结束时给优胜者加分，给失败者罚分。游戏可以形式化成含有下列组成部分的一类搜索问题。

  • https://latex.csdn.net/eq?So ：初始状态，规范游戏开始时的情况。
  • https://latex.csdn.net/eq?PLAYER%28s%29 ：定义此时该谁行动。
  • https://latex.csdn.net/eq?ACTIONS%28s%29 ：返回此状态下的合法移动集合。
  • https://latex.csdn.net/eq?RESULT%28s%2Ca%29 ：转移模型，定义行动的结果。
  • https://latex.csdn.net/eq?TERMINAL-TEST%28s%29 ：终止测试，游戏结束返回真，否则返回假。游戏结束的状态称为终止状态。
  • https://latex.csdn.net/eq?UTILITY%28s%2Cp%29 ：效用函数（也可称为目标函数或收益函数），定义游戏者 https://latex.csdn.net/eq?p 在终止状态 https://latex.csdn.net/eq?s 下的数值。在国际象棋中，结果是赢、输或平，分别赋予数值 https://latex.csdn.net/eq?+1 ， https://latex.csdn.net/eq?0 ，或 https://latex.csdn.net/eq?1/2 。

零和博弈是指在同样的棋局实例中所有棋手的总收益都一样的情况。国际象棋是零和博弈，棋局的收益是 https://latex.csdn.net/eq?0+1%2C%201+0 或 https://latex.csdn.net/eq?1/2+1/2 。“常量和”可能是更好的术语，但称为零和更传统，可以将这看成是下棋前每个棋手都被收了 https://latex.csdn.net/eq?1/2 的入场费。

初始状态、 https://latex.csdn.net/eq?ACTIONS 函数和 https://latex.csdn.net/eq?RESULT 函数定义了游戏的博弈树其中结点是状态 ，边是移动。下图给出了井字棋的部分博弈树。在初始状态 https://latex.csdn.net/eq?MAX 有九种可能的棋招。游戏轮流进行， https://latex.csdn.net/eq?MAX 下 https://latex.csdn.net/eq?x ， https://latex.csdn.net/eq?MIN 下 https://latex.csdn.net/eq?0 ，直到到达了树的终止状态即一位棋手的标志占领一行、一列、一对角线或所有方格都被填满。叶结点上的数字是该终止状态对于 https://latex.csdn.net/eq?MAX 来说的效用值；值越高对 https://latex.csdn.net/eq?MAX 越有利，而对 https://latex.csdn.net/eq?MIN 则越不利（这也是棋手命名的原因）。

https://i-blog.csdnimg.cn/blog_migrate/7b3dc1a008d5daab85464f9228237640.png

3.4 零和游戏

在零和游戏中，代理具有相反的效用，他们必需争夺一个或者一组可用的资源。如果一个代理得到了它，另一个代理就没有得到它。简言之，对方得到的越多，你得到的就越少。

这意味着，我们只需要为其中一个代理设计效用函数（ https://latex.csdn.net/eq?utilities ），另一个代理就具有相反的效用函数（代理1效用函数的负值）。零和游戏模拟了一种纯竞争的情况。

其他类型的游戏，代理可能会拥有独立的 https://latex.csdn.net/eq?utilities ，可能会带来双赢的结果。

3.5 对抗性搜索

3.5.1 单代理博弈树

https://i-blog.csdnimg.cn/blog_migrate/76eb2b65fdca17a64b76f1f270fd3690.png

有两个可用的操作：向西或者向东。以此类推：

https://i-blog.csdnimg.cn/blog_migrate/65a041996a9f756684212bd0745fb886.png

https://i-blog.csdnimg.cn/blog_migrate/f62dc0e175710b06f2327d139ca30ba7.png

在这些游戏场景中，对于每个终端状态，我们关联一个 https://latex.csdn.net/eq?utility ：

https://i-blog.csdnimg.cn/blog_migrate/b352ff082742536a81330f4935818c9c.png

8：每走一步扣一分，吃一个豆子加十分，走了两步吃了一个豆子，所以8分。

https://i-blog.csdnimg.cn/blog_migrate/f05556405e06d027d9ffc6e9fdc3d7de.png

对于非终止状态，我们查看子集并取子集值得最大值。

https://i-blog.csdnimg.cn/blog_migrate/7e7263464f7fe0dfa95391cad7f3cc0a.png

3.5.2 对抗性游戏

https://i-blog.csdnimg.cn/blog_migrate/77145de568eb9d2ce1557364168e022b.png

吃豆人和鬼魂互相对抗，吃豆人试图最大化得分，幽灵想通过吃吃豆人来最小化得分。

假设吃豆人和鬼魂交替移动：

https://i-blog.csdnimg.cn/blog_migrate/483b0abbd536c814d0d9f7f40c9e904c.png

https://i-blog.csdnimg.cn/blog_migrate/07b9676d6815bb52fb661269d1036732.png

3.5.2.1 Minmax

进阶版吃豆人游戏 ：

https://i-blog.csdnimg.cn/blog_migrate/77a7846dec656dc0a470df51d069b4a0.png

这里，你无法通过最后一层得取值得到你想要得分数（ https://latex.csdn.net/eq?+8 ），因为第二层由鬼魂控制。由于鬼魂得目标是最小化你的分数，所以第二层的取值左边是 https://latex.csdn.net/eq?-8 ，右边是 https://latex.csdn.net/eq?-10 。最终你可以从第二层中选择最大的值作为下一步的行为（ https://latex.csdn.net/eq?-8 ）。

https://i-blog.csdnimg.cn/blog_migrate/585d9e517f2223cfe9ec1bb9e6894e7e.png

https://i-blog.csdnimg.cn/blog_migrate/f1bdc9a7dbf0b7e7dcf8c444d2113545.png

井字游戏 ：

根节点的取值我无法直接得出，只能由下而上的获取，但它必定是 https://latex.csdn.net/eq?%5B-1%2C0%2C1%5D 中的一个。并且我们知道如果是两个绝对聪明的人在玩井字游戏，根节点的值一定是 https://latex.csdn.net/eq?0 ，即平局，用术语来说，井字游戏被解决了（ https://latex.csdn.net/eq?be%5C%3A%20%5C%3A%20solved ）。

https://i-blog.csdnimg.cn/blog_migrate/60fe65c585a5be0e219c7b13637cffef.png

正式化对抗搜索（Minmax）

对于确定性零和游戏：井字游戏，国际象棋，跳棋，一个玩家最大化叶节点的 https://latex.csdn.net/eq?utility ，另一个是将其最小化。

在极大极小搜索（ https://latex.csdn.net/eq?Minmax ）中：

https://i-blog.csdnimg.cn/blog_migrate/0a81091e5c18b9aa9f05916f30d7f69c.png

  • 我们有一个状态空间搜索树；
  • 玩家轮流交替；
  • 为了计算每个节点的极大极小值，我们从底向上工作。

https://i-blog.csdnimg.cn/blog_migrate/4027f44da8a95ba4086297ab9c831b99.png

在 https://latex.csdn.net/eq?max%20%5C%3A%20%5C%3A%20node 处，我们初始化该节点的估计值为负无穷大。然后我们开始检查所有子节点，看后继节点的值是多少，如果它们高于我们目前的值，我们增加并最终返回我们在所有后继节点中看到的最大值。

https://i-blog.csdnimg.cn/blog_migrate/6ad013131004ec4e7e93818a4f2c3751.png

https://latex.csdn.net/eq?Min 是确切的对应物，开始初始化为无穷大，然后每检查一个新的后继节点是否比之前的后继节点更适合 https://latex.csdn.net/eq?minimizer 。如果是则更新该值。

https://i-blog.csdnimg.cn/blog_migrate/cb84c0258b73839923940c2ce1bb793a.png

代码中必须有某种类型的 https://latex.csdn.net/eq?base%20%5C%3A%20%5C%3A%20case ，还需要有计算状态值的调度函数：

https://i-blog.csdnimg.cn/blog_migrate/27b8959462ecd20401ad727ccf37c51c.png

首先检查，我是否到达了 https://latex.csdn.net/eq?base%20%5C%3A%20%5C%3A%20case 。如果我遇到的 https://latex.csdn.net/eq?base%20%5C%3A%20%5C%3A%20case 是终止状态，则返回该终止状态的值。如果不是，那么检查我所在的节点，是否在 https://latex.csdn.net/eq?maximizer%5C%3A%20%5C%3A%20node ，然后调用 https://latex.csdn.net/eq?max 。如果我在 https://latex.csdn.net/eq?minimizer%5C%3A%20%5C%3A%20node ，调用 https://latex.csdn.net/eq?min ：

https://i-blog.csdnimg.cn/blog_migrate/1b4d51a52dbff93e66c2f471396ed67c.png

https://latex.csdn.net/eq?Minmax 演示：

https://i-blog.csdnimg.cn/blog_migrate/8665aa30403857c22e1d9fb11e382274.png

使用 https://latex.csdn.net/eq?Minmax ，玩家得出自己最大的得分是 https://latex.csdn.net/eq?10 ，所以会选择左边的行为。但这是基于我们的对手绝对聪明的情况下。

https://i-blog.csdnimg.cn/blog_migrate/6edfb060d5633569cd21ff49f2bd8bee.png

那假如我们的对手没有那么聪明，他会周期性的犯错，玩家就会选择右边，因为即使对手没有犯错，玩家依然能拿到 https://latex.csdn.net/eq?9 分，但如果对手犯错，玩家可以拿到惊人的 https://latex.csdn.net/eq?100 分。

https://i-blog.csdnimg.cn/blog_migrate/1e7667722adf40770a625e53b8586117.png

在下面这种吃豆人的场景中，吃豆人依据 https://latex.csdn.net/eq?Minmax 做出的选择是什么：往右走，在最少的步数被吃掉。（步数会扣分）

https://i-blog.csdnimg.cn/blog_migrate/b6d70426b7e75dcf72268b2ff9935e7c.png

https://i-blog.csdnimg.cn/blog_migrate/dac329fc40da39d06b543be41089e1c6.png

但是同样，我们可以假设蓝色的鬼魂犯错，它朝着远离我们的方向行进。如果它确实这样做了，吃豆人就可以吃完豆子赢得比赛。即使蓝色鬼魂没有犯错，朝着吃豆人，行进，吃豆人也可以重新选择俯冲向红色鬼魂。

https://i-blog.csdnimg.cn/blog_migrate/c30eb3b8eeb4ed797396fc5649ebe057.png

https://i-blog.csdnimg.cn/blog_migrate/33c94f954d09d9d6d63331a1f370a5f0.png

3.5.2.2 Minmax的效率

类似于穷尽的深度优先搜索：

时间复杂度： https://latex.csdn.net/eq?O%28b%5E%7Bm%7D%29

空间复杂度： https://latex.csdn.net/eq?O%28bm%29

3.5.3 博弈树修剪

https://i-blog.csdnimg.cn/blog_migrate/47d272721fe518bcc60a111e37430a54.png

第一个分支要遍历完我们才能获取游戏的初始信息，并将 https://latex.csdn.net/eq?3 更新到根节点：

https://i-blog.csdnimg.cn/blog_migrate/6d906434d3ac7112b9a2e65f91dc0279.png

第二个分支，当发现并更新 https://latex.csdn.net/eq?2 的时候，我们就已经知道这个分支的所有叶子节点值被 https://latex.csdn.net/eq?minimizer 选择的上限就是 https://latex.csdn.net/eq?2 。然而根节点依据 https://latex.csdn.net/eq?maximizer 只会关注比 https://latex.csdn.net/eq?3 大的值，所以第二分支剩下的节点是可以被剪裁掉的。

https://i-blog.csdnimg.cn/blog_migrate/20178b1f6c91ce7fbba7d29e0c6b71fb.png

第三个分支，第一个叶节点更新 https://latex.csdn.net/eq?14 ，但是这里我们并不能停止搜索，因为 https://latex.csdn.net/eq?14 是 https://latex.csdn.net/eq?maximizer 感兴趣的取值：

https://i-blog.csdnimg.cn/blog_migrate/98ff0a7c2587079acef0bc4caf010676.png

第三个分支遍历到 https://latex.csdn.net/eq?5 的时候，父节点的值更新为 https://latex.csdn.net/eq?%5Cleq%205 ，同样是 https://latex.csdn.net/eq?maximizer 感兴趣的取值，我们需要继续搜索查看

https://i-blog.csdnimg.cn/blog_migrate/591b07b4d9db21e527abb2151464eb58.png

3.5.3.1 Alpha-Beta Pruning

Alpha-Beta: : Pruning

在这个博弈树中，我们计算某个节点的最小值 https://latex.csdn.net/eq?n 。因此要遍历 https://latex.csdn.net/eq?n 的子节点，在我们遍历它的子节点的过程中，该节点的取值不断下降。当某一时刻，这个节点的最小值 https://latex.csdn.net/eq?n 小于 https://latex.csdn.net/eq?a ，那我们知道无论后继节点还有什么， https://latex.csdn.net/eq?maximizer 都不会让这条路发生。所以我们并不关心 https://latex.csdn.net/eq?n 的真实取值，因为游戏不会在那里结束，我们只关心它是否小于 https://latex.csdn.net/eq?a 。通过这种方式我们可以剪裁掉大量计算。

https://i-blog.csdnimg.cn/blog_migrate/6ffe25f17e26b188b0b4996c44ff8b3c.png

https://i-blog.csdnimg.cn/blog_migrate/a4ae30af068452a91c54dc7fd2aa8edc.png

https://latex.csdn.net/eq?Alpha-Beta%5C%3A%20%5C%3A%20Pruning 的特性

这种剪枝对根的最大最小值计算没有影响！

中间节点的值可能是错的：

  • 重要：根的子元素可能具有错误的值。
  • 所以最原始的版本不会让你做动作选择。

例如下面的例子：

左边的 https://latex.csdn.net/eq?10 是我们确切得到的，由于运行了 https://latex.csdn.net/eq?Alpha-Beta%5C%3A%20%5C%3A%20Pruning ，右边的 https://latex.csdn.net/eq?10 并不意味着玩家走这条路会得到 https://latex.csdn.net/eq?10 分，相反他会得到 https://latex.csdn.net/eq?0 分。所以我们就要做出一些保证，确保玩家不会被右边的值误导。比如，我们记住第一个计算出来的值并选择他，这个值是有保证的。第二个方法是在子结点上运行 https://latex.csdn.net/eq?Alpha-Beta%5C%3A%20%5C%3A%20Pruning 。第三个方法，我们在修剪时只修剪严格小于和严格大于，而完整计算等于的分支（这样可能会少剪裁很多分支）。

https://i-blog.csdnimg.cn/blog_migrate/ad1df998f77b6394d2f51d697ac9b681.png

良好的子排序可以提高修剪效率。意思是当你洞察全局，可以先修剪好的选择再修剪坏的选择，会极大的提高效率。

经过完美排序后：

时间复杂度降为： https://latex.csdn.net/eq?O%28b%5E%7Bm/2%7D%29 （ https://latex.csdn.net/eq?m 代表游戏结束前的移动步数），这也意味着我们可以看到两倍的深度。但依然不足以解决国际象棋这类游戏。

这是一个简单的元推理的例子：进行计算以确定要计算内容的地方。

3.5.3.2 资源限制

在现实的游戏中找不到叶子。

https://i-blog.csdnimg.cn/blog_migrate/98489b46e4b2a3487076fb98fac93490.png

我们进行深度限制搜索，我们只搜索到自己定义的终端节点（不是真正的终端节点），对于终端节点我们会近似的估算他的取值而不是他的真实取值，就像启发式函数一样。

例如：假设我们有 https://latex.csdn.net/eq?100 秒，可以探索 https://latex.csdn.net/eq?10K 个节点/秒，所以每一步可以检查 https://latex.csdn.net/eq?100 万个节点， https://latex.csdn.net/eq?%5Calpha%20-%5Cbeta 达到大约 https://latex.csdn.net/eq?8 级深度——好的国际象棋程序。

最佳游戏的保证已经消失。

更多的层级会带来很大的不同。

使用迭代深化来实现一个随时随地的算法。比如刚开始搜索到深度 https://latex.csdn.net/eq?2 ，如果还有时间就搜索到深度直到时间耗尽，从以前的搜索结果中获取答案。

3.5.3.3 深度限制带来的问题

https://i-blog.csdnimg.cn/blog_migrate/8f4ec164738ab80f75bedb4543527531.png

重新规划代理人的危险：

  • 他知道现在吃了这个点，他的分数会提高（西，东）。
  • 他知道他的分数会在稍后吃点（东，西）时同样增加。
  • 在吃完圆点后，没有得分的机会（在地平线内，这里有两个）。
  • 因此，等待似乎和吃东西一样好：他可以向东走，然后在下一轮重新规划时再向西走!

因为深度限制重新定义了游戏，他只会判断在这两步中那一步最好。所以我们需要增加一些额外的东西，比如靠近点的奖励。

3.5.4 评估函数

评估函数对深度有限的搜索中的非端点进行评分：

https://i-blog.csdnimg.cn/blog_migrate/bc1fa79f1571b1376d02bc39c2b282f5.png

理想函数：返回位置的实际最小值。

在实践中：通常是加权的线性特征之和：

https://i-blog.csdnimg.cn/blog_migrate/2a87e2b726b05b2aa4678a0f2bbee0be.png

https://i-blog.csdnimg.cn/blog_migrate/b2dc7d391254a457ad18e5693e25ccc9.png

我们需要不断测试和调整我们的评估函数：

https://i-blog.csdnimg.cn/blog_migrate/8264e0b6f73ef416aef7a488b34c8ff3.png

当下面的情况比上面糟糕的时候，我们的评估函数是否给出了一个更坏的分数：

https://i-blog.csdnimg.cn/blog_migrate/dc01a51566c08267d29d78f427993f94.png

https://i-blog.csdnimg.cn/blog_migrate/66f2fced4e0ad58b1cc8d129b376cb20.png

https://i-blog.csdnimg.cn/blog_migrate/e7cca9e19f68be2b9acfe462053a174e.png

鬼魂的策略是跟随吃豆人，但是当它们发现可以结束游戏时（吃掉吃豆人），它们就会选择结束游戏的行为。

双方都使用Minmax进行对抗的吃豆人

深度的重要性：

https://i-blog.csdnimg.cn/blog_migrate/d9ab8a14309a85867fb46c9578166014.png

评估函数总是不完美的，

评估函数在树上埋得越深，评估函数的质量就越不重要，

特征的复杂性和计算的复杂性之间权衡的一个重要例子。花费在评估函数上的时间越多，我们花费在搜索上的时间越少。

3.5.5 Alpha-Beta Pruning和评估函数之间是否存在协同作用

我们将它们视为两个正交的事务：

  • 评估函数是一种有效的将节点当作终端节点的方法，而不需要一定要搜索到底部节点。
  • https://latex.csdn.net/eq?Alpha-Beta 是一种跳过部分树的方法。

https://latex.csdn.net/eq?Alpha-Beta 的修剪量取决于我们的扩展顺序，而评估函数又可以指导我们先扩展什么。因为我们说过如果我们先找到了好的选择，我们就可以修剪更多的分支，所以它们是相辅相成的。

https://latex.csdn.net/eq?Alpha-Beta 中， https://latex.csdn.net/eq?min 节点的价值一直在继续下降，一旦最小节点的值低于到根路径上最大可用的更好选项，您就可以停止。这是如何决定停止的替代方法。但是当我们拥有一个有界的评估函数，如果能够快速估算节点的价值，那么修剪也会更快的发生。

更新于 2022-05-28
 算法, 学习, 人工智能
返回 | 主页