·88 智能系统学报 第2卷 算法比较 索使用33s访问133384个节点成功求解，pn搜 +a3无置换表-*-pn+ +ag有置换表…dfpn 索只使用260ms访问2094个节点成功求解.pn --pn *…df-pnt 50r 搜索的求解过程很像人的思考方法：进行深而且 45 本… 窄的搜索 治 40H 30 100 300500 700 900 时间/ms 图4所解问题数(1s内限制) 3②①④⑧0 Fig 4 Problems solved within I second 算法比较 9△ +a3无置换表-*-pn叶 。a3有置换表…df-pn 55 -★-pn +…df-pn+ 50 图7一个pn搜索求解快于AlphaBeta搜索的问题 g,7 A problem pmsearch solved faster than search 45 5.3 Alpha-Beta搜索中的数据分析 程序记录了Alpha-Beta搜索过程中每一层迭 40 345678910 代加深所得到的最佳值.发现对于不同种类的问题， 时间/ms 每类问题所得到的最佳值的变化存在着相似的模 式.图6~8是最佳值随深度增加而变化的几种示 图5所解问题数(10s内限制) 例 Fig 5 Problems solved within 10 seconds 某一深度的最佳值是在搜索到此深度所得到目 标棋块关键链的一阶和二阶气的评估.值越小越有 对于其中的I3个问题，Alpha-Beta搜索比 pn搜索求解时间少.图6所示问题Alpha-Beta搜 利于吃子方，值越大越有利于逃脱方.当目标被吃住 时值变为0， 索使用640ms访问3139个节点成功求解，pn搜 对于那些成功吃死的问题，最佳值可能会先有 索使用3384ms访问16791个节点成功求解. 所增加然后逐渐降为0.对于那些成功逃脱的问题， 6 最佳值一般越来越大.对于那些未能求解的问题，最 佳值在一定范围内徘徊· 需要进一步的研究这种模式是否可以帮助在结 果未知的情况下对结果进行预测.对于实际的博弈 程序分配给某一问题的搜索时间通常非常有限，很 难进行全面的搜索.如果这种预测可信，那么它将非 常实用 图6一个AlphaBeta搜索求解快于pn搜索的问题 5.4pn搜索中的数据分析 Fig 6 A problem search solved faster than prrsearch 程序记录了pn搜索过程中根节点的proof 对于其中的29个问题，pn搜索比Alpha-Be number和disproof number的变化.可以发现对于 ta搜索求解时间少，图7所示问题Alpha-Beta搜 每种类型的问题根节点的proof number和disproof number的变化也存在着一定的模式.图9和l0是 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net图 4 所解问题数(1 s 内限制) Fig14 Problems solved within 1 second 图 5 所解问题数(10 s 内限制) Fig15 Problems solved within 10 seconds 对于其中的 13 个问题 , Alp ha2Beta 搜索比 p n 搜索求解时间少. 图 6 所示问题 Alp ha2Beta 搜 索使用 640 ms 访问 3 139 个节点成功求解 ,p n 搜 索使用 3 384 ms 访问 16 791 个节点成功求解. 图 6 一个 Alpha2Beta 搜索求解快于 pn 搜索的问题 Fig16 A problemαβ2search solved faster than pn2search 对于其中的 29 个问题 ,p n 搜索比 Alp ha2Be2 ta 搜索求解时间少. 图 7 所示问题 Alp ha2Beta 搜 索使用 33 s 访问 133 384 个节点成功求解 ,p n 搜 索只使用 260 ms 访问 2 094 个节点成功求解. p n 搜索的求解过程很像人的思考方法 :进行深而且 窄的搜索. 图 7 一个 pn 搜索求解快于 Alpha2Beta 搜索的问题 Fi g17 A problem pn2search solved faster thanαβ2search 513 Alp ha2Beta 搜索中的数据分析 程序记录了 Alp ha2Beta 搜索过程中每一层迭 代加深所得到的最佳值. 发现对于不同种类的问题 , 每类问题所得到的最佳值的变化存在着相似的模 式. 图 6～8 是最佳值随深度增加而变化的几种示 例. 某一深度的最佳值是在搜索到此深度所得到目 标棋块关键链的一阶和二阶气的评估. 值越小越有 利于吃子方 ,值越大越有利于逃脱方. 当目标被吃住 时值变为 0. 对于那些成功吃死的问题 ,最佳值可能会先有 所增加然后逐渐降为 0. 对于那些成功逃脱的问题 , 最佳值一般越来越大. 对于那些未能求解的问题 ,最 佳值在一定范围内徘徊. 需要进一步的研究这种模式是否可以帮助在结 果未知的情况下对结果进行预测. 对于实际的博弈 程序分配给某一问题的搜索时间通常非常有限 ,很 难进行全面的搜索. 如果这种预测可信 ,那么它将非 常实用. 514 p n 搜索中的数据分析 程序记录了 p n 搜索过程中根节点的 proof number 和 disproof number 的变化. 可以发现对于 每种类型的问题根节点的 proof number 和 disproof number 的变化也存在着一定的模式. 图 9 和 10 是 ·88 · 智 能 系 统 学 报 第 2 卷