搜索策略培训教材.ppt

* * 极大极小过程 极大极小过程是考虑双方对弈若干步之后，从可能的走法中选一步相对好的走法来走，即在有限的搜索深度范围内进行求解。 需要定义一个静态估价函数f,以便对棋局的态势做出评估。 第二百二十三页，共二百四十二页。 * * 这个函数可以根据棋局的态势特征进行定义。假定对弈双方分别为MAX和MIN，规定： 有利于MAX方的态势：f(p)取正值 有利于MIN方的态势：f(p)取负值 态势均衡的时候：f(p)取零 其中p代表棋局。 第二百二十四页，共二百四十二页。 * * MINMAX基本思想： (1)当轮到MIN走步的节点时（取与时），MAX应考虑最坏的情况（即f(p)取极小值）。 (2)当轮到MAX走步的节点时（取或时），MAX应考虑最好的情况（即f(p)取极大值）。 (3)评价往回倒推时，相应于两位棋手的对抗策略，交替使用（1）和（2）两种方法传递倒推值。 所以这种方法称为极大极小过程。 第二百二十五页，共二百四十二页。 * * 用一字棋说明极大极小过程，设只进行两层，即每方只走一步。 一字棋游戏规则如下：设有一个三行三列的棋盘，如图所示，两个棋手轮流走步，每个棋手走步时往空格上摆一个自己的棋子，谁先使自己的棋子成三子一线为赢。设MAX方的棋子用×标记，MIN方的棋子用○标记，并规定MAX方先走步。 第二百二十六页，共二百四十二页。 * * 为了不致于生成太大的博弈树，假设每次仅扩展两层。估价函数定义如下： 设棋局为P，估价函数为e(P)。 (1)若格局p对任何一方都不是获胜的，则 e(p) = (棋局P上有可能使MAX成为三子成一线的状态的数目) –（棋局P上有可能使MIN成为三子成一线的状态的数目）= e(+p)-e(-p) (2)若p是MAX获胜，则 e(p) = +∞ （3） 若p是MIN获胜，则 e(p) = -∞ 第二百二十七页，共二百四十二页。 * * 若p为下图所示，且 e(P)=e(+P)-e(-P)=5-4=1 第二百二十八页，共二百四十二页。 * * 假设由MAX先走棋，且我们站在MAX立场上。下图给出了MAX的第一着走棋生成的博弈树。图中节点旁的数字分别表示相应节点的静态估值或倒推值。由图可以看出，对于MAX来说最好的一着棋是S3，因为S3比S1和S2有较大的估值。 第二百二十九页，共二百四十二页。 * * α-β过程 上面讨论的极大极小过程先生成一棵博弈搜索树，而且会生成规定深度内的所有节点，然后再进行估值的倒推计算，这样使得生成博弈树和估计值的倒推计算两个过程完全分离，因此搜索效率较低。 如果能边生成博弈树，边进行估值的计算，则可能不必生成规定深度内的所有节点，以减少搜索的次数，这就是下面要讨论的α-β过程。 第二百三十页，共二百四十二页。 * * α-β过程就是把生成后继和倒推值估计结合起来，及时剪掉一些无用分支，以此来提高算法的效率。 下面仍然用一字棋进行说明。现将原图左边所示的一部分重画在图中。 第二百三十一页，共二百四十二页。 * * 与或图的启发式搜索 2) AO*算法 AO*算法应用例 启发式函数h(ni)的估算如下： h(n0)=3 h(n1)=2 h(n2)=1 h(n3)=1 h(n4)=4 h(n5)=2 h(n6)=2 h(n7)=1 h(n8)=1 h(n13)=3 0 1 2 3 5 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 第一百九十一页，共二百四十二页。 * * 初始化 候选的待扩展局部解图集LGS: 0 3 0 第一百九十二页，共二百四十二页。 * * 0 1 2 3 5 4 循环1 候选的待扩展局部解图集LGS: 3 2 1 1 4 2 0 第一百九十三页，共二百四十二页。 * * 0 1 2 3 5 4 循环1 候选的待扩展局部解图集LGS: 3 2 1 1 4 2 0 3 1 2 0 1 2 3 5 4 3 2 1 1 4 2 0 第一百九十四页，共二百四十二页。 * * 0 1 2 3 5 4 循环1 候选的待扩展局部解图集LGS: 10 2 1 1 4 2 0 5 1 2 f(n) = K + h(n1) + h(n2) + … + h(nk) 取代原先的f(n); f1(n0) = 2 + h(n1) + h(n2)=5 f2(n0) = 3 + h(n3) + h(n4)+h(n5) =10 第一百九十五页，共二百四十二页。 * * 0 1 2 3 5 4 循环2 候选的待扩展局部解图集LGS: 10 2 1 1 4 2 0 5 6 7 8 2 1 1 1