中国象棋之二 ElephantEye 引擎浅析

发表于 2020-03-16 阅读次数：评论数：本文字数： 4.8k 阅读时长 ≈ 4 分钟

社区

大纲

一、简介

ElephantEye 是一款自由的中国象棋程序，在遵循《GNU 宽松通用公共许可协议》(GNU Lesser General Public Licence) 的前提下，广大象棋爱好者和程序设计师可以自由使用 ElephantEye 及其源程序。ElephantEye 中文名称为 “象眼”，它跟 “马腿” 和 “炮架子” 一起构成了中国象棋 “棋盘上的第三维”。ElephantEye 通常与一个象棋棋谱编辑软件 ElephantBoard 配合使用，寓意有板有眼 (英文 Board 的意思是 “板”)。注：现在 ElephantBoard 已更名为 “象棋巫师”

二、引擎协议

ElephantEye 支持 UCCI 3.0，浅红象棋用户可通过 UCCI 引擎适配器 (UCCI2QH) 调用 ElephantEye 引擎，UCCI 命令使用帮助如下。

支持的UCCI命令有：
　　ucci
　　setoption ...
　　position {fen <fen_str> | startpos} [moves <move_list>]
　　banmoves <move_list>
　　go [ponder | draw] ...
　　ponderhit [draw] | stop
　　probe {fen <fen_str> | startpos} [moves <move_list>]
　　quit

可以返回的UCCI信息有：
　　id {name <engine_name> | version <version_name> | copyright <copyright_info> | author <author_name> | user <user_name>}
　　option ...
　　ucciok
　　info ...
　　pophash [bestmove <best_move>] [lowerbound <value> depth <depth>] [upperbound <value> depth <depth>]
　　{nobestmove | bestmove <best_move> [ponder <ponder_move>] [draw | resign]}
　　bye

三、参数设置

ElephantEye 作为 UCCI 引擎，有若干可以设置的参数 (可以直接在 < 象棋巫师> 中设置)：
(1) 开局库：
　　默认的开局库为 ElephantEye 程序 (ELEEYE.EXE) 所在目录下的 BOOK.DAT，含有 10,000 个对称局面的着法。
(2) 思考时间：
　　限定思考深度通常不是很好的选择，建议给定限时让程序自动分配时间。而在解杀局或分析局面时，则可让程序无限制思考，并可随时中止思考。
(3) 置换表大小：
　　尽管置换表大小对程序的运行速度影响不大，默认 16MB 的设置已经足够，但 ElephantEye 还是提供了设置置换表大小的功能。在内存允许的情况下，下慢棋时可以适当增加置换表的大小，但建议不要超过物理内存的一半。
(3) 裁剪程度：
　　为加快程序的运算速度，ElephantEye 默认使用空着裁剪，并且产生负面影响的可能性很小。只有最低级别会禁用空着裁剪。
(4) 知识量：
　　知识量和局面评价的准确性有关，在 ElephantEye 的知识量等级中，只有最低级别是不采用局面评价函数的 (只考虑子力价值)，在解排局等不需要依靠审局知识来分析的局面时，可以尝试用这种设置。
(5) 随机性：
　　ElephantEye 设有 4 级随机性。随机性越大，程序越有可能走出它认为不是最好的着法，但 “不是最好的着法” 并非一点好处也没有，尤其在没有启用开局库时，适当增大随机性，可以避免程序在相同的局面下走出一样的着法。

四、规则

从 2.0 版开始，ElephantEye 除了支持 “单方面长将判负” 的规则外，还支持 “长打判负”，“打” 包括 “将” 和 “捉”。尽管 ElephantEye 在复杂的情况可能无法正确识别长打，但由于支持 UCCI 命令 banmoves … ，一旦用户认为引擎走了 “长打” 的禁着，可以用 < 象棋巫师 > 的 “设置禁着” 功能让引擎强制变着。由于程序复杂性方面的限制，只有以下三种情况被识别成 “捉”，分别是： A. 马捉车或有根的炮兵 (卒)；B. 车捉有根的马炮兵 (卒)；C. 炮捉车或有根的马兵 (卒)。　　

五、博弈算法

