搜索(博弈树的启发式搜索)

博弈树的启发式搜索1博弈问题如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。博弈有很多种，我们讨论最简单的“二人零和、全信息、非偶然”博弈，其特征如下：双人对弈，对垒的双方轮流走步。零和。即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利、或均无利的棋。对弈的结果是一方赢，而另一方输，或者双方和棋。信息完备，对垒双方所得到的信息是一样的，不存在一方能看到，而另一方看不到的情况。任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选取对自已为最有利而对对方最为不利的对策，不存在掷骰子之类的碰运气因素。即双方都是很理智地决定自己的行动。博弈是一类富有智能行为的竞争活动，如下棋、打牌、战争等。博弈可分为双人完备信息博弈和机遇性博弈。所谓双人完备信息博弈，就是两位选手对垒，轮流走步，每一方不仅知道对方已经走过的棋步，而且还能估计出对方未来的走步。对弈的结果是一方赢，另一方输；或者双方和局。这类博弈的实例有象棋、围棋等。所谓机遇性博弈，是指存在不可预测性的博弈，例如掷币等。对机遇性博弈，由于不具备完备信息，因此我们不作讨论。34这里我们主要讨论双人完备信息博弈问题。在双人完备信息博弈过程中，双方都希望自己能够获胜。因此，当任何一方走步时，都是选择对自己最为有利，而对另一方最为不利的行动方案。假设博弈的一方为MAX，另一方为MIN。在博弈过程的每一步，可供MAX和MIN选择的行动方案都可能有多种。从MAX方的观点看，可供自己选择的那些行动方案之间是“或”的关系，原因是主动权掌握在MAX手里，选择哪个方案完全是由自己决定的；而对那些可供MIN选择的行动方案之间则是“与”的关系，原因是主动权掌握在MIN的手里，任何一个方案都有可能被MIN选中，MAX必须防止那种对自己最为不利的情况的发生。5若把双人完备信息博弈过程用图表示出来，就可得到一棵与/或树，这种与/或树被称为博弈树。在博弈树中，那些下一步该MAX走步的节点称为MAX节点，而下一步该MIN走步的节点称为MIN节点。博弈树具有如下特点：（l）博弈的初始状态是初始节点；（2）博弈树中的“或”节点和“与”节点是逐层交替出现的；（3）整个博弈过程始终站在某一方的立场上，所有能使自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都是不可解节点。例如，站在MAX方，所有能使MAX方获胜的节点都是可解节点，所有能使MIN方获胜的节点都是不可解节点。一.博弈树概述博弈问题空间模型化只考虑两个游戏者:MAX和MIN,两个人轮流出招,直到游戏结束.四元组：（初始状态，操作集合，终止测试（非目标测试），判定函数）初始状态：包括棋局的局面和确定该哪个游戏者出招后继函数：返回(move,state)对的一个列表,其中每一对表示一个合法的着数和其结果状态终止测试：判断游戏是否结束,游戏结束的状态称为终止状态判定函数：又称为目标函数或者收益函数,对终止状态给出一个数值.（比如：可以-1表示输，0表示和局，1表示赢）博弈的初始格局是初始节点在博弈树中，或节点和与节点是逐层交替出现的。如果我们站在MAX方的立场上，则可供MAX方选择的若干行动方案之间是“或”关系，因为主动权操在MAX方手里，他或者选择这个行动方案，或者选择另一个行动方案，完全由MAX方自已决定。当MAX方选取任一方案走了一步后，MIN方也有若干个可供选择的行动方案，此时这些行动方案对MAX方来说它们之间则是与关系，因为这时主动权操在MIN方手里，这些可供选择的行动方案中的任何一个都可能被MIN方选中，MAX方必须应付每一种情况的发生。8对简单的博弈问题，可以生成整个博弈树，找到必胜的策略。但对于复杂的博弈，如国际象棋，大约有10120个节点，可见要生成整个搜索树是不可能的。一种可行的方法是用当前正在考察的节点生成一棵部分博弈树，由于该博弈树的叶节点一般不是哪一方的获胜节点，因此，需利用估价函数f(n)对叶节点进行静态评估，对MAX有利的节点其估价函数取正值；那些对MIN有利的节点，其估价函数取负值；那些使双方均等的节点，其估价函数取接近于0的值。二.极大极小过程为了计算非叶节点的值，必须从叶节点向上倒推。对于MAX节点，由于MAX方总是选择估值最大的走步，因此，MAX节点的倒推值应该取其后继节点估值的最大值。对于MIN节点，由于MIN方总是选择使估值最小的走步，因此MIN节点的倒推值应取其后继节点估值的最小值。这样一步一步的计算倒推值，直至求出初始节点的倒推值为止。由于我们是站在MAX的立场上，因此应选择具有最大倒推值的走步。这一过程称为极大极小过程。下面给出一个极大极小过程的例子。极小极大法基本思想:首先假定，有一个评价函数可以对所有的棋局进行评估。当评价函数值大于0时，表示棋局对我方有利，对对方不利;当评价函数小于0时，表示棋局对我方不利，对对方有利;而评价函数值越大，表示对我方越有利。当评价函数值等于正无穷大时，表示我方必胜。评价函数值越小，表示对我方越不利。当评价函数值等于负无穷大时，表示对方必胜;假设双方都是对弈高手，在只看一步棋的情况下，我方一定走评价函数值最大的一步棋，而对方一定走评价函数值最小的一步棋。人下棋的思考方式人下棋实际上采用一种试探性的方法:假定走了一步棋,看对方会有哪些应法;再根据对方的每一种应法,看我方是否有好的回应;这一过程一直进行下去,直到若干步后,找到一个满意的走法为止.极大极小搜索方法模拟的就是人的这样一种思维过程.极大极小搜索方法是一种在有限搜索深度范围进行求解的方法.ABCD31282145246b1b2b33c1c2c32d1d2d32a1a2a3MAXMIN3定义一个静态估计函数f,以便对棋局的叶子节点作出优劣估值2.非叶子节点的估值由倒推取值的方法取得a.MAX走步必然选择对自己最有利的一步,如A节点的估计值是3b.MIN走步必然选择对自己最有利的一步,如D节点的估计值是21.首先按照一定的搜索深度生成出给定深度d以内的所有状态，计算所有叶节点的评价函数值。获得根节点取值的那一分枝，即为所选择的最佳走步节点A,轮到MAX下棋….算法框架整个算法分为四个步骤：1、以当前状态为根结点产生一个博弈树。2、对博弈树的每一个叶结点，利用判定函数给出它的判定值。3、从叶结点开始，一层一层地回溯。在回溯过程中，利用最大/最小判定为每一个结点给出其判定值。4、MAX方选择下一层中判定值最大的结点，作为它的下一状态。FunctionMinimax-Decision(state)returnanactionv←Max-Value(state)returnactioninsuccessors(state)withvaluevFunctionMax-Value(state)returnautilityvalueifTerminal-Test(state)thenreturnUtility(state)v←-∞forsinsuccessors(state)dov←Max(v,Min_Value(s))ReturnvFunctionMin-Value(state)returnanutilityvalueifTerminal-Test(state)thenreturnUtility(state)v←+∞forsinsuccessors(state)dov←Min(v,Max_Value(s))Returnv13例：一字棋游戏。设有一个三行三列的棋盘，如下图所示，两个棋手轮流走步，每个棋手走步时往空格上摆一个自己的棋子，谁先使自己的棋子成三子一线为赢。设MAX方的棋子用×标记，MIN方的棋子用○标记，并规定MAX方先走步。解：为了对叶节点进行静态估值，规定估价函数e（P）如下：若P是MAX的必胜局，则e（P）=+∞；若P是MIN的必胜局，则e（P）=-∞；若P对MAX、MIN都是胜负未定局，则e（P）=e（+P）－e（-P）其中，e（+P）表示棋局P上有可能使×成三子一线的数目；e（-P）表示棋局P上有可能使○成三子一线的数目。二.极大极小过程14例如，对图1所示的棋局有估价函数值e（P）＝6-4＝2图1棋局1在搜索过程中，具有对称性的棋局认为是同一棋局。例如，图2所示的棋局可以认为是同一个棋局，这样可以大大减少搜索空间。图3给出了第一着走棋以后生成的博弈树。图中叶节点下面的数字是该节点的静态估值，非叶节点旁边的数字是计算出的倒推值。从图中可以看出，对MAX来说S2是一着最好的走棋，它具有较大的倒推值。图2对称棋局的例子15图3一子棋的极大极小搜索S0S1S2S3S4S5-11-26-5=15-5=06-5=15-5=04-5=-15-6=-15-5=06-6=05-6=-14-6=-25-4=16-4=2一字棋游戏极小极大树定义一个静态估计函数f,以便对棋局的叶子节点作出优劣估值2.非叶子节点的估值由倒推取值的方法取得a.MAX走步必然选择对自己最有利的一步,如节点的估计值是1b.MIN走步必然选择对自己最有利的一步,如节点的估计值是-21.首先按照一定的搜索深度生成出给定深度d以内的所有状态，计算所有叶节点的评价函数值。获得根节点取值的那一分枝，即为所选择的最佳走步MAX在初始节点时应该怎么走…一字棋游戏极小极大树MAX在第二步应该怎么走…α-β剪枝在极小极大搜索方法中，由于要先生成指定深度以内的所有节点，其节点数将随着搜索深度的增加呈指数增长。这极大地限制了极小极大搜索方法的使用。α-β剪枝的基本思想:边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。ABCD[-∞,+∞][-∞,3]3128[3,+∞][-∞,+2]2[3,3][-∞14]14[3,14]52[2,2][3,3]α-β剪枝α=到目前为止我们在路径上的任意选择点发现MAX的最佳(即极大值)选择β=到目前为止我们在路径上的任意选择点发现MIN的最佳(即极小值)选择算法框架(1)对于一个与节点MIN，若能估计出其倒推值的上确界β，并且这个β值不大于MIN的父节点(一定是或节点)的估计倒推值的下确界α，即α≥β，则就不必再扩展该MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响)。这一过程称为α剪枝。(2)对于一个或节点MAX，若能估计出其倒推值的下确界α，并且这个α值不小于MAX的父节点(一定是与节点)的估计倒推值的上确界β，即α≥β，则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响)。这一过程称为β剪枝。算法特点：(1)MAX节点(包括起始节点)的α值永不减少；(2)MIN节点(包括起始节点)的β值永不增加。α和β值的计算方法：(1)一个MAX节点的α值等于其后继节点当前最大的最终倒推值。(2)一个MIN节点的β值等于其后继节点当前最小的最终倒推值。一字棋第一阶段α-β剪枝方法第一个被访问的叶子节点访问完节点1,初始节点s的取值范围是[-1,+∞]开始访问完节点7,访问完节点8,节点7的取值范围是[-∞,-1]节点7的父节点是s此时,α≥β,节点7不必在分裂下去了,即剪掉该枝深度搜索…例若以最理想的情况进行搜索，即对MIN节点先扩展最低估值的节点（若从左向右顺序进行，则设节点估计值从左向右递增排序），MAX先扩展最高估值的节点（设估计值从左向右递减排序）。则当搜索树深度为D，分枝因子为B时，若不使用α-β剪枝技术，搜索树的端节点数ND=BD；若使用α-β剪枝技术．可以证明理想条件下生成的端节点数最少，有ND＝2BD/2-1（D为偶数）ND＝B(D+1)/2+B(D-1)/2-1（D为奇数）比较后得出最佳α-β搜索技术所生成深度为D处的端节点数约等于不用α-β搜索技术所生成深度为D／2处的端节点数。这就是说，在一般条件下使用α-β搜索技术，在同样的资源限制下，可以向前考虑更多的走步数，这样选取当前的