国际象棋程序设计(二)：数据结构

　

François Dominic Laramée/文

　

　　上个月我简要介绍了象棋程序设计中所需要的知识，其他信息完全的双人游戏也是一样的。现在我们将讨论一些细节——棋盘的内部表示方法。

　　在棋盘表示方法这个理念上，近三十年内没有多大发展，你可能会觉得很吃惊。它的发展需要智慧的推动，很早就有人提出过绝妙的方案了，但同时也受到制约，因为这些方案需要数据结构的支持，某些数据结构至今还没有实现。

　　尽管如此，我还是会介绍三种数据结构，尽管它们并不是必需的，但是对于提高你的下棋水平是大有帮助的。其中两种可以加快思考速度(但是其中一种需要无限多的存储器)，另一种可以加快着法产生速度。【译注：分别指后面要提到的置换表、历史表和着法生成预处理的数据库。】

　　在我们继续讨论之前，我提一句格言：“无论是象棋还是其他游戏，你通常使用的数据结构，应该是能达到目的的最简单的数据结构。”然而象棋程序设计者提出了很多技巧，它们能让程序运行的更快，其中相当多的还适用于其他游戏。如果你对你要设计的游戏不很了解，而且手头的资料很有限，那么你应该好好掌握我所提到的这些技巧，你可以把这些技巧试验到你的程序上。

　

基本的棋盘表示

　

　　在上世纪70年代，个人电脑的存储器是稀有资源，所以棋盘表示得越紧凑越好。很多人会很自信地说：用一个64字节的数组，每个字节表示棋盘上的一个格子，用一个整数就可以表示格子的位置了。(任何棋盘的数据结构都必须用一些额外的字节，来记录吃过路兵的目标格、王车易位权利等信息，但是这里我们暂且忽略它，因为这些因素可以独立处理，而且处理方法大同小异。)

　　后来又流行一些更优化的算法：

　

　　1. 早期的SARGON【一个象棋程序】扩展了64字节的数组，在它的外围加了两圈“虚格”，并在这些格子上作了非法标记。这一技巧能加快着法产生的速度，例如象在走棋时会延斜线滑行，直到走到虚格上才中止。这样就没有必要用复杂的运算来预先判断象到达的格子是否会超出存储器上的表示了。第二圈虚格是给马用的，例如位于盘角的马试图跳出棋盘，这就必须用两圈虚格来保护。

　　2. MYCHESS用了相反的方法，它只用32字节表示一个棋盘，每个字节代表一个棋子，例如代表白方王、黑方王翼马前兵【英文居然是black King's Knight's Pawn，一开始让我大惑不解】等，它存储的信息是棋盘上的位置，或者已经被吃的标记。这种技术有一个缺点，它无法描述由兵升变而来的其他棋子(同时这个棋子在棋盘上还有一个)。在后来的版本中，这个缺点被修正了。【其实这并不难办，一个字节取值从0到255，通常255表示该子已被吃，从0到63表示该子在棋盘上的位置，兵通常是升变成后的，那么从64到127可以表示该子已经升变为后，如果升变为车、马或象，则需要额外的字节来处理。】

　

　　如今，这种极端吝啬的数据结构只可能出现在掌上电脑、手机或电视机机顶盒上，它们的80~90%的资源都被操作系统占用，没有额外的空间给游戏使用。但是，某些游戏却别无选择地使用这种方法【我也不知道什么游戏非得使用这种方法不可】。

　　想更多地了解以前的象棋程序，可以看一下David Welsh在1984年写的《计算机象棋》(Computer Chess)一书。

　

位棋盘

　

　　用一个数组来表示棋盘，对于很多游戏来说，就找不到更好的办法了。但是对于像象棋、西洋跳棋之类在64格棋盘上的游戏来说，有一个高明的技巧——“位棋盘” (首先由苏联的KAISSA制作组提出)，在上世纪60年代末诞生了。

　　KAISSA是运行在64位处理器上的程序【我很怀疑当时就有64位处理器，或许当时处理器字长的概念和现在的有所不同】。“64”恰巧是象棋棋盘格子的数目，所以这就有可能让一个字来表示一个棋盘，以判断某个格子的状态是“是”或者“非”。例如，一个位棋盘可以回答棋盘的每个格子“是否有白子”。【把位棋盘运用到中国象棋上，这是我将要进行的一个课题，中国象棋的棋盘有90个格点，可以用3个32位的字来表示。】

