解剖大象的眼睛——中国象棋程序设计探索（七）
发布时间：2008-11-20
点击：
来源：本站原创
录入者：黄晨
(七) 开局库
在阅读本章前，建议读者先阅读《象棋百科全书》网站中《对弈程序基本技术》专题的以下几篇译文：
(1) 其他策略——开局库(Martin Fierz)。
7.1 象棋程序对开局库的处理
开局库是象棋程序中知识含量最多的部分，各种程序的棋力会因为开局库的不同而有所差距。互联网上介绍国际象棋开局库的文章很多，而中国象棋开局库的原理和国际象棋是完全一样的，因此笔者就不作太多的介绍了。
很多国际象棋的程序中，开局库并不被引擎处理，而是由界面来完成的，棋局进入中局脱离棋谱后，才让引擎作搜索。ChessBase的系列软件Junior和Fritz，以及支持UCI协议的Shredder，都使用这种工作方式，由于它们使用同一套ChessBase的界面，因此开局库格式是统一的。由于WinBoard本身并不能处理开局库，因此支持WinBoard的引擎都具有处理开局库的能力，而且每个引擎都有各自的开局库格式。
而中国象棋目前没有统一的界面，因此也没有统一的开局库格式。ElephantEye的开局库具有非常明显的特点——它是文本格式的，每一行记录一个着法，依次是着法(红色部分)、权重(绿色部分)和局面(紫色部分)：
b2e2 5895 rnbakabnr/9/1c5c1/p1p1p1p1p/9/9/P1P1P1P1P/1C5C1/9/RNBAKABNR w - - 0 1
由于记录局面时使用FEN串，这就增加了开局库的可读性，但同时使开局库变得特别庞大，ElephantEye的开局库(BOOK.DAT)仅有20,000多个着法却达到了1.6M。
开局库的类型大致分为树型和局面型，ElephantEye的开局库显然属于后者。对于局面型的开局库来说，把它导入置换表是最合适的，ElephantEye的置换表标志除了HASH_ALPHA、HASH_PV、HASH_BETA外，还专门为开局库局面增设BOOK_UNIQUE(局面只有一个开局库着法)和BOOK_MULTI(局面有多个开局库着法)两项。开局库中大多数局面只有唯一着法，因此着法直接存入置换表项的最佳着法区域内，而多个着法则需要另设一个专门的数据结构来保存各种着法及其权重。
ElephantEye处理开局库的代码在<hashbook.cpp>中，LoadBook()函数用来导入开局库，GetBookMove()函数用来读取开局库。如果局面没有在置换表中找到，那么程序将进行搜索，搜索的时候会把置换表中的开局库局面覆盖掉。因此，当棋局重新开始时，开局库要重新导入。
7.2 开局库的制作
ElephantEye现有的开局库是从《象棋百科全书》网站上收录的8000多局对局中整理出来的，这些对局涵盖了1990年到2004年的全国顶级象棋比赛(团体赛、个人赛、甲级联赛和五羊杯)，因此具有代表性。由于笔者没有为ElephantEye写开局库制作程序，因此开局库的制作是在数据库管理软件的帮助下手工完成的(笔者使用的是FoxPro)，现在简要介绍一下开局库的制作流程。
(1) 编写一个PGN2FEN程序(能把PGN文件的每个出现的局面转换成FEN串、后续着法和胜负信息，并对每个局面作一份翻转棋盘的拷贝)，对《象棋百科全书》网站上收录的8000多个PGN文件转换为一个FEN列表文件；
(2) 把FEN列表文件转换为数据库，数据库包括FEN串、着法、胜局数、和棋局数、负局数这几个域(根据胜负情况，对胜局数、和棋局数或负局数置1)；
(3) 按照“FEN串+着法”为索引合并重复记录，对胜局数、和棋局数、负局数分别合计；
(4) 增加权重这个域，按照笔者观点，权重 = 胜局数 x 3 + 和棋局数 - 负局数；
(5) 过滤掉权重小于4的着法(即收入开局库的着法至少是一胜一和的)；
(6) 按照着法、权重和FEN串的顺序，按权重排序导出为开局库文件(BOOK.DAT)。
这个流程使得ElephantEye现有的开局库存在很多问题，主要有：
(1) 用文本格式太浪费空间，用Zobrist键值取代FEN串，并采用二进制格式记录，那么每个着法只需要12个字节(Zobrist键值4字节，Zobrist锁4字节，着法2字节，权重2字节)，这样就可以节省大量空间；
(2) 仅由8000多局对局整理出的开局库是远远不够的，顶尖象棋软件的开局库一般是从100,000局以上的对局中整理出来的，这些对局大都是高水平的网络对局；
(3) 需要一个开局库制作程序，权重可以根据自己的需要来设定(笔者的权重计算方法并不一定合理)，读者有兴趣的话，可以在数据库平台上自己设计这样的开局库制作程序；
(4) 开局库中存在一些可能导致长将的着法，笔者已经发现ElephantEye在开局库阶段就走出长将的不合理着法了，这些着法应该被过滤掉。
 关闭窗口  打印文档 |
账号登录