Programming 版 (精华区)
发信人: zjliu (秋天的萝卜), 信区: Programming
标 题: [转载]国际象棋程序设计(三):着法的产生(转译)
发信站: BBS 哈工大紫丁香站 (Thu Nov 11 10:51:49 2004)
国际象棋程序设计(三):着法的产生
Fran?ois Dominic Laramée/文
上个月,我完成了连载的第二部分,介绍了在着法产生的预处理中涉及的数据结构
。现在我们把话题回到着法产生,详细介绍两种着法产生的策略,并解释一下在特定的
情况下如何在这两个策略中作出选择。
困境
不管你怎么对付象棋,它就是一个复杂的游戏,对于电脑来说就更是如此了。
在通常局面下,棋手要在30多种着法中选择,有些是好的,有些则是自杀棋。对于
受过训练的人来说,他能判断出大多数愚蠢和没有目的着法,甚至初学者都知道,后处
于被吃的位置时该怎么逃跑。专家(多数是通过直觉而非推理)则知道哪几步棋会比较有
力。
但是,把这些信息(特别是无意识的那些)编写到计算机里去,被证明是极端困难的
但是,把这些信息(特别是无意识的那些)编写到计算机里去,被证明是极端困难的
,连那些最强的象棋程序(除了个别程序以外,例如Hans Berliner的Hitech和它的姊妹
程序)都已经放弃这条路线了,取而代之的是“蛮力”——如果你能以足够快的速度分析
所有的着法,并且足够深远地预测他们的结果,无论你是否有一个清晰的思路,你最终
会走出一步好棋。所以,着法的产生和搜索必须越快越好,以减小蛮力方法的花费。
搜索技术将在连载的第四和第五部分介绍。这个月,我们会关注着法产生。历史上
有以下三条主要的策略:
1. 选择生成:检测棋盘,找到一部分可能的着法,把其他的全不要;
2. 渐进生成:产生一些着法,希望沿着某个着法下去,可以证明这条路线好到(或
坏到)足以中止搜索的程度(而不必再去找其他的着法)【即后面要提到的“截断”】;
3. 完全生成:产生所有的着法,希望换位表(在第二部分曾讨论过)会包含有关的信
息,从而没有必要对这些着法进行搜索。
选择生成(由之衍生出的搜索技术称为“朝前裁剪”(Forward Pruning),上世纪70
年代中期以前,几乎所有的程序都这么做的,但是从那以后就突然消失了。另外两个方
法代表了一枚硬币的两面——着法产生和搜索之间的权衡。对于那些着法产生简单并且
有很多路线可以到达相同局面的游戏(或者具备其中一个特征),例如黑白棋(Othello)和
五子棋(GoMoku),完全生成效率会更高些,而当着法产生的规则复杂的时候,渐进生成
的速度会更快。不过两种策略都是很好的策略。
【这里就黑白棋发挥几句。可能原作者认为,凡是只由黑白两子构成的游戏就一定
具有这两个特征了,就像围棋和五子棋。但是我曾经做过黑白棋的程序,这个程序已经
强到我自己无法赢它了。我发现两个特点,一是着法产生并不像想象中的那么容易,它
强到我自己无法赢它了。我发现两个特点,一是着法产生并不像想象中的那么容易,它
有点类似于中国象棋中的炮的着法,二是殊途同归的局面比起国际象棋来说少得多,原
因就在于走一步棋最多会改变18个格子的颜色,这与原作者的观点大相径庭。】
早期的策略:朝前裁剪
在1949年(确实如此),Claude Shannon提出了两个象棋程序的算法:
1. 着眼于对于所有的着法及其应对着法,循环下去;
2. 只检查“最好”的着法,这个着法由对局面的分析来确定,然后也只选择“最好
”的应对着法,循环下去。
起初,第二种选择看上去成功的可能更大。毕竟人就是这么做的,从逻辑上说在每
个结点上只考察某些着法,总比考虑所有的着法要快。不幸的是,这条理论被事实推翻
了,用选择搜索的程序,棋下得并不怎么样。它们最好的也只能达到中等俱乐部棋手的
水平,最坏的情况下还会犯低级错误。打败世界冠军(现实一点,水平发挥得稳定一些)
是遥不可及的。
在上世纪70年代中期,著名的美国西北大学Slate和Atkin的小组决定放弃复杂的“
最佳着法”生成办法,后来证明,他们绕过复杂分析所省下来的时间,足以进行全面的
搜索(检查所有的着法)。无论怎么说,这项改革善意地把“朝前裁剪”埋葬了。
下面介绍一下鲍特维尼克的工作。
上世纪70年代到80年代早期,在前世界冠军鲍特维尼克(Mikhail Botvinnik)的领导
上世纪70年代到80年代早期,在前世界冠军鲍特维尼克(Mikhail Botvinnik)的领导
下,苏联发展了一个特别的朝前裁剪的例子。鲍特维尼克认为,计算机要达到大师级水
平,唯一的途径就是像大师一样,即只考虑少量着法,但是要足够深远足够细致。他的
程序试图判定世界级选手才能掌握的局面,还要实现很高水平的作战计划。尽管这个过
程中诞生了一些吸引人的著作,揭示了只有鲍特维尼克本人才具备的大师级思路,但是
这项工作最终没有达到预期的目标。
产生全部着法
自从朝前裁剪被淘汰以后,最直接的实现完全搜索的方法是:
1. 找到局面中所有合理的着法;
2. 对他们进行排列,想要提高搜索速度就必须选择最佳的顺序;
3. 对他们逐一进行搜索,直到全部搜索完成或者被截断【运用Alpha-Beta等搜索方
法,可以在特定的情况提前中止搜索,以后的搜索就没有必要,这种情况就称为“截断
”(Cut-off),连载的第四部分会介绍这类搜索方法】。
早期的程序(例如Sargon)每次都扫描棋盘的每个格子,找有没有可以移动的棋子,
然后计算可能的着法。当时存储器是稀有矿产,额外花费CPU的时间每次把着法重新计算
一遍,是别无选择的蠢事。
如今,预处理的数据结构(就像我上个月描述的那个)可以避免大量计算,而复杂的
代码会多花费几十KB的空间。当这个超快的着法产生方法和换位表结合在一起的时候,
程序员眼前又多了一条思路——如果某些着法已经被搜索过,它的价值(保存在换位表中
程序员眼前又多了一条思路——如果某些着法已经被搜索过,它的价值(保存在换位表中
)足以产生截断,那么根本就不需要搜索任何着法了。很明显,换位表越大,并且换位可
能越多(它由游戏规则决定),换位表的作用就越明显。
这个技术不仅在概念上简单,而且普遍适用于其他游戏(但着法却不是普遍适用的,
象棋着法可以分为吃子和不吃子,其他游戏像黑白棋就不那么容易分类了)。因此,如果
试图让你的程序不止能玩一种游戏,你应该尽可能地用这个技术来代替下面要介绍的一
个技术。
一次只产生一步棋
老牌的象棋程序(至少是CHESS 4.5以前的)则采取了相反的策略——一次产生少量着
法,然后搜索,如果产生截断,就不需要产生剩下的着法了。
这种方法的流行是因为下列因素结合在一起了:
1. 搜索是不需要太大的存储器的。上世纪70年代以前的程序只能处理很小的换位表
,也没有预处理的数据结构,这些都限制了完全搜索方案(就是上一节提到的方案)的运
用。
2. 在象棋着法产生的预处理比其他游戏复杂得多,有上王车易位、吃过路兵,不同
的棋子要区别对待。
3. 通常,这个方案的说服力(就是某步棋可以产生截断的例子)在于吃子。例如,某
棋手送吃他的后,对手就会毫不犹豫地吃掉它,棋局也因此结束了。因为一个局面中能
吃子的着法不多,而且产生吃子着法相对要容易一些,所以计算吃子的着法有很多产生
截断的机会。
截断的机会。
4. 吃子是静态搜索(Quiescence Search,这个将在后面几部分提到)中需要检查的
着法(不是唯一一类着法【可能除了吃子以外就是将军了】),所以单独产生吃子的着法
是非常有效的。
所以,很多程序都是先产生吃子的着法的,而且从吃最有价值的子开始,来找到最
快的截断。有些技术是专门提高吃子着法的产生速度的,多数运用了位棋盘的技术:
CHESS 4.5 用了两个组64个的位棋盘,棋盘上的每一格对应一个位棋盘。一组由 “
这个格子上的子可以攻击的格子”的位棋盘组成,另一组正好相反,由“可以攻击这个
格子的棋子所占的格子”的位棋盘组成。所以,如果程序去找吃黑后的着法,它先从基
本位棋盘的数据库中找到黑后的位置,然后用这两组位棋盘来确定【其实只要用后一组
就可以了】攻击后的棋子的位置,并且只产生这些子的着法。
每走一步都需要维护这些位棋盘,这就需要引进很多技术,有一个称为“旋转的位
棋盘”(Rotated Bitboard)的作用最显著。对于第一组位棋盘的产生办法,我见过的最
好的论述是由James F. Swafford写的,这篇文章是在网上找到的,网址是:
http://sr5.xoom.com/_XMCM/jswaff/chessprg/rotated.htm。
【可以参阅我从Allan Liu那里整理的译文《对弈程序基本技术》专题之《数据结构
(二)——旋转的位棋盘》,现在Swafford教授的那个网站关了(这至少是5年以前的网站
了),我正在考虑写eMail给他,向他索取原文。】
对着法排序以加快搜索速度
我们下次要提到,搜索效率取决于搜索着法的顺序。着法排列的好坏直接影响到效
率——好的排列方法可以产生很多的截断,大大减小搜索树的大小减小,其结点数只有
用最坏的排列的搜索树的平方根那么多。
不幸的是,可以证明,最好的顺序应该从最佳着法开始。当然,如果你知道哪个着
法是最佳的,你还有必要做搜索吗?不过仍旧有一些“猜”的方法能确定可能比较好的
着法。例如,你可以从吃子、兵的升变(它会大幅度改变子力平衡),或者是将军(它的应
对着法很少)。紧接着是前面搜索过的在搜索树的同一层【肯定是在搜索树的不同分枝上
】上产生截断的着法(即所谓的“杀手着法”),然后是剩下的。这就是迭代加深(Iterat
ive Deeping)的Alpha-Beta搜索(下个月会详细讨论的)和历史表(上次讨论过了)的原理
。要注意的是,这些技巧区别于朝前裁减——所有的着法最终是被检测的,那些坏的着
法只是排在后边,而不排除在考虑范围以外。
最后要注意的是,在象棋中,有些着法因为被将军而是非法的。但是这些状况毕竟
是罕见情况,可以证明判断着法的合理性需要花费很多运算量。更有效的办法是所有的
着法都搜索完了再来作检查,例如某步棋走完后有个吃王的应对着法,这时才来裁定这
步棋为非法,搜索就此中止。很明显,如果搜索到这步棋以前,就产生截断了,那就不
会对这步棋的合法性作出判断了【这部分的时间不就省下来了吗】。
我的选择
在我的象棋程序里,我选择产生所有的着法,只是因为以下几个原因:
1. 我想让这个程序作为其他游戏的基础,这些游戏没有像象棋一样的吃子着法;
1. 我想让这个程序作为其他游戏的基础,这些游戏没有像象棋一样的吃子着法;
2. 我有足够的存储器来运行这个游戏;
3. 这个技术需要的代码写起来比较容易,也比较看得懂;
4. 已经有很多免费的程序,可以实现只产生吃子的着法,有兴趣的读者可以去看Cr
afty的源程序,还有James Swafford的Galahad。
我的程序的整个表现似乎比别的稍差了些,我的程序(是用Java写的,没有用别的)
不想和深蓝去比,所以我感觉这并不算太坏。
下一个月
现在我们准备探索象棋程序的核心部分——搜索技术了。这是一个很大的专题,需
要两篇文章。我们从所有游戏最基本的搜索算法开始说起,然后才是最新发展起来的专
门针对象棋的优化方法。
Fran?ois Dominic Laramée,2000年7月
出处:www.gamedev.net
译者:黄阿姨 (auntyellow@citiz.net)
类型:全译
--
╔═══════════════════╗
║★★★★★友谊第一 比赛第二★★★★★║
╚═══════════════════╝
※ 来源:·哈工大紫丁香 http://bbs.hit.edu.cn·[FROM: 202.118.229.*]
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间:4.413毫秒