第2卷第3期 智能系统学报 Vol.2 Ne 3 2007年6月 CAAI Transactions on Intelligent Systems Jun.2007 棋类游戏中的先行权 黄晨 (复旦大学化学系，上海200433) 摘要：通过对一些典型的棋类和球类游戏规则的考察，指出先行权问题在游戏规则中的重要作用，由先行权引发 的规则问题甚至导致了诸如六子棋这样全新的棋类游戏的产生.还结合奇偶层效应对先行权作了量化指出空着裁 剪的本质同其他基于AlpharBeta窗口的诸多裁剪算法是一致的，并阐述了诸多裁剪算法的作用被空着裁剪算法所 掩盖的原因 关键词：先行权；六子棋；计算机博弈；奇偶层效应；空着裁剪 中图分类号：TP18文献标识码：A文章编号：16734785(2007)03-0091-04 The first-move advantage in board ga mes HUANG Chen (Department of Chemistry,Fudan University,Shanghai 200433,China) Abstract:The importance of the first-move advantage in rules of board and ball games is presented in this article.Consideration of the first-move advantage in Connect-Five lead to the invention of a new board game,Connect-Six.The value of the first-move advantage can be calculated after studying the evemodd effect in computer gaming programs.Since the first-move advantage can be evaluated,the principle of null- move pruning is identical to other pruning algorithms based on an AlphaBeta window.This is the reason the functions of other pruning algorithms are concealed by null-move pruning in chess programs. Key words:first-move advantage;Connect-Six;computer games;evemodd effect;null-move pruning 象棋和围棋中有个术语叫“先手”，文中称为“先 着裁剪如此有效，而诸如Multi-ProbCut等著名算 行权”.不管是棋类游戏球类比赛还是在战场上，先 法在它面前却不值得一提，本文试图从先行权问题 手、球权、先发制人等术语都和主动权、优势联系起 中寻找答案 来.因此，对先行权的研究也就成了博弈、竞技和军 1先行权及其相关规则 事研究中的一个重要课题. 在棋界，先行权一直是棋类规则的重点讨论对 1.1棋类游戏 象，由此也引发出很多争论，诸如围棋先手应该贴几 棋类游戏的一大特点就是双方轮流下子，这样 目的问题.要解决由先行权引发的规则问题，首先要 就会有先走方保持优势的问题.以中国象棋为例，对 对先行权的本质有所了解，再对先行权作具体的量 大量棋局的统计表明，先胜、先和与先负的比例是 化，才能制定出一套合理的方案.通过对棋类规则的 37:37:26,这说明先行方是占明显优势的，即先行 改进，全新的棋类游戏就会孕育而生，“六子棋”就是 方胜率为56%（换算成El0等级分，先行方要高出 一个最典型的例子.人类自从20世纪中期计算机诞 40分)1. 生以来就希望它会下棋，可是计算机的博弈水平直 和中国象棋类似，国际象棋、五子棋、围棋等，都 到90年代“空着裁剪”提出以后才有大幅度的提高. 存在明显的先行权，其中五子棋在没有禁手的规则 到现在为止，空着裁剪仍旧是大多数中国象棋和国 下是先行必胜的.五子棋的禁手规则、围棋的贴目规 际象棋博弈程序所采用的唯一的裁剪算法.为何空 则等，就是用来消除先行权的，这类规则通常会给予 先后双方略微不同的限制.至于中国象棋和国际象 收稿日期：20060821. 棋，就棋类规则本身而言，先行权是无法消除的，然 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 2 卷第 3 期 智 能 系 统 学 报 Vol. 2 №. 3 2007 年 6 月 CAA I Transactions on Intelligent Systems J un. 2007 棋类游戏中的先行权 黄 晨 (复旦大学 化学系 ,上海 200433) 摘 要 :通过对一些典型的棋类和球类游戏规则的考察 ,指出先行权问题在游戏规则中的重要作用 ,由先行权引发 的规则问题甚至导致了诸如六子棋这样全新的棋类游戏的产生. 还结合奇偶层效应对先行权作了量化 ,指出空着裁 剪的本质同其他基于 Alpha2Beta 窗口的诸多裁剪算法是一致的 ,并阐述了诸多裁剪算法的作用被空着裁剪算法所 掩盖的原因. 关键词 :先行权 ;六子棋 ;计算机博弈 ;奇偶层效应 ;空着裁剪 中图分类号 : TP18 文献标识码 :A 文章编号 :167324785 (2007) 0320091204 The first2move advantage in board games HUAN G Chen (Department of Chemistry , Fudan University , Shanghai 200433 , China) Abstract :The importance of t he first - move advantage in rules of board and ball games is presented in this article. Consideration of the first2move advantage in Connect2Five lead to t he invention of a new board game , Connect2Six. The value of t he first2move advantage can be calculated after st udying t he even2odd effect in comp uter gaming p rograms. Since t he first2move advantage can be evaluated , the p rinciple of null2 move pruning is identical to other pruning algorit hms based on an Alp ha2Beta window. This is t he reason t he f unctions of ot her pruning algorit hms are concealed by null2move pruning in chess p rograms. Keywords :first2move advantage ; Connect2Six ; comp uter games; even2odd effect ; null2move pruning 收稿日期 :2006208221. 象棋和围棋中有个术语叫“先手”,文中称为“先 行权”. 不管是棋类游戏、球类比赛还是在战场上 ,先 手、球权、先发制人等术语都和主动权、优势联系起 来. 因此 ,对先行权的研究也就成了博弈、竞技和军 事研究中的一个重要课题. 在棋界 ,先行权一直是棋类规则的重点讨论对 象 ,由此也引发出很多争论 ,诸如围棋先手应该贴几 目的问题. 要解决由先行权引发的规则问题 ,首先要 对先行权的本质有所了解 ,再对先行权作具体的量 化 ,才能制定出一套合理的方案. 通过对棋类规则的 改进 ,全新的棋类游戏就会孕育而生“, 六子棋”就是 一个最典型的例子. 人类自从 20 世纪中期计算机诞 生以来就希望它会下棋 ,可是计算机的博弈水平直 到 90 年代“空着裁剪”提出以后才有大幅度的提高. 到现在为止 ,空着裁剪仍旧是大多数中国象棋和国 际象棋博弈程序所采用的唯一的裁剪算法. 为何空 着裁剪如此有效 ,而诸如 Multi2ProbCut 等著名算 法在它面前却不值得一提 ,本文试图从先行权问题 中寻找答案. 1 先行权及其相关规则 1. 1 棋类游戏 棋类游戏的一大特点就是双方轮流下子 ,这样 就会有先走方保持优势的问题. 以中国象棋为例 ,对 大量棋局的统计表明 ,先胜、先和与先负的比例是 37 ∶37 ∶26 ,这说明先行方是占明显优势的 ,即先行 方胜率为 56 % (换算成 Elo 等级分 ,先行方要高出 40 分) [1 ] . 和中国象棋类似 ,国际象棋、五子棋、围棋等 ,都 存在明显的先行权 ,其中五子棋在没有禁手的规则 下是先行必胜的. 五子棋的禁手规则、围棋的贴目规 则等 ,就是用来消除先行权的 ,这类规则通常会给予 先后双方略微不同的限制. 至于中国象棋和国际象 棋 ,就棋类规则本身而言 ,先行权是无法消除的 ,然
·92 智能系统学报 第2卷 而棋类以外的规则却有很大的灵活性，有学者建议 尽管如此，某些心理上的因素仍然会导致公平 给后手方更多些时间，也不失为一种可以尝试的做 性的失衡，一个典型的例子就是足球比赛中的互射 法 点球.在“一旦射失即将输掉比赛”的情况下，球员会 还有些棋类的规则看似怪异，实际上也是用来 承受巨大的心理压力，导致罚球命中率下降，所以一 消除先行权的，只是它对先后手给予同样的限制，使 般来说先罚球的一方在心理上稍占上风。 一方的先行权有所削弱.一个最典型的例子就是古 规则上比较完善的是网球的抢七局，为了避免 代围棋的“座子”，在4个星位分别放2个黑子和2 打成平局后总是由一方先发球，就采用先发一个球， 个白子（对角交错），然后再开始对弈.由于先行方采 此后一人连发2球的规则，这样就使得“一旦发球丢 用平行型布局要比交错型布局更有优势，因此开局 分就会输掉整盘”的情况轮流发生了 前硬是给定交错型布局，会很大程度上削弱先行方 1.3六子棋 优势.五子棋也可以对先后手方做同样的限制来削 六子棋在规则上只和五子棋上有2点差异，一 弱先行权，在日本有一种“提二子”的玩法，如果一步 是“连成六子得胜”，二是“每次连下2子”（黑方第一 棋能夹住对方（当且仅当）2个子，就可以把这2个 步只下一子).尽管规则非常简明，但直到2005年这 子提走.这样，很多先行方扩大优势的手段就被限制 个规则才有完整的官方记录（首先由新竹清华大学 了（如图1所示） 的吴毅成教授发表在2005年的ICGA会议上) 不管六子棋的诞生是否受了网球抢七局发球制 度的启发，但是“每次连下两子”的规则初衷显然是 消除双方的先行权优势—每方在落子前盘面上总 是比对方少一子，落子后总是多一个子2引 六子棋尽管规则简单，但“每次连下2子”给棋局 带来无穷变数，这两个子既可以都用来进攻（制造“活 图1提二子规则 ig.I NinukiRenju with a rule of sandwith Capturing 四)，又可以都用来防守（围堵“活四），也可以一个 子进攻、一个子防守（由“活三”制造“活四”，再去拦截 按照一般的五子棋规则（即便有禁手的情况下） 对手的“活三”.因此六子棋可能会取代围棋，成为世 走到白4都是先行方（黑方）必胜的，但在提二子规 界上规则最简单，但最难以驾御的一种棋。 则下，黑只能走A位（不是必胜点），否则被白走到 A位就可以提掉1、3二黑子了 2先行权问题在博弈程序中的体现 1.2从球类比赛中得到启发 2.1奇偶层效应 其实很多球类游戏也有先行权的问题，比如网 象棋程序通常会用到“迭代加深”(iterative 球、乒乓球是发球方占优势，排球、羽毛球则是接发 deepening)这个算法，即从n=l开始做深度为n的 球方占优势.换发球规则尽管形式不同（网球是每人 Alpha-Beta搜索，逐渐增加搜索深度n,直到程序用 发一局，乒乓球是每人发2球，都是轮流发球制：排 足计划好的时间为止.采用迭代加深算法有时会出 球和羽毛球都是由赢球方发球的每球得分制，早期 现一种很奇特的现象，例如使用象棋程序Elephant- 都是发球得分制)，但目的就是让双方具有同等的先 Eye的“棋子-位置数组)做简单的局面评价，在起 行权 始局面会得到如表1所示的结果 表1奇偶层效应 Table 1 Even-odd effect 深度分值 主要变例 累积节点数分枝因子 1 9马八进七 97 20马八进七马2进3 673 6.9 39马八进七马2进3马二进三 2029 3.0 40马八进比马2进3马二进三马8进7 8594 4.2 56马八进七马2进3马二进三马8进7车九进一 23711 2.8 61马八进七马2进3兵七进一马8进9马七进六炮8平5 73628 3.1 77马八进七马2进3车九进一炮2平1车九平四车1平2马二进一 290124 3.9 @1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
而棋类以外的规则却有很大的灵活性 ,有学者建议 给后手方更多些时间 ,也不失为一种可以尝试的做 法. 还有些棋类的规则看似怪异 ,实际上也是用来 消除先行权的 ,只是它对先后手给予同样的限制 ,使 一方的先行权有所削弱. 一个最典型的例子就是古 代围棋的“座子”,在 4 个星位分别放 2 个黑子和 2 个白子(对角交错) ,然后再开始对弈. 由于先行方采 用平行型布局要比交错型布局更有优势 ,因此开局 前硬是给定交错型布局 ,会很大程度上削弱先行方 优势. 五子棋也可以对先后手方做同样的限制来削 弱先行权 ,在日本有一种“提二子”的玩法 ,如果一步 棋能夹住对方(当且仅当) 2 个子 ,就可以把这 2 个 子提走. 这样 ,很多先行方扩大优势的手段就被限制 了(如图 1 所示) . 图 1 提二子规则 F ig. 1 Ninuki2Renju with a rule of sandwith Capturing 按照一般的五子棋规则(即便有禁手的情况下) 走到白 4 都是先行方 (黑方) 必胜的 ,但在提二子规 则下 ,黑只能走 A 位 (不是必胜点) ,否则被白走到 A 位 ,就可以提掉 1、3 二黑子了. 1. 2 从球类比赛中得到启发 其实很多球类游戏也有先行权的问题 ,比如网 球、乒乓球是发球方占优势 ,排球、羽毛球则是接发 球方占优势. 换发球规则尽管形式不同(网球是每人 发一局 ,乒乓球是每人发 2 球 ,都是轮流发球制 ;排 球和羽毛球都是由赢球方发球的每球得分制 ,早期 都是发球得分制) ,但目的就是让双方具有同等的先 行权. 尽管如此 ,某些心理上的因素仍然会导致公平 性的失衡 ,一个典型的例子就是足球比赛中的互射 点球. 在“一旦射失即将输掉比赛”的情况下 ,球员会 承受巨大的心理压力 ,导致罚球命中率下降 ,所以一 般来说先罚球的一方在心理上稍占上风. 规则上比较完善的是网球的抢七局 ,为了避免 打成平局后总是由一方先发球 ,就采用先发一个球 , 此后一人连发 2 球的规则 ,这样就使得“一旦发球丢 分就会输掉整盘”的情况轮流发生了. 1. 3 六子棋 六子棋在规则上只和五子棋上有 2 点差异 ,一 是“连成六子得胜”,二是“每次连下 2 子”(黑方第一 步只下一子) . 尽管规则非常简明 ,但直到 2005 年这 个规则才有完整的官方记录 (首先由新竹清华大学 的吴毅成教授发表在 2005 年的 ICGA 会议上) . 不管六子棋的诞生是否受了网球抢七局发球制 度的启发 ,但是“每次连下两子”的规则初衷显然是 消除双方的先行权优势 ———每方在落子前盘面上总 是比对方少一子 ,落子后总是多一个子[2 - 3 ] . 六子棋尽管规则简单 ,但“每次连下 2 子”给棋局 带来无穷变数 ,这两个子既可以都用来进攻(制造“活 四”) ,又可以都用来防守 (围堵“活四”) ,也可以一个 子进攻、一个子防守(由“活三”制造“活四”,再去拦截 对手的“活三”) . 因此六子棋可能会取代围棋 ,成为世 界上规则最简单 ,但最难以驾御的一种棋. 2 先行权问题在博弈程序中的体现 2. 1 奇偶层效应 象棋程序通常会用到“迭代加深”(iterative deepening) 这个算法 ,即从 n = 1 开始做深度为 n 的 Alp ha2Beta 搜索 ,逐渐增加搜索深度 n ,直到程序用 足计划好的时间为止. 采用迭代加深算法有时会出 现一种很奇特的现象 ,例如使用象棋程序 Elep hant2 Eye 的“棋子2位置数组”[4 ] 做简单的局面评价 ,在起 始局面会得到如表 1 所示的结果. 表 1 奇偶层效应 Table 1 Even2odd effect 深度 分值 主要变例 累积节点数 分枝因子 1 9 马八进七 97 2 0 马八进七 马 2 进 3 673 6. 9 3 9 马八进七 马 2 进 3 马二进三 2029 3. 0 4 0 马八进七 马 2 进 3 马二进三 马 8 进 7 8594 4. 2 5 6 马八进七 马 2 进 3 马二进三 马 8 进 7 车九进一 23711 2. 8 6 1 马八进七 马 2 进 3 兵七进一 马 8 进 9 马七进六 炮 8 平 5 73628 3. 1 7 7 马八进七 马 2 进 3 车九进一 炮 2 平 1 车九平四 车 1 平 2 马二进一 290124 3. 9 · 29 · 智 能 系 统 学 报 第 2 卷
第3期 黄晨：棋类游戏中的先行权 ·93· 续表1 深度分值 主要变例 累积节点数分枝因子 81马八进七马2进3马二进三马8进7兵七进一车9进1马七进六车9平4 999417 3.4 96马八进七马2进3马二进三马8进7兵七进一车9进1车九进一车9平4车九平四 2751341 2.8 101马八进比马8进9马二进三车9进1车九进一马2进3车九平四车9平4兵七进一车1进1119867464.4 当程序搜索奇数层时，先行方总比后行方多走 if (bWhite Turn) 一步，而当程序搜索偶数层时，先行方走的着数和后 return nWhite Value nBlack Value 行方一样多，因此奇数层的搜索分值总是比偶数层 else 略大.这种现象称为奇偶层效应 return nBlack Value-nWhite Value; 如果博弈程序运用了窗口搜索技术（如期望窗 口、PVS MTD(f)等)，那么搜索效率就会因奇偶层 为了消除奇偶层效应，可以在局面评价函数中 效应而降低.MTD(f)算法的创始人Plaat甚至建 增加了“先行权分值” 议，为克服奇偶层效应的影响，在迭代加深时把深度 define ADVANCED 3 步长改成2) int EvaluateAdjust (void){ 2.2先行权分值 return Evaluate()+ADVANCED: 既然奇偶层效应是由于先行权引起的，那么可 以考虑在局面评价函数上作先行权的调整，让奇偶 使用了调整后的局面评价函数，各层的分值、分 层的评价尽可能地接近.例如，表1的搜索结果，采 枝因子都会比较接近，而搜索的节点数则有明显的 用的局面评价函数是： 下降，可见搜索效率有了充分的提高，见表2. int Evaluate(void) 表2削弱的奇偶层效应 Table 2 Weakened everodd effect 深度分值 主要变例 累积节点数分枝因子 1 6 马八进七 97 2 3 马八进七马2进3 563 5.8 3 6 马八进七马2进3马二进三 2109 3.7 4 3 马八进七马2进3马二进三马8进7 7812 3.7 5 6 马八进七马2进3车九进一马8进7车九平四 18284 2.3 6 3 马八进七马2进3车九进一车1进1车九平四车1平4 59725 3.3 7 6 马八进七马2进3车九进一车1进1车九平四车1平4马二进三 190052 3.2 8 3 马八进七马2进3车九进一车1进1车九平四车1平4马二进三马8进7 596068 3.1 9 3马八进七马2进3车九进一车1进1车九平四车1平4马二进三马8进7车一进一2099191 3.5 103马八进七马2进3车九进一车1进1车九平四车1平4马二进三马8进7车一进一 5782475 2.8 每一着棋都会有一个价值，使局势朝有利于自 右1.随着棋局进入收官阶段，先行权分值锐减，收 己的方向发展，这个价值的一半就是先行权分值.然 到单官就是零了， 而，先行权分值并不是始终不变的，一般情况下，开 2.3空着裁剪 局的先行权分值最大随着棋局渐渐进入残局，先行 空着裁剪(null-move pruning)的思想是，假设 权分值会减小甚至丧失.中国象棋和国际象棋中还 对手连走2着，如果本方在浅层的搜索中仍旧具有 有“无等着”局面(Zugzwang),此时走任何一着棋都 良好表现（产生Beta截断），那么就不需要进行完全 会让自己的局势更糟，在这种情况下，先行权分值就 深度的搜索了.写成伪代码，就是： 相当于负值」 if (can do null()) 围棋的局势最容易被量化，布局和中盘阶段可 do null(); 认为先行权分值是5.5目（因为先手方贴目5.5 value =-search(-beta,1-beta,depth R-1); 目)，由此可认定平均每一着棋的价值在11目左 undo_null(); if (value >beta)f 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
续表 1 深度 分值 主要变例 累积节点数 分枝因子 8 1 马八进七 马 2 进 3 马二进三 马 8 进 7 兵七进一 车 9 进 1 马七进六 车 9 平 4 999417 3. 4 9 6 马八进七 马 2 进 3 马二进三 马 8 进 7 兵七进一 车 9 进 1 车九进一 车 9 平 4 车九平四 2751341 2. 8 10 1 马八进七 马 8 进 9 马二进三 车 9 进 1 车九进一 马 2 进 3 车九平四 车 9 平 4 兵七进一 车 1 进 1 11986746 4. 4 当程序搜索奇数层时 ,先行方总比后行方多走 一步 ,而当程序搜索偶数层时 ,先行方走的着数和后 行方一样多 ,因此奇数层的搜索分值总是比偶数层 略大. 这种现象称为奇偶层效应. 如果博弈程序运用了窗口搜索技术 (如期望窗 口、PVS、M TD (f) 等) ,那么搜索效率就会因奇偶层 效应而降低. M TD (f) 算法的创始人 Plaat 甚至建 议 ,为克服奇偶层效应的影响 ,在迭代加深时把深度 步长改成 2 [5 ] . 2. 2 先行权分值 既然奇偶层效应是由于先行权引起的 ,那么可 以考虑在局面评价函数上作先行权的调整 ,让奇偶 层的评价尽可能地接近. 例如 ,表 1 的搜索结果 ,采 用的局面评价函数是 : int Evaluate (void) { if (bWhiteTurn) { return nWhiteValue2nBlackValue ; } else { return nBlackValue2nWhiteValue ; } } 为了消除奇偶层效应 ,可以在局面评价函数中 增加了“先行权分值”: # define ADVANCED 3 int EvaluateAdjust (void) { return Evaluate () + ADVANCED ; } 使用了调整后的局面评价函数 ,各层的分值、分 枝因子都会比较接近 ,而搜索的节点数则有明显的 下降 ,可见搜索效率有了充分的提高 ,见表 2. 表 2 削弱的奇偶层效应 Table 2 Weakened even2odd effect 深度 分值 主要变例 累积节点数 分枝因子 1 6 马八进七 97 2 3 马八进七 马 2 进 3 563 5. 8 3 6 马八进七 马 2 进 3 马二进三 2109 3. 7 4 3 马八进七 马 2 进 3 马二进三 马 8 进 7 7812 3. 7 5 6 马八进七 马 2 进 3 车九进一 马 8 进 7 车九平四 18284 2. 3 6 3 马八进七 马 2 进 3 车九进一 车 1 进 1 车九平四 车 1 平 4 59725 3. 3 7 6 马八进七 马 2 进 3 车九进一 车 1 进 1 车九平四 车 1 平 4 马二进三 190052 3. 2 8 3 马八进七 马 2 进 3 车九进一 车 1 进 1 车九平四 车 1 平 4 马二进三 马 8 进 7 596068 3. 1 9 3 马八进七 马 2 进 3 车九进一 车 1 进 1 车九平四 车 1 平 4 马二进三 马 8 进 7 车一进一 2099191 3. 5 10 3 马八进七 马 2 进 3 车九进一 车 1 进 1 车九平四 车 1 平 4 马二进三 马 8 进 7 车一进一 5782475 2. 8 每一着棋都会有一个价值 ,使局势朝有利于自 己的方向发展 ,这个价值的一半就是先行权分值. 然 而 ,先行权分值并不是始终不变的 ,一般情况下 ,开 局的先行权分值最大 ,随着棋局渐渐进入残局 ,先行 权分值会减小甚至丧失. 中国象棋和国际象棋中还 有“无等着”局面(Zugzwang) ,此时走任何一着棋都 会让自己的局势更糟 ,在这种情况下 ,先行权分值就 相当于负值. 围棋的局势最容易被量化 ,布局和中盘阶段可 认为先行权分值是 5. 5 目 (因为先手方贴目 5. 5 目) ,由此可认定平均每一着棋的价值在 11 目左 右[6 ] . 随着棋局进入收官阶段 ,先行权分值锐减 ,收 到单官就是零了. 2. 3 空着裁剪 空着裁剪 ( null2move pruning) 的思想是 ,假设 对手连走 2 着 ,如果本方在浅层的搜索中仍旧具有 良好表现(产生 Beta 截断) ,那么就不需要进行完全 深度的搜索了. 写成伪代码 ,就是 : if (can_do_null() ) { do_null() ; value =2search (2beta ,12beta , depth2R21) ; undo_null() ; if (value > = beta) { 第 3 期 黄 晨 :棋类游戏中的先行权 · 39 ·
·94· 智能系统学报 第2卷 return value; value =eval()+MARGIN 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.net
return 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 卷