国际象棋顺序设想(五):低级搜索要领
 
François Dominic Laramée/
 
  哇,看上去似乎有许多人在看我的连载,我的脸都红了!
  这是倒数第二篇美文,咱们会引见和搜索有关的低级手艺,他们既能提升速率,又能增强棋力(也许只需一个功用)。他们中有许多,观点上(顺序代码能够不可)能够运用就任何2人游戏中,然则让它们用到一些详细问题上,对许多读者来说还要求加工。
 
干嘛要那末贫苦?
 
  到此为止,咱们知道的一切搜索算法,都把局势推演到流动的深度。然则这一定是件坏事。譬喻,假定你的顺序最多能够用迭代加深的Alpha-Beta算法搜索到5层,那末来看下这几个案例:
 
  1. 顺着某条线路,你发现在第3层有将死或逼和的局势。显著你不想再搜索下去了,由于游戏的一直目的到达了。搜索5层不只是虚耗时刻,而且能够会让计算机自身把自身引入分歧适的状态。
  2. 现在假定在5层你吃到了兵。顺序能够会以为这个局势稍稍有益,而且会这么走下去。然则,若是你看得更长远些,能够会发现吃了兵以后你的后就处于被进击的状态,完了!
  3. 最终,假定你的后被捉了,不论你怎样走,她会在第4层被对手吃掉,然则有一条线路可以让她僵持到第6层。若是你的搜索深度是5,那末后在第4层被吃掉的线路会被检测出来,这些状况会评价成灾难局势,然则唯一能使后在第6(超越了搜索树)捉到的那条线路,关于计算机来说被吃是不能被发现的,因而它会以为后很平安,从而打一个较高的分数。现在,为了让后被吃的状况扫除在搜索树之外,唯一的设施就是调虎离山,这样做是很冒险的——牺牲一些局势,照样有能够让对手犯下毛病使你的后溜掉的。那末若是你要经由历程牺牲一个车来减慢后的被吃呢?对计算机来说,在第4层丢车要比丢后损失小,以是在这个搜索水平上,它宁愿丢一个那末大的子,来推延谁人不幸的后的被吃了。(固然在随后一回合里,计算机会发现不论怎样走,它的后会在第4层被吃掉,而且车丢得稀里懵懂。)很早之前Hans Berliner就把这个状况称为“水平线效应”,这在很大水平上能够经由历程前面即将引见的“静态搜索”来革新。
 
  最终要说一句:象棋中的许多局势(其他游戏也一样)太弗成展望了,真实很难适外地评价。评定函数只能在“恬静”的局势下起功用,即这些局势在不久的未来不能够发作很大的转变。这将是咱们引见下一个内容。
 
致意静!
 
  有两种评价局势的设施——静态评价(看局势会怎样生长)和静态评价(看它像甚么样子容貌,不去管未来怎样)。静态评价要求深切的搜索。咱们刚刚说到,局势在不久的未来不能够发作很大的转变的状况下,静态评价才是可行的。这些一定稳固的局势称为“恬静”(Quiet)或“幽静”(Quiescent)的局势,它们要求经由历程“静态搜索”(Quiescence Search)来到达。
  静态搜索的最基本的观点是指:当顺序搜索到流动深度时(例如6),咱们选择性地连续各条线路,只搜索“非静态”的着法,直到找到静态着法为止,这样才最先评价。
  找到静态局势是要求游戏知识的。譬喻,甚么样的着法能够引发棋盘上子力平衡的伟大改动?关于象棋来说,子力平衡会致使局势的猛烈转变,以是任何改动子力的着法就是——吃(稀奇是吃主要棋子)、兵的升变都是,而将军也是值得一看的(仅仅是能致使将死的将军)【译注:我以为任何将军都应当斟酌出来,由于它会致使抽吃、长将等注定性局势的发生】。在西洋棋里,吃子和升变【西洋棋的棋子分兵棋(Man)和王棋(King),兵棋冲究竟线就酿成王棋,因而我判定它是国际象棋的前身】都是选择。在是非棋中,每一步都必需吃子,而且“子力平衡”【仅仅指现在棋子的若干,它和一直棋子的若干没多大联系】在短时刻内翻覆无常,以是能够说它基础不存在“静态局势”!
  我自身的顺序用了简朴的静态搜索,它只斟酌一切带吃子着法的线路(x层完整搜索以后)。由于一般局势下没有太多恰当的吃子着法,以是静态搜索的分枝因子异常小(匀称在4-6,双方在吃子后会迅速下落到0)。然则,静态搜索算法要剖析少量的局势,它能够会占用悉数处置责罚器一半上述的时刻。当你的顺序运用这个计划之前,你要一定你是否是要求用它。
  当没有吃子发作时,我的顺序才最先评定局势。其效果就是将层数流动的搜索树作选择性的延长,它能战胜大少数由“水平线效应”发生的结果。
 
