对抗搜索之【最大最小搜索】【Alpha-Beta剪枝

简介: 对抗搜索之【最大最小搜索】【Alpha-Beta剪枝

 本节这里我们讨论的是确定的、完全可观测、序贯决策、零和游戏下的对抗搜索。

  所谓零和博弈是博弈论的一个概念,属非合作博弈。指参与博弈的各方,在严格竞争下,一 方的收益必然意味着另一方的损失,博弈各方的收益和损失相加总和永远为“零”,双方不存在 合作的可能。

  对抗搜索(Adversarial Search)一般指的是博弈双方会阻止对方收益最大化,也称为博弈搜索(Game Search)。在博弈游戏中经常会碰到,比如围棋这种零和游戏。智能体(agents)之间通过竞争实现相反的利益。

  对抗搜索主要有三种:最大最小搜索(Minimax Search)、Alpha-Beta剪枝搜索(Pruning Search)和蒙特卡洛树搜索(Monte-Carlo Tree Search)。

最小最大搜索

  最小最大搜索是在对抗搜索中最为基本的一种让玩家来计算最优策略的方法.。在开始之前我们需要定义如下基本概念:

202002081134090.png

  以Tic-Tac-Toe游戏的对抗搜索 为例,如下图所示:

20200208142349965.png

  上图中的MAXMIN可以看作是两个对手,MAX希望游戏的终局得分高,MIN希望游戏的终局得分低。其所形成游戏树的叶子节点有9!=362880种。

minimax算法

  那minimax算法大体的工作流程是怎样的呢?我们给出如下例子:

  如果最后一排是终止节点,那么MIN则会选择其中最小的数值,如上图中红色框中所选择出来的数值。而MAX会从MIN选择最小的数值之后从中选择一个最大的数值3

  用人话来逻辑理解一下:从最糟糕的情况中选择一个最好的情况。比如让你选择掉100块钱还是50块钱,两种情况都不好,但是你依旧会选择掉50块钱这一个相对来说不那么糟糕的情况。

  在minimax算法里面,MAX会选择后续玩法最大的一种玩法。而MIN会选择后续玩法里面最小的一种玩法。两者轮流竞争。

20200208144432148.png

  minimax的算法非常简单有效的对抗搜索算法,如果计算资源足够的话,这种算法可返回最优结果。但是就是这个计算资源可能会导致在对一些复杂的情况下无法穷举,无法在有效时间内返回结果。

  由此后人改进提出了:用alpha-beta pruning算法来减少搜索节点;或者对节点进行采样、而非逐一搜索 (蒙特卡洛树搜索)。

alpha、beta剪枝搜索

  一种对最小最大搜索进行改进的算法,即在搜索过程中可剪除无需搜索的分支节点,且不影响搜索结果。该算法需要尽量去剪除那些不用搜索的节点。

  那如何来剪枝呢?

20200208145718516.png

  如上图所示,假设我们已近搜完了B BB节点,得到其最小收益为3,然后开始搜C CC节点,当搜到2的时候,剩下的两个46就没有必要搜索下去了,因为不管接下来搜到什么,整个C CC得出来的结果都会比B BB的结果3要小。

  可以看出,如果对于一颗非常巨大的树来说,如果可以剪枝一部分对搜索结果没有影响的分支,将会大大提高搜索的效率。

  整个的搜索流程可展示为下图所示过程:

