什么是对抗算法
为了解决信息确定、全局可观察、竞争对⼿轮流⾏动、输赢收益零和假设下的两⼈博弈问题⽽提出的⼀种算法。即零和博弈，所谓零和博弈是博弈论的⼀个概念，属⾮合作博弈。指参与博弈的各⽅，在严格竞争下，⼀ ⽅的收益必然意味着另⼀⽅的损失，博弈各⽅的收益和损失相加总和永远为“零”，双⽅不存在合作的可能。 ⾸先介绍⼀种常见的基础对抗算法：最⼩最⼤搜索算法。
最⼩最⼤搜索是在对抗搜索中最为基本的⼀种让玩家来计算最优策略的⽅法.。在开始之前我们需要定义如下基本概念：
产权比率 以井字棋游戏的对抗搜索为例，如下图所⽰：
上图中的MAX和MIN可以看作是我和对⼿之间的博弈，但需要注意的是这个遍历树是以⾃⼰的视⾓出发所构建的，即在该游戏中max 代表⾃⼰需要获得的⾼分，⽽min代表对⼿希望⾃⼰获得的低分 。其所形成游戏树的叶⼦节点有9！=362880种，即会出现的情况。 minimax算法流程
我们给出如下例⼦：
如果最后⼀排是终⽌节点，那么MIN则会选择其中最⼩的数值，如上图中红⾊框中所选择出来的数值。⽽MAX会从MIN选择最⼩的数值之后从中选择⼀个最⼤的数值3。
恢复精力Alpha-Beta剪枝算法
⼀种对最⼩最⼤搜索进⾏改进的算法，即在搜索过程中可剪除⽆需搜索的分⽀节点，且不影响搜索结果。该算法需要尽量去剪除那些不⽤搜索的节点从⽽节省时间和空间。ddm
如何进⾏剪枝呢？请看下图：
美术馆旁边的动物园
shifugao如上图所⽰，假设我们已近搜完了B节点，得到其最⼩收益为3，然后开始搜C节点，当搜到2的时候，剩下的两个4和6就没有必要搜索下去了，因为不管接下来搜到什么，整个C得出来的结果都会⽐B的结果3要⼩。
可以看出，如果对于⼀颗⾮常巨⼤的树来说，如果可以剪枝⼀部分对搜索结果没有影响的分⽀，将会⼤⼤提⾼搜索的效率。
整个的搜索流程可展⽰为下图所⽰过程：
那alpha、beta剪枝搜索中的Alpha，Beta⼜是什么呢？
Alpha值α：假设n是MIN节点，如果n的⼀个后续节点可提供的收益⼩于α，则n及其后续节点可被剪枝。因为你是MIN节点，搜到⼀个更⼩的节点对⼿不会这么⼲，所以没必要搜索下去。
Beta值β：假设n是MAX节点，如果n的⼀个后续节点可获得收益⼤于β，则n及其后续节点可被剪枝。因为你是MAX节点，搜到⼀个更⼤的节点虽然你⾃⼰很喜欢，但是对⼿也不会让你这么⼲的。
每个节点有两个值，分别是α值和β值。节点α和β值在搜索过程中不断变化。其中α从负⽆穷⼤逐渐增加、β从正⽆穷⼤逐渐减少，如果⼀个节点中α > β ，则该节点的后续节点可剪枝。
值得注意的是，剪枝本⾝并不会影响算法输出结果，⽽节点先后次序会影响剪枝效率。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议