也说棋类游戏

    也说棋类游戏

一.引子

之前自己编写过一点关于棋类游戏的代码，所以对于这类游戏的大致构成也算是有一些肤浅的认识，前一阵子突然想到应该将这些个零散知识好好总结一番，以算作为自己学习的一点交代。可恨这不总结还好，一总结才发现自己以前自认为通晓的知识原来还是一知半解，更是发现了一堆自己先前遗漏的知识，唉，真可谓学海无涯啊......不过本着学习“八成”原则（这是我前阵子看过的一本书中的观点，感觉还是颇为心有戚戚的，意思大抵是学习过程中不要太过求全求通，慢慢学下去自会变全变通，书名曰《超级学习法》，是本老书了，作者是一名日本的教授，具体姓氏已经不记得了，有兴趣的朋友可以Google看看），自己还是就着多有纰漏的知识储备总结了起来，并且还煞有其事的编写了一些代码，本想借着这篇博文写一写自己总结来的看法，但后来想想与其自己肤浅的在这搬运知识，还不如将自己在学习过程中参考的一些文献介绍给大家，毕竟这原版终归要胜过盗版啊 ：）

二.起兴

记得那时为了完成自己的“五子棋游戏”，我千搜万集了许多资料，包括很多的专业论文、学文论文，只可惜在其中我并没发现许多有价值的东西，倒是对我国普遍的“抄袭”现象有了更深一层的认识，后来在网上胡乱Google了一阵，倒被我发现了不少的金矿！一个名为象棋百科全书的网站，虽然“门面”不大，“招牌”不显，但是却存有很多出色的棋类游戏编程介绍，不仅内容详实，而且由浅入深，一篇篇都可谓不可多得，对于棋类游戏感兴趣的读者一定不要错过啊！（ 本人申明：我不是托儿，真不是 ：） ），在此就索性转载一篇，就算是小小的起兴吧：

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

François Dominic Laramée/文 

（ 特注：【】中内容是翻译者的评注 ）

　　这是国际象棋程序设计连载的第一部分，本连载共有六部分，他们不仅仅是针对象棋【译注：以后如不特别指出，都指国际象棋】的，还可以运用到别的益智类游戏中。 　　在人工智能领域中，专家对象棋进行了大量卓有成效的研究，这其中就有电脑对抗卡斯帕罗夫等世界冠军的比赛。象棋在人工智能上的地位，就相当于果蝇在遗传学上的地位，举足轻重。我的连载将着重介绍人工智能的程序设计艺术，这其中包括“深蓝”(Deep Blue)等著名程序。 　　

  我的连载从2000年4月开始，每个月一次，到10月结束的时候，我会用Java写一个简单的程序来实现对弈。到时候你们可以从我的网站上随便下载，耐心地等吧。 　 

信息完备的游戏

象棋是“信息完备”的游戏，因为游戏双方面对的局面是同一个局面，任何一方所掌握的棋子及其位置的信息是一样的。除了象棋以外，西洋跳棋(Checkers)、围棋(Go)、五子棋(Go-Moku)、西洋双陆棋(Backgammon)、黑白棋(Othello)【也有称Reversi的，可译为“翻棋”】可等也属于这一范畴。但是纸牌游戏却不是，因为你不知道对手手上的牌是什么【在中国的棋类游戏中，陆站棋(起源于欧洲)和四国大战棋也不是】。 　　

  我的连载中将提到各种算法，大多数算法对所有的信息完备的游戏都是有效的，只是细节上有所不同罢了。很明显，无论棋盘、着法、位置等因素有那些，搜索算法就是搜索算法，它不会因为游戏规则而改变。 　 

我们需要什么？

  能下棋的电脑软件至少要包括下列组件： 　 　　

1. 棋盘的表示方法，即局面在存储器中的存储方法，程序是根据它来分析局面的； 　

