·86 智能系统学报 第2卷 Node Evaluation =Crucial chain's First lib- 小节点的最差可能值.使用这些值，很多分支可以被 erties *4+#Crucial chain's Second liberties 裁减掉 1.4终止状态测试 在儿子节点被最好排序的情况下，Alpha-Beta 算法中设定一个节点评估值的上限来进行终止 搜索为求解问题需要访问的节点数目约为w2,w 状态测试.如果节点的评估值大于这个上限，则目标 是平均候选着法的数目，d是搜索的深度.在最坏情 棋块被认为可以逃脱.如果目标棋块可以被直接吃 况下，为了求解它需要搜索整个博弈树 掉或者被征子吃掉则被认为可以吃掉 文中使用Alpha-Beta搜索及迭代加深、置换 表.每次迭代深度增加为2.关于置换表使用Zobrist 2 博弈树搜索算法 哈希161和线性探查 对于二人、零和、完备信息的棋类游戏，例如围 几种常用的用于博弈树搜索算法比较的指标 棋、象棋、国际象棋和跳棋，博弈树算法对构建一个 有：CPU时间、访问的叶子节点数、访问的所有节点 强大的博弈程序是关键的.博弈树搜索的目标是要 数.文中使用访问的所有节点数来衡量算法的表 找到极大极小博弈树或者与和树的最佳值以及最佳 现 着法序列.一般博弈树非常大以至于不能被当前的 这里使用Kano围棋系列的第3册中的吃子问 计算机所求解.降低博弈树大小的策略包括缩小候 题来检验算法效果.每一个问题的搜索时间被限制 选着法的数目以缩小展开因子、当搜索到某一深度 在200s内.表1包含了Alpha-Beta搜索不使用置 时使用评估函数以及使用搜索路径选择策略.选择 换表和使用置换表的测试结果 候选着法以及使用评估函数很大程度上取决于领域 使用置换表的算法表现比不使用置换表的算法 知识.搜索路径选择策略则一般与领域知识无关.深 表现好：使用的时间较少、访问的节点较少，将节点 度优先搜索和最佳优先搜索是最主要的2种搜索路 的最佳值存储在置换表中可以避免对同样的局面重 径选择策略 新计算，在迭代加深中使用置换表也可以帮助候选 AlpharBeta搜索是深度优先搜索算法而且是 着法排序。 当前博弈游戏程序最广泛使用的博弈树搜索算 候选着法排序的质量对Alpha-Beta搜索的效 法io..候选着法的排序对于Alpha-Beta搜索的 率是关键的.但对于不同问题很难给出统一的评估 效率是关键的.Alpha-Beta搜索有很多扩展，其中 函数去得到候选着法的最佳排序.进一步的工作可 包括迭代加深、置换表、历史启发函数等，大多数用 以使用模式数据库去帮助候选着法排序 于得到更好的候选着法排序，使用迭代加深的A: 结果发现Alpha-Beta搜索不能解决的问题主 pha-Beta搜索可以得到某一深度的最优值，这可以 要由于以下3个原因： 作为限制时间搜索下的近似解.Alpha-Beta搜索的 I)在时间限制下Alpha-Beta搜索很难搜索到 缺点是很难搜索到很深的深度 很深的深度.对于那些需要很深深度搜索才能求解 pn搜索是最佳优先搜索算法.对于非均衡树的 的问题，Alpha-Beta搜索一般用光时间从而失败. 求解，pn搜索是非常强大的2].pn搜索需要将整个 2)候选着法没有包括所有可能着法：正确着法 搜索树保存在内存中，所以内存消耗很大.近年来， 缺失 出现了一些pn搜索的深度优先搜索的变体，例如 3)解决此问题需要其他知识如连接和死活知 pn*l、df-pn和df-pn+.使用proof number 识 和disproof number的阈值，这些算法可以以深度优 先的方式去搜索博弈树，但是所展开的博弈树与pn proof-number搜索 搜索是一样的.这些深度优先的变体可以减少内存 pn搜索是最佳优先搜索算法.对于非均衡树的 的使用，但是效果与pn搜索相似 求解pn搜索是非常强大的.pn搜索的思想是总是 目前Alpha-Beta搜索及其扩展仍然是最广泛 展开那些用最小代价就可以证明或者否证与或博弈 使用的博弈树搜索算法山.pn搜索及其变体变得 树的节点2.pn搜索将节点分为2种：与节点和或 越来越流行口 节点.在每个与节点努力去否证节点，在每个或节点 努力去证明节点.在每个节点上使用2个数值： 3 Alpha-Beta搜索 proof number最少需要展开的叶子节点去证明 Alpha-Beta搜索的思想是利用Alpha值 此节点的数目；disproof number最少需要展开 对于极大节点的最差可能值和Beta值对于极 的叶子节点去否证此节点的数目.对于博弈树有时 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.netNode Evaluation = # Crucial chain’s First lib2 erties 3 4 + # Crucial chain’s Second liberties 114 终止状态测试 算法中设定一个节点评估值的上限来进行终止 状态测试. 如果节点的评估值大于这个上限 ,则目标 棋块被认为可以逃脱. 如果目标棋块可以被直接吃 掉或者被征子吃掉则被认为可以吃掉. 2 博弈树搜索算法 对于二人、零和、完备信息的棋类游戏 ,例如围 棋、象棋、国际象棋和跳棋 ,博弈树算法对构建一个 强大的博弈程序是关键的. 博弈树搜索的目标是要 找到极大极小博弈树或者与和树的最佳值以及最佳 着法序列. 一般博弈树非常大以至于不能被当前的 计算机所求解. 降低博弈树大小的策略包括缩小候 选着法的数目以缩小展开因子、当搜索到某一深度 时使用评估函数以及使用搜索路径选择策略. 选择 候选着法以及使用评估函数很大程度上取决于领域 知识. 搜索路径选择策略则一般与领域知识无关. 深 度优先搜索和最佳优先搜索是最主要的 2 种搜索路 径选择策略. Alp ha2Beta 搜索是深度优先搜索算法而且是 当前博弈游戏程序最广泛使用的博弈树搜索算 法[10 - 11 ] . 候选着法的排序对于 Alp ha2Beta 搜索的 效率是关键的. Alp ha2Beta 搜索有很多扩展 ,其中 包括迭代加深、置换表、历史启发函数等 ,大多数用 于得到更好的候选着法排序. 使用迭代加深的 Al2 p ha2Beta 搜索可以得到某一深度的最优值 ,这可以 作为限制时间搜索下的近似解. Alp ha2Beta 搜索的 缺点是很难搜索到很深的深度. p n 搜索是最佳优先搜索算法. 对于非均衡树的 求解 ,p n 搜索是非常强大的[12 ] . p n 搜索需要将整个 搜索树保存在内存中 ,所以内存消耗很大. 近年来 , 出现了一些 p n 搜索的深度优先搜索的变体 ,例如 p n 3 [13 ] 、df - p n 和 df - p n + [14 ] . 使用 proof number 和 disproof number 的阈值 ,这些算法可以以深度优 先的方式去搜索博弈树 ,但是所展开的博弈树与 p n 搜索是一样的. 这些深度优先的变体可以减少内存 的使用 ,但是效果与 p n 搜索相似. 目前 Alp ha2Beta 搜索及其扩展仍然是最广泛 使用的博弈树搜索算法[11 ] . p n 搜索及其变体变得 越来越流行[1 ] . 3 Alp ha2Beta 搜索 Alp ha2Beta 搜索的思想是利用 Alp ha 值 ——— 对于极大节点的最差可能值和 Beta 值 ———对于极 小节点的最差可能值. 使用这些值 ,很多分支可以被 裁减掉[ 15 ] . 在儿子节点被最好排序的情况下 ,Alp ha2Beta 搜索为求解问题需要访问的节点数目约为 w d/ 2 , w 是平均候选着法的数目 , d 是搜索的深度. 在最坏情 况下 ,为了求解它需要搜索整个博弈树. 文中使用 Alp ha2Beta 搜索及迭代加深、置换 表. 每次迭代深度增加为 2. 关于置换表使用 Zobrist 哈希[16 ]和线性探查. 几种常用的用于博弈树搜索算法比较的指标 有 :CPU 时间、访问的叶子节点数、访问的所有节点 数[17 ] . 文中使用访问的所有节点数来衡量算法的表 现. 这里使用 Kano 围棋系列的第 3 册中的吃子问 题来检验算法效果. 每一个问题的搜索时间被限制 在 200 s 内. 表 1 包含了 Alp ha2Beta 搜索不使用置 换表和使用置换表的测试结果. 使用置换表的算法表现比不使用置换表的算法 表现好 :使用的时间较少、访问的节点较少. 将节点 的最佳值存储在置换表中可以避免对同样的局面重 新计算. 在迭代加深中使用置换表也可以帮助候选 着法排序. 候选着法排序的质量对 Alp ha2Beta 搜索的效 率是关键的. 但对于不同问题很难给出统一的评估 函数去得到候选着法的最佳排序. 进一步的工作可 以使用模式数据库去帮助候选着法排序. 结果发现 Alp ha2Beta 搜索不能解决的问题主 要由于以下 3 个原因 : 1) 在时间限制下 Alp ha2Beta 搜索很难搜索到 很深的深度. 对于那些需要很深深度搜索才能求解 的问题 ,Alp ha2Beta 搜索一般用光时间从而失败. 2) 候选着法没有包括所有可能着法 :正确着法 缺失. 3) 解决此问题需要其他知识如连接和死活知 识. 4 proof2number 搜索 p n 搜索是最佳优先搜索算法. 对于非均衡树的 求解 p n 搜索是非常强大的. p n 搜索的思想是总是 展开那些用最小代价就可以证明或者否证与或博弈 树的节点[12 ] . p n 搜索将节点分为 2 种 :与节点和或 节点. 在每个与节点努力去否证节点 ,在每个或节点 努力去证明节点. 在每个节点上使用 2 个数值 : proof number ———最少需要展开的叶子节点去证明 此节点的数目 ; disproof number ———最少需要展开 的叶子节点去否证此节点的数目. 对于博弈树有时 ·86 · 智 能 系 统 学 报 第 2 卷