　　因此，一个完整的局面需要用12个位棋盘表示：白兵、白车、黑兵等等。再加上两个用来表示“所有白子”和“所有黑子”的位棋盘，以加快运算速度。【其实只需要8个就可以了，同一兵种(不管黑白)用一个位棋盘，一共是6个，再加上代表“所有白子”和“所有黑子”的。做得更过分的是，有人把象和后并作一个位棋盘，车和后并作一个位棋盘，这样又可以减少一个。如果要表示白方的象，只要“所有白子”、“所有车或后”的补集(用“非”运算)、“所有象或后”这三个位棋盘作“与”运算就可以了。】或许你还想用一个位棋盘表示被某种子力攻击到的格子，诸如此类，这些位棋可以盘灵活运用在着法产生的运算过程中。

　　位棋盘之所以有效，是因为很多运算可以转化为处理器的一个逻辑指令。例如，假设你需要确认黑王被白后将军，如果用简单的数组来表示棋盘，那么你需要这样做：

　

　　1. 首先找到后的位置，这需要从64个字节中一个一个地找；

　　2. 然后在后所能走的八个方向找，直到找到王或者找到后走不到的格子为止。

　

　　这些运算是相当花费时间的，如果后碰巧是在数组的最后一格，更糟的是，将军只会发生在少数情况下【这种运算纯粹是白费时间！】。

　　如果用位棋盘，那你只要这样做：

　

　　1. 载入“白方后的位置”的位棋盘；

　　2. 根据这个位置，从索引数据库中找到被后攻击的位棋盘；

　　3. 用这个位棋盘和“黑方王的位置”的位棋盘作“与”运算。

　

　　如果结果不是零，则说明黑王被白后将军。假设被后攻击的位棋盘是储藏于存储器中的【这是上面提到的第二步的前提】，那么整个操作只需要3到4个时钟周期【通常计算机执行1条指令需要1(算术或逻辑运算)到2(寻址操作)个时钟周期】。

　　【这里允许我发挥一下，原作所说的“从索引的数据库中找到”(即上面提到的第二步)，其实并非是简单的一步，对于后的每个位置，都有一定的攻击格子(从边线到中心依次是21、23、25和27格)，但是要考虑被别的子阻挡的情况，程序无法为所有的情况都作索引，最多只能对某条线(横线、纵线或斜线)的棋子占有情况作索引，这也需要2⁸ = 256 种情况，再加后本身有64种位置，所以即使这样，数据库中也至少要保存256x64 = 16384个位棋盘。另外，横线、纵线和两条斜线的处理方法各不相同，横线只要作简单的“移位运算”就可以了，而纵线和两条斜线都要用到“位棋盘旋转”的技术，为了提高运算效率，程序的复杂程度是惊人的，细节可以参考《对弈程序基本技术》专题之《数据结构——旋转的位棋盘》一文，文中作者多次提示读者用咖啡来提神，以完成烦琐的程序。】

　　再举一个例子，如果在当前的棋盘上，你要产生白马的所有着法，那么你只要找到当与前位置相关联的“马能走到的格子”的位棋盘，并“与”(AND)上“所有被白方占有的格子”的位棋盘的补集(就是对这个位棋盘作“非”(NOT)运算)，因为马的着法限制仅仅在于它不能去吃自己的子。【国际象棋比较简单，而中国象棋中还有“绊马腿”的限制(还有象也是)，这种情况该怎样使用位棋盘，也是我将要研究的课题。】

　　如果你想更详细地了解位棋盘(也只是稍微详细一点而已)，可以去看看描述CHESS 4.5 (它是由美国西北大学开发的)的文章——Peter Frey写的《人脑和电脑的象棋技巧》(Ches Skill in Man and Machine)，现在至少已经出了两版了，分别出版于1977年和1981年。

　　值得注意的事，到今天为止，几乎还没有真正意义上使用64位处理器的个人电脑，所以位棋盘的速度优势是要打折扣的。尽管如此，位棋盘的技术仍是行之有效的。【苹果公司的Macintosh图形工作站据说是64位处理器，但不知有没有针对这种电脑的象棋软件。时隔4年，到我翻译这篇文章时，还没有什么别的64位处理器用在个人电脑上。因为毕竟没这个必要，除非你专门用它来玩国际象棋。】

　

置换表

　

　　在象棋里，有很多着法可以到达相同的位置。例如，不管你先走 1. P-K4 ... 2. P-Q4或者1. P-Q4... 2.P-K4，【这里K4和Q4即e4和d4的，在实战中有这样的例子，1. e4 e6 2. d4和1. d4 e6, 2. e4是形成法兰西防御一种变例的两种途径。】最终局面是一样的。有不同的路线可以达到同样位置的，这种现象称为“置换”(Transposing)。【在中国象棋中，置换现象更为普遍，通常用成语“殊途同归”来称呼这种现象。】