主要的空着
 
  有个加速象棋顺序速率的有用要领,就是引入空着的观点。
  简而言之,空着就是自身不走而让对手连走两次。大少数局势中,甚么事都不做显著不是设施,你总是必需做点事项来革新局势。(忠实说,有一些“走也不是,不走也不是”的局势,空着实在是你的最好选择,但不能走,这类 “自愿移动”(Zugzwang)局势是没有希冀的,以是没需要对计算机感应失望。)
  在搜索中让计算机走空着,能够提升速率和准确性。譬喻:
 
  1. 假定局势临你来说是压服性优势,纵使你甚么都不走,对手也没有设施挽回。(用顺序的术语来说,你不走棋也能够发生Beta截断。)假定这个局势正本准备搜索N层,而空着庖代了悉数搜索树(你的一符恰当着法用空着庖代了),而且你的分枝因子是B,那末搜索空着就相即是只搜索了一个N-1层的分枝,而不是B个这样的分枝。在中局阶段一般B=35,以是空着搜索只斲丧了完整搜索所需的3%的资源。若是空着搜索注解你以前壮大到没有需要再走棋(即会发生截断)的田地,那末你少花了97%的气力。若是没有,你就必需搜检恰当的着法,这只是多花了3%的气力。匀称来说,收益是伟大的。【固然,空着搜索关于处置责罚“自愿移动∷刂势照样有负面功用的,稀奇是在残局中,这个功用相等显著。能够参考《棋战顺序基本手艺》专题之《低级搜索要领——空着裁剪》一文。】
  2. 假定在静态搜索中,你面临一个只需车吃兵一种吃子着法的局势,然则接上去对手就会走马吃车。你最好不去吃子而走其他不吃子的着法对吗?你能够在静态搜索中拔出空着来模拟这类状况,若是在某个局势下空着比其他吃子着法有益,那末你连续吃子就是坏的选择。而且由于最好着法是静态着法,以是这个局势就是评价函数能够功用的局势。
 
  总的来说,空着启示会增加20%75%的搜索时刻。这固然值得,稀奇是当你把这个要领用在静态搜索算法上的时刻,就像改动“走子的一方”这类代码一样简朴,用不了十行就好了。
  【许多书上把“空着”这一手艺称为“空着启示”(Null-Move Heuristic),本文就是这个意义,现实上在历史表、迭代加深等启示的功用下,空着启示以前意义不大了。现在绝大少数顺序都运用了称为“空着的向前裁剪”(Null-Move Forward Pruning)的搜索(它跟空着启示是有区分的),只管是一种不完整搜索,但它却是诸多向前裁剪的搜索中最有用的一个。】
 
希冀搜索和MTD(f)
 
  一般的老式Alpha-Beta搜索对某个局势一直的“最小-最大”值没有假定。看上去它斟酌就任何状况,不论有多失常。然则,若是你有一个异常好的主张(譬喻由于你在做迭代加深,从而想到前一次的效果),你就会找出那些和你预期的差得远的线路,预先把它们截断。
  譬喻,假定一个局势的值靠近于0,由于异常平衡。现在来假定对一个外部结点作先前的评定,它的值在+20,000【这里的单元应当是“千分兵值”, 即1000相即是一个兵的价值,那末马和象即是3000,车5000,后9000,其他重点要点也折算成这个值,而UCI和谈中则用“百分兵值”,由于没有需要过于准确】,那末你能够有充裕自信心对它截断。
  这就是“希冀搜索”(Aspiration Search)面前的头脑,一个Alpha-Beta搜索的变种,最先时用从负无限大到正无限大来限制搜索局限,然后在希冀值左近设置小的窗口。若是现实数值正好落在窗口之内,那末你赢了,你会准确无误地找到线路,而且比其他的线路快(由于许多线路都被截断了)。若是没有,那末算法就失利了,然则这个毛病是很随意纰漏被检测的(由于“最小-最大”值就是其中一条界限),你必需虚耗一点时刻,用一个更大的窗口重新搜索。若是前面的状况比前面的状况多,那末整体上你照样赢了。很显著,你预先猜的数值越好,这个手艺的奏效就越大。
  在上世纪90年月中期,研讨员Aske Plaat把希冀搜索拓展为一个逻辑问题:若是你把带希冀的Alpha-Beta搜索的窗口巨细设定成0,将会发作甚么事?它固然永远不会胜利。然则若是它胜利了,那速率将是惊人的,由于它把险些一切的线路全都截断了。现在,若是失利意味真现实数值缺乏你的预计,那末你用稍低点的宽度为零的窗口再试一次,一次又一次下去。这样,你就即是用Alpha-Beta搜索来做某个“最小-最大”值的拆半查找(Binary Search),直到你一直找到谁人宽度为零的窗口。
  这个伟大的想象宣布在一个网站上:http://theory.lcs.mit.edu/~plaat/mtdf.html,它的详细完成称为MTD(f)搜索算法,只需十多行。加上Alpha-Beta搜索和置换表的运用,MTD(f)显现出惊人的效能,还长于做并行盘算。它在“粗拙”(简朴且快速)的局势剖析中运转得更好,很显著,若是局势评价的最小单元越大(譬喻从0.001个兵增长到0.1个兵),它搜索的步数就越少。
  在Alpha-Beta搜索的变种当中,另有许多具有普遍用途的算法(譬喻名声散乱的NegaScout,我宁肯给呆子讲狭义一定论,也不想给你们讲这些)【之以是说NegaScout名声散乱,是由于它的发现者Reinefeld首次宣布该算法时,顺序中有一个致命毛病,致使搜索效能大幅度下降,以至缺乏一般的Alpha-Beta搜索,现在这个算法更多地被PVS(主要变例搜索)庖代,由于它更随意纰漏体谅】,然则Plaat僵持以为MTD(f)是至今为止效能最高的算法。我就信了他的话,以是我的顺序里用了MTD(f),你们能够会叹息这个算法是何等冗长啊!
  【MTD(f)在悉数历程当中只运用极小窗口,而且每次都从根结点最先的,这个历程极大水平地依托于置换表,称为“用存储器增强的探索驱动器”(Memory-enhanced Test Driver,简称MTD),它只要求通报两个参数(深度n和探索值f),故得名为MTD(n,f),缩写为MTD(f)。现实运作中MTD(f)是以迭代的形式收敛的,而不是原作者所说的拆半查找。
  在Plaat的美文中,MTD(f)的代码有10行,而跟它异曲同工的算法PVS,则只比一般的Alpha-Beta多了5行前后,因而很新鲜原作者(Laramée)为甚么这样看好MTD(f)MTD(f)在并行盘算上实在比PVS有优势,由于Plaat等人拿MTD(f)PVS算法的对照是在并行机上完成的,才得出MTD(f)优于PVS的结论,而现实上大局部的顺序用的都是PVS。】
 
单步延长
 
  在咱们完毕这个主题之前,这是最终一个话题。在象棋中,很多若干着法显著比其他的好,这样就能够够没需要搜索其他的转变了。
  譬喻,假定你在迭代加深历程当中正在做深度为N - 1的搜索,发现某步的评分为+9000(即你吃了对方的后),而其他都缺乏0。若是像竞赛一样想勤俭时刻,你会跳过前面的N层搜索而对这步停止N层搜索【关于这步来说,搜索加深了一层,关于优势局势来说,优势应当是越来越大的,以是加深一层后评分应一般要高】,若是这步分外搜索的评分不比预期的低,那末你能够假定这步棋会比其他着法都好,这样你就能够够提早完毕搜索了。(记住,若是匀称每层有35种恰当着法,那末你就能够够节约97%的时刻!)
  深蓝的小组生长了这个头脑并提出了“单步延长”(Singular Extension)的观点。若是在搜索中某步看上去比其他转变好许多,它就会加深这步搜索以确认里边没有圈套。(现实历程远比这里说的要庞大,固然基本头脑没变。)单步延长是消耗时刻的,对一个结点增长一层搜索会使搜索树的巨细翻一番,评价局势的盘算量同时也翻一番。换句话说,只需深蓝那种硬件水平才吃得消它,我那拙笨的Java代码一定不可。然则它的效果是不能否认的,不是吗?【原作者的意义多是指,单步延长手艺会显著提升棋力,同时也会增长搜索时刻。】
 
下三十天
 
  在第六局部中,咱们会着重议论局势评价函数,它才真正通知顺序一个局势是好是坏。这个主题具有极为普遍的内容,能够花几年时刻来革新评价要领(也实在一些人这样做),因而咱们必需对这些内容停止完全议论,包孕它们的可行性和主要水平。【在这篇提高型的连载中,作者怎样能够给你们讲那末多呢?】若是任何事项都依照设计停止,我就该用一些Java代码来给你们填饱肚子,然则这很难办到,不是吗?
 
  François Dominic Laramée20009
 
  原文:http://www.gamedev.net/reference/programming/features/chess5/
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译加译注
  • 上一篇 国际象棋顺序设想():基本搜索要领
  • 下一篇 国际象棋顺序设想():局势评价函数
  • 返 回 象棋百科全书——计算机象棋
  • www.xqbase.com