第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 ·