2. 掌握规则，即什么样的着法是合理的，如果程序连不合理的着法都不能检测出来，那么对手就可以利用这种着法来欺骗程序； 　　

3. 找出所有合理着法的算法，这样程序就可以从这些着法中找到最好的，而不是随便找一种着法； 　　

4. 比较方法，包括比较着法的方法和比较局面的方法，这样程序就可以选择最佳的着法； 　　5. 用户界面。 　 　　

  本连载将涉及以上除了用户界面以外的所有内容，用户界面在所有二维棋类游戏中都是差不多的，这里就不作介绍了。接下来将对以上几个部分作逐一介绍，并且引出许多重要的概念。 　 

棋盘的表示方法

在早期的程序设计过程中，存储器是非常有限的(有些程序只用8K或更少的存储器)，所以最简单、最节省的表示方法就是最有效的方法。一个典型的国际象棋棋盘可以用一个8x8的数组表示，棋盘上的每个格子用一个字节表示——空的格子用0，黑方的王用1，等等。 　　如今，象棋程序可以在64位计算机上运行了，精心设计的“位棋盘”表示诞生了。在60年代后期，位棋盘在苏联诞生，一个位棋盘由一个64位的字【“字”是计算机中一次运算所涉及的存储单元，我认为当时还没有字长为64位的计算机，所以一个位棋盘应该由多个较短的字来构成，如8个8位的字或4个16位的字，即便是现在的个人电脑上，一个位棋盘也必须由两个32位的字构成】来表示局面中的某个状态，一位代表一个格子。例如，一个位棋盘能表示“所有被黑兵占有的格子”，或者“处于e3格的后可以走的格子”，或者“被黑马攻击的白子所处的格子”，等等。位棋盘用途广泛，并且具有很快的运算速度，因为局面分析时要做大量的逻辑运算【就是“与或非”运算，也称布尔代数】，而一个位棋盘的运算只需要一次操作就可以了。 　　

  这部分内容将在连载的第二部分作详细介绍。 　

着法的产生

  所谓棋类游戏的规则，指的就是某一方可以走哪些着法。某些游戏很容易就找到合理着法，例如在井字棋中【Tic-Tac-Toe，在3x3的棋盘上轮流占格子，先在同一条线(横线、纵线或斜线)上占有3枚棋子者得胜】，所有空的格子都是合理着法。但是在象棋中，情况就有些复杂了，每个棋子都有它特定的着法，例如兵吃子时走斜线，而不吃子时走纵线，又例如把王走到被将军的格子是不允许的，还有诸如“吃过路兵”【法语en passant】、兵的升变、王车易位等着法只有在特殊场合才是合理的。 　　

  事实上在象棋程序设计中，着法的产生已经被证实为最复杂和最费时的事。幸运的是，着法的产生有一些预处理的技巧，我还会介绍一些数据结构，它们能显著提高着法产生的速度。 　　

  这部分内容将在连载的第三部分作详细介绍。 　 

