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毫秒