Programming 版 (精华区)

发信人: zjliu (秋天的萝卜), 信区: Programming
标  题: [转载]国际象棋程序设计(一)：引言(转译)
发信站: BBS 哈工大紫丁香站 (Thu Nov 11 10:50:30 2004)

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

Francois Dominic Laramee/文

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

Deep Blue)等著名程序。
　　我的连载从2000年4月开始，每个月一次，到10月结束的时候，我会用Java写一个简

单的程序来实现对弈。到时候你们可以从我的网站上随便下载，耐心地等吧。

信息完备的游戏

　　象棋是“信息完备”的游戏，因为游戏双方面对的局面是同一个局面，任何一方所
掌握的棋子及其位置的信息是一样的。除了象棋以外，西洋跳棋(Checkers)、围棋(Go)
掌握的棋子及其位置的信息是一样的。除了象棋以外，西洋跳棋(Checkers)、围棋(Go)
、五子棋(Go-Moku)【这是译者猜的，可能不是，因为五子棋流行于日本，名称好像叫Re

nju】、西洋双陆棋(Backgammon)、黑白棋(Othello)【也有称Reversi的，可译为“翻棋

”】可等也属于这一范畴。但是纸牌游戏却不是，因为你不知道对手手上的牌是什么【
在中国的棋类游戏中，陆站棋(起源于欧洲)和四国大战棋也不是】。
　　我的连载中将提到各种算法，大多数算法对所有的信息完备的游戏都是有效的，只
是细节上有所不同罢了。很明显，无论棋盘、着法、位置等因素有那些，搜索算法就是
搜索算法，它不会因为游戏规则而改变。

我们需要什么？

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

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

　　2. 掌握规则，即什么样的着法是合理的，如果程序连不合理的着法都不能检测出来

，那么对手就可以利用这种着法来欺骗程序；
　　3. 找出所有合理着法的算法，这样程序就可以从这些着法中找到最好的，而不是随

便找一种着法；
　　4. 比较方法，包括比较着法的方法和比较局面的方法，这样程序就可以选择最佳的

着法；
　　5. 用户界面。

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

棋盘的表示方法

　　在早期的程序设计过程中，存储器是非常有限的(有些程序只用8K或更少的存储器)
，所以最简单、最节省的表示方法就是最有效的方法。一个典型的国际象棋棋盘可以用
一个8?8的数组表示，棋盘上的每个格子用一个字节表示——空的格子用0，黑方的王用1

，等等。
　　如今，象棋程序可以在64位计算机上运行了，精心设计的“位棋盘”表示诞生了。
在上世纪60年代后期【原文写于2000年，就当时来说并不能算“上世纪”】，位棋盘在
苏联诞生，一个位棋盘由一个64位的字【“字”是计算机中一次运算所涉及的存储单元
，译者认为当时还没有字长为64位的计算机，所以一个位棋盘应该由多个较短的字来构
成，如8个8位的字或4个16位的字，即便是现在的个人电脑上，一个位棋盘也必须由两个

32位的字构成】来表示局面中的某个状态，一位代表一个格子。例如，一个位棋盘能表
示“所有被黑兵占有的格子”，或者“处于e3格的后可以走的格子”，或者“被黑马攻
击的白子作处的格子”，等等。位棋盘用途广泛，并且具有很快的运算速度，因为局面
分析时要做大量的逻辑运算【就是“与或非”运算，也称布尔代数】，而一个位棋盘的
运算只需要一次操作就可以了。
　　这部分内容将在连载的第二部分作详细介绍。

着法的产生
着法的产生

　　所谓棋类游戏的规则，指的就是某一方可以走哪些着法。某些游戏很容易就找到合
理着法，例如在井字棋中【Tic-Tac-Toe，在3?3的棋盘上轮流占格子，先在同一条线(横

线、纵线或斜线)上占有3枚棋子者得胜】，所有空的格子都是合理着法。但是在象棋中
，情况就有些复杂了，每个棋子都有它特定的着法，例如兵吃子时走斜线，而不吃子时
走纵线，又例如把王走到被将军的格子是不允许的，还有诸如“吃过路兵”【用法语en
passant表示】、兵的升变、王车易位等着法只有在特殊场合才是合理的。
　　事实上在象棋程序设计中，着法的产生已经被证实为最复杂和最费时的事。幸运的
是，着法的产生有一些预处理的技巧，我还会介绍一些数据结构，它们能显著提高着法
产生的速度。
　　这部分内容将在连载的第三部分作详细介绍。

搜索技巧

　　对于计算机来说，判断一个着法是好的或坏的，并不是件容易的事。判断着法优劣
的最佳办法，就是看它们的后续结果，只有推演以后一系列的着法，才能确定看那步是
好的。在保证不犯错误的前提下，我们要设想对手会走出最好的应着。这一基本原理称
为“最小-最大”搜索算法，它是所有象棋程序的基础。
　　不幸的是，“最小-最大”法的运算量是O(bn)【数学上指它和bn是一个数量级的】
，b(分支因子)指平均每步的合理着法，n(深度)指思考的步数(一回合有两步)。所以当
步数增长时，运算量以几何级数迅速增长，如果要思考得更深一些，就必须用更为合理
的算法。其中，迭代加深的Alpha-Beta搜索、NegaScout搜索和MTD(f)搜索是最基本的算

的算法。其中，迭代加深的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)是主导因素，因
为一个小小的兵的领先就可能足以保证优势一方取得胜利【而在中国象棋中，这算不了
什么，这足以证明本节的观点——局面估计方法完全取决于规则】，而在五子棋(Go-Mok

u)中却没什么影响，在黑白棋(Othello)里，根据子力上的数值分析局面则完全会成为误

导，你可能一直处于领先状态，但最后几步局面却翻了盘。
u)中却没什么影响，在黑白棋(Othello)里，根据子力上的数值分析局面则完全会成为误

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

结论

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

　　Francois Dominic Laramee，2000年4月

　　出处：www.gamedev.net
　　译者：黄阿姨 (auntyellow@citiz.net)
　　类型：全译
--
╔═══════════════════╗
║★★★★★友谊第一  比赛第二★★★★★║
╚═══════════════════╝


※ 来源:·哈工大紫丁香 http://bbs.hit.edu.cn·[FROM: 202.118.229.*]