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