本文主要粗略的讲解一下min-max和剪枝原理,
背景:
min-max是香农首先提出的 ,剪枝可以认为是min-max的一个细节优化后的实现方法
主要考虑背景为2人棋类博弈
简化模型如下:
给定一2叉树,树的节点表示对弈状态,
节点的父子关系,表示父节点状态可以通过一种合理走法到达的子节点状态;
根节点用方形,表示轮到我走棋,三角形,表示轮到对手走棋;
然后每一层级类型交替出现;
为简化假设这个树的每个分支的长度都是一样的;
最后的叶子节点对应棋局结束,这个节点不对应走子,因此用圆形表示,只存了一个数字,表示这条走子路径下的终局得分,
我希望得分越高越好,对手希望得分越少越好;
给出图示(来自网络):
图中方形表示我走,三角形表示对手走,
min-max的目标就是给定这个博弈树,希望求出根节点的双方最优下法的终局得分;
图中就是20,显然图中有些博弈路径能够到大比20更大的值,那为何结果是20呢,原因在于双方最优下法;
什么叫双方最优下法?
所谓双方最优下法,其定义是递归的;
对于某个节点来说,如果它是轮到我走子,那么就是:
当前所有可能走法中,对手在该走法下选择对他最优下法的终局得分的 最大值所对应的下法;
可见该定义依赖对手的最优下法的定义;
对手的最优下法定义如下:在当前所有可能的走法中,我在该走法下选择对我最优下法下的终局的得分 的最小值所对应的下法;
这个递归显然不能无穷无尽;
最后到叶子节点的上一级节点就比较简单了,如果是我,就是叶子节点较大的那个值所对应的走法;如果是对手就是叶子节点较小值所对应的走法 ;
由此可见,这个递归定义是合理的,前提是这个博弈树必须给定,博弈给定的情况下,我们就可以从最下面的节点开始依次定义每个节点的最优下法;
其实这个定义直接就给出了min-max算法的实现过程了,从最下面的走子节点开始,
首先:第三层最左边的节点是20,方形,说明轮到我走子,按定义该节点的最优走法对应的值是20;
类似,图中已经清楚的给出了每一级的值;
可以看出对于方形节点就是取 子节点中 最大的那个,而对于三角形节点就是取子节点中最小的那个,这些值其实就是对应着当前节点的最优下法对应的终局得分;
至此min-max就讲完了,min-max的算法实现也差不多,自底向上遍历整棵树,但是这个算法实现上有一些问题;
首先真实对弈环境这个博弈树是巨大的,如果所有节点都遍历,计算量吃不消,因此需要算法能够减少遍历节点的数量,
剪枝就是在这个背景下提出的,下面直入主题:
先说下算法实现,首先给根节点一个值和值,
之后通过类似深度优先遍历的方式遍历整个树,不过在下降的过程中经历的节点也算遍历一次,举例来说遍历逻辑如下:
1
2 3
4 5 6 7
遍历顺序为: 1->2->4-2->5->2->1->3->6->3->7->3->1
也就是除了叶子节点每个节点都要从子节点返回来一次共访问2次;
然后遍历的时候不断更新每个节点的alpha-beta值;
当满足条件 alpha>=beta的时候,该节点还没有遍历的右边的子节点就不用遍历了;这就是alpha-beta剪枝的含义(当然遍历过程中还要向min-max一样保留最优解的值);
关键是如何更新以及如何剪枝;
原则如下:
1,对于方形节点来说,对应名字叫max节点
对于三角形来说,对应名字叫叫min节点,按照上面的顺序遍历节点,每次遍历到节点就更新其对应的值
2,从子节点回溯过来的case下:
2-1 :max节点,如果其子节点是叶子节点,则更新对应的为子节点中较大的那个;
如果不是,则 这个child表示刚刚从该child回溯过来的那个child;
2-2:,min节点,如果其子节点是叶子节点,令为其中较小者;
否则,令
3,从父节点下降过来的case下:
不管min,max节点,
好了,现在问题来了,为什么这样整就可以剪枝了,有些节点就不用遍历了?
下面来分析一下的含义以及算法原理
这里是全文最核心的部分,
的含义可以这么理解:
对于max节点来说,表示:遍历到该节点为止,该节点在双方最优走法下所能取到的最大值,(这里遍历到该节点为止的意思是只考虑遍历到该节点之前走过的那些路径,其余的都不考虑)
对于max节点来说,其含义仅仅是,遍历到该节点为止,该节点的父节点在双方最优走法下所能取到的值的最小值;(该节点的父节点是一个 min节点)
对于min节点来说,表示:遍历到该节点为止,该节点在双方最优下法下所能取到的最小值;
对于min节点来说,表示遍历到该节点为止,该节点的父节点在双方最优走法下所能取到的最大值;
根据定义,我们看为何就能剪枝了,
首先,我们看一max节点回溯公式:
在该迭代之前,我们归纳假设已经符合定义,此时从该分支回溯回来之后,child子树已经全部遍历完了,此时按归纳表示 该节点在双方最优下法下所能取到的最小值,而child显然是个min节点,它显然就会取这个最小值;那么,如果这个值比现在的值还大,那么max节点按照定义就应该更新为这个值;
对于的分析省略了,对称的;
再看下下降公式:
下降过程中,如果是下降到max节点,
由于此时该节点的值还不知道应该取什么,并且其子节点都未遍历,按定义就应该不变;
而根据定义继承自父节点;
$\beta\ 也可以类似 分析;
最后看剪枝公式 这个公式对于
max节点来说其含义是:
其父节点的值比 当前的 不大
这就意味着,父节点按最优解,不会选择这条路径了,它已经通过别的路径可以选择到 值,父节点是min节点,它只会考虑子节点的值的值,而该max节点是它的一个子节点,并且其取值已经是\alpha,虽然该节点含有一些路径没遍历完,但是即使遍历完,由于该节点是max节点,它也不会选择那些的值,所以,最终该max节点取值一定,所以父节点最优选择并不包括该路径,则该节点的剩下还没有遍历的子路径就不用再遍历了;
对于min节点来说,也可以类似方式理解;
至此,最核心的部分就讲解完了,这篇文章不够精细严谨,只是作为一个导引性质让读者最快速的了解算法精髓。