20200208150939890.png

  那alphabeta剪枝搜索中的AlphaBeta又是什么呢?

  • Alpha值α \alphaα:假设n nnMIN节点,如果n nn的一个后续节点可提供的收益小于α \alphaα,则n nn及其后续节点可被剪枝。因为你是MIN节点,搜到一个更小的节点对手不会这么干,所以没必要搜索下去。
  • Beta值β \betaβ:假设n nnMAX节点,如果n nn的一个后续节点可获得收益大于β \betaβ,则n nn及其后续节点可被剪枝。因为你是MAX节点,搜到一个更大的节点虽然你自己很喜欢,但是对手也不会让你这么干的。

  每个节点有两个值,分别是α \alphaα值和β \betaβ值。节点α \alphaαβ \betaβ值在搜索过程中不断变化。其中α \alphaα从负无穷大逐渐增加、β \betaβ从正无穷大逐渐减少,如果一个节点中α > β \alpha > \betaα>β,则该节点的后续节点可剪枝。

  • Alpha、Beta剪枝算法伪代码

  AlphaBeta剪枝算法的伪代码如下图所示:

20200208153619246.png

  • 剪枝本身并不会影响算法输出结果。节点先后次序会影响剪枝效率。

我的微信公众号名称:深度学习先进智能决策

微信公众号ID:MultiAgent1024

公众号介绍:主要研究深度学习、强化学习、机器博弈等相关内容!期待您的关注,欢迎一起学习交流进步!

相关文章
|
3月前
|
机器学习/深度学习 算法
R语言超参数调优:深入探索网格搜索与随机搜索
【9月更文挑战第2天】网格搜索和随机搜索是R语言中常用的超参数调优方法。网格搜索通过系统地遍历超参数空间来寻找最优解,适用于超参数空间较小的情况;而随机搜索则通过随机采样超参数空间来寻找接近最优的解,适用于超参数空间较大或计算资源有限的情况。在实际应用中,可以根据具体情况选择适合的方法,并结合交叉验证等技术来进一步提高模型性能。
|
6月前
|
搜索推荐 开发者
如何在 Elasticsearch 中选择精确 kNN 搜索和近似 kNN 搜索
【6月更文挑战第8天】Elasticsearch 是一款强大的搜索引擎,支持精确和近似 kNN 搜索。精确 kNN 搜索保证高准确性但计算成本高,适用于对精度要求极高的场景。近似 kNN 搜索则通过牺牲部分精度来提升搜索效率,适合大数据量和实时性要求高的情况。开发者应根据业务需求和数据特性权衡选择。随着技术发展,kNN 搜索将在更多领域发挥关键作用。
189 4
|
6月前
|
机器学习/深度学习 算法
机器学习中的超参数优化涉及手动尝试、网格搜索、随机搜索、贝叶斯优化、梯度优化、进化算法等策略
【6月更文挑战第28天】**机器学习中的超参数优化涉及手动尝试、网格搜索、随机搜索、贝叶斯优化、梯度优化、进化算法等策略。工具如scikit-optimize、Optuna助力优化,迁移学习和元学习提供起点,集成方法则通过多模型融合提升性能。资源与时间考虑至关重要,交叉验证和提前停止能有效防止过拟合。**
82 0
|
机器学习/深度学习 人工智能 算法
|
存储 机器学习/深度学习 算法
搜索与图论 - 搜索与图在算法中的应用【上】
搜索与图论 - 搜索与图在算法中的应用【上】
|
机器学习/深度学习 算法
搜索与图论 - 搜索与图在算法中的应用【中】
搜索与图论 - 搜索与图在算法中的应用【中】
|
移动开发 算法
秒懂算法 | A*搜索
本篇内容包括了A*搜索算法的原理精解以及2个例题。
562 1
秒懂算法 | A*搜索
|
存储 并行计算 算法
秒懂算法 | 搜索基础
本篇介绍了BFS和DFS的概念、性质、模板代码。
167 0
秒懂算法 | 搜索基础
|
XML 算法 C语言
干货 | 自适应大邻域搜索(ALNS)和禁忌搜索(TS)实验对比附代码
干货 | 自适应大邻域搜索(ALNS)和禁忌搜索(TS)实验对比附代码
1411 0
干货 | 自适应大邻域搜索(ALNS)和禁忌搜索(TS)实验对比附代码
【TP5.1】模糊搜索的调整
【TP5.1】模糊搜索的调整
115 0
【TP5.1】模糊搜索的调整