　　如果你的程序已经对1. P-Q4... 2.P-K4产生的结果竭尽全力作了搜索和评估，那么你最好记住这个结果，以避免碰到1. P-K4... 2.P-Q4时再作同样的运算。自上世纪60年代Richard Greenblatt的Mac Hack VI问世以来，所有的对弈程序都会吸纳“置换表”这一技术，这就是原因所在。

　　置换表存储的是已经搜索过的结果，它通常使用类似于散列表(Hash Dictionary)的数据结构来达到最快的查询速度。在搜索某个局面时，结果(包括局面分析的值、搜索深度、最佳着法等)就存储到置换表里。当搜索新的局面时，我们先从置换表里找，如果已经有这种局面，那么就可以利用它，省去重复的搜索。

　　这种处理有以下很多好处：

　

　　1. 加快速度。在置换情况发生得很多时(特别是残局局面里，棋盘上棋子很少时)，90%以上的局面可以在表中找到。【在中国象棋中，这优势时更为明显，因为它的子力密度小，在开局阶段就有很多“殊途同归”的现象。】

　　2. 任意深度。假设你需要对某个局面搜索到一个指定的深度，例如4步(也就是两个回合)，如果置换表里有这个局面而且已经搜索了6步，那么你不仅可以跳过这次搜索，还可以得到比预期更精确的结果。

　　3. 用途广泛。通常每个象棋程序都配有“开局库”(Opening Book)，即包含一些常见局面及其最好的着法，这些通常是从已有的记载中提炼的【例如特级大师们写的“象棋开局大全”或“象棋开局手册”之类的书，而我本人更倾向于从大量对局记录中提炼的结果】。有了开局库，程序就不必在开局阶段就做傻事了【因为前人已经做过无数次的计算了】。既然开局库的操作过程和置换表是一样的(即搜索局面)，那么为什么不在棋局一开始就把开局库装入我们的置换表里去呢？如果这样做，即使棋局暂时脱离了开局库，后来又回到开局库里的局面【要注意，这个局面可以是棋局过程中出现的局面，但更多的情况是搜索程序推演到的】，那么置换表里保留了这样的局面，我们仍旧有机会用到它。

　

　　置换表唯一的缺点就是它贪婪地占用着存储器，无论如何它至少需要存储成千上万个局面，百万甚至上亿就更好了。如果每个局面用16字节【用最紧凑的办法至少也需要32字节(用MYCHESS这种吝啬的办法)，但是这里可以存放“散列键值”，下面会提到这个技术】，那么在存储器紧缺的时候这将成为很严重的问题。

　　置换表还有其他用途。

　　CHESS 4.5还用散列表来存储其他的局面计算结果【指下面提到的兵型、子力平衡等】，这些计算结果在多数情况下是不会变动的，例如：

　　1. 兵型(Pawn Structure)。散列表只存储兵的位置，这需要较小的存储空间，由于兵的移动不会很频繁，所以99%的兵型局面可以在散列表中找到；【国际象棋的局面分析中，需要考虑连兵、叠兵、孤兵、通路兵等因素，这些计算是相当费时的，而中国象棋就没有这个必要了。】

　　2. 子力平衡(Material Balance)，即棋盘上子力的相对强弱，它只在吃子或兵升变时变动。

　　在CPU速度不快的今天，这些方法或许看来用处不是很大，但是它们还是有指导意义的，一些稍微花费存储器的预处理可以节省相当多的计算。【因为寻址操作(特别指在若干M的大范围区域内寻址)所占用的时间要远多于简单的运算指令，如果哪天寻址操作的速度接近于基本运算了，那么这种技术将会对程序运行速度有很大的提升。】如果你仔细研究你的程序，或许你会发现这方面是值得改进的。

　

为棋盘产生散列键值

　

　　上面提到的置换表的结构，是由散列表来实现的，由此引发了以下课题：你如何快速而有效地从棋盘来产生散列键值(Hash Key)？

　　以下是1970年Zobrist的方案。

　　1. 产生12x64个N位的随机数(如果置换表能储存2^N个局面)，并把他们做成一张表。每个随机数只跟某个位置上的某种棋子有关(例如H4格的黑车)，空的格子用零表示；【因为棋子总共有12种，棋盘总共有64格，所以是12x64个数，空的格子不用随机数而用0表示。】

　　2. 先把散列键值设为零；

