第3期 张培刚，等：使用不同的博弈树搜索算法解决计算机围棋的吃子问题 ·85* 助在结果未知的情况下对结果进行预测.本文的工 作也为解决其他计算机围棋问题和其他博弈问题提 供了一个框架 1吃子问题 1.1计算机围棋吃子问题 围棋是一项非常古老而且受欢迎的棋类游戏 计算机围棋是人工智能中一个很吸引人的研究领 域561由于其内在复杂性，计算机围棋程序的棋力 与人相比在目前仍然大大落后.计算机围棋遇到各 图2数字标出的点是候选招法， 种类型的问题，为人工智能的各种方法提供了极佳 2是吃住目标的正确着法 的试验场.它包括许多有趣的战术问题，例如死活、 Fig 2 The candidate moves to capturing the marked 吃子和连接问题.构建一个强大的计算机围棋程序 tone,location 2 is the right move to capture the target 需要很好地解决这些战术问题 策略、终止状态检测、中间节点和叶子节点评估.然 吃子计算的目的是要得到一块棋能否被吃死或 后将使用同样的方法来产生候选着法、节点评估、终 者能否逃脱以及如何吃死或者逃脱.吃子计算对于 止状态检测并将它们用于不同的搜索算法.关于计 计算机围棋程序是基本和关键的].几乎所有的计 算机围棋和吃子问题的一些术语可以见文献[3,6] 算机围棋程序都包括吃子模块.吃子算法可以被用 于解决单独的吃子问题或者被嵌入游戏引擎进行实 1.2候选着法产生 时的吃子计算.由于在实时计算中时间是非常有限 候选着法一般靠近目标棋块或者上一手棋.一 的，所以吃子算法的效率非常重要 块棋的相关选点被定义为这块棋的气和二次气以及 吃子问题为博弈树搜索算法提供了很好的试验 对手相邻这块棋并且不大于三气的棋块的气.这里 场.一些研究者提出了一般用途的算法并且以解决 使用一个简单的评估函数，将着这手棋下在棋盘上 吃子问题作为示例8).这些算法解决吃子问题的 并且计算： 速度非常慢.为了得到更好的和更实际的结果，需要 Point Evaluation =Block's First liberties 进一步的研究 4 +Block's Second liberties 在作者以前的一项研究中，基于Alpha-Beta搜 然后选择评估值比较大的相关选点 索并高度性选择的启发式搜索被用于解决围棋的吃 考虑5种类型的棋块 子问题，得到了很好的结果).文中使用不同的搜索 1)目标棋块； 算法利用相对简单的评估函数并且考虑更多的候选 2)目标棋块的关键链； 着法以处理各种不同的可能情况 3)上一手棋所属棋块： 面对吃子问题，高水平的围棋选手一般能够很 4)对手相邻棋块； 快发现棋子的弱点并进行深而且窄的搜索.对于大 5)上一手棋的相邻棋块 多数情况，基于以前经验所形成的知识，他们能够发 每一种类型的棋块都能产生一些相关选点，在 现棋形的弱点 数目上设定了上限和下限.基本上从这5种类型的 在下面的几节将介绍候选着法的产生和排序的 棋块的相关选点中选择候选着法， 使用2种类型的目标去帮助选择候选着法：吃 子目标和逃脱目标.如果下一手棋轮目标棋块方下 是逃脱目标，否则就是吃子目标.对于不同目标候选 着法的选择策略也略有不同.例如，对于逃脱目标， 候选着法不能使目标棋块被直接征子吃掉 算法中也使用一些其他条件去排除候选着法 候选着法不能填自己的真眼.候选着法的总数被限 图1如图标出的白子是吃子的目标 制在15以下，对于绝大多数情况这是足够的 如果轮黑棋下能够被吃住 1.3节点评估 Fig I The marked white stone is the target, 使用对目标棋块的关键链的评估值作为中间节 it could be captured if black move next 点和叶子节点的评估值： 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved. http://www.cnki.net助在结果未知的情况下对结果进行预测. 本文的工 作也为解决其他计算机围棋问题和其他博弈问题提 供了一个框架. 1 吃子问题 111 计算机围棋吃子问题 围棋是一项非常古老而且受欢迎的棋类游戏. 计算机围棋是人工智能中一个很吸引人的研究领 域[5 - 6 ] . 由于其内在复杂性 ,计算机围棋程序的棋力 与人相比在目前仍然大大落后. 计算机围棋遇到各 种类型的问题 ,为人工智能的各种方法提供了极佳 的试验场. 它包括许多有趣的战术问题 ,例如死活、 吃子和连接问题. 构建一个强大的计算机围棋程序 需要很好地解决这些战术问题[7 ] . 吃子计算的目的是要得到一块棋能否被吃死或 者能否逃脱以及如何吃死或者逃脱. 吃子计算对于 计算机围棋程序是基本和关键的[3 ] . 几乎所有的计 算机围棋程序都包括吃子模块. 吃子算法可以被用 于解决单独的吃子问题或者被嵌入游戏引擎进行实 时的吃子计算. 由于在实时计算中时间是非常有限 的 ,所以吃子算法的效率非常重要. 吃子问题为博弈树搜索算法提供了很好的试验 场. 一些研究者提出了一般用途的算法并且以解决 吃子问题作为示例[8 - 9 ] . 这些算法解决吃子问题的 速度非常慢. 为了得到更好的和更实际的结果 ,需要 进一步的研究. 在作者以前的一项研究中 ,基于 Alp ha2Beta 搜 索并高度性选择的启发式搜索被用于解决围棋的吃 子问题 ,得到了很好的结果[3 ] . 文中使用不同的搜索 算法利用相对简单的评估函数并且考虑更多的候选 着法以处理各种不同的可能情况. 面对吃子问题 ,高水平的围棋选手一般能够很 快发现棋子的弱点并进行深而且窄的搜索. 对于大 多数情况 ,基于以前经验所形成的知识 ,他们能够发 现棋形的弱点. 图 1 如图标出的白子是吃子的目标 , 如果轮黑棋下能够被吃住 Fig11 The marked white stone is the target , it could be captured if black move next 在下面的几节将介绍候选着法的产生和排序的 图 2 数字标出的点是候选招法 , 2 是吃住目标的正确着法 Fig12 The candidate moves to capturing the marked s tone , location 2 is the right move to capture the target 策略、终止状态检测、中间节点和叶子节点评估. 然 后将使用同样的方法来产生候选着法、节点评估、终 止状态检测并将它们用于不同的搜索算法. 关于计 算机围棋和吃子问题的一些术语可以见文献[ 3 ,6 ]. 112 候选着法产生 候选着法一般靠近目标棋块或者上一手棋. 一 块棋的相关选点被定义为这块棋的气和二次气以及 对手相邻这块棋并且不大于三气的棋块的气. 这里 使用一个简单的评估函数 ,将着这手棋下在棋盘上 并且计算 : Point Evaluation = # Block’s First liberties 3 4 + # Block’s Second liberties 然后选择评估值比较大的相关选点. 考虑 5 种类型的棋块 : 1) 目标棋块 ; 2) 目标棋块的关键链 ; 3) 上一手棋所属棋块 ; 4) 对手相邻棋块 ; 5) 上一手棋的相邻棋块. 每一种类型的棋块都能产生一些相关选点 ,在 数目上设定了上限和下限. 基本上从这 5 种类型的 棋块的相关选点中选择候选着法. 使用 2 种类型的目标去帮助选择候选着法 :吃 子目标和逃脱目标. 如果下一手棋轮目标棋块方下 是逃脱目标 ,否则就是吃子目标. 对于不同目标候选 着法的选择策略也略有不同. 例如 ,对于逃脱目标 , 候选着法不能使目标棋块被直接征子吃掉. 算法中也使用一些其他条件去排除候选着法. 候选着法不能填自己的真眼. 候选着法的总数被限 制在 15 以下 ,对于绝大多数情况这是足够的. 113 节点评估 使用对目标棋块的关键链的评估值作为中间节 点和叶子节点的评估值 : 第 3 期 张培刚 ,等 :使用不同的博弈树搜索算法解决计算机围棋的吃子问题 ·85 ·