博弈树的搜索

博弈树的搜索双人完备信息两位选手对垒，轮流走步。这时每一方不仅知道对方过去已经走过的棋步，而且还能估计出对方未来可能的走步。对弈的结果是一方赢（另一方则输），或者双方和局。博弈问题可以用产生式系统的形式来描述。产生式系统构造知识型系统和建立认知模型时常用的知识表示的形式系统。一个产生式系统由下列3部分组成：一个总数据库(globaldatabase)，它含有与具体任务有关的信息。一套规则，它对数据库进行操作运算。每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。应用规则来改变数据库。一个控制策略，它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。例如中国象棋，综合数据库可规定为棋盘上棋子各种位置布局的一种描述，产生式规则是各类棋子合法走步的描述，目标则可规定为将（帅）被吃掉，规则作用于数据库的结果便生成出博弈图或博弈树。Grundy博弈问题：有一堆数目为N的钱币，由两位选手轮流进行分堆，要求每个选手每次只把其中某一堆分成数目不等的两小堆。例如选手甲把N分成两堆后，轮到选手乙就可以挑其中一堆来分，如此进行下去直到有一位选手先无法把钱币再分成不相等的两堆时就得认输。当初始钱币数为7时的状态空间图，如下：MIN代表对方走，MAX代表我方走。对于简单问题可以这样找到取胜策略，但对于复杂问题就不可能了。下面讨论：如何根据有限的状态，得到较好走步的搜索方法。极小极大搜索方法极小极大搜索方法是博弈树搜索的基本方法。首先假定，有一个评价函数可以对所有的棋局进行评估。当评价函数值大于0时，表示棋局对我方有利，对对方不利。当评价函数小于0时，表示棋局对我方不利，对对方有利。方法：当轮到我方走棋时，首先按照一定的搜索深度生成出给定深度d以内的所有状态，计算所有叶节点的评价函数值。然后从d-1层节点开始逆向计算：对于我方要走的节点（用MAX标记，称为极大节点）取其子节点中的最大值为该节点的值（因为我方总是选择对我方有利的棋）。对于对方要走的节点（用MIN标记，称为极小节点）取其子节点中的最小值为该节点的值（对方总是选择对我方不利的棋）。一直到计算出根节点的值为止。获得根节点取值的那一分枝，即为所选择的最佳走步。因此，极小极大过程是一种假定对手每次回应都正确的情况下，如何从中找出对我方最有利的走步的搜索方法。值得注意的是，不管设定的搜索深度是多少层，经过一次搜索以后，只决定了我方一步棋的走法。等到对方回应一步棋之后，需要在新的棋局下重新进行搜索，来决定下一步棋如何走。静态估计函数f(x)一般规定有利于MAX的势态，f(p)取正值，有利于MIN的势态，f(p)取负值，势均力敌的势态，f(p)取0值。若f(p)＝＋∞，则表示MAX赢，若f(p)＝－∞，则表示MIN赢。下面的讨论规定：顶节点深度d＝0，MAX代表程序方，MIN代表对手方，MAX先走。当用端节点的静态估计函数f（p）求倒推值时，两位选手应采取不同的策略，从下往上逐层交替使用极小和极大的选值方法，故称极小极大过程。3×3棋盘的一字棋为例问题：在九宫格棋盘上，两位选手轮流在棋盘上摆各自的棋子（每次一枚），谁先取得三子一线的结果就取胜。设程序方MAX的棋子用（×）表示，对手MIN的棋子用（○）表示，MAX先走。静态估计函数f（p）规定如下：若p对任何一方来说都不是获胜的格局，则f(p)＝（所有空格都放上MAX的棋子之后，MAX的三子成线（行、列、对角）的总数）－（所有空格都放上MIN的棋子之后，MIN的三子成线（行、列、对角）的总数）若p是MAX获胜的格局，则f(p)＝∞；若p是MIN获胜的格局，则f(p)＝－∞。一字棋第一阶段搜索树一字棋第二阶段搜索树一字棋第三阶段搜索树α-β搜索过程能否在搜索深度不变的情况下，利用已有的搜索信息减少生成的节点数呢？MIN-MAX过程是把搜索树的生成和格局估值这两个过程分开来进行，即先生成全部搜索树，然后再进行端节点静态估值和倒推值计算，这显然会导致低效率。实际上把生成和倒推估值结合起来进行，再根据一定的条件判定，有可能尽早修剪掉一些无用的分枝，同样可获得类似的效果，这就是α-β过程的基本思想。用一字棋的例子来说明α-β剪枝方法为了使生成和估值过程紧密结合，采用有界深度优先策略进行搜索，这样当生成达到规定深度的节点时，就立即计算其静态估值函数，而一旦某个非端节点有条件确定其倒推值时就立即计算赋值。一字棋第一阶段α-β剪枝方法（1）α剪枝：若任一极小值层节点的β值小于或等于它任一先辈极大值居节点的α值，即α（先辈层）≥β（后继层），则可中止该极小值层中这个MIN节点以下的搜索过程。这个MIN节点最终的倒推值就确定为这个β值（2）β剪枝：若任一极大值层节点的α值大于或等于它任一先辈极小值层节点的β值，即α（后继层）≥β（先辈层），则可以中止该极大值层中这个MAX节点以下的搜索过程。这个MAX节点的最终倒推值就确定为这个α值。通过对下图的搜索，来说明α-β剪枝搜索过程根据这些剪枝规则，很容易给出α-β算法描述，显然剪枝后选得的最好优先走步，其结果与不剪枝的MINIMAX方法所得完全相同，因而α-β过程具有较高的效率。在一般条件下使用α-β搜索技术，在同样的资源限制下，可以向前考虑更多的走步数，这样选取当前的最好优先走步，将带来更大的取胜优势。其他改进方法（1）不严格限制搜索的深度，当到达深度限制时，如出现博弈格局有可能发生较大变化时（如出现兑子格局），则应多搜索几层，使格局进入较稳定状态后再中止，这样可使倒推值计算的结果比较合理，避免考虑不充分产生的影响，这是等候状态平稳后中止搜索的方法。（2）当算法给出所选的走步后，不马上停止搜索，而是在原先估计可能的路径上再往前搜索几步，再次检验会不会出现意外，这是一种增添辅助搜索的方法。（3）对某些博弈的开局阶段和残局阶段，往往总结有一些固定的对弈模式，因此可以利用这些知识编好走步表，以便在开局和结局时使用查表法。只是在进入中盘阶段后，再调用其他有效的搜索算法，来选择最优的走步。需要作进一步的研究和探讨的问题（1）在一个短时期内短兵相接，进攻和防御的战术变化剧烈，这些情况如何在搜索策略中加以考虑。（2）基于极小极大过程的一些方法都设想对手总是走的最优走步，即我方总应考虑最坏的情况，实际上再好的选手也会有失误，如何利用失误加强攻势，也值得考虑。（3）选手的棋风问题。