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

国际象棋程序设计(三)：着法的产生 　 François Dominic Laramée/文 　 　　上个月，我完成了连载的第二部分，介绍了在着法产生的预处理中涉及的数据结构。现在我们把话 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 回到着法产生，详细介绍两种着法产生的策略，并解释一下在特定的情况下如何在这两个策略中作出选择。 　 困境 　 　　不管你怎么对付象棋，它就是一个复杂的游戏，对于电脑来说就更是如此了。 　　在通常局面下，棋手要在30多种着法中选择，有些是好的，有些则是自杀棋。对于受过训练的人来说，他能判断出大多数愚蠢和没有目的着法，甚至初学者都知道，后处于被吃的位置时该怎么逃跑。专家(多数是通过直觉而非推理)则知道哪几步棋会比较有力。 　　但是，把这些信息(特别是无意识的那些)编写到计算机里去，被证明是极端困难的，连那些最强的象棋程序(除了个别程序以外，例如Hans Berliner的Hitech和它的姊妹程序)都已经放弃这条路线了，取而代之的是“蛮力”——如果你能以足够快的速度 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 所有的着法，并且足够深远地预测他们的结果，无论你是否有一个清晰的思路，你最终会走出一步好棋。所以，着法的产生和搜索必须越快越好，以减小蛮力方法的花费。 　　搜索技术将在连载的第四和第五部分介绍。这个月，我们会关注着法产生。历史上有以下三条主要的策略： 　 　　1. 选择生成：检测棋盘，找到一部分可能的着法，把其他的全不要； 　　2. 渐进生成：产生一些着法，希望沿着某个着法下去，可以证明这条路线好到(或坏到)足以中止搜索的程度(而不必再去找其他的着法)【译注：即后面要提到的“截断”】； 　　3. 完全生成：产生所有的着法，希望置换 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf (在第二部分曾讨论过)会包含有关的信息，从而没有必要对这些着法进行搜索。 　 　　选择生成(由之衍生出的搜索技术称为“朝前裁剪”(Forward Pruning))，上世纪70年代中期以前，几乎所有的程序都这么做的，但是从那以后就突然消失了。另外两个方法代表了一枚硬币的两面——着法产生和搜索之间的权衡。对于那些着法产生简单并且有很多路线可以到达相同局面的游戏(或者具备其中一个特征)，例如黑白棋(Othello)和五子棋(GoMoku)，完全生成效率会更高些，而当着法产生的规则复杂的时候，渐进生成的速度会更快。不过两种策略都是很好的策略。 　　【这里就黑白棋发挥几句。可能原作者认为，凡是只由黑白两子构成的游戏就一定具有这两个特征了，就像围棋和五子棋。但是我曾经做过黑白棋的程序并发现两个特点，一是着法产生并不像想象中的那么容易，它有点类似于中国象棋中的炮的着法，二是殊途同归的局面比起国际象棋来说少得多，原因就在于走一步棋最多会改变18个格子的颜色，这与原作者的观点大相径庭。】 　 早期的策略：朝前裁剪 　 　　在1949年(确实如此)，Claude Shannon提出了两个象棋程序的算法： 　 　　1. 着眼于对于所有的着法及其应对着法，循环下去； 　　2. 只检查“最好”的着法，这个着法由对局面的分析来确定，然后也只选择“最好”的应对着法，循环下去。 　 　　起初，第二种选择看上去成功的可能更大。毕竟人就是这么做的，从逻辑上说在每个结点上只考察某些着法，总比考虑所有的着法要快。不幸的是，这条理论被事实推翻了，用选择搜索的程序，棋下得并不怎么样。它们最好的也只能达到中等俱乐部棋手的水平，最坏的情况下还会犯低级错误。打败世界冠军(现实一点，水平发挥得稳定一些)是遥不可及的。 　　在上世纪70年代中期，著名的美国西北大学Slate和Atkin的小组决定放弃复杂的“最佳着法”生成办法，后来证明，他们绕过复杂分析所省下来的时间，足以进行全面的搜索(检查所有的着法)。无论怎么说，这项改革善意地把“朝前裁剪”埋葬了。 　　下面介绍一下鲍特维尼克的工作。 　　上世纪70年代到80年代早期，在前世界冠军鲍特维尼克(Mikhail Botvinnik)的领导下，苏联发展了一个特别的朝前裁剪的例子。鲍特维尼克认为，计算机要达到特级大师级水平，唯一的途径就是像特级大师一样，即只考虑少量着法，但是要足够深远足够细致。他的程序试图判定世界级选手才能掌握的局面，还要实现很高水平的作战 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 。尽管这个过程中诞生了一些吸引人的著作，揭示了只有鲍特维尼克本人才具备的特级大师级思路，但是这项工作最终没有达到预期的目标。 　 产生全部着法 　 　　自从朝前裁剪被淘汰以后，最直接的实现完全搜索的方法是： 　 　　1. 找到局面中所有合理的着法； 　　2. 对他们进行排列，想要提高搜索速度就必须选择最佳的顺序； 　　3. 对他们逐一进行搜索，直到全部搜索完成或者被截断【运用Alpha-Beta等搜索方法，可以在特定的情况提前中止搜索，以后的搜索就没有必要，这种情况就称为“截断”(Cut-off)，连载的第四部分会介绍这类搜索方法】。 　 　　早期的程序(例如Sargon)每次都扫描棋盘的每个格子，找有没有可以移动的棋子，然后计算可能的着法。当时存储器是稀有矿产，额外花费CPU的时间每次把着法重新计算一遍，是别无选择的蠢事。 　　如今，预处理的数据结构(就像我上个月描述的那个)可以避免大量计算，而复杂的代码会多花费几十KB的空间。当这个超快的着法产生方法和置换表结合在一起的时候，程序员眼前又多了一条思路——如果某些着法已经被搜索过，它的价值(保存在置换表中)足以产生截断，那么根本就不需要搜索任何着法了。很明显，置换表越大，并且置换可能越多(它由游戏规则决定)，置换表的作用就越明显。 　　这个技术不仅在概念上简单，而且普遍适用于其他游戏(但着法却不是普遍适用的，象棋着法可以分为吃子和不吃子，其他游戏像黑白棋就不那么容易分类了)。因此，如果试图让你的程序不止能玩一种游戏，你应该尽可能地用这个技术来代替下面要介绍的一个技术。 　 一次只产生一步棋 　 　　老牌的象棋程序(至少是CHESS 4.5以前的)则采取了相反的策略——一次产生少量着法，然后搜索，如果产生截断，就不需要产生剩下的着法了。 　　这种方法的流行是因为下列因素结合在一起了： 　 　　1. 搜索是不需要太大的存储器的。上世纪70年代以前的程序只能处理很小的置换表，也没有预处理的数据结构，这些都限制了完全搜索 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 (就是上一节提到的方案)的运用。 　　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年以前的网站了)，但事实证明，他的那套方案并不那么有效，有误导之嫌。】 　 对着法排序以加快搜索速度 　 　　我们下次要提到，搜索效率取决于搜索着法的顺序。着法排列的好坏直接影响到效率 好的排列方法可以产生很多的截断，大大减小搜索树的大小减小，其结点数只有用最坏的排列的搜索树的平方根那么多。 　　不幸的是，可以证明，最好的顺序应该从最佳着法开始。当然，如果你知道哪个着法是最佳的，你还有必要做搜索吗？不过仍旧有一些“猜”的方法能确定可能比较好的着法。例如，你可以从吃子、兵的升变(它会大幅度改变子力平衡)，或者是将军着法开始(它的应对着法很少)。紧接着是前面搜索过的在搜索树的同一层【肯定是在搜索树的不同分枝上】上产生截断的着法(即所谓的“杀手着法”)，然后是剩下的。这就是迭代加深(Iterative Deeping)的Alpha-Beta搜索(下个月会详细讨论的)和历史表(上次讨论过了)的原理。要注意的是，这些技巧区别于朝前裁减——所有的着法最终是被检测的，那些坏的着法只是排在后边，而不排除在考虑范围以外。 　　最后要注意的是，在象棋中，有些着法因为被将军而是非法的。但是这些状况毕竟是罕见情况，可以证明判断着法的合理性需要花费很多运算量。更有效的办法是所有的着法都搜索完了再来作检查，例如某步棋走完后有个吃王的应对着法，这时才来裁定这步棋为非法，搜索就此中止。很明显，如果搜索到这步棋以前，就产生截断了，那就不会对这步棋的合法性作出判断了【这部分的时间不就省下来了吗】。 　　【这里就本节提到的“杀手”着法作一些发挥：大多数程序往往不是生成全部着法的，而是先判断杀手着法的合理性(判断着法合理性所做花的时间要比产生全部着法少得多)，如果是合理着法就先搜索这些着法。因为杀手着法是产生截断几率很高的着法，所以很有可能不需要生成着法了。 　　另外，排序技术也非常有讲究，因为排序所花的时间可能会比着法产生的时间更多。排序的算法很多，常用的有冒泡排序、Shell排序、快速排序等，我个人倾向于最慢的冒泡排序，原因是冒泡排序每扫描一趟会产生一个最大值，希望它能产生截断而没有必要对后面的着法再进行排序。】 　 我的选择 　 　　在我的象棋程序里，我选择产生所有的着法，只是因为以下几个原因： 　　1. 我想让这个程序作为其他游戏的基础，这些游戏没有像象棋一样的吃子着法； 　　2. 我有足够的存储器来运行这个游戏； 　　3. 这个技术需要的代码写起来比较容易，也比较看得懂； 　　4. 已经有很多免费的程序，可以实现只产生吃子的着法，有兴趣的读者可以去看Crafty的源程序，还有James Swafford的Galahad。 　 　　我的程序的整个表现似乎比别人的稍差了些【我想可能就是受了James Swafford的误导吧】，我的程序(是用Java写的，没有用别的)不想和深蓝去比，所以我感觉这并不算太坏。 　 下一个月 　 　　现在我们准备探索象棋程序的核心部分——搜索技术了。这是一个很大的专题，需要两篇文章。我们从所有游戏最基本的搜索算法开始说起，然后才是最新发展起来的专门针对象棋的优化方法。 　 　　François Dominic Laramée，2000年7月 　 　　原文：http://www.gamedev.net/reference/programming/features/chess3/ 　　译者：象棋百科全书网 (webmaster@xqbase.com) 　　类型：全译加译注