搜索技巧

  对于计算机来说，判断一个着法是好的或坏的，并不是件容易的事。判断着法优劣的最佳办法，就是看它们的后续结果，只有推演以后一系列的着法，才能确定看那步是好的。在保证不犯错误的前提下，我们要设想对手会走出最好的应着。这一基本原理称为“最小-最大”搜索算法，它是所有象棋程序的基础。 　　

  不幸的是，“最小-最大”法的运算量是O(bn)【数学上指它和bn是一个数量级的】，b(分支因子)指平均每步的合理着法【有研究表明，在国际象棋中这个值约为38，中国象棋则更多些，为42(这是中国象棋程序“七星大师”的作者赵德志的研究结果)】，n(深度)指思考的步数(一回合有两步)。所以当步数增长时，运算量以几何级数迅速增长，如果要思考得更深一些，就必须用更为合理的算法。其中，迭代加深的Alpha-Beta搜索、NegaScout搜索和MTD(f)搜索是最基本的算法，这些会在连载的第四部分介绍。除此以外，还要依靠数据结构和启发式算法的帮助，启发式算法是增强棋力的算法，例如置换表(Transposition Tables)、历史启发和将杀启发(History/Killer Heuristic)等。 　　

  在象棋程序设计中，另一个头痛的问题是“水平线效应”(Horizon Effect)，它首先由Hans Berliner提出。假设你的程序的搜索深度是8步，并且程序算出对手会在第六步捉死你的后。按照程序自己的设想，它会献出象来延缓后的捉死(假定这样做可以让后在第10步才被捉死)，因为程序只能看到8步。从程序的角度看，后是被“保住”了，因为在它的搜索范围内后没有被捉死，但事实上却多丢了一个象。从这个例子可以看出，要把程序的工作重心放置到位，并不是一件简单的事情【意思是，某些变化没有必要搜索得太深，而关键的变化需要更深层次的搜索】，如果把每条变化都搜索到同一深度，那么结果是自取灭亡。很多技术是用来克服水平线效应，在连载的第五部分关于高级搜索的阐述中，将要介绍静态搜索(Quiescence Search)和深蓝(Deep Blue)的单步延伸(Singular Extensions)。 　 

评价局面

  最后，程序必须有一个估计局面(占优或处于劣势)的方法。局面估计方法完全取决于规则(即子的走法)——在象棋中，“子力平衡”(Material Balance)是主导因素，因为一个小小的兵的领先就可能足以保证优势一方取得胜利【而在中国象棋中，多一个兵算不了什么，这足以证明本节的观点——局面估计方法完全取决于规则】，而在五子棋中却没什么影响，在黑白棋里，根据子力上的数值分析局面则完全会成为误导，你可能一直处于领先状态，但最后几步局面却翻了盘。 　　

  建立有效的局面评估方法，这常常会成为程序设计中的难点和焦点。连载的第六部分将详细阐述著名象棋程序的局面评估方法，其中包括Chess 4.5、Cray Blitz和Belle(尤物)。 　 

结论

  我们已经找到了完成拼版的所需要的碎片，现在是开始动手做的时候了。下个月我将介绍最常用的棋盘表示方法，敬请关注。 

怎么样，还不赖吧，如果你觉得值得继续品味，那还等什么，赶快系好安全带上路吧！

三.结语

最后想说说的就是自己为了总结而写的一些代码，由于棋类游戏的搜索知识大抵都是相通的，所以我认为完全可以进行一个统一的抽象，循着这个思路，我便尝试着写下了现在的这些代码，具体的思路可以照着上面所转载的论文主题进行阐述：

1.棋盘的表示方法：在抽象层（基类）中并未存在任何用于棋盘表示的数据结构，而在用作示例的具体层（派生类）中我则选用了最为简单的数组表示法，即使用大小与棋盘一致的数组来表示棋局的当前状态，但出于容量、速度方便的考虑，位棋盘自然是更好的选择，只是相应的操作复杂度也提升了。

2.着法的产生：同样的道理，抽象层次并不固定着法生成的方法，相应的只是提供了一个抽象接口以便具体层的自行实现，由于程序中采用“黑白棋”作为示例棋类，并且处于简单考虑，所以方法相对简单，仅是生成合法着法。

3.搜索技巧：由于棋类游戏的搜索方法大同小异，所以我在抽象层中便实现了默认的搜索函数代码，但具体层根据需要亦可重载改写，这个默认实现综合运用了一些棋类搜索技巧：例如 散列技术、PVS、期望搜索和MTD(f)、单步延伸与迭代加深等等。

4.评价局面：同着法产生一样，抽象层留有抽象接口以便具体层可以实现这项功能，示例程序的评价局面实现非常简单，仅是统计棋子数目而已。

  好了，代码就介绍至此吧，有兴趣的朋友可以看看　：）

　最后附上程序的ＵＭＬ类图（比较粗糙，多多包涵）：