第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 ] . 和中国象棋类似 ,国际象棋、五子棋、围棋等 ,都 存在明显的先行权 ,其中五子棋在没有禁手的规则 下是先行必胜的. 五子棋的禁手规则、围棋的贴目规 则等 ,就是用来消除先行权的 ,这类规则通常会给予 先后双方略微不同的限制. 至于中国象棋和国际象 棋 ,就棋类规则本身而言 ,先行权是无法消除的 ,然