　　3. 搜索整个棋盘，每遇到一个子，就在原来的散列键值上“异或”(XOR)它所对应的随机数，重复这个过程直到整个棋盘被检查一遍。

　　这个方案有趣的一面在于，每走一步，散列键值的更新都非常容易，不需要重新搜索整个棋盘。你知道“XOR图形处理”(XOR-Graphics)吗？某个图形用XOR运算作用到背景上，然后再作同样一次运算，不就又回到背景了吗？这里也同样这么做。【如果你熟悉图形操作中的技术，就不难理解了，原文把这个过程比作“位图”(Bitmap)操作，12x64个棋子的状态就对应12x64张位图，原先的散列键值被比作“背景”(Background)，只要在背景上作位图的粘贴操作(用的是XOR处理)就可以了。】举个H1格的白车吃掉了H4格的黑兵的例子，要产生这个散列键值，先XOR“在H1格的白车”这个随机数(把这个图形擦掉)，然后是“在H4格的黑兵”(把这个图形也擦掉)和“在H4格的白车”(粘贴一个新的图形，代表新的车的位置)【其实顺序是无关紧要的】。

　　用相同的方法，不同的随机数，可以产生第二个散列键值，或称“散列锁”(Hash Lock)【在英语中Lock(锁)和Key(钥匙)是对应的】，它是在置换表中存储的真正有用的信息。这个技术是用来检测冲突的，如果恰巧有两个局面具有相同的散列键值，那么他们具有同样的散列锁的几率是微乎其微的。

　

历史表

　

　　“历史启发”(History Heuristic)是“杀手着法”(Killer Move)【杀手着法指能产生截断的着法，以后的连载会提到的】技术的衍生技术。一篇研究性的文章是这么解释的，历史表用来保存这些着法，在过去的搜中非常有意义(因为使用高效搜索技术的而对它进行了很深的搜索)，这个着法今后还可能用到。历史表由一个64x64的整数数组构成【着法的起始格和到达格，共有64x64种组合】，记录每种着法的数值，当搜索算法认为某个着法很有用时，它会让历史表增加这步的数值。表中的数值是用来对着法排序的，“历史上占优势”的着法会优先考虑。

　

着法产生的预处理

　

　　着法的产生(即决定特定位置下那些着法是合理的)和局面的估计一样，是象棋程序设计中计算量最大的部分。因此，在这个方面的一点预处理会对提高速度大有帮助。

　　我个人喜欢Jean Goulet在1984年写的《象棋的数据结构》(Data Structures for Chess，McGill大学出版社)一书中提到的方案，它概括为：

　

　　1. 出于着法产生的目的，棋子的颜色是无关紧要的，除了兵以外，它只朝对面走；

　　2. 对于基本的子力和它的位置，有64x5=320种组合【指除了兵以外的5种棋子，根据上一条，这些棋子是不分黑白的】，黑兵有48个格子可以放(他们后面一行是走不到的，并且一到第八行就会变成别的棋子)，白兵也有48个格子；

　　3. 从某个格子沿某个方向，可以确定一条着法“射线”，例如，后从H3格朝北走，这就是一条“射线”；

　　4. 每个格子上的每个棋子，都有确定的几条射线可以走，例如位于中央的王可以朝8个方向走，而位于盘角的象却只有一条逃生的路；

　　5. 在开始游戏之前，要计算数据库里在所有格子的所有棋子的所有射线，假设棋盘是空的(即着法只受到棋盘边缘的限制，不受其他棋子的限制)；

　　6. 当你为某个格子的某个棋子产生着法时，朝每个方向搜索直到碰到棋子为止。如果是对方的棋子，最后一种着法就是吃子的着法，如果是本方的棋子，最后一种着法就是不合理的。

　

　　有了恰当的数据库，着法的产生就变成简单得接近于线性的寻找了，几乎用不着什么计算。整个事情就掌握在这么几千个字节里，只是置换表的一个零头。

　

　　以上提到的所有技术(位棋盘、置换表、历史表和预处理数据库)都会反映在我自己的程序中，当我写完这个连载以后就会发布出来。下个月我会详细介绍着法产生的方法。

　

　　François Dominic Laramée，2000年6月

　

　　原文：http://www.gamedev.net/reference/programming/features/chess2/

　　译者：象棋百科全书网 (webmaster@xqbase.com)

　　类型：全译加译注

上一篇　国际象棋程序设计(一)：引言

下一篇　国际象棋程序设计(三)：着法的产生

返　回　象棋百科全书——电脑象棋

www.xqbase.com