.792 智能系统学报 第11卷 象棋、国际跳棋等博弈程序里，MTD(f)算法平均 的时间停止。 表现出色。 迭代深化利用Alpha-Beta剪枝算法对子节点排 此外，还有各种在Apha-Beta搜索基础上优化 序敏感的特点，使用上次迭代后得到的博弈值，作为 的算法，例如，有学者提出在博弈树同层结点中，用 当前迭代的搜索窗口估值，以此为启发式信息计算 广度优先搜索，接力式空窗探测，平均搜索效率高于 当前迭代的博弈值。另外，它利用时间控制遍历次 MTD(f)搜索[。通常，裁剪算法需要与置换表技 数，只要时间一到，搜索立即停止。在关键的开局和 术相结合，以减少博弈树的规模，提高搜索效率。 残局，由于分支较少，可以进行较深层次的搜索。 4.2.3置换表[5]技术 Alpha-Beta剪枝经过一系列技术如置换表、历史启 置换表是一个大的直接访问表，用来存储已经 发、迭代深化等增强后，其性能可大幅提高。 搜索过结点（或者子树）的结果，下次搜索遇到时直 4.2.6最佳优先算法 接运用。置换表的构造，一般使用Hash表和Zo 最佳优先的搜索算法，不受节点排序的影响，其 bristHash技术来实现。 搜索空间小于深度优先的最小树，理论上应该优于 合理使用置换表，可以提高搜索效率，当博弈树 深度优先。实际上，最佳优先算法仍处于理论研究 的深度很大时，置换表对内存空间要求巨大。通常 阶段。最佳优先算法分为两类：采用极大极小算法 的对策是对置换表分配有限大小，并采用散列方式 取值的SSS[63-64]算法和DUAL·算法，不采用极大 管理存取。具体应用到各个棋种中时，还要根据实 极小方法取值的B·[]和PB·[6算法。 际局面的节点类型，进行处理。 1)SSS·和DUAL·算法[63-64] 4.2.4启发式算法 SSS·和DUAL·算法都属于状态空间搜索 “启发”(Heuristic)是指通过排序让Alpha-Beta (State Space Search),把极大极小树看成状态图，在 剪枝的搜索树尽可能地接近最小树，优先搜索好的 不同的分支上展开多条路径，并且维护一个关于状 着法。启发通常有置换表启发、历史启发和杀手启 态图的全局信息表。这两种算法是两个操作相反的 发等常用的算法。 过程，前者在搜索深度为偶数的极大极小搜索中表 1)置换表启发[8-9 现较佳，后者则在深度为奇数搜索中较佳。 置换表启发是置换表与Alpha-Beta剪枝算法相 SSS·和DUAL·算法都过于复杂，难于理解，且时 结合的产物。在中国象棋等棋种中，通过引进置换 间和空间开销较大，在计算机博弈中实际应用较少。 表启发技术来增强搜索效率。 2)B·和PB·算法[6s-66 2)历史启发[0] B·算法用一个乐观值和一个悲观值来评价节点。 历史启发也是迎合alpha-beta搜索对节点排列 当根节点的一个孩子的悲观值不比所有其他节点的乐 顺序敏感的特点来提高剪枝效率的。它通过维护着 观值差的时候，B·算法就结束了。算法搜索控制的关 法历史，每当遇到好的着法，就给其历史得分一个相 键是尽快找到终止条件。由于它对局面估值的依赖性 应的增量，使其具有更高的优先被搜索的权利。 太强，估值的可信度将直接影响最终结果。 历史启发是一种基于经验的择序标准，它克服 PB·算法就是基于概率的B·算法，这个算法对 了基于知识择序存在的知识不足的缺点，使得算法 概率的准确估计比较敏感，实现困难。 的择序具有很强的动态适应性。 4.2.7随机搜索 3)杀手启发[61] 随机搜索有两种算法：拉斯维加斯算法和蒙特 杀手启发可以看作是历史启发的特例。它把同 卡罗算法。采样越多，前者越有机会找到最优解，后 层中引发剪枝最多的节点称为杀手，当下次搜索到 者则越接近最优解。 同一层时，如果杀手移动是合法的话，就优先搜索杀 通常，要根据问题的约束条件来确定随机算法， 手。杀手启发可以对着法进行动态重排序，且提高 如果对采样没有限制，但必须给出最优解，则采用拉 了置换表的使用效率。 斯维加斯算法。反之，如果要求在有限采样内求解， 4.2.5迭代深化[62 但不要求是最优解，则采用蒙特卡罗算法。 迭代深化也称为遍历深化，是一种常用的蛮力 计算机博弈中，每步着法的运算时间、堆栈空间 搜索机制，经常使用在深度优先搜索中。迭代深化 都是有限的，且仅要求局部优解，适合采用蒙特卡罗 最初是作为控制时间的机制而提出的，通过对博弈 算法。由于非完备信息博弈也具有不确定性博弈的 树进行多次遍历，并逐渐提高搜索深度，一直到指定 一些特征，所以蒙特卡罗算法也适用于非完备信息象棋、国际跳棋等博弈程序里，ＭＴＤ（ ｆ ） 算法平均 表现出色。 此外，还有各种在 Ａｌｐｈａ⁃Ｂｅｔａ 搜索基础上优化 的算法，例如，有学者提出在博弈树同层结点中，用 广度优先搜索，接力式空窗探测，平均搜索效率高于 ＭＴＤ（ ｆ ）搜索［５７］ 。 通常，裁剪算法需要与置换表技 术相结合，以减少博弈树的规模，提高搜索效率。 ４．２．３ 置换表［５８］技术 置换表是一个大的直接访问表，用来存储已经 搜索过结点（或者子树）的结果，下次搜索遇到时直 接运用。 置换表的构造，一般使用 Ｈａｓｈ 表和 Ｚｏ⁃ ｂｒｉｓｔＨａｓｈ 技术来实现。 合理使用置换表，可以提高搜索效率，当博弈树 的深度很大时，置换表对内存空间要求巨大。 通常 的对策是对置换表分配有限大小，并采用散列方式 管理存取。 具体应用到各个棋种中时，还要根据实 际局面的节点类型，进行处理。 ４．２．４ 启发式算法 “启发”（Ｈｅｕｒｉｓｔｉｃ）是指通过排序让 Ａｌｐｈａ⁃Ｂｅｔａ 剪枝的搜索树尽可能地接近最小树，优先搜索好的 着法。 启发通常有置换表启发、历史启发和杀手启 发等常用的算法。 １）置换表启发［５８－５９］ 置换表启发是置换表与 Ａｌｐｈａ⁃Ｂｅｔａ 剪枝算法相 结合的产物。 在中国象棋等棋种中，通过引进置换 表启发技术来增强搜索效率。 ２）历史启发［６０］ 历史启发也是迎合 ａｌｐｈａ⁃ｂｅｔａ 搜索对节点排列 顺序敏感的特点来提高剪枝效率的。 它通过维护着 法历史，每当遇到好的着法，就给其历史得分一个相 应的增量，使其具有更高的优先被搜索的权利。 历史启发是一种基于经验的择序标准，它克服 了基于知识择序存在的知识不足的缺点，使得算法 的择序具有很强的动态适应性。 ３）杀手启发［６１］ 杀手启发可以看作是历史启发的特例。 它把同 层中引发剪枝最多的节点称为杀手，当下次搜索到 同一层时，如果杀手移动是合法的话，就优先搜索杀 手。 杀手启发可以对着法进行动态重排序，且提高 了置换表的使用效率。 ４．２．５ 迭代深化［６２］ 迭代深化也称为遍历深化，是一种常用的蛮力 搜索机制，经常使用在深度优先搜索中。 迭代深化 最初是作为控制时间的机制而提出的，通过对博弈 树进行多次遍历，并逐渐提高搜索深度，一直到指定 的时间停止。 迭代深化利用 Ａｌｐｈａ⁃Ｂｅｔａ 剪枝算法对子节点排 序敏感的特点，使用上次迭代后得到的博弈值，作为 当前迭代的搜索窗口估值，以此为启发式信息计算 当前迭代的博弈值。 另外，它利用时间控制遍历次 数，只要时间一到，搜索立即停止。 在关键的开局和 残局，由于分支较少，可以进行较深层次的搜索。 Ａｌｐｈａ⁃Ｂｅｔａ 剪枝经过一系列技术如置换表、历史启 发、迭代深化等增强后，其性能可大幅提高。 ４．２．６ 最佳优先算法 最佳优先的搜索算法，不受节点排序的影响，其 搜索空间小于深度优先的最小树，理论上应该优于 深度优先。 实际上，最佳优先算法仍处于理论研究 阶段。 最佳优先算法分为两类：采用极大极小算法 取值的 ＳＳＳ ∗ ［６３－６４］算法和 ＤＵＡＬ ∗ 算法，不采用极大 极小方法取值的 Ｂ ∗ ［６５］和 ＰＢ ∗ ［６６］算法。 １）ＳＳＳ ∗和 ＤＵＡＬ ∗算法［６３－６４］ ＳＳＳ ∗ 和 ＤＵＡＬ ∗ 算 法 都 属 于 状 态 空 间 搜 索 （Ｓｔａｔｅ Ｓｐａｃｅ Ｓｅａｒｃｈ），把极大极小树看成状态图，在 不同的分支上展开多条路径，并且维护一个关于状 态图的全局信息表。 这两种算法是两个操作相反的 过程，前者在搜索深度为偶数的极大极小搜索中表 现较佳，后者则在深度为奇数搜索中较佳。 ＳＳＳ ∗和 ＤＵＡＬ ∗算法都过于复杂，难于理解，且时 间和空间开销较大，在计算机博弈中实际应用较少。 ２）Ｂ ∗和 ＰＢ ∗算法［６５－６６］ Ｂ ∗算法用一个乐观值和一个悲观值来评价节点。 当根节点的一个孩子的悲观值不比所有其他节点的乐 观值差的时候，Ｂ ∗算法就结束了。 算法搜索控制的关 键是尽快找到终止条件。 由于它对局面估值的依赖性 太强，估值的可信度将直接影响最终结果。 ＰＢ ∗算法就是基于概率的 Ｂ ∗算法，这个算法对 概率的准确估计比较敏感，实现困难。 ４．２．７ 随机搜索 随机搜索有两种算法：拉斯维加斯算法和蒙特 卡罗算法。 采样越多，前者越有机会找到最优解，后 者则越接近最优解。 通常，要根据问题的约束条件来确定随机算法， 如果对采样没有限制，但必须给出最优解，则采用拉 斯维加斯算法。 反之，如果要求在有限采样内求解， 但不要求是最优解，则采用蒙特卡罗算法。 计算机博弈中，每步着法的运算时间、堆栈空间 都是有限的，且仅要求局部优解，适合采用蒙特卡罗 算法。 由于非完备信息博弈也具有不确定性博弈的 一些特征，所以蒙特卡罗算法也适用于非完备信息 ·７９２· 智 能 系 统 学 报 第 １１ 卷