基于mtd(f)算法的六子棋程序设计研究.doc

基于 MTD(f)算法的六子棋程序设计研究张润梅，刘长城，王传对1 安徽建筑工业学院电子信息工程学院2 安徽建筑工业学院电子信息工程学院3 安徽建筑工业学院电子信息工程学院摘 要: 该课题中研究出的博弈搜索可很好地应用实际的软件开发中，现在六子棋的研究处于起步阶段，有广阔的研究意义和商业价值，目前在苹果 iPhone的 App Store(软件商店)有六子棋的上架，很受喜爱，大陆内地和台湾学术界都在研究其中的复杂技术，很好地推动人工智能领域在商业、军事和经济领域的应用，本文重点介绍六子棋开发过程中博弈搜索算法 MTD(F)和搜索引擎中的置换表关键词：机器博弈，MTD(F)，置换表，六子棋Abstract: Developed the game search in this subject can be well applied in actual software development, the study of Connect6 Computer Game is in its infancy, there is broad research significance and commercial value, Connect6 Computer Game can be found in the Apple iPhone App Store (software store), mainland and Taiwan’s academia are in study of its complex technology to promote the field of artificial intelligence in commercial, military and economic, this article focuses on Connect6 Computer Game development processing the MTD (f) for game search algorithm and the Transposition Tab for search engine.Keywords: Computer Game, MTD (f), Transposition Tab, Connect 61.前 言目前已知博弈的算法在中国象棋和其他棋类博弈中都有很好的体现，但是适合六子棋状态空间的算法就需要在实际的开发中进行比较，本文的 MTD(F)算法在 Alpha-Beta 基础上进行深层次的改进，很好地综合了前有算法优点，在处理海量数据方面取得了明显优势；一个好的算法就对应一种好的优化方法，文中介绍的 Deeper-Always Transposition Table 置换表方法在处理 Alpha-Beta算法的数据冗余、提高 Alpha-Beta 算法效率方面有很高的优越性。

2.MTD(F)算法博弈算法也即博弈搜索，下面介绍 Alpha-Beta 剪枝博弈算法来导出 MTD(F)算法的优点一般搜索树中有三种类型的结点： （1）偶数层的中间结点，代表棋手甲要走的局面； （2）奇数层的中间结点，代表棋手乙要走的局面； （3）叶子结点，代表棋局结束的局面，即棋手甲或乙获胜，或者是和局2.1 Alpha-Beta 剪枝算法在普通的搜索算法中，要遍历整个博弈树，会造成冗余，所以要剔除一些分枝，Bruno 在 1963 年首先提出了 Alpha-Beta 剪枝算法 α-β 剪枝搜索是一种基于 α-β 剪枝(α-β cut-off)的深度优先搜索 (Depth-first search)它去掉了一些不影响最终结果的分支而返回与 MINIMAX 相同走步的过程我们假设六子棋用一个静态估值函数，用 MINIMAX 过程对博弈树进行搜索，每一次扩展 19×19=361 个结点，假设一个性能好的程序在一台普通的 PC 机上，一秒内可搜索 10 000 个结点，对于三层的 MINIMAX 搜索树需扩展 11 390 625 个结点，则需 1 139s 约 19min 的时间下一步棋。

这显然是不可忍受的幸运的是，我们不用把每个结点都搜索一遍也可获得和 MINIMAX 搜索同样结果的走步不搜索分支结点而舍弃该分支的过程称为剪枝α 值为倒推值下界，β 值为倒推值上界Alpha-Beta 搜索首先使某一部分达到最大深度 ，从而计算出 Max 节点的 α 值， Min 节点的 β 值，然后继续搜索，不断修改这些值，在修改过程中，α 值永不下降，β 值永不增加将走棋方定为 MAX 方，因为它选择着法时总是对其子节点的评估值取极大值，即选择对自己最为有利的着法；而将应对方定为 MIN 方，因为它走棋时需要对其子节点的评估值取极小值，即选择对走棋方最为不利的、最有钳制作用的着法因此可以利用这个规则进行剪枝，剪枝规则如下：规则 1：在对博弈树采取深度优先的搜索策略时, 从左路分枝的叶节点倒推得到某一层 MAX 节点的值, 可表示到此为止得以“落实”的着法最佳值，记为α显然此 α 值可作为 MAX 方着法指标的下界当任何 MIN 节点的 β 值小于等于它的 MAX 父节点的 α 值时，则可以中止该 MIN 节点以下的搜索，同时该 β 值作为 MIN 节点的最终倒推值当满足该规则而减少了搜索时，称进行了 α 剪枝。

Figure 1.α 剪枝示意图规则 2：由左路分枝的叶节点倒推得到某一层 MIN 节点的值，可表示到此为止对方着法的钳制值，记为 β显然此 β 值可作为 MAX 方可能实现着法指标的上界当任何 MAX 节点的 α 值大于等于它的 MIN 父节点的 β 值时，则可以中止该 MAX 节点以下的搜索，同时该 α 值即为 MIN 节点的最终倒推值当满足该规则而减少了搜索时，称进行了 β 剪枝Figure 2.β 剪枝示意图α-β 剪枝是根据极大极小搜索规则的进行的, 虽然它没有遍历某些子树的大量节点, 但它仍不失为穷尽搜索的本性采用 Alpha-Beta 搜索所得的走法总与同样条件下使用极大极小搜索取得的走法一致，但 Alpha-Beta 搜索的节点数更少同极大极小搜索算法一样，Alpha-Beta 搜索算法需要在奇数层进行 α 剪枝，在偶数层进行 β 剪枝不过只要将负极大值的形式套用上去，这样在任何一层都只进行 β 剪枝，同负极大值算法一样简洁剪枝技巧的发现, 一下便为博弈树搜索效率的提高开创了崭新的局面将 α-β 剪枝作用延伸到多个回合之后，于是又出现了深层 α-β 剪枝(Deepα-βcut-off) 算法，也取得很好效果。

