第3期 张培刚，等：使用不同的博弈树搜索算法解决计算机围棋的吃子问题 ·87 可以看成是与或树，有时可以看成是极大极小树，与 搜索到更深的深度.pn搜索及其变体未能解的问题 节点通常与极小节点是一样的，或节点通常与极大 是Alpha-Beta搜索未能解的问题的子集 节点是一样的 使用pn搜索及其变体的另外一个好处是它们 近年来出现的pn`df-pn和df-pn+等变体 不需要对候选着法的排序.这也会节省相当时间 使用哈希表存储中间结果.内存消耗可以减小到哈 结果发现那些没有解决的问题主要由于以下2 希表的大小 个原因： 对于非终止节点pn搜索和df-pn将proof 1)候选着法没有包括所有可能着法：正确着法 number和disproof number设为l.Df-pn+使用 缺失 评估函数h和cost来计算proof number和dis 2)解决此问题需要其他知识如连接和死活知 proof number.类似的也可以对pn搜索使用评估函 识 数来计算proof number和disproof number,可以称 这种算法为pn+ 5结果分析 对于pn+, 5.1算法比较 pn=E dn=(x5) 对于大多数问题，pn搜索及其变体比Alpha- Beta搜索效果好.大多数问题可以在1s内被解出， 对于df-pn+, pn搜索pn+、df-pn和df-pn+没有解出的6个 cost =0,h.pn=h dn =(x25) 问题是相同的问题，他们是Alpha-Beta搜索未能解 式中：E是节点评估值，pn是proof number,dn是 出的问题的子集.在所有解出的问题中，其中13个 disproof number 问题Alpha-Beta搜索比pn搜索效果好；29个问题 这里使用pn搜索pn+、df-pn和df-pn+解 pn搜索比Alpha-Beta搜索效果好；l3个问题pn搜 决吃子问题.候选着法产生和终止状态测试与A 索和Alpha-Beta搜索表现相当.从上表也可以看 pha-Beta搜索是一样的.算法中设定了访问的节 到，pn+表现比pn搜索好，df-pn+比df-pn表现 点总数和搜索时间来限定搜索.对于df-pn和df- 好.使用评估函数计算proof number和disproof pn+,一些候选着法产生但没有被访问，所以所访 number的算法，证明和否证根节点所访问的节点数 问的节点计数显得比pn搜索和pn+要少 比较少 这里使用Kano围棋系列的第3册中的吃子问 图3一5是在限定时间下各种算法的表现比较」 题来检测算法的效果.每一个问题的搜索时间被限 可以看到搜索时间如果限定在100ms,pn+的表现 制在200s内.表1包含了测试结果 最好 从图4和图5可以看到pn搜索及其变体有基 表1不同算法解决伯o系列第3册中吃子问题的结果 本相同的表现而且比Alpha-Beta搜索表现好 Table 1 Results of different algorithms to solve 5.2吃子问题分析 capturing problems in Kano book 3) Kano系列第3册中的61个吃子问题的搜索结 求解成 求解失 果为：49个问题成功吃死，6个问题成功逃脱，6个 算法 时间/ms节点数深度 功问题败问题 问题未成功求解 算法比较 ag6无置换表 52 9 5502 28746 5.6 一→a明无置换表-*-pt 明有置换表 53 8 2785 13187 5.8 一a卵有置换表*dfpm 40 -*-pn *“df-p时 pn 55 6 2148 18607 7.2 35 pn+ 55 6 1303 10931 7.0 301 -4 df-pn 55 6 2259 5792 7.4 2 df-pn+ 55 6 16482175 6.7 30 10 表1中，时间是求解问题所用平均时间(ms); 节点数是求解问题所访问平均节点数：深度是平均 102030405060708090100 深度 时间/ms pn搜索及其变体比Alpha-Beta搜索解出了更 图3所解问题数(100ms内限制) 多的问题、花费了更少的时间、访问了更少的节点和 Fig 3 Problems solved within 100 milliseconds 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net可以看成是与或树 ,有时可以看成是极大极小树 ,与 节点通常与极小节点是一样的 ,或节点通常与极大 节点是一样的. 近年来出现的 p n 3 、df - p n 和 df - p n + 等变体 使用哈希表存储中间结果. 内存消耗可以减小到哈 希表的大小. 对于非终止节点 p n 搜索和 df - p n 将 proof number 和 disproof number 设为 1. Df - p n + 使用 评估函数 h 和 cost 来计算 proof number 和 dis2 proof number. 类似的也可以对 p n 搜索使用评估函 数来计算 p roof number 和 disproof number ,可以称 这种算法为 p n + . 对于 p n + , p n = E 2 ,dn = ( 1 E ×25) 2 . 对于 df - p n + , cost = 0 , h. p n = E 2 , h. dn = ( 1 E ×25) 2 . 式中 : E 是节点评估值 , p n 是 proof number , dn 是 disproof number. 这里使用 p n 搜索、p n + 、df - p n 和 df - p n + 解 决吃子问题. 候选着法产生和终止状态测试与 Al2 p ha - Beta 搜索是一样的. 算法中设定了访问的节 点总数和搜索时间来限定搜索. 对于 df - p n 和 df - p n + ,一些候选着法产生但没有被访问 ,所以所访 问的节点计数显得比 p n 搜索和 p n + 要少. 这里使用 Kano 围棋系列的第 3 册中的吃子问 题来检测算法的效果. 每一个问题的搜索时间被限 制在 200 s 内. 表 1 包含了测试结果. 表 1 不同算法解决 Kano 系列第 3 册中吃子问题的结果 Table 1 Results of different algorithms to solve capturing problems in Kano book 3) 算法 求解成 功问题 求解失 败问题 时间/ ms 节点数 深度 αβ无置换表 52 9 5 502 28 746 516 αβ有置换表 53 8 2 785 13 187 518 pn 55 6 2 148 18 607 712 pn + 55 6 1 303 10 931 710 df - pn 55 6 2 259 5 792 714 df - pn + 55 6 1 648 2 175 617 表 1 中 ,时间是求解问题所用平均时间 (ms) ; 节点数是求解问题所访问平均节点数 ;深度是平均 深度. p n 搜索及其变体比 Alp ha2Beta 搜索解出了更 多的问题、花费了更少的时间、访问了更少的节点和 搜索到更深的深度. p n 搜索及其变体未能解的问题 是 Alp ha2Beta 搜索未能解的问题的子集. 使用 p n 搜索及其变体的另外一个好处是它们 不需要对候选着法的排序. 这也会节省相当时间. 结果发现那些没有解决的问题主要由于以下 2 个原因 : 1) 候选着法没有包括所有可能着法 :正确着法 缺失. 2) 解决此问题需要其他知识如连接和死活知 识. 5 结果分析 511 算法比较 对于大多数问题 ,p n 搜索及其变体比 Alp ha2 Beta 搜索效果好. 大多数问题可以在 1 s 内被解出. p n 搜索、p n + 、df - p n 和 df - p n + 没有解出的 6 个 问题是相同的问题 ,他们是 Alp ha2Beta 搜索未能解 出的问题的子集. 在所有解出的问题中 ,其中 13 个 问题 Alp ha2Beta 搜索比 p n 搜索效果好 ;29 个问题 p n 搜索比 Alp ha2Beta 搜索效果好 ;13 个问题 p n 搜 索和 Alp ha2Beta 搜索表现相当. 从上表也可以看 到 ,p n + 表现比 p n 搜索好 ,df - p n + 比 df - p n 表现 好. 使用评估函数计算 proof number 和 disproof number 的算法 ,证明和否证根节点所访问的节点数 比较少. 图 3～5 是在限定时间下各种算法的表现比较. 可以看到搜索时间如果限定在 100 ms ,p n + 的表现 最好. 图 3 所解问题数(100 ms 内限制) Fig13 Problems solved within 100 milliseconds 从图 4 和图 5 可以看到 p n 搜索及其变体有基 本相同的表现而且比 Alp ha2Beta 搜索表现好. 512 吃子问题分析 Kano 系列第 3 册中的 61 个吃子问题的搜索结 果为 :49 个问题成功吃死 ,6 个问题成功逃脱 ,6 个 问题未成功求解. 第 3 期 张培刚 ,等 :使用不同的博弈树搜索算法解决计算机围棋的吃子问题 ·87 ·