《极小极大搜索过程》由会员分享，可在线阅读，更多相关《极小极大搜索过程（17页珍藏版）》请在金锄头文库上搜索。
1、极小极大搜索过程 2011-03-30 09:59转载自 shengtingjiaju最终编辑 shengtingjiaju极小极大搜索方法是博弈树搜索的基本方法，现在博弈树搜索中最常用的 - 剪枝搜索方法，就是从这一方法发展而来的。首先假定，有一个评价函数可以对所有的棋局进行评估。当评价函数值大于 0 时，表示棋局对我方有利，对对方不利。当评价函数小于 0 时，表示棋局对我方不利，对对方有利。而评价函数值越大，表示对我方越有利。当评价函数值等于正无穷大时，表示我方必胜。评价函数值越小，表示对我方越不利。当评价函数值等于负无穷大时，表示对方必胜。假设双方都是对弈高手，在只看一步棋的情况下，我方
2、一定走评价函数值最大的一步棋，而对方一定走评价函数值最小的一步棋。会下棋的读者都知道，在只看一步的情况下最好的棋，从全局来说不一定就好，还可能很不好。因此为了走出好棋，必须多看几步，从多种可能状态中选择一步好棋。 想一想人是如何下棋的呢？人实际上采用的是一种试探性的方法。首先假定走了一步棋，看对方会有那些应法，然后再根据对方的每一种应法，看我方是否有好的回应.这一过程一直进行下去，直到若干步以后，找到了一个满意的走法为止。初学者可能只能看一、两个轮次，而高手则可以看几个，甚至十几个轮次。极小极大搜索方法，模拟的就是人的这样一种思维过程。当轮到我方走棋时，首先按照一定的搜索深度生成出给定深度 d
3、 以内的所有状态，计算所有叶节点的评价函数值。然后从 d-1 层节点开始逆向计算：对于我方要走的节点（用 MAX 标记，称为极大节点）取其子节点中的最大值为该节点的值（因为我方总是选择对我方有利的棋）；对于对方要走的节点（用 MIN 标记，称为极小节点）取其子节点中的最小值为该节点的值（对方总是选择对我方不利的棋）。一直到计算出根节点的值为止。获得根节点取值的那一分枝，即为所选择的最佳走步。在图 3.5 所示的例子中，假定搜索深度为 2，DJ 是 7 个叶节点，在它们下边括号中的数字是这些节点的评价函数值（假定可以计算得到）。A、B、C 是三个极小节点，它们分别取各自子节点最小值为自己的值，得
4、到三个节点的值分别为-6、-2 和-4。s 是极大节点，从 A、B、C 三个节点的值中取最大值，得到-2。由于-2 来自于节点 B，所以搜索的结果是应选择 B 作为我方的走步。对于我方来说，-2 并不是一个好的结果，但却是在对方不犯错误的情况下，对我方最有利的结果。因为从图中可以看出，如果选择 A 为我方的走步，如果对方回应 D 的话，我方可以得到评价值 9，固然对我方有利。但是如果对方是一个高手的话，他一定回选择 E，而不是 D。在这种情况下，我方只能得到-6，结果岂不是更差。因此，极小极大过程是一种假定对手每次回应都正确的情况下，如何从中找出对我方最有利的走步的搜索方法。值得注意的是，不管
5、设定的搜索深度是多少层，经过一次搜索以后，只决定了我方一步棋的走法。等到对方回应一步棋之后，需要在新的棋局下重新进行搜索，来决定下一步棋如何走。 极小极大搜索策略是考虑双方对弈若干步之后，从可能的走步中选一步相对好棋的着法来走，即在有限的搜索深度范围内进行求解。为此要定义一个静态估计函数 f，以便对棋局的势态（节点）作出优劣估值，这个函数可根据势态优劣特征来定义（主要用于对端节点的价值进行度量）。一般规定有利于 MAX 的势态，f（p）取正值，有利于 MIN 的势态，f（p）取负值，势均力敌的势态，f（p）取 0 值。若 f（p），则表示 MAX 赢，若 f（p），则表示 MIN 赢。下面的讨
6、论规定：顶节点深度 d0，MAX 代表程序方，MIN 代表对手方，MAX 先走。图 3.5 是一个表示考虑两步棋的例子，图中端节点给出的数字是用静态函数 f（p）计算得到，其他节点不用 f（p）估计，因为不够精确，而应用倒推的办法取值。例如A、B、C 是 MIN 走步的节点，MAX 应考虑最坏的情况，故其估值应分别取其子节点 f（p）估值中最小者，而 s 是 MAX 走步的节点，可考虑最好的情况，故估值应取 A、B、C 值中的最大者。这样求得 f（s）2，依此确定了相对较优的走步应是走向 B，因为从 B 出发，对手不可能产生比 f（s）2 更差的效果。实际上可根据资源条件，考虑更多层次的搜索过
7、程，从而可得到更准确的倒推值，供 MAX 选取更正确的走步。当用端节点的静态估计函数 f（p）求倒推值时，两位选手应采取不同的策略，从下往上逐层交替使用极小和极大的选值方法，故称极小极大过程。图 3.5 f(p)求值过程过程 MINIMAX：T:（s，MAX），OPEN:（s），CLOSED:（ ）；开始时树由初始节点构成，OPEN 表只含有 s。LOOP1:IF OPEN（ ）THEN GO LOOP2；n:FIRST（OPEN），REMOVE（n，OPEN），ADD（n，CLOSED）；IF n 可直接判定为赢、输或平局THEN f（n）:0，GO LOOP1ELSE EXPAND（n）n
8、i，ADD（ ，T）IF d（ni）k THEN ADD（ ，OPEN），GO LOOP1ELSE 计算 f（ ），GO LOOP1；nI 达到深度 k，计算各端节点 f 值。LOOP2：IF CLOSEDNIL THEN GO LOOP3ELSE :FIRST（CLOSED）；IF（ MAX）（f（ MIN）有值）THEN f（ ）:maxf（ ），REMOVE（ ，CLOSED）；若 MAX 所有子节点均有值，则该 MAX 取其极大值。IF （ MIN）（f（ MAX）有值）THEN f（ ）:minf（ ），REMOVE（ ，CLOSED）；若 MIN 所有子节点均有值，则该 MIN 取
9、其极小值。GO LOOP2；LOOP3：IF f（s）NIL THEN EXIT（ENDM（Move，T）；s 有值，则结束或标记走步。该算法分两个阶段进行，第一阶段-是用宽度优先法生成规定深度的全部博弈树，然后对其所有端节点计算其静态估计函数值。第二阶段-是从底向上逐级求非端节点的倒推估计值，直到求出初始节点的倒推值 f（s）为止，此时其中 表示深度为 k 的端节点。再由 f（s）即可选得相对较好的走步来，过程遂造结束。等对手响应走步后，再以当前的状态作为起始状态 s，重复调用该过程。下面通过最简单的 33 棋盘的一字棋为例来说明算法的应用过程。在九宫格棋盘上，两位选手轮流在棋盘上摆各自的棋
10、子（每次一枚），谁先取得三子一线的结果就取胜。设程序方 MAX 的棋子用（）表示，对手 MIN 的棋子用（）表示，MAX 先走。静态估计函数 f（p）规定如下：若 p 对任何一方来说都不是获胜的格局，则f（p）（所有空格都放上 MAX 的棋子之后，MAX 的三子成线（行、列、对角）的总（所有空格都放上 MIN 的棋子之后，MIN 的三子成线（行、列、对角）的总数）若 p 是 MAX 获胜的格局，则 f（p）；若 p 是 MIN 获胜的格局，则 f（p）。例如，当 p 的格局如下时，则可得 f（p）642；设考虑走两步的搜索过程，利用棋盘对称性的条件，则第一次调用算法产生的搜索树如图 3.6 所
11、示，图中端节点下面是计算的 f（p）值，非端节点的倒推值标记在圆圈内。为了使初始节点具有最大的倒推值，可以看出第一步的最好着法是把棋子下在中央位置。图 3.6 一字棋第一阶段搜索树设 MAX 走完第一步后，MAX 的对手是在之上的格子下子，这时 MAX 就要在新格局下调用算法，第二次产生的搜索树如图 3.7 所示。类似的第三次的搜索树如图 3.8 所示。至此MAX 走完最好的走步后，不论 MIN 怎么走，都无法挽回败局，因此只好认输了，否则还要进行第四轮回的搜索。图 3.7 一字棋第二阶段搜索树图 3.8 一字棋第三阶段搜索树有一种很有意思的游戏，就是有物体若干堆，可以是火柴棍或是围棋子等等均
12、可。两个人轮流从堆中取物体若干，规定最后取光物体者取胜。这是我国民间很古老的一个游戏，别看这游戏极其简单，却蕴含着深刻的数学原理。下面我们来分析一下要如何才能够取胜。（一）巴什博奕（Bash Game）：只有一堆 n 个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取 m 个。最后取光者得胜。显然，如果 n=m+1，那么由于一次最多只能取 m 个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果n=（m+1）r+s，（r 为任意自然数，sm),那么先取者要拿走 s 个物品，如果后取者拿走k（m)个，那么先取者再拿走 m+1-k
13、 个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十个，谁能报到 100 者胜。（二）威佐夫博奕（Wythoff Game）：有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。 这种情况下是颇为复杂的。我们用（ak，bk）（ak bk ,k=0，1，2，,n)表示两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是：（0，0）
14、、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）。可以看出,a0=b0=0,ak 是未在前面出现过的最小自然数,而 bk= ak + k，奇异局势有如下三条性质：1。任何自然数都包含在一个且仅有一个奇异局势中。由于 ak 是未在前面出现过的最小自然数，所以有 ak ak-1 ，而 bk= ak + k ak-1 + k-1 = bk-1 ak-1 。所以性质 1。成立。2。任意操作都可将奇异局势变为非奇异局势。事实上，若只改变奇异局势（ak，bk）的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。如果使（ak
15、，bk）的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。3。采用适当的方法，可以将非奇异局势变为奇异局势。假设面对的局势是（a,b），若 b = a，则同时从两堆中取走 a 个物体，就变为了奇异局势（0，0）；如果 a = ak ，b bk，那么，取走 b bk 个物体，即变为奇异局势；如果 a = ak ， b ak ，b= ak + k,则从第一堆中拿走多余的数量 a ak 即可；如果 a (1,8,9)奇异局势乙:(1,8,9)-(1,8,4)甲:(1,8,4)-(1,5,4)奇异局势乙:(1,5,4)-(1,4,4)甲:(1,4,4)-(0,4,4)
16、奇异局势乙:(0,4,4)-(0,4,2)甲:(0.4,2)-(0,2,2)奇异局势乙:(0,2,2)-(0,2,1)甲:(0,2,1)-(0,1,1)奇异局势乙:(0,1,1)-(0,1,0)甲:(0,1,0)-(0,0,0)奇异局势甲胜。取火柴的游戏题目 1：今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根， 可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。 题目 2：今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根， 可将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。嘿嘿，这个游戏我早就见识过了。小时候用珠算玩这个游戏：第一档拨一个，第二档拨两个，依次直到第五档拨五个。然后两个人就轮流再把棋子拨下来，谁要是最后一个拨谁就赢。有一次暑假看见两个小孩子在玩这个游戏，我就在
