极小极大搜索算法的判据_广度优先搜索图解「建议收藏」

极小极大搜索算法的判据_广度优先搜索图解「建议收藏」极小极大算法(TheMinimaxAlgorithm)[说明]本文基于,本文中的图片均来源于此笔记

极小极大算法 (The Minimax Algorithm)


[说明] 本文基于 
<>, 本文中的图片均来源于此笔记。

极小极大算法常用于二人博弈游戏,目的是寻找最优的方案使得自己能够利益最大化。基本思想就是假设自己(A)足够聪明,总是能选择最有利于自己的方案,而对手(B)同样足够聪明,总会选择最不利A的方案。

下面举个例子进行说明:
设:正方形代表自己(A),圆代表对手(B),节点的每个孩子节点代表一个候选方案。
极小极大搜索算法的判据_广度优先搜索图解「建议收藏」

上图中显示了所有候选方案。让我们如下分析:(注意:图中的所有数字都是A的利益值,越大越有利于A)
极小极大搜索算法的判据_广度优先搜索图解「建议收藏」

假设A选择第一个方案,B有两个候选方案,B为了使得A利益最小化,所有在7和3中选择了3,所以A只能获得3。
极小极大搜索算法的判据_广度优先搜索图解「建议收藏」

假设A选择第二个方案,B只有一个选择,A最终可以获得15。
极小极大搜索算法的判据_广度优先搜索图解「建议收藏」

假设A选择第三个方案,B有4个可选方案,为了使得A利益最小,B选择第一个方案,则A只能获得利益1。
极小极大搜索算法的判据_广度优先搜索图解「建议收藏」

A为了使得自己利益最大,所以A会选择第一个方案,即获得利益15。

从上图可以看出,B总是选择候选方案中的最小值,而A总是选择候选方案中的最大值,极小极大的名字也就源于此。

该算法使用深度优先搜索(Depth First Search)遍历决策树来填充树中间节点的利益值,叶子节点的利益值通常是通过一个利益评估函数算得。

通常决策树的分支呈指数增长,所以基本不可能遍历整棵决策树,所以实际应用中通常会控制决策树深度,从而减少计算量。正因为无法遍历完整的决策树,所以该算法有可能造成误导,即选取的方案可能是局部最优而不是全局最优的。

有时候为了得到较好的效果不得不增加搜索树的深度,这样就增加了大量的计算。为了加快计算速度,减少计算量,可以使用Alpha-Beta剪枝算法(Alpha Beta Pruning)对搜索树进行剪枝。因为搜索树中有很多分支不需要遍历。

Alpha-Beta剪枝算法(Alpha Beta Pruning)

[说明] 本文基于<>,文中的图片均来源于此笔记。


Alpha-Beta剪枝用于裁剪搜索树中没有意义的不需要搜索的树枝,以提高运算速度。


假设α为下界,β为上界,对于α ≤ N ≤ β:

若 α ≤ β  则N有解。

若 α > β 则N无解。


下面通过一个例子来说明Alpha-Beta剪枝算法。

极小极大搜索算法的判据_广度优先搜索图解「建议收藏」

上图为整颗搜索树。这里使用极小极大算法配合Alpha-Beta剪枝算法,正方形为自己(A),圆为对手(B)。

初始设置α为负无穷大,β为正无穷大。

极小极大搜索算法的判据_广度优先搜索图解「建议收藏」

对于B(第四层)而已,尽量使得A获利最小,因此当遇到使得A获利更小的情况,则需要修改β。这里3小于正无穷大,所以β修改为3。

极小极大搜索算法的判据_广度优先搜索图解「建议收藏」

(第四层)这里17大于3,不用修改β。

极小极大搜索算法的判据_广度优先搜索图解「建议收藏」

对于A(第三层)而言,自己获利越大越好,因此遇到利益值大于α的时候,需要α进行修改,这里3大于负无穷大,所以α修改为3

极小极大搜索算法的判据_广度优先搜索图解「建议收藏」

B(第四层)拥有一个方案使得A获利只有2,α=3,  β=2, α > β, 说明A(第三层)只要选择第二个方案, 则B必然可以使得A的获利少于A(第三层)的第一个方案,这样就不再需要考虑B(第四层)的其他候选方案了,因为A(第三层)根本不会选取第二个方案,多考虑也是浪费.

极小极大搜索算法的判据_广度优先搜索图解「建议收藏」

B(第二层)要使得A利益最小,则B(第二层)的第二个方案不能使得A的获利大于β, 也就是3. 但是若B(第二层)选择第二个方案, A(第三层)可以选择第一个方案使得A获利为15, α=15,  β=3, α > β, 故不需要再考虑A(第三层)的第二个方案, 因为B(第二层)不会选择第二个方案.

极小极大搜索算法的判据_广度优先搜索图解「建议收藏」

A(第一层)使自己利益最大,也就是A(第一层)的第二个方案不能差于第一个方案, 但是A(第三层)的一个方案会导致利益为2, 小于3, 所以A(第三层)不会选择第一个方案, 因此B(第四层)也不用考虑第二个方案.

极小极大搜索算法的判据_广度优先搜索图解「建议收藏」

当A(第三层)考虑第二个方案时,发现获得利益为3,和A(第一层)使用第一个方案利益一样.如果根据上面的分析A(第一层)优先选择了第一个方案,那么B不再需要考虑第二种方案,如果A(第一层)还想进一步评估两个方案的优劣的话, B(第二层)则还需要考虑第二个方案,若B(第二层)的第二个方案使得A获利小于3,则A(第一层)只能选择第一个方案,若B(第二层)的第二个方案使得A获利大于3,则A(第一层)还需要根据其他因素来考虑最终选取哪种方案.


今天的文章极小极大搜索算法的判据_广度优先搜索图解「建议收藏」分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/86121.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注