第2卷第1期 智能系统学报 Vol.2№1 2007年2月 CAAI Transactions on Intelligent Systems Fcb.2007 中国象棋计算机博弈开局库研究与设计 魏钦刚，王骄，徐心和，南晓斐 (东北大学人工智能与机器人研究所，辽宁沈阳110004) 摘要：开局库是一种为了增强计算机的博弈水平而必不可少的辅助手段，开局阶段的着法采用查询数据库的方式 生成，从而避免耗时的搜索、评估和出现战略性错误.研究了中国象棋机器博弈系统中应用开局库的一些技术问题 介绍了开局库的计算机自动生成方法，对统计开局库作了详细的探讨和论述，提出了理想开局库的设计思想以及开 局库评估系统的必要性 关键词：计算机博弈；开局库；统计开局库；理想开局库 中图分类号：TP18文献标识码：A文章编号：1673-4785(2007)01-008505 A study and design of opening book of computer Chinese Chess WEI Qin-gang,WAN G Jiao,XU Xim he,NAN Xiao-fei (Institute of Artificial Intelligence and Robotics,Northeastern University,Shenyang 110004,China) Abstract:The opening-book is a necessary assistant method for improving the game performance and avoi- ding expensive search and evaluation functions,and some tactic mistakes in the beginning period.In this paper,some relative technologies about opening book in Chinese computer chess game system are dis- cussed.First,the method of automatically creating an opening book are introduced.Then,the design and implementation of statistical openingbook is discussed in details.At last,the idea of designing the desired opening book and the necessity of evaluation system to opening-book are put forward. Key words:Cmputer Cchess game;opening-book;statistical opening book;desired opening-book 中国象棋历史悠久，魅力无穷.整个博弈过程是 还会选择一些冷门开局，使局面很快“脱谱”，迅速进 双方各占棋盘的一半地盘开始进行对弈，分为开局、入到中、残局.所以中国象棋开局阶段是整个对弈过 中局、残局3个阶段，将对方的“老将”（王）“将死”为 程中变化最多的阶段，开局的好坏对之后的中、残局 止.中国象棋棋有“蹩马腿”等独特的规则限制，因此 意义重大 开局阶段注重的是大子的出动速度，抢占重要位置， 研究中国象棋的机器博奔系统，开局阶段是个 以争取主动」 重点.首先，开局变化多，且各个局面相对来说没有 中国象棋开局类型多样，一般先走的红方多采 明显的优劣差异，因此如果用搜索和评估选择开局 用进攻型开局，分为急攻、缓攻等，黑方多采用防守 着法的话，那么计算机所选择的着法常常贻笑大方 型开局，分为积极防御、消极防御等 另外，开局阶段是棋手排兵布阵、施行战略的基础， 中国象棋的开局变化极多，每一种着法都能产 而计算机一般只按照一些子力评估的分值进行选 生出一些新的变化.单就中炮开局就有中炮对屏风 择，很可能盲目地抢先，造成其后的失利.所以，为了 马、中炮对反宫马、中炮对左3步虎等数十种变化. 解决这个问题，必须认真借鉴各种经典的和成熟的 其各个开局又都有自身的变化.这些开局都遵循开 开局着法，设计开发博弈系统的开局库，应用开局战 局的规律：“明车”即车路要通：“活马”即马与兵阵的 术 配合合理，使马能有活动的空间；“好炮位”，即炮要 占住子力疏密适中的要点，封锁对方进攻路线，配合 1开局库的重要性 其他子力展开进攻】.另外当进行快棋赛时，棋手 开局库顾名思义是存储着开局着法的数据库」 收稿日期：20060821. 在对弈的开局阶段，系统不用调用搜索引擎进行搜 1994-2009 China Academic Joumnal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 2 卷第 1 期 智 能 系 统 学 报 Vol. 2 №. 1 2007 年 2 月 CAA I Transactions on Intelligent Systems Feb. 2007 中国象棋计算机博弈开局库研究与设计 魏钦刚 ,王 骄 ,徐心和 ,南晓斐 (东北大学 人工智能与机器人研究所 ,辽宁 沈阳 110004) 摘 要 :开局库是一种为了增强计算机的博弈水平而必不可少的辅助手段 ,开局阶段的着法采用查询数据库的方式 生成 ,从而避免耗时的搜索、评估和出现战略性错误. 研究了中国象棋机器博弈系统中应用开局库的一些技术问题. 介绍了开局库的计算机自动生成方法 ,对统计开局库作了详细的探讨和论述 ,提出了理想开局库的设计思想以及开 局库评估系统的必要性. 关键词 :计算机博弈 ;开局库 ;统计开局库 ;理想开局库 中图分类号 : TP18 文献标识码 :A 文章编号 :167324785 (2007) 0120085205 A study and design of opening2book of computer Chinese Chess WEI Qin2gang , WAN G Jiao , XU Xin2he , NAN Xiao2fei (Institute of Artificial Intelligence and Robotics , Northeastern University , Shenyang 110004 , China) Abstract :The opening2book is a necessary assistant met hod for improving t he game performance and avoi2 ding expensive search and evaluation f unctions , and some tactic mistakes in t he beginning period. In this paper , some relative technologies about opening2book in Chinese comp uter chess game system are dis2 cussed. First , t he met hod of automatically creating an opening2book are introduced. Then , t he design and implementation of statistical opening2book is discussed in details. At last , the idea of designing the desired opening2book and t he necessity of evaluation system to opening2book are p ut forward. Keywords :Cmp uter Cchess game ;opening2book ;statistical opening2book ;desired opening2book 收稿日期 :2006208221. 中国象棋历史悠久 ,魅力无穷. 整个博弈过程是 双方各占棋盘的一半地盘开始进行对弈 ,分为开局、 中局、残局 3 个阶段 ,将对方的“老将”(王)“将死”为 止. 中国象棋棋有“蹩马腿”等独特的规则限制 ,因此 开局阶段注重的是大子的出动速度 ,抢占重要位置 , 以争取主动. 中国象棋开局类型多样 ,一般先走的红方多采 用进攻型开局 ,分为急攻、缓攻等 ,黑方多采用防守 型开局 ,分为积极防御、消极防御等[1 ] . 中国象棋的开局变化极多 ,每一种着法都能产 生出一些新的变化. 单就中炮开局就有中炮对屏风 马、中炮对反宫马、中炮对左 3 步虎等数十种变化. 其各个开局又都有自身的变化. 这些开局都遵循开 局的规律“: 明车”即车路要通“; 活马”即马与兵阵的 配合合理 ,使马能有活动的空间 “; 好炮位”,即炮要 占住子力疏密适中的要点 ,封锁对方进攻路线 ,配合 其他子力展开进攻[1 - 2 ] . 另外当进行快棋赛时 ,棋手 还会选择一些冷门开局 ,使局面很快“脱谱”,迅速进 入到中、残局. 所以中国象棋开局阶段是整个对弈过 程中变化最多的阶段 ,开局的好坏对之后的中、残局 意义重大. 研究中国象棋的机器博弈系统 ,开局阶段是个 重点. 首先 ,开局变化多 ,且各个局面相对来说没有 明显的优劣差异. 因此如果用搜索和评估选择开局 着法的话 ,那么计算机所选择的着法常常贻笑大方. 另外 ,开局阶段是棋手排兵布阵、施行战略的基础 , 而计算机一般只按照一些子力评估的分值进行选 择 ,很可能盲目地抢先 ,造成其后的失利. 所以 ,为了 解决这个问题 ,必须认真借鉴各种经典的和成熟的 开局着法 ,设计开发博弈系统的开局库 ,应用开局战 术. 1 开局库的重要性 开局库顾名思义是存储着开局着法的数据库. 在对弈的开局阶段 ,系统不用调用搜索引擎进行搜
·86 智能系统学报 第2卷 索，而从开局库内搜索着法.这对于整个博弈系统来 说有3点好处：1)防止战略性错误：2)形成较为稳妥 2 开局库的计算机自动生成 和有利的局面；3)节省了大量的搜索时间 由计算机自动生成开局库是国际象棋系统很早 利用一个对局来说明这3点.现用安装在配置 就研究出来的一种生成开局库的方法.其原理是将 相同的计算机上采用相同搜索引擎的2个博弈系 所有的局面视为存在于博弈树3上的分枝，生成 统进行对弈，其中红方使用开局库，黑方不使用开局 开局库时从“树根”即根节点开始向下展开，通过某 库，记录数据如表】所示 种计算选择出若干个路径进行扩展，从而将开局阶 表1使用与不使用开局库对弈结果 段的着法全部录入开局库内.根据计算扩展路径的 Tible 1 The result of comparing useopening book with nonuse 方式可分为2种主要的方法3」，一是最优扩展方 回合红方若法红方用时/s黑方着法黑方用时/$ 式，一是脱谱扩展方式 炮八平五 0.01 马2进3 113.33 2.1最优扩展法的基本原理 2 马八进七 0.01 车1平2 1.02 已经知道所有着法都连在博弈树的节点上，要 3 车九平八 0.01 马8进7 4.06 生成一个完善的开局库就需将“树”上那些的令人满 兵七进一 0.01 炮8平9 43.12 意枝干上的节点写入开局库.然而一个节点下会有 5 炮二平四 41.02 车9平8 17.57 很多个子节点.扩展开局库，要做的就是判断选取哪 6 马二进三 1.02 车8进5 13.00 一个子节点.最优扩展法就是一种根据局面优劣来 个 车八进五 50.46 卒7进1 1.02 判断是否扩展的方法，这种方式需要给每一个节点 车一进一 39.10 炮2平1 39.05 上附加一个优先值，以表示该着法的优劣.根据评估 9 车八进五 1.02 马3退2 1.02 算法对局面的评价给各个节点的优先值赋值，然后 10 象七进九 6.53 车2平4 37.58 就能够由优先值的大小来判断是否扩展了.优先值 越大则扩展的可能性就越大.扩展方式可以选择阈 从表1可以看出使用开局库的耗时明显小于不 值扩展，即优先值达到某一阈值时就进行扩展；也可 使用开局库的耗时.此时棋盘情况如图1所示。 以选择固定数目扩展，即按照优先值大小向下扩展 固定数目的节点 2.2脱谱扩展法的基本原理 最优扩展方式的优先值是根据对当前局面的评 估来计算的，还不能完全表明着法的实际效果.脱谱 扩展法(drop-out expansion)便是对最优扩展法进 行改进而产生的.国际象棋多数软件的开局库就是 兵)（兵） 采用这种方式制作的，例如国际象棋程序Othello 相 马) 大炮炮马) (奥赛罗)]和A mazo ns!等 车 纯在相 对于某一叶子节点，其优劣性不能直接看出来 因为即使当前局面令计算机满意，可是继续向下的 图1测试后局面 情况就有可能失去控制；当前不太占优的局面也许 Fig.I The picture of testing 后续着法会是相当好的.所以根据后续结果来对叶 此局为五六炮对屏风马局，红方子力紧密防守 子节点做出判断就有更大的说服力.脱谱扩展法的 积极，进攻稳健，形势较好；黑方子力松散，双炮力量 基本思想是给叶子节点制定一个表，按照搜索与评 不大，只有一过河车对红方的进攻造成了一些影响. 估相结合的方法来判断后续着法的情况，当达到要 以后红方补士，黑方反架中炮跳马呈反宫马，但黑方 求层数时，对搜索到的后续着法进行评估.通过这种 出子速度已经赶不上红方，红方占优.红方从第5回 方式来给先前叶子节点一个较合理的优先值，然后 合开始脱谱，以后转为搜索引擎进行搜索 选择一个优先值较高的路径进行扩展 开局库在开局阶段为中后局节省了大量时间 3统计开局库的设计与使用 并且着法与人类棋手类似，前4回合过后形成了“明 车、活马、好炮位”的优势局面.而未使用开局库的黑 除了计算机自动生成开局库方式以外，还有一 方局面有些未尽人意.另外黑方不能像人类棋手一 种生成开局库的方式就是从以往人类或计算机对局 样全面考虑局面，所走着法在开局库中找不到，这也 棋谱中提取开局着法.通过这种方式生成的开局库 是红方过早脱谱的原因 称作“统计开局库”.顾名思义，就是对以往棋谱通过 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.ne
索 ,而从开局库内搜索着法. 这对于整个博弈系统来 说有 3 点好处 :1) 防止战略性错误 ;2) 形成较为稳妥 和有利的局面 ;3) 节省了大量的搜索时间. 利用一个对局来说明这 3 点. 现用安装在配置 相同的计算机上、采用相同搜索引擎的 2 个博弈系 统进行对弈 ,其中红方使用开局库 ,黑方不使用开局 库 ,记录数据如表 1 所示. 表 1 使用与不使用开局库对弈结果 Table 1 The result of comparing use2opening2book with nonuse 回合 红方着法 红方用时/ s 黑方着法 黑方用时/ s 1 炮八平五 0. 01 马 2 进 3 113. 33 2 马八进七 0. 01 车 1 平 2 1. 02 3 车九平八 0. 01 马 8 进 7 4. 06 4 兵七进一 0. 01 炮 8 平 9 43. 12 5 炮二平四 41. 02 车 9 平 8 17. 57 6 马二进三 1. 02 车 8 进 5 13. 00 7 车八进五 50. 46 卒 7 进 1 1. 02 8 车一进一 39. 10 炮 2 平 1 39. 05 9 车八进五 1. 02 马 3 退 2 1. 02 10 象七进九 6. 53 车 2 平 4 37. 58 从表 1 可以看出使用开局库的耗时明显小于不 使用开局库的耗时. 此时棋盘情况如图 1 所示. 图 1 测试后局面 Fig. 1 The picture of testing 此局为五六炮对屏风马局 ,红方子力紧密 ,防守 积极 ,进攻稳健 ,形势较好 ;黑方子力松散 ,双炮力量 不大 ,只有一过河车对红方的进攻造成了一些影响. 以后红方补士 ,黑方反架中炮跳马呈反宫马 ,但黑方 出子速度已经赶不上红方 ,红方占优. 红方从第 5 回 合开始脱谱 ,以后转为搜索引擎进行搜索. 开局库在开局阶段为中后局节省了大量时间. 并且着法与人类棋手类似 ,前 4 回合过后形成了“明 车、活马、好炮位”的优势局面. 而未使用开局库的黑 方局面有些未尽人意. 另外黑方不能像人类棋手一 样全面考虑局面 ,所走着法在开局库中找不到 ,这也 是红方过早脱谱的原因. 2 开局库的计算机自动生成 由计算机自动生成开局库是国际象棋系统很早 就研究出来的一种生成开局库的方法. 其原理是将 所有的局面视为存在于博弈树[3 - 5 ] 上的分枝 ,生成 开局库时从“树根”即根节点开始向下展开 ,通过某 种计算选择出若干个路径进行扩展 ,从而将开局阶 段的着法全部录入开局库内. 根据计算扩展路径的 方式可分为 2 种主要的方法[3 - 4 ] ,一是最优扩展方 式 ,一是脱谱扩展方式. 2. 1 最优扩展法的基本原理 已经知道所有着法都连在博弈树的节点上 ,要 生成一个完善的开局库就需将“树”上那些的令人满 意枝干上的节点写入开局库. 然而一个节点下会有 很多个子节点. 扩展开局库 ,要做的就是判断选取哪 一个子节点. 最优扩展法就是一种根据局面优劣来 判断是否扩展的方法. 这种方式需要给每一个节点 上附加一个优先值 ,以表示该着法的优劣. 根据评估 算法对局面的评价给各个节点的优先值赋值 ,然后 就能够由优先值的大小来判断是否扩展了. 优先值 越大则扩展的可能性就越大. 扩展方式可以选择阈 值扩展 ,即优先值达到某一阈值时就进行扩展 ;也可 以选择固定数目扩展 ,即按照优先值大小向下扩展 固定数目的节点. 2. 2 脱谱扩展法的基本原理 最优扩展方式的优先值是根据对当前局面的评 估来计算的 ,还不能完全表明着法的实际效果. 脱谱 扩展法 ( drop2out expansion) 便是对最优扩展法进 行改进而产生的. 国际象棋多数软件的开局库就是 采用这种方式制作的 ,例如国际象棋程序 Ot hello (奥赛罗) [3 ]和 Amazons [4 ]等. 对于某一叶子节点 ,其优劣性不能直接看出来 , 因为即使当前局面令计算机满意 ,可是继续向下的 情况就有可能失去控制 ;当前不太占优的局面也许 后续着法会是相当好的. 所以根据后续结果来对叶 子节点做出判断就有更大的说服力. 脱谱扩展法的 基本思想是给叶子节点制定一个表 ,按照搜索与评 估相结合的方法来判断后续着法的情况 ,当达到要 求层数时 ,对搜索到的后续着法进行评估. 通过这种 方式来给先前叶子节点一个较合理的优先值 ,然后 选择一个优先值较高的路径进行扩展. 3 统计开局库的设计与使用 除了计算机自动生成开局库方式以外 ,还有一 种生成开局库的方式就是从以往人类或计算机对局 棋谱中提取开局着法. 通过这种方式生成的开局库 称作“统计开局库”. 顾名思义 ,就是对以往棋谱通过 ·86 · 智 能 系 统 学 报 第 2 卷
第1期 魏钦刚，等：中国象棋计算机博弈开局库研究与设计 ·87· 统计计算提取着法形成的开局库.下面将对统计开 ×10 局库的一些问题做详细论述 39 3.1统计方式设计 现在很多棋谱都提供了与对局相关的很多信 K 息，这样就有了统计所需的样本.与局面优劣相关的 27 信息总的来说有如下几点： 1)一个着法所走过的次数.次数越多，这个着法 25 就可能越好 0 1020304050607080 2)棋手的棋力.特级大师的着法肯定会比普通 胜率% 棋手的着法好 3)下棋的时间.最近的着法一般会比以前的着 图3胜率与开局库节点数关系示意图 Fig.3 The relation between the wimrate and 法好 the note-number 4)对局结果.赢棋方的着法可能会更好 5)通过人为注释棋谱优劣，判断棋谱优劣 授为棋类搜索发明的算法，被称为“Zobrist哈希技 从以上信息在某种程度上可以判断出着法的优 术”，其数据结构称为“哈希表”.此算法的思想是创 劣，其中第1)、4)、5)条更有说服力.具体统计过程 建一个hash[chessman][location]的数组，数组中 如图2所示 每一个元素都是一个64位随机数.对中国象棋来 说，就是hash[14][90].求当前局面的哈希值，就是 开始 将棋盘上所有棋子在数组中对应的64位数做异或 将棋谱按步读入并等待处理 运算，生成这一局面的唯一标识数哈希技术有2个 明显的优点：1)64位数使得局面冲突的可能性非常 将着法按照局面哈希值排列 小，基本可以唯一标识当前局面，可以用作哈希表的 按哈希值顺序统计各着法的 索引；2)不用每一次展开节点时都计算局面的哈希值」 胜负及使用频率 只要在搜索开始时做初始化运算，在着法执行过程中 通过异或运算求出变动的棋子及其位置即可， 将符合条件的着法录入开局库 开局库数据结构定义如下： 结束 typedef struct Hash position; /164位哈希值 图2着法统计流程图 int statu-played; //32位局面权值 Fig.2 The flow chart of the moves statistic BOOK_KEY; 其实不必将所有的局面全部录入开局库内，只 此结构包含了一个着法的信息.开局库即为若 需要选择一些比较好的着法.这同样也是根据统计 干该种数据组成.Hash position为局面的哈希值 信息实现的.定义变量WinCount表示一个着法赢 共64位，将局面按“簇”存储，根据哈希值的高15位 过的次数，定义变量LossCount表示这个着法输过 值将局面分为若干簇，簇数量为25个，所以哈希值 的盘数，为胜率，作为阈值，根据阈值来决定是否将 的高15位可作为哈希表的簇索引，即一级索引，索 此着法录入开局库.阈值公式为 引数量共为32768个，然后在相应簇中通过哈希值 WinCount 即可搜索到相应局面，哈希值可视为二级索引，这种 P=LossCount WinCount (1) 方式大大提高了搜索开局库的效率； 现通过实际录入过程来说明阈值的作用.取 int statu-played表示局面权值，各位的意义如表2 1000个对局棋谱，共39000个局面（节点），来制作 表2开局库局面权值各位说明 统计开局库，胜率从0开始每增10%进行测试，记 Table 2 The illumination of the opening book variables 录胜率与录入节点数量的关系，其示意图如图3所 位长度 标识 第几位 含义 示.由图可看出，选取合适得胜率阈值将减少录入局 1 红胜 面的数量 31 标识红方胜 1 和棋 3.2数据结构设计与应用 30 标识和棋 开局库作为博弈系统的数据库，要求其查询效 1 黑胜 29 标识黑方胜 自定义 24-28 自定义优劣 率尽量的高，因此其数据结构要合理、精简.由此选 24 使用频率 0-23 着法使用频率 择哈希技术实现开局库的设计.1970年Zobrist教 1994-2009 China Academic Journal Electronie Publishing House.All rights reserved. http://www.cnki.net
统计计算提取着法形成的开局库. 下面将对统计开 局库的一些问题做详细论述. 3. 1 统计方式设计 现在很多棋谱都提供了与对局相关的很多信 息 ,这样就有了统计所需的样本. 与局面优劣相关的 信息总的来说有如下几点 : 1) 一个着法所走过的次数. 次数越多 ,这个着法 就可能越好. 2) 棋手的棋力. 特级大师的着法肯定会比普通 棋手的着法好. 3) 下棋的时间. 最近的着法一般会比以前的着 法好. 4) 对局结果. 赢棋方的着法可能会更好. 5) 通过人为注释棋谱优劣 ,判断棋谱优劣. 从以上信息在某种程度上可以判断出着法的优 劣 ,其中第 1) 、4) 、5) 条更有说服力. 具体统计过程 如图 2 所示. 图 2 着法统计流程图 Fig. 2 The flow chart of the moves statistic 其实不必将所有的局面全部录入开局库内 ,只 需要选择一些比较好的着法. 这同样也是根据统计 信息实现的. 定义变量 WinCount 表示一个着法赢 过的次数 ,定义变量 LossCount 表示这个着法输过 的盘数 ,为胜率 ,作为阈值 ,根据阈值来决定是否将 此着法录入开局库. 阈值公式为 P = WinCount LossCount + WinCount . (1) 现通过实际录入过程来说明阈值的作用. 取 1 000个对局棋谱 ,共 39 000 个局面 (节点) ,来制作 统计开局库 ,胜率从 0 开始每增 10 %进行测试 ,记 录胜率与录入节点数量的关系 ,其示意图如图 3 所 示. 由图可看出 ,选取合适得胜率阈值将减少录入局 面的数量. 3. 2 数据结构设计与应用 开局库作为博弈系统的数据库 ,要求其查询效 率尽量的高 ,因此其数据结构要合理、精简. 由此选 择哈希技术实现开局库的设计. 1970 年 Zobrist 教 图 3 胜率与开局库节点数关系示意图 Fig. 3 The relation between the win2rate and the note2number 授为棋类搜索发明的算法 ,被称为“Zobrist 哈希技 术”,其数据结构称为“哈希表”. 此算法的思想是创 建一个 hash [ chessman ] [location ]的数组 ,数组中 每一个元素都是一个 64 位随机数. 对中国象棋来 说 ,就是 hash[14 ][ 90 ]. 求当前局面的哈希值 ,就是 将棋盘上所有棋子在数组中对应的 64 位数做异或 运算 ,生成这一局面的唯一标识数. 哈希技术有 2 个 明显的优点 :1) 64 位数使得局面冲突的可能性非常 小 ,基本可以唯一标识当前局面 ,可以用作哈希表的 索引 ;2)不用每一次展开节点时都计算局面的哈希值. 只要在搜索开始时做初始化运算 ,在着法执行过程中 通过异或运算求出变动的棋子及其位置即可. 开局库数据结构定义如下 : typedef struct { Hash position ; / / 64 位哈希值 int stat u played ; / / 32 位局面权值 }BOO K KEY; 此结构包含了一个着法的信息. 开局库即为若 干该种数据组成. Hash position 为局面的哈希值 , 共 64 位 ,将局面按“簇”存储 ,根据哈希值的高 15 位 值将局面分为若干簇 ,簇数量为 2 15 个 ,所以哈希值 的高 15 位可作为哈希表的簇索引 ,即一级索引 ,索 引数量共为 32 768 个. 然后在相应簇中通过哈希值 即可搜索到相应局面 ,哈希值可视为二级索引 ,这种 方式大大提高了搜索开局库的效率 ; int statu played 表示局面权值 ,各位的意义如表 2. 表 2 开局库局面权值各位说明 Table 2 The illumination of the opening2book variables 位长度 标识 第几位 含义 1 红胜 31 标识红方胜 1 和棋 30 标识和棋 1 黑胜 29 标识黑方胜 5 自定义 24～28 自定义优劣 24 使用频率 0～23 着法使用频率 第 1 期 魏钦刚 ,等 :中国象棋计算机博弈开局库研究与设计 ·87 ·
·88 智能系统学报 第2卷 制作一个“反应”式的开局库，并且不需要录入太多 开局库 索引1 局面1 的局面和着法，这将是研究的目标」 局面2 4.2“理想”开局库的设计 “反应”式开局库，就是要求计算机接收到对方 局面N 走棋信息以后，不用计算而立刻就走出对着.那么开 索引2 局面1 局库内部结构必然是一对一的关系，一个局面唯一 地对应于另一局面，并且对手的着法尽量都能在开 局面2 局库中搜索到.所以在博弈树上的节点不用全部展 开，而只展开对方尽量多的叶子节点.己方叶子节点 局面N 只要展开一个.考虑到先手和后手的不同，这种开局 图4开局库内部结构 库由先手开局库和后手开局库组成，其树结构形式 Fig.4 The inter-structure of the opening-book 如图5和图6所示. 设计后的开局库内部结构如图4所示 开局库内表示的是单个局面的信息，并没有涉 及到上一局面的情况，所以开局库在使用中采用如 下方法实现搜索 将当前棋局转换为哈希数，用作棋局的存储与 查询.哈希数的最大优点就在它求的是64位数的异 6 7 或和，当在着法（涉及所走棋子、棋子起始位置、棋子 目标位置、所吃棋子等变量)的作用下，棋局发生了 图5“理想”开局库（先手）树结构示意图 变化，只要将相应变化棋子的哈希数再异或一次，便 Fig.5 The sketch map of the desired opening-book 可以转变成新局面对应的哈希数.具体实现如式 structure(red) (2) Ha1=Hn·ga+1,Ho=H0, (2) 32 H。=Random64(k,(p. 3) 式中：g+1表示着法算子（即当前着法），HO)表示 初始局面，H。表示n步后的局面，⊙为异或算子，k 表示相应的棋子，(P),表示第j个棋子n步后在 棋盘上的位置， 789102345 通过式2)可以从当前局面(H)计算出若干个 后续局面(Hn+1),然后就能够以Hm+1的高15位为 图6“理想”开局库（后手）树结构示意图 Fig.6 The sketch map of the desired opening-book 一级索引搜索到局面所在簇中，再以H.+1作为二级 structure(black) 索引在相应簇中对局面进行搜索，大大提高了搜索 效率 明确了“理想”开局库的结构，接下来需要讨论 的是生成问题.如果采用计算机自动生成“理想”开 4“理想”开局库 局库，虽然在局面数量上有所减少，但策略以及形式 4.1“理想”开局库的提出 问题还是解决不了，所以为了保证能够吸收人类棋 统计开局库在使用中要从众多的着法中按照统 手的经验，还是要利用统计开局库的结果，将统计出 计信息来选择出一个分值最好的着法.这是统计开 的最好的着法作为己方的扩展方向，即可保证开局 局库的设计特点决定的.因此开局库搜索过程中就 策略正确.但是统计开局库的局面数量有限，这样的 要进行一些必要的计算， “理想”开局库很容易脱谱，所以也要进行必要的计 大家都能注意到，象棋大师在对局时也好似有 算机自动生成.“理想”开局库设计流程如图7所示 一个开局库，他们的开局要比计算机有效率.他们不 4.3“理想”开局库的问题 可能记住太多的棋谱，但并不影响行棋速度.该走哪 通过以上讨论可以看出，“理想”开局库是在计 步棋己经成为自身本能的反应.那么计算机能否也 算机自动生成开局库与统计开局库基础上开发的， 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
图 4 开局库内部结构 Fig. 4 The inter2structure of the opening2book 设计后的开局库内部结构如图 4 所示. 开局库内表示的是单个局面的信息 ,并没有涉 及到上一局面的情况 ,所以开局库在使用中采用如 下方法实现搜索. 将当前棋局转换为哈希数 ,用作棋局的存储与 查询. 哈希数的最大优点就在它求的是 64 位数的异 或和 ,当在着法(涉及所走棋子、棋子起始位置、棋子 目标位置、所吃棋子等变量) 的作用下 ,棋局发生了 变化 ,只要将相应变化棋子的哈希数再异或一次 ,便 可以转变成新局面对应的哈希数. 具体实现如式 (2) . Hn+1 = Hn ·qn+1 , H0 = H (0) , (2) Hn = © 32 j =1 Random64 ( kj , ( P M n ) j) . (3) 式中 :qn + 1表示着法算子 (即当前着法) , H (0) 表示 初始局面 , Hn 表示 n 步后的局面 , ©为异或算子 , kj 表示相应的棋子 , ( P M n ) j 表示第 j 个棋子 n 步后在 棋盘上的位置. 通过式(2) 可以从当前局面( Hn ) 计算出若干个 后续局面( Hn + 1 ) ,然后就能够以 Hn + 1 的高 15 位为 一级索引搜索到局面所在簇中 ,再以 Hn + 1作为二级 索引在相应簇中对局面进行搜索 ,大大提高了搜索 效率. 4 “理想”开局库 4. 1 “理想”开局库的提出 统计开局库在使用中要从众多的着法中按照统 计信息来选择出一个分值最好的着法. 这是统计开 局库的设计特点决定的. 因此开局库搜索过程中就 要进行一些必要的计算. 大家都能注意到 ,象棋大师在对局时也好似有 一个开局库 ,他们的开局要比计算机有效率. 他们不 可能记住太多的棋谱 ,但并不影响行棋速度. 该走哪 步棋已经成为自身本能的反应. 那么计算机能否也 制作一个“反应”式的开局库 ,并且不需要录入太多 的局面和着法 ,这将是研究的目标. 4. 2 “理想”开局库的设计 “反应”式开局库 ,就是要求计算机接收到对方 走棋信息以后 ,不用计算而立刻就走出对着. 那么开 局库内部结构必然是一对一的关系 ,一个局面唯一 地对应于另一局面 ,并且对手的着法尽量都能在开 局库中搜索到. 所以在博弈树上的节点不用全部展 开 ,而只展开对方尽量多的叶子节点. 己方叶子节点 只要展开一个. 考虑到先手和后手的不同 ,这种开局 库由先手开局库和后手开局库组成 ,其树结构形式 如图 5 和图 6 所示. 图 5 “理想”开局库(先手) 树结构示意图 Fig. 5 The sketch map of the desired opening2book structure (red) 图 6 “理想”开局库(后手) 树结构示意图 Fig. 6 The sketch map of the desired opening 2book structure (black) 明确了“理想”开局库的结构 ,接下来需要讨论 的是生成问题. 如果采用计算机自动生成“理想”开 局库 ,虽然在局面数量上有所减少 ,但策略以及形式 问题还是解决不了. 所以为了保证能够吸收人类棋 手的经验 ,还是要利用统计开局库的结果 ,将统计出 的最好的着法作为己方的扩展方向 ,即可保证开局 策略正确. 但是统计开局库的局面数量有限 ,这样的 “理想”开局库很容易脱谱 ,所以也要进行必要的计 算机自动生成.“理想”开局库设计流程如图 7 所示. 4. 3 “理想”开局库的问题 通过以上讨论可以看出 “, 理想”开局库是在计 算机自动生成开局库与统计开局库基础上开发的 , ·88 · 智 能 系 统 学 报 第 2 卷
第1期 魏钦刚，等：中国象棋计算机博弈开局库研究与设计 ·89· 开始 参考文献： ■■ 将棋谱按步录入计算机等待处理 [1]黄少龙.象棋开局战术精华[M].上海：华南理工大学出 版社，2002. 将局面排序并按照统计方法进行统计 [2]黄少龙.象棋开局[M].成都：蜀蓉棋艺出版社，2002. 生成对方所有着法列表 [3]THOMAS R.Lincke,Strategies for the automatic con- struction of opening books [A ]Computer and Games: Second International Conference[C].Hamamutsu Japan, 统计结果中有 没有好的局面 2000. [4]KARAPETYAN A,RICHARD J.Lorentz,generating 应用脱谱扩展法进行扩展节点 ￥ an opening book for amazons[A].4th Internatinal Con 将着法录入开局库 ference on Computers and Game[C].Ramat-Gam,Israel, 2004. 奢法列表是否扩展完N [5 MICHAEL B.Toward opening book learning M]. USA,NEC research Institute,2001. [6]王小春.PC游戏编程[M].重庆：重庆大学出版社， 是否达到开局长度限>N 2002. [7]徐心和，王骄.中国象棋计算机博弈关键技术分析U]. 小型微型计算机系统，2006,27(6)：961.969. 洁束 XU Xinhe,WANG Jiao.Key technologies analysis of Chinese Chess computer game [J ]Mini-Micro Systems. 图7“理想”开局库设计制作流程图 2006,27(6):961.969. Fig.7 The flow chart of design the desired opening-book [8]国际象棋Crafty引擎说明文档[B/OL】.fp:/1fp 应该能够比较完整地搜索完开局阶段的着法，而不 cis.uab.edu/pub/hyatt/.2006-07-10. 容易脱谱.甚至可以通过己有棋谱制作某个大师的 作者简介： 开局库，能够完全地保持大师的行棋风格，对于学棋 魏钦刚，男，1984生，主要研究方向 者来说也是一个不可多得的导师」 为中国象棋计算机博弈开局库的研究。 但是“理想”开局库也有缺点，就是对局着法唯 Email weiqingang.gang @163. 一，不经过任何计算直接走开局库内的着法，实现了 com. “反应式”搜索，但是如果不能保证着法的最优，或者 说没有一个明确的策略的话，那么局面就有可能失 去优势.而且象棋本就是一种变化的策略游戏，如果 单个局面的最优着法存在且唯一，就无形中承认了 象棋有解这种观点，对于今后的发展是不利的.所以 王骄，男，1978年生，博士研究 还要对开局库进一步研究，使其能够自行决定如何 生，主要研究方向为人工智能与机器博 弈 适当变化开局着法 5结束语 讨论了中国象棋人机博弈系统开局库部分的设 徐心和，男，1940年生，教授，博士 计方法，对计算机自动生成开局库、统计开局库以及 生导师，主要研究方向为控制理论与应 “理想”开局库进行了探讨，论述了各方法的优缺点， 用、系统仿真、智能机器人、机器博弈 提出了开局库应该以为中后局奠定良好基础为目标 等 的设计思想.最后论述了开局库自学习的设计思想， 并阐述了建立开局评估体系的重要性 中国象棋的局面发展是变化莫测的，期待能够 通过研究尽量开发出更加完善和精确的开局库，不 断推动中国象棋的发展 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
图 7 “理想”开局库设计制作流程图 Fig. 7 The flow chart of design the desired opening 2book 应该能够比较完整地搜索完开局阶段的着法 ,而不 容易脱谱. 甚至可以通过已有棋谱制作某个大师的 开局库 ,能够完全地保持大师的行棋风格 ,对于学棋 者来说也是一个不可多得的导师. 但是“理想”开局库也有缺点 ,就是对局着法唯 一 ,不经过任何计算直接走开局库内的着法 ,实现了 “反应式”搜索 ,但是如果不能保证着法的最优 ,或者 说没有一个明确的策略的话 ,那么局面就有可能失 去优势. 而且象棋本就是一种变化的策略游戏 ,如果 单个局面的最优着法存在且唯一 ,就无形中承认了 象棋有解这种观点 ,对于今后的发展是不利的. 所以 还要对开局库进一步研究 ,使其能够自行决定如何 适当变化开局着法. 5 结束语 讨论了中国象棋人机博弈系统开局库部分的设 计方法 ,对计算机自动生成开局库、统计开局库以及 “理想”开局库进行了探讨 ,论述了各方法的优缺点 , 提出了开局库应该以为中后局奠定良好基础为目标 的设计思想. 最后论述了开局库自学习的设计思想 , 并阐述了建立开局评估体系的重要性. 中国象棋的局面发展是变化莫测的 ,期待能够 通过研究尽量开发出更加完善和精确的开局库 ,不 断推动中国象棋的发展. 参考文献 : [1 ]黄少龙. 象棋开局战术精华[ M ]. 上海 :华南理工大学出 版社 ,2002. [2 ]黄少龙. 象棋开局[ M]. 成都 :蜀蓉棋艺出版社 ,2002. [3 ] THOMAS R. Lincke , Strategies for the automatic con2 struction of opening books [ A ]. Computer and Games: Second International Conference[C]. Hamamutsu ,Japan , 2000. [4 ] KARAPET YAN A , RICHARD J. Lorentz , generating an opening book for amazons[ A ]. 4th Internatinal Con2 ference on Computers and Game[ C]. Ramat2Gam ,Israel , 2004. [5 ] MICHA EL B. Toward opening book learning [ M ]. USA ,N EC research Institute ,2001. [6 ]王小春. PC 游戏编程 [ M ]. 重庆 : 重庆大学出版社 , 2002. [7 ]徐心和 ,王 骄. 中国象棋计算机博弈关键技术分析[J ]. 小型微型计算机系统 ,2006 ,27 (6) :961 - 969. XU Xinhe , WAN G Jiao. Key technologies analysis of Chinese Chess computer game [J ]. Mini2Micro Systems. 2006 ,27 (6) :961 - 969. [8 ] 国际象棋 Crafty 引擎说明文档 [ EB/ OL ]. ftp :/ / ftp . cis. uab. edu/ pub/ hyatt/ . 2006 - 07 - 10. 作者简介 : 魏钦刚 ,男 ,1984 生 ,主要研究方向 为中国象棋计算机博弈开局库的研究. E2mail : weiqingang. gang @ 163. com. 王 骄 ,男 , 1978 年生 ,博士研究 生 ,主要研究方向为人工智能与机器博 弈. 徐心和 ,男 ,1940 年生 ,教授 ,博士 生导师 ,主要研究方向为控制理论与应 用、系统仿真、智能机器人、机器博弈 等. 第 1 期 魏钦刚 ,等 :中国象棋计算机博弈开局库研究与设计 ·89 ·