Alpha-Beta 搜索算法的效率与子节点被搜索的先后顺序密切相关在最理想情况 (极小树)，即最左路的分枝就是最佳路径，其生成的节点数目为：ND=2BD/2-1(D 为偶数) (a)ND=B(D+1)/2+B(D-1)/2-1(D 为奇数) (b)其中 D 为搜索深度，B 为分支因子(Branching factor)而在最糟糕情况下，右节点的得分情况总是好于左节点，搜索过程将不做任何剪枝，此时需要搜索的节点数是 ND=BD故分析可知，最理想情况下 Alpha-Beta 算法搜索深度为 D 的节点相当于搜索深度为 D/2 的不做任何剪枝的节点数，其复杂度仍很大，需要优化2.2 MTD(f)算法MTD(f)介绍：MTD(f)算法的全称是 Memory-enhanced Test Driver with node n and value f，缩写为 MTD(n,f)或 MTD(f)实现原理：算法通过多次调用 Alpha-Beta 来完成搜索，每次调用均采用空窗口进行搜索，该调用返回一个真实值的上（或下）界，然后利用该返回值修改 MTD(f)的上边界或下边界。

在搜索过程中上下边界的范围不断缩小，逐步向真实值逼近，当下边界的值大于或等于上边界时，搜索就完成了MTD(f)算法流程图如下：NoYESNOYesNOYesFigure 3.MTD(f)流程示意图定义 beta、猜测值 guess定义上界 upper、下界 lower下界<上界猜测值=下界Beta = guess+1使用 FailsoftAlphaBe 空窗探测真实值的范围Beta = guess猜测值<下界修改上界 缩小窗口修改下界 缩小窗口返回猜测值结束开始分析：算法中无大窗口搜索，全部皆为空窗口搜索，剪枝效率很高但因重复搜索次数多，需与置换表相结合，以重复利用搜索中生成过的节点，提高搜索效率此外，初始预测值 guess 的好坏会影响逼近的速度，因此也需与迭代加深相结合，以得到较好的初始预测值，提高搜索效率 3.置换表优化博弈过程实现原理：置换表基于内存增强原理，带有一定启发信息，当在搜索中遇到相同的节点时，如其值有效，可通过置换表来直接引用节点估值；若其值无效，也可利用表中的最佳走法进行很好的子节点排序下图是基于 Alpha-Beta算法置换表的实现原理图：Alpha-Beta 计算Value保存到预置表中Value=nullValue! = nullFigure 4.置换表原理图分析：省去重复的工作，这是置换表的一大特色，但是在一般的局面里，置换表的另一个作用更为重要，在每个散列项里都有局面中最好的着法，首先搜索好的着法可以大幅度提高搜索效率。

因此如果在散列项里找到最好的着法，那么你首先搜索这个着法，这样会改进你的着法顺序，减少分枝因子，从而在短的时间内搜索得更深置换策略分析：置换表策略主要有深度优先(Deeper Priority)和随时替换(Always Replace)两种，深度优先策略主要基于深度的考虑，忽略了棋局不断演变产生的新棋局信息对以后局势的影响，无法保证棋局信息的实时性，从而Alpha-Beta 搜索函数根据搜索节点和搜索深度来查询其对应预置表中 Value判断预置表返回值Value预置表 Transposition Tab返回该节点的搜索值Value降低了置换表的效率，有时甚至引发非法剪枝而随时替换策略虽然充分考虑了棋局新信息，具有较好的实时性，但却丢掉了拥有较深层数的棋局数据，浪费了资源并增加了搜索时间，效率不如深度优先策略(下文验证实验结果证明了这一结论)基于以上考虑，利用上述两种置换策略的优点，引入双置换表(Deeper-Always Transposition Table)策略双置换表(Deeper-Always Transposition Table)策略结合了以上两种策略的优势，即采用两个置换表分别进行深度优先替换和随时替换策略的搜索。

其基本思想：首先基于深度优先的考虑，一般来说深度越深其子树的节点数越多，就更容易显示 Deeper-Always Transposition Table 的优势，减少搜索节点数，并且数据的可靠性越高，因而将深度优先策略作为 Deeper-Always Transposition Table 的第一层；其次，依据局部性原理，最近访问的内容往往在不远的将来会被再次访问的可能性非常大，因而一旦遇到与表中以前所存局面相同时就立即替换，随时替换置换表策略在写入和读出时都不用做深度判断，只要可以剪枝就执行，因此将随时替换策略作为 Deeper-Always Transposition Table 的第二层然而 Deeper-Always Transposition Table并不是两个表的简单罗列，其最大的难点在于如何使这两个表有机配合工作，确定什么时候该剪枝及以哪个表中的数据为准进行剪枝如果配合不好其效率将会大大降低，甚至导致误剪枝等严重后果另外，两个置换表的同时使用必然增加存储量，从而加大了置换表查找和写入的时间和空问难度等基于以上问题，置换策略设计如下：(1)如果待置入节点的深。