第3期 张培刚，等：使用不同的博弈树搜索算法解决计算机围棋的吃子问题 ·89· 成功吃死问题示例：228.sg number和disproof number一般持续增长 35 70r 成功吃死问题示例：45.5gf -p 60 -dn 20 840 民30 20 4 68 101214 10f。●鲁指。小 搜索深度 0 节点访向数 图8最佳值随深度变化（成功吃死问题示例） Fig 8 The best value of search with search deepening 1lpn搜索过程中根节点的proof number和disproof captured problem example number的变化（成功吃死问题示例） 120r 成功逃脱问题示例：15sgf Fig 11 The variation of proof number and disproof number 100H 914100 during pr search,captured problem example 804 成功逃脱问题示例：15.sg1 60 160-Pm 40 47 Dn 20 16 120 民 0 35 9i13s 且 80 搜索深度 40 图9最佳值随深度变化（成功逃脱问题示例） 0 节点访问数 Fig 9 The best value of search with search deepening, escaped problem example 图12pn搜索过程中根节点的proof number和disproof 未解出向题示例：8.sgf number的变化（成功逃脱问题示例） 40r 3333 363333 Fig 12 The variation of proof number and disproof number 30 28 during pr search,escaped problem example 20 21 需要进一步的研究这种模式是否可以帮助在结 15 果未知的情况下对结果进行预测 0 4680立14 6结束语 搜索深度 与其他相关工作比较，本文的吃子算法的表现 图10最佳值随深度变化（未能求解问题示例） 是出色的.pn搜索及其变体在解决吃子问题中有更 Fig 10 The best value of search with search deepening, 好的表现.大多数问题可以在不到1s的时间内求 unsolved problem example 解成功.这一成果可以被用于计算机围棋程序在比 随搜索访问节点数的增加根节点的proof number 赛中使用. 和disproof number的变化情况 那些未能求解的问题基本上可以归为2个原 proof number是最少需要展开的叶子节点去 因：评估函数的质量不高和需要其他类型的领域知 证明此节点的数目；disproof number是最少需要展 识如连接和死活.这需要提高评估函数的质量和使 开的叶子节点去否证此节点的数目，如果根节点的 用其他围棋战术知识： proof number变为0则目标被吃死.如果根节点的 进一步的工作包括 disproof number变为0则目标逃脱.对于那些成功 1)进一步优化吃子问题的评估函数.包括优化 吃死的问题proof number一般增加到一定的峰值 候选着法的产生、节点评估和用于pn+和df-pn+ 然后逐渐下降直到0，disproof number一般持续增 中的评估函数.机器学习的方法例如遗传算法可以 长.对于那些成功逃脱的问题，proof number一般 持续增长，disproof number一般增加到一定的峰值 引入以帮助优化评估函数 然后逐渐下降直到0.对于那些未解出的问题，proof 2)进一步研究Alpha-Beta搜索和pn搜索中的 模式及其对搜索结果的预测 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net图 8 最佳值随深度变化(成功吃死问题示例) Fig18 The best value ofαβ2search with search deepening , captured problem example 图 9 最佳值随深度变化(成功逃脱问题示例) Fig19 The best value ofαβ2search with search deepening , escaped problem example 图 10 最佳值随深度变化(未能求解问题示例) Fig110 The best value ofαβ2search with search deepening , unsolved problem example 随搜索访问节点数的增加根节点的 proof number 和 disproof number 的变化情况. proof number 是最少需要展开的叶子节点去 证明此节点的数目 ;disproof number 是最少需要展 开的叶子节点去否证此节点的数目. 如果根节点的 proof number 变为 0 则目标被吃死. 如果根节点的 disproof number 变为 0 则目标逃脱. 对于那些成功 吃死的问题 ,proof number 一般增加到一定的峰值 然后逐渐下降直到 0 ,disproof number 一般持续增 长. 对于那些成功逃脱的问题 ,proof number 一般 持续增长 ,disproof number 一般增加到一定的峰值 然后逐渐下降直到 0. 对于那些未解出的问题 ,proof number 和 disproof number 一般持续增长. 图 11 pn 搜索过程中根节点的 proof number 和 disproof number 的变化(成功吃死问题示例) Fig111 The variation of proof number and disproof number during pn2search , captured problem example 图 12 pn 搜索过程中根节点的 proof number 和 disproof number 的变化(成功逃脱问题示例) Fig112 The variation of proof number and disproof number during pn2search , escaped problem example 需要进一步的研究这种模式是否可以帮助在结 果未知的情况下对结果进行预测. 6 结束语 与其他相关工作比较 ,本文的吃子算法的表现 是出色的. p n 搜索及其变体在解决吃子问题中有更 好的表现. 大多数问题可以在不到 1 s 的时间内求 解成功. 这一成果可以被用于计算机围棋程序在比 赛中使用. 那些未能求解的问题基本上可以归为 2 个原 因 :评估函数的质量不高和需要其他类型的领域知 识如连接和死活. 这需要提高评估函数的质量和使 用其他围棋战术知识. 进一步的工作包括 : 1) 进一步优化吃子问题的评估函数. 包括优化 候选着法的产生、节点评估和用于 p n + 和 df - p n + 中的评估函数. 机器学习的方法例如遗传算法可以 引入以帮助优化评估函数. 2) 进一步研究 Alp ha2Beta 搜索和 p n 搜索中的 模式及其对搜索结果的预测. 第 3 期 张培刚 ,等 :使用不同的博弈树搜索算法解决计算机围棋的吃子问题 ·89 ·