机器博弈研究报告

机器博弈及其搜索算法的研究摘要机器博弈是人工智能一种老式的研究领域。本文从机器博弈的基本理论谈起，简介了机器博弈理论和机器博弈系统的一般构成，尤其论述了现今已存在的多种机器博弈搜索算法及其优缺陷。关键词博弈系统博弈搜索算法alpha-beta搜索最佳优先搜索1序言机器博弈的研究广泛而深入。早在上世纪五十年代，就有人设想运用机器智能来实现机器与人的对弈。国内外许多著名学者和著名科研机构都曾经涉足这方面的研究，历经半个多世纪，到目前为止已经获得了许多惊人的成就。1997年IBM的“深蓝”战胜了国际象棋世界冠军卡斯帕罗夫，惊动了世界。除此之外，加拿大阿尔伯塔大学的奥赛罗程序Logistello和西洋跳棋程序Chinook也相继成为确定的、二人、零和、完备信息游戏世界冠军[1]，而西洋双陆棋这样的存在非确定原因的棋类也有了美国卡内基梅隆大学的西洋双陆琪程序BKG这样的世界冠军[1]。对围棋、中国象棋、桥牌、扑克等许多种其他种类游戏博弈的研究也正在进行中。机器博弈的关键技术是博弈搜索算法，这也是机器博弈研究的热点。本文首先简介机器博弈的基本理论和机器博弈系统的一般构成，然后重点讲述现存的多种博弈搜索算法。2机器博弈的基本思想机器博弈的关键思想并不复杂，实际上就是对博弈树节点的估值过程和对博弈树搜索过程的结合。[7]在博弈的任何一种中间阶段，站在博弈双方其中一方的立场上，可以设想一种博弈树。这个博弈树的根节点是目前时刻的棋局，它的儿子节点是假设再行棋一步后来的多种棋局，孙子节点是从儿子节点的棋局再行棋一步的多种棋局，以此类推，构造整棵博弈树，直到可以分出胜败的棋局。整棵的博弈树非常庞大，且不一样的棋类有所不一样，分支因子大的如围棋的博弈树显然要比分支因子小的如国际象棋的博弈树要大得多。博弈程序的任务就是对博弈树进行搜索找出目前最优的一步行棋。对博弈树进行极大极小搜索，可以到达这一目的。极大极小搜索，是由于博弈双方所要到达的目的相反，一方要寻找的利益恰是一方失去的利益，因此博弈的一方总是但愿下一走是儿子节点中取值最大者，而另一方恰恰相反。这便形成了极大极小过程。当然，程序不能也没有必要做到搜索整棵博弈树的所有节点，对于某些已经确定为不佳的走步可以将以它为根节点的子树剪掉。并且，搜索也不必真地进行到分出胜败的棋局，只需要在一定深度范围内对局面进行评价即可。只有搜索空间缩小到一定程度，搜索才可以真正的进行。当搜索进行到一定深度，用局面评价机制来评价棋局，按照极大极小的原则选出最优，向上回溯，给出这一局面的父亲节点的价值评价，然后再继续向上回溯，一直到根节点，最优走步就是这样搜索出来的。在这个过程中，最为重要的是搜索算法，高效的搜索算法可以保证用尽量少的时间和空间损耗来到达寻找高价值的走步。不过真的想要博弈程序棋力提高，还必须有一种好的局面评价机制，即估值算法作后盾。就是说，用这个估值算法评价的局面价值必须是客观的、对的的，可以确凿的评价局面的优劣以及优劣的程度。3机器博弈系统根据机器博弈的基本思想，可以确定一种机器博弈系统的一般构成[6]。首先是知识表达的问题，选用一种合适的措施记录棋局。这时需要考虑在这种知识表达的数据构造之上将要进行的多种操作，知识表达应当使最常常进行的操作花费的时间和空间代价最小。另一方面，根据不一样的棋类的不一样规则集，要有一种对应的走法产生机制。它的作用是用来产生整棵博弈树，即处在博弈树的任何一种节点位置上，应当可以运用该机制产生这个节点的所有儿子节点，也就是接下来的所有合法走步。除了以上两个模块以外，就是博弈关键的搜索技术和与之配合的估值技术了。这四个部分互相配合运转起来，就可以实现机器博弈。4博弈搜索博弈搜索的基本思想已经提出半个多世纪，目前广泛研究的是确定的、二人、零和、完备信息的博弈搜索。也就是说，没有随机原因的博弈在两个人之间进行，在任何一种时刻，一方失去的利益即为另一方得到的利益，不会出现“双赢”的局面，并且在任何时刻，博弈的双方都明确的懂得每一种棋子与否存在和存在于哪里。二人、零和、完备信息的博弈搜索理论已经很系统。极大极小算法是所有搜索算法的基础。在这个基础上，目前在这一领域的算法重要有两类，一类是作为主流的深度优先的alpha-beta搜索及其系列增强算法，另一类是最佳优先的系列算法[2]。4．1基本搜索算法1．极大极小值算法（MinimaxAlgorithm）一直站在博弈一方的立场上给棋局估值，有助于这一方的棋局予以一种较高的价值分数，不利于这一方（有助于另一方）的予以一种较低的价值分数，双方优劣不明显的局面予以一种中间价值分数。在这一方行棋的时候，选择价值极大的儿子节点走步，另一方行棋则选择价值极小的儿子节点走步。这就是一种极大极小过程。2．负极大值搜索（NegamaxAlgorithm）在极大极小过程中，每一次进行极大或者极小的比较之前，都要对究竟是要选择极大还是极小节点进行判断，1975年Knuth和Moore提出的负极大值算法意在消除两方面的差异，使算法简洁优雅。它的关键思想在于：父节点的值是各子节点的负数的极大值。负极大值搜索的原理和极大极小值是搜索同样的，只是体现形式不一样，并且由于它的简洁，目前已经广泛取代了极大极小值算法。4．2深度优先的alpha-beta搜索及其增强算法在极大极小搜索的过程中，存在着一定程度的数据冗余，剔除这些冗余数据，是减小搜索空间的必然做法，所采用的措施就是1975年MonroeNewborn提出的alpha-beta剪枝。把alpha-beta剪枝应用到极大极小搜索或者负极大值搜索中，就形成了alpha-beta搜索。alha-beta剪枝的过程是这样的，如图4-1左半部所示极大极小树的片断，节点B的值为18，节点D的值为16，由此可以判断节点C的值将不不小于等于16（取极小值）；而节点A的值为节点Max（B，C），为18，也就是说不再需要估节点C的其他子节点如E、F的值就可以得出父节点A的值了。这样将节点D的后继兄弟节点减去称为alpha剪枝。图4-1右半部所示极大极小树的片断，节点B的估值为8，节点D的估值为18，由此可以判断节点C的值将不小于等于18（取极大值）；而节点A的值为节点Min（B，C），为8。也就是说不再需规定节点C的其他子节点如E、F的值就可以得出父节点A的值了。这样将节点D的后继兄弟节点减去称为beta剪枝。图4-1alpha-beta搜索由于过程简朴、轻易理解、且占用空间小等优良特点被广泛应用，成为目前主流的搜索算法的基础。不过它也有缺陷，即它对于节点的排列非常敏感。对于同一层上的节点，假如排列合适，剪枝效率就很高，可以使实际搜索的博弈树到达最小树。所谓最小树就是一经向下搜索，第一种节点就是要寻找的走步。可是，假如节点的排列次序不是从最差到最佳，就有也许使剪枝一直无法进行，从而实际上搜索了整棵的博弈树。大多数alpha-beta剪枝算法都采用深度优先的搜索方略，是由于深度优先搜索较之宽度优先搜索节省存储空间，只需保留根节点到目前搜索节点的途径上的节点信息即可。针对alpha-beta搜索的特点，有许多种增强算法被提出，这些算法有些已经被证明为是非常有效的，从而成为该领域的原则搜索算法。下面是alpha-beta的增强算法的简介。渴望搜索（AspirationSearch）在alpha-beta剪枝过程中，初始的的搜索窗口往往是从-∞（即初始的alpha值）到+∞（初始的beta值），在搜索进行中再不停缩小窗口，加大剪枝效果。渴望搜索就是渴望从一开始就使用小的窗口，从而在搜索初起，就可以进行大量的剪枝。这个初始窗口的选定很重要，假如选择精确，即所要寻找的走步就在这个窗口内，搜索便可以继续进行。假如第一步搜索的返回值证明最佳走步不小于beta值，就需要重新确定窗口。以本来的beta值为alpha值，以+∞为新的beta值重新搜索。相反假如第一步的返回值证明最佳走步不不小于alpha值，重新确定的窗口就是以-∞为alpha值，本来的alpha值为beta值了。可见第一次搜索猜测的窗口非常重要，假如猜测精确，搜索时间可以大大缩短，假如不精确，这一优势就不明显了。由于渴望搜索是一种基本的搜索措施，它在和背面论述的遍历深化结合使用的时候，就可以借助前一次深度为depth的搜索的成果来猜测目前深度为depth+1搜索的窗口了。极小窗口搜索（MinimalWindowSearch）极小窗口搜索，也被称为是主变量导向搜索（PrincipalVariationSearch），常常简称为PVS算法或者NegaScout算法。这个算法应用非常广泛。它的出发点是和渴望搜索大体相似的，即用极小的窗口来限制剪枝范围。它的过程是这样的：在根节点处，假定第一种儿子节点为主变量，也就是假定它为最佳走步，对它进行完整窗口(a,b)的搜索并得到一种返回值v，对背面的儿子节点依次用极小窗口（也被称为是零窗口）（v,v+1）来进行搜索，假如搜索返回值不小于零窗口，则证明这一分支亦为主变量，对它进行窗口为（v+1,b）的搜索，可是假如返回值不不小于零窗口，这一分支就可以忽视，由于它的最佳走步还不如已经有的走步。极小窗口搜索采用了极小的窗口，剪枝效率最高，并且只对主变量进行大窗口的搜索，因此大部分搜索动作是有效的，搜索产生的博弈树也很小。置换表（TranspositionTable）在搜索进行中，查询所有的走步，常常会在相似的或者不一样的途径上碰到相似的棋局，这样的子树就没有必要反复搜索，把子树根节点的估值、子树的最佳走步和获得这个值的深度信息保留在一种称为置换表的数据构造中，下次碰届时直接运用即可。不过，对不一样的状况要区别看待。对于固定深度的搜索，假如前一次保留的子树深度不不小于新节点要搜索的深度，还是要进行重新的搜索以保证所获得数据的精确程度。反之，假如置换表中保留的子树信息表明，子树的深度不小于或者等于目前的新节点规定的搜索深度，它的信息就可以直接运用了。置换表增强假如和有效的alpha-beta搜索结合使用，成果就会使实际搜索的博弈树不不小于最小树。博弈树搜索的问题实际上是一种有向图的搜索。那些在置换表中被命中的节点，就是有向图中若干途径的交叉点。只有防止这些交点被反复搜索，搜索过程中生成的搜索树才有也许不不小于最小树。这也是后来证明深度优先的算法并不比最佳优先的算法差的原因之一[3]。这个算法存在的问题是，置换表的构造，必须使对置换表的查找和插入操作不成为整个搜索的承担，才能提高效率。一般使用散列表来实现。遍历深化（IterativeDeepening）遍历深化是因对博弈树进行多次遍历，又不停加深其深度而得名，有人还把它称为蛮力搜索。算法运用了alpha-beta算法对子节点排序敏感的特点。它但愿通过浅层的遍历给出节点的大体排序，把这个排序作为深层遍历的启发式信息。此外，算法用时间控制遍历次数，时间一到，搜索立即停止，这也符合人类棋手的下棋特点。在关键的开局和残局，由于分支较少，也可以进行较深层次的搜索。算法的过程是，对以目前棋局为根节点的博弈树进行深度为二的遍历，得出其儿子节点的优劣排序，接着再从根节点进行深度为三的遍历，这一次优先搜索上次遍历中得出的最优者，从而加大剪枝效果，以此类推，在进行第三次、第四次的遍历，一直到达限定期间为止。由于这个算法的每次遍历都从根节点开始，因此有人称其为蛮力搜索，但实际上由于每次都可以优先搜索相对好的节点，导致剪枝效率增大，其实算法效率是很高的，目前这一算法也得到了广泛的承认。历史启发搜索（HistoryHeuristic）[4]历史启发也是迎合alpha-beta搜索对节点排列次序敏感的特点来提高剪枝效率的，即对节点排序，从而优先搜索好的走法。所谓好的走法即可以引起剪枝的走法或者是其兄弟节点中最佳的走法。一种这样的走法，一经碰到，就给其历史得分一种对应的增量，使其具有更高的优先被搜索的权利。杀手启发搜索(KillerHeuristic)杀手启发实际上是历史启发的特例。它是把同一层中，引起剪枝最多的节点称为杀手，当下次搜索时，搜索到同一层次，假如杀手走步是合法的话，就优先搜索杀手。MTD(f)算法MTD(f)搜索的全称是Memory–enhancedTestDriverwithfandn。它是一种较新的算法，在1995左右年由AskePlaat等人提出。它不是单一的alpha-beta算法的增强，但也是alpha-beta算法的改善。在算法进行中多次调用了零窗口的alpha-beta搜索过程。在算法初起，要给定一种初始值f，一种上界和一种下界。初始值要尽量的靠近最终要找到的最优走步值，上界和下界要保证能把这个最优走步包括在内。算法实际上就是不停的应用零窗口的alpha-beta搜索，缩小上界和下界，并移动初始值使其靠近最优走步。如下使这个算法的伪代码[1]。functionMTD(n)–〉;g:=;+:=+∞;:=－∞;repeatifg=－thenγ:=g+1elseγ:=g;g:=alphabeta(n,γ-1,γ)/*g:=Alpha-Beta(n－1)isequivalent*/ifg<γthen+:=gelse－:=g;until－≥+;returng;图4-2在这个伪代码中，可以看出算法名称中的f为初始值，而n为搜索深度，这里g为最终要找的最佳走步，γ为零窗口的上界。由于算法运用了多次alpha-beta搜索，因此需要配合置换表，这样才能使速度足够的快，从而到达提高效率的目的。MTD(f)算法简朴并且比前述多种算法都高效。有不少实践者的试验证明，在国际象棋、西洋跳棋等博弈程序里，MTD(f)的平均体现要比PVS好，当今最强大的国际象棋程序之一，麻省理工学院的Cilkchess就使用了并行的MTD(f)替代了其初始版本的NegaScout作为搜索算法[8]。4．3最佳优先算法理论上，最佳优先的搜索算法，由于不受节点排序的影响，其搜索空间不不小于深度优先的最小树，应当优于深度优先。因此在二十世纪六七十年代，相继有人提出了最佳优先的系列算法。不过，最佳优先算法可以说一直都待在研究人员的试验室里。真正的博弈程序开发者很少有使用这个算法的。而Alpha-Beta通过一系列增强如置换表、历史启发、零窗探测、遍历深化等手段，其性能已远远高于最初的Alpha-Beta。某些研究人员发既有部分基于AlphaBeta的博弈程序实际生成的搜索树已不不小于最小树[3]。最佳优先算法分为两类[5]，一类是仍然采用极大极小措施取值的SSS*算法和DUAL*算法，另一类是没有采用极大极小措施取值的B*和PB*算法。SSS*和DUAL*算法这两种算法即为状态空间搜索（StateSpaceSearch），由Stockman在1979年提出。它们是把极大极小树的搜索当作是对状态图的搜索，在不一样的分支上展开多条途径，并且维护一种有关状态图的全局信息表。搜索过程同一般的状态图搜索大体同样，还需要维护一种有序的OPEN队列辅助。SSS*算法和DUAL*算法是两个相对的过程，两者对最大值或最小值的操作相反，最大化操作和最小化操作相反，OPEN队列的排列的排列也是相反的。AskePlaat等人的研究表明SSS*算法在搜索深度为偶数的极大极小搜索中体现较佳，DUAL*则在深度为奇数搜索中较佳。这两个算法的缺陷是：算法复杂，难于理解；额外的数据构造占用空间大；并且维护有序的OPEN队列所用的时间开销大。B*和PB*算法1969年Berliner提出了B*算法，用一种乐观值和一种消极值来表达评价值。算法从这点出发，用这两个界来证明哪个节点是最佳的。当根节点的一种孩子的消极值不比所有其他节点的乐观值差的时候，B*算法就结束了。算法的搜索控制就是尽量快的得到终止条件。B*算法的缺陷是它对局面的乐观值和消极值的估计得可信赖程度，它对这个估值的依赖性太强。PB*算法就是基于概率的B*算法，由Paley在1983年提出。这个算法对概率的精确估计比较敏感，实现困难。5结语以上简要地论述了机器博弈理论的原理，并且对现存的二人零和完备信息搜索措施给出了比较全面的讲述。二人零和完备信息博弈的研究已经有半个多世纪的历史，其知识构造系统，层次清晰，已经获得了许多惊人的成果。另一种方向是非完备信息游戏的博弈研究，本文没有波及。这方面的研究也获得了某些成果，如拼字游戏Scrabble，桥牌和扑克，都可以实现人机对战的过程，有某些程序还相称强大，但比之完备信息的博弈，它的研究还远远不够广泛。重要参照文献Plaat.ReachRe:Search&Re-Search.PhDthesis,ErasmusUniversity,Dept.pfCom