·94· 智能系统学报 第2卷 return value; value =eval()+MARGIN if (value <=alpha){ countinue; 空着裁剪由Donninger在1993年首次发表以 }//Alpha型裁剪，低过边界则跳过搜索 后1，就一直被绝大多数的国际象棋和中国象棋程 序所采用，但也因此带来了其他问题有些基于 3结束语 Alpha-Beta窗口的传统裁剪算法，如无效裁剪(fur tility pruning))、剃刀裁剪(razoring)、multi-probcut 面对由先行权引出的诸多问题，仅仅就事论事 等算法都失效了.看来观察以下的裁剪算法： 是远远不够的.就以六子棋来说，尽管它的初衷是消 define MARGIN 6 除五子棋中明显的先行权优势，然而它自诞生之日 if (can_do_razor()){ 起就成为一种全新的棋类游戏，其丰富的战略战术 value search beta MARGIN 1,beta MARGIN, 思想跟其他棋类迥然不同，也不是一个先行权问题 depth R)-MAR GIN; 所能够解决的. if (value>=beta){ “先手”在棋类游戏中占有重要的地位，但先手 return value; 不是目的而是手段，只有擒王（对于象棋来说）和争 }//Beta型裁剪，高过边界则直接返回 夺地盘（对于围棋来说）才是目的.所以，本文对先行 权的研究只是一个开端，对于博弈理论来说，如何把 这是一个Beta型的剃刀裁剪算法，它和前面空 着裁剪的伪代码有些相似.根据先前介绍的先行权 先行权化为真正的优势，才是需要进一步研究的课 题 分值的概念，用了“do null()”函数以后，就相当对 手争取到了2倍的先行权分值，因此以上2段代码 参考文献： 中加粗的部分，有异曲同工之妙 [1]黄晨.ELO等级分计算公式详解[W].2004 当然，在搜索到的大多数局面下，先行权分值都 [2]台湾交通大学资讯工程系.六子棋首页[W].2005. 会非常大（如果对手正在捉吃一个车，那么先行权分 [3]WuC.Connect6[J].ICGA J,2009,29(4):234-241. 值就会高达一个车的分数，比如说200分)，所以空 [4]黄晨.中国象棋对弈程序Elephant Eye[W].2006. 着裁剪在大多数情况下都是安全的 [5]PLATT A.MTD(f)-A Minimax Algorithm faster than 而对于无效裁剪和剃刀裁剪来说，2倍于先行 NegaScout [W].1997 权分值的边界实在太不安全了，因此实际使用时不 [6]陈志行.电脑围棋小洞天[M].广州：中山大学出版社， 得不把边界大幅度提高（比如说从代码中的6提高 2001. 到100，即一个马或炮的价值).因此无效裁剪和剃 [7]DONN IN GER C.Null move and deep search:selective 刀裁剪跟空着裁剪同时使用时，效果就会被空着裁 search heuristics for obtuse chess programs[J ]ICGA J, 剪完全淹没 1993,16(3):137-143. [8]HEINZ EA.AEL pruning[J ]ICGA J,2000,23(1):21 国际象棋程序Dark Thought的作者Heiz曾 -32 经把这3种裁剪混合在一起应用，称为AEL算法. 作者简介： 在这种算法中，无效裁剪和剃刀裁剪都是Alpha型 黄晨，男，1981年生，硕士研究生， 的，这才使得它们发挥在空着裁剪所不能管辖的 主要研究方向为量子化学计算理论和应 Alpha结点上（到目前为止，空着裁剪都是Beta型 用的研究，业余从事中国象棋的计算机 的)，在程序中起到非常有限的效果] 博弈理论研究 define MARGIN 50 Email:webmaster elephantbase. if (can do razor()&&depth==R) net. 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.netreturn value ; } } 空着裁剪由 Donninger 在 1993 年首次发表以 后[7 ] ,就一直被绝大多数的国际象棋和中国象棋程 序所采用 ,但也因此带来了其他问题 ———有些基于 Alp ha2Beta 窗口的传统裁剪算法 ,如无效裁剪 (f u2 tility pruning) 、剃刀裁剪 (razoring) 、multi2probcut 等算法都失效了. 看来观察以下的裁剪算法 : # define MARGIN 6 if (can_do_razor () ) { value = search ( beta + MARGIN - 1 , beta + MARGIN , depth2R)2MARGIN ; if (value > = beta) { return value ; } / / Beta 型裁剪 ,高过边界则直接返回 } 这是一个 Beta 型的剃刀裁剪算法 ,它和前面空 着裁剪的伪代码有些相似. 根据先前介绍的先行权 分值的概念 ,用了“do_ null () ”函数以后 ,就相当对 手争取到了 2 倍的先行权分值 ,因此以上 2 段代码 中加粗的部分 ,有异曲同工之妙. 当然 ,在搜索到的大多数局面下 ,先行权分值都 会非常大(如果对手正在捉吃一个车 ,那么先行权分 值就会高达一个车的分数 ,比如说 200 分) ,所以空 着裁剪在大多数情况下都是安全的. 而对于无效裁剪和剃刀裁剪来说 ,2 倍于先行 权分值的边界实在太不安全了 ,因此实际使用时不 得不把边界大幅度提高 (比如说从代码中的 6 提高 到 100 ,即一个马或炮的价值) . 因此无效裁剪和剃 刀裁剪跟空着裁剪同时使用时 ,效果就会被空着裁 剪完全淹没. 国际象棋程序 Dark Thought 的作者 Heinz 曾 经把这 3 种裁剪混合在一起应用 ,称为 A EL 算法. 在这种算法中 ,无效裁剪和剃刀裁剪都是 Alp ha 型 的 ,这才使得它们发挥在空着裁剪所不能管辖的 Alp ha 结点上 (到目前为止 ,空着裁剪都是 Beta 型 的) ,在程序中起到非常有限的效果[8 ] . # define MARGIN 50 if (can_do_razor () & & depth = = R) { value = eval() + MARGIN ; if (value < = alpha) { countinue ; } / / Alpha 型裁剪 ,低过边界则跳过搜索 } 3 结束语 面对由先行权引出的诸多问题 ,仅仅就事论事 是远远不够的. 就以六子棋来说 ,尽管它的初衷是消 除五子棋中明显的先行权优势 ,然而它自诞生之日 起就成为一种全新的棋类游戏 ,其丰富的战略战术 思想跟其他棋类迥然不同 ,也不是一个先行权问题 所能够解决的. “先手”在棋类游戏中占有重要的地位 ,但先手 不是目的而是手段 ,只有擒王 (对于象棋来说) 和争 夺地盘(对于围棋来说) 才是目的. 所以 ,本文对先行 权的研究只是一个开端 ,对于博弈理论来说 ,如何把 先行权化为真正的优势 ,才是需要进一步研究的课 题. 参考文献 : [1 ]黄 晨. ELO 等级分计算公式详解[ W]. 2004. [2 ]台湾交通大学资讯工程系. 六子棋首页[ W]. 2005. [3 ]Wu IC. Connect 6[J ]. ICGA J ,2009 ,29 (4) :2342241. [4 ]黄 晨. 中国象棋对弈程序 Elephant Eye[ W]. 2006. [5 ] PLA TT A. MTD (f)2A Minimax Algorithm faster than NegaScout[ W]. 1997. [6 ]陈志行. 电脑围棋小洞天[ M ]. 广州 :中山大学出版社 , 2001. [7 ]DONNIN GER C. Null move and deep search : selective search heuristics for obtuse chess programs[J ]. ICGA J , 1993 ,16 (3) :137 - 143. [ 8 ] HEINZ E A. A EL pruning[J ]. ICGA J , 2000 ,23 (1) :21 - 32. 作者简介 : 黄 晨 ,男 ,1981 年生 ,硕士研究生 , 主要研究方向为量子化学计算理论和应 用的研究 ,业余从事中国象棋的计算机 博弈理论研究. E2mail : webmaster @ elephantbase. net. · 49 · 智 能 系 统 学 报 第 2 卷