ElephantEye 属于偏向蛮力的象棋程序，使用了严谨而有效的博弈算法：
(1) 使用位行和位列的着法生成器：
　　位行 (BitRanks) 和位列 (BitFiles) 有利于滑动棋子 (车和炮) 的着法 (尤其是吃子着法) 生成，位行和位列可以用查表来代替在射线上做的循环运算。在 ElephantEye 中，位行和位列的技术不仅用在着法生成器中，也用到了牵制的判断上。
(2) 静态局面搜索：
　　在做静态搜索时，ElephantEye 搜索了吃子或解将的着法，在搜索吃子着法时，ElephantEye 过滤掉不重要的吃子，例如吃不过河的兵、吃不处于防守中的士象等着法，都不在静态搜索的范围之内。
(3) 循环着法和长将检测：
　　ElephantEye 可以识别循环着法，出现循环着法时可以判断哪方为长将，并且会利用禁止长将的规则来谋求优势，但目前 ElephantEye 还无法识别长捉。
(4) 置换表：
　　ElephantEye 参考了中国象棋程序 “纵马奔流” 的设计思路，使用深度优先和始终覆盖的双层置换表，并采用低出 (高出) 边界修正的置换表更新策略。
(5) 带检验的空着裁剪：
　　ElephantEye 使用 R=2 的空着裁剪，在残局阶段使用带检验的空着裁剪。
(6) 迭代加深 / 吃子着法 / 杀手着法 / 历史表启发：
　　ElephantEye 的着法排序非常简单清晰，依次是迭代加深着法、好的吃子着法、杀手着法和按历史表排序的生成着法。
(7) 将军 / 唯一应将 / 兑子延伸：
　　在选择性延伸上，ElephantEye 采用了将军、唯一应将和兑子延伸。
(8) Alpha-Beta 主要变例搜索：
　　ElephantEye 使用传统意义上的递归式 Alpha-Beta 主要变例搜索。
(9) 开局库：
　　ElephantEye 的开局库共包含了 10,000 个对称着法，是从 1990 年到 2005 年全国象棋个人赛、团体赛、五羊杯、联赛等 8,000 局顶尖比赛中提取的。
(10) 后台思考和时间分配策略：
　　ElephantEye 支持后台思考功能，同时提供了时段制和加时制两种时间分配策略，会自动合理分配时间。

六、开局库

ElephantEye 的开局库可由 “ElephantEye 开局库制作工具” 制作。运行制作工具后，首先要选择 PGN 棋谱所在的文件夹，然后保存为开局库文件 (通常是 BOOK.DAT)。通常，用来生成开局库的棋谱数量越多，生成的开局库文件就越大。为了使制作的开局库对 ElephantEye 生效，只需要把生成的开局库文件替换掉 ElephantEye 目录下的 BOOK.DAT 即可，也可以在 < 象棋巫师 > 的 “引擎设置” 对话框中指定开局库文件。

七、局面评价函数库

ElephantEye 从 2.1 版开始，程序的搜索部分和局面评价部分就分离了，搜索部分通过调用 API 函数的形式与局面评价部分耦合。其他象棋程序设计师可以在 ElephantEye 的基础上更自由地发挥。根据 LGPL 协议，搜索和局面评价这两个部分都作为独立的程序库，运用其中任何一部分都只需要公开该部分的源程序即可。换句话说，如果局面评价部分没有使用任何开放代码，那么程序设计师就没有义务公开这部分的源程序，搜索部分也是如此。ElephantEye 的局面评价 API 函数接口定义如下：

A. 局面评价引擎名称：const char *GetEngineName(void);
B. 局面预评价函数接口：void PreEvaluate( PositionStruct *lppos, PreEvalStruct *lpPreEval);
C. 局面评价函数接口：int Evaluate(const PositionStruct *lppos, int vlAlpha, int vlBeta);

其中 PositionStruct 和 PreEvalStruct 必须分别符合 position.h 和 pregen.h 中定义的结构。

八、源代码

ElephantEye 的源代码包括 9 个模块，内容大致为：
(1) ucci.h/ucci.cpp
　　UCCI 命令解释模块，包括 Windows 和 Unix 下的行输入接收程序；
(2) pregen.h/pregen.cpp
　　Zobrist 数组和着法预置表的生成模块。ElephantEye 的预置表分两个部分，一是滑动棋子的着法预置表 (包括不吃子、车吃子、炮吃子和隔两子吃子)，它是实现位行和位列技术的基础；二是其他棋子的着法预置表，使得着法生成时避免了烦琐的边界判断。
(3) position.h/position.cpp
　　主要描述着法和局面的数据结构及功能。局面的处理是本模块的重点，处理内容包括局面初始化、FEN 串导入、棋子移动、杀手着法的合理性判断、将军判断、长将和循环检测、子力价值分调整等过程，还包括 5 个子力位置价值表。
(4) genmoves.cpp
　　着法生成器，包括生成吃子着法和生成不吃子着法的两个，但不能只生成解除将军的着法。在生成吃子着法的同时赋予每个着法以相应的 MVV (LVA)(或称准 SEE) 值。该模块还有一个专门判断棋子是否有保护的函数，来计算 MVV (LVA) 值，对于有保护的棋子，计算 MVV-LVA 的值 (小于零不计)，对于无保护的棋子，只计算 MVV 的值。因此，判断棋子是否有根的程序也包括在本模块中。
(5) hash.h/hash.cpp
　　置换表、历史表和着法列表管理模块，包括置换表的分配和存取、主要变例获取等操作。
(6) book.h/book.cpp
　　开局库读取模块。
(7) movesort.h/movesort.cpp
　　着法列表排序模块。
(8) search.h/search.cpp
　　搜索模块，除了静态搜索、完全搜索和根结点搜索这三个主要过程外，还包括迭代加深控制、后台思考、时间分配、搜索参数统计和搜索信息输出等内容。该模块是整个程序的核心模块。
(9) eleeye.cpp
　　主程序 (即 main 函数)。
(10) preeval.cpp
　　子力位置数组预生成器，ElephantEye 根据 “进攻 / 防守” 和 “开局 / 中局 / 残局” 两个参数线性调整子力位置数组。
(11) evaluate.cpp
　　局面评价函数，ElephantEye 采用了四级偷懒评价的机制，最粗的层次只评价特殊棋型，进一层次评价牵制，再进一层次评价车的灵活性，最高层次还评价马的阻碍。

九、引擎表现

ElephantEye 的设计重点在搜索算法，但在知识上比较欠缺。在 2.8 GHz 的处理器上每秒可搜索约 1,000,000 个结点 (包括常规搜索和静态搜索)，一般的中局局面在 1 分钟内可搜索约 11 层。在棋力上，ElephantEye 和 “棋隐”、SaoLa (象棋挑战者) 等程序具有同等水平，但由于局面评估函数上的缺陷，ElephantEye 距离顶尖的商业象棋软件 (谢谢大师、象棋世家、象棋奇兵、棋天大圣等) 尚有一定的差距。ElephantEye 在联众、弈天等象棋对弈网站上作过测试，用等级分来衡量，联众网的战绩在 2500 分左右，弈天网快棋的战绩在 2000 分左右，慢棋在 1500 分左右。2005 年 9 月在台湾象棋软件爱好者施金山的帮助下，ElephantEye 参加了在台北举行的第 10 届 ICGA 电脑奥林匹克大赛中国象棋组比赛，战绩是 7 胜 5 和 14 负，在 14 个程序中排名第 11；2006 年 8 月 ElephantEye 参加了在北京举行的全国首届计算机博弈锦标赛，战绩是 7 胜 2 和 11 负，在 18 个程序中排名第 7。

十、附加模块

ElephantEye 的源代码包除了 ElephantEye 本身的源代码外，还包括以下几个附加模块：
(1) 基础代码 (base)：提供了汇编指令、系统函数调用等功能；
(2) 中国象棋规则模块 (cchess)：为其他软件使用 ElephantEye 代码提供了接口；
(3) 开局库制作模块 (BOOK)：制作开局库 BOOK.DAT 的代码；
(4) UCCI 引擎联赛模拟器 (LEAGUE)：为 UCCI 引擎测试和比赛提供了自动批量对局的平台；
(5) UCCI 引擎搜索树分析器 (TREE)：UCCI 引擎 (支持 UCCI 2.2+) 的搜索路线分析工具；
(6) XQF 棋谱工具 (XQFTOOLS)：提供 XQF 等多种棋谱转换为 PGN 的工具；
(7) 浅红象棋适配器 (UCCI2QH)：为浅红象棋调用 UCCI 引擎提供了接口；
(8) 浅红象棋引擎支持 UCCI 的适配器 (QH2UCCI)：为 “梦入神蛋” 浅红象棋加入 UCCI 引擎测试提供了接口；
(9) BBS Chess (BBSCHESS)：一个用 Visual Basic 制作的国际象棋局面设置工具，可在各高校 BBS 上粘贴彩色的国际象棋局面；
(10) 棋盘图片生成器 (FEN2BMP)：一个可以把国际象棋和中国象棋的 FEN 文件转换成 BMP 文件的实用工具；
(11) 编码转换 (codec)，包括简繁转码、UNIX 文本转码、Base64 转码等；
(12) 其他工具 (MISC)：包括简易网络通讯、管道测试等工具；
(13) 说明文档 (DOC)：即《中国象棋程序设计探索》系列连载；
(14) 参赛棋谱 (CCGC)：ElephantEye 参加首届全国计算机博弈锦标赛 (CCGC) 的全部棋谱。