国际象棋顺序设想(二):数据组织
 
François Dominic Laramée/
 
  上个月我简要引见了象棋顺序设想中所要求的知识,其他信息完整的双人游戏也是一样的。现在咱们将议论一些细节——棋盘的外部透露表现要领。
  在棋盘透露表现要领这个理念上,近三十年内没有多大生长,你能够会以为很受惊。它的生长要求智慧的推进,很早就一些人提出过绝妙的计划了,但同时也遭到制约,由于这些计划要求数据组织的支持,某些数据组织至今还没有完成。
  只管这样,我照样会引见三种数据组织,只管它们并非需要的,然则关于提升你的下棋水平是大有资助的。其中两种能够加速思索速率(然则其中一种要求有限多的存储器),其余一种能够加速着法发生速率。【译注:离别指前面要说到的置换表、历史表和着法天生预处置责罚的数据库。】
  在咱们连续议论之前,我提一句格言:“不论是象棋照样其他游戏,你一般运用的数据组织,应当是能到达目的的最简朴的数据组织。”然则象棋顺序设想者提出了许多窍门,它们能让顺序运转的更快,其中相等多的还适用于其他游戏。若是你对你要设想的游戏不很相识,而且手头的资料很有限,那末你应当好好掌握我所说到的这些窍门,你能够把这些窍门调研到你的顺序上。
 
基本的棋盘透露表现
 
  在上世纪70年月,小我私家计算机的存储器是有数资源,以是棋盘透露表现得越松散越好。许多人会很自信地说:用一个64字节的数组,每一个字节透露表现棋盘上的一个格子,用一个整数就能够够透露表现格子的职位了。(任何棋盘的数据组织都必需用一些分外的字节,来纪录吃过路兵的目的格、王车易位权益等信息,然则这里咱们暂时疏忽它,由于这些重点要点能够自力处置责罚,而且处置责罚要领迥然分歧。)
  厥后又盛行一些更优化的算法:
 
  1. 早期的SARGON【一个象棋顺序】扩展了64字节的数组,在它的中心加了两圈“虚格”,并在这些格子上作了合法符号。这一窍门能加速着法发生的速率,譬喻象在走棋时会延斜线滑行,直到走到虚格上才中缀。这样就没有需要用庞大的运算来预先剖断象抵达的格子是否是会超越存储器上的透露表现了。第二圈虚格是给马用的,譬喻位于盘角的马试图跳出棋盘,这就必需用两圈虚格来珍爱。
  2. MYCHESS用了相反的要领,它只用32字节透露表现一个棋盘,每一个字节象征一个棋子,譬喻象征白方王、黑方王翼马前兵【英文居然是black King's Knight's Pawn,一最先让我大惑不解】等,它存储的信息是棋盘上的职位,也许以前被吃的符号。这类手艺有一个瑕玷,它没有设施形貌由兵升变而来的其他棋子(同时这个棋子在棋盘上另有一个)。在厥后的版本中,这个瑕玷被修正了。【事实上这并很容易办,一个字节取值从0255,一般255透露表现该子已被吃,从063透露表现该子在棋盘上的职位,兵一般是升酿成后的,那末从64127能够透露表现该子以前升酿成后,若是升酿成车、马或象,则要求分外的字节来处置责罚。】
 
  现在,这类极端小气的数据组织只能够显现在掌上计算机、手机或电视机机顶盒上,它们的80~90%的资源都被支配系统占用,没有分外的空间给游戏运用。然则,某些游戏却别无选择地运用这类要领【我也不知道甚么游戏非得运用这类要领弗成】
  想更多地相识之前的象棋顺序,能够看一下David Welsh1984年写的《盘算机象棋》(Computer Chess)一书。
 
位棋盘
 
  用一个数组来透露表现棋盘,关于许多游戏来说,就找不到更好的设施了。然则关于像象棋、西洋跳棋之类在64格棋盘上的游戏来说,有一个拙劣的窍门——“位棋盘” (首先由苏联的KAISSA制造组提出),在上世纪60年月末降生了。
  KAISSA是运转在64位处置责罚器上的顺序【我很疑心事先就有64位处置责罚器,也许事先处置责罚器字长的观点和现在的有所分歧】。“64”恰巧是象棋棋盘格子的数目,以是这就有能够让一个字来透露表现一个棋盘,以剖断某个格子的状态是“是”也许“非”。譬喻,一个位棋盘能够回覆棋盘的每一个格子“是否是有白子”。【把位棋盘运用到中国象棋上,这是我将要停止的一个课题,中国象棋的棋盘有90个格点,能够用332位的字来透露表现。】
  因而,一个完整的局势要求用12个位棋盘透露表现:白兵、白车、黑兵等等。再加上两个用来透露表现“一切白子”和“一切黑子”的位棋盘,以加速运算速率。【事实上只要求8个就能够够了,统一军种(不论是非)用一个位棋盘,一共是6个,再加上象征“一切白子”和“一切黑子”的。做得更太过的是,一些人把象和后并作一个位棋盘,车和后并作一个位棋盘,这样又能够增加一个。若是要透露表现白方的象,只需“一切白子”、“一切车或后”的补集(用“非”运算)、“一切象或后”这三个位棋盘作“与”运算就能够够了。】也许你还想用一个位棋盘透露表现被某种子力进击到的格子,诸这样类,这些位棋能够盘天真运用在着法发生的运算历程当中。
  位棋盘之以是有用,是由于许多运算能够改动为处置责罚器的一个逻辑指令。譬喻,假定你要求确认黑王被白后将军,若是用简朴的数组来透露表现棋盘,那末你要求这样做:
 
  1. 首先找到后的职位,这要求从64个字节中一个一个地找;
  2. 然后在后所能走的八个偏向找,直到找到王也许找到后走不到的格子为止。
 
  这些运算是相等破费时刻的,若是后恰巧是在数组的最终一格,更糟的是,将军只会发作在少数状况下【这类运算地道是空费时刻!】
  若是用位棋盘,那你只需这样做:
 
  1. 载入“白方后的职位”的位棋盘;
  2. 依据这个职位,从索引数据库中找到被后进击的位棋盘;
  3. 用这个位棋盘和“黑方王的职位”的位棋盘作“与”运算。
 
  若是效果不是零,则说明黑王被白后将军。假定被后进击的位棋盘是贮藏于存储器中的【这是下面说到的第二步的条件】,那末悉数支配只要求34个时钟周期【一般盘算机执行1条指令要求1(算术或逻辑运算)2(寻址支配)个时钟周期】
  【这里允许我展现一下,原作所说的“从索引的数据库中找到”(即下面说到的第二步),事实上并非是简朴的一步,关于后的每一个职位,都有一定的进击格子(从边线到中央依次是21232527),然则要斟酌被其余子阻挠的状况,顺序没有设施为一切的状况都作索引,最多只能对某条线(横线、纵线或斜线)的棋子占无状况作索引,这也要求28 = 256 种状况,再加后自身有64种职位,以是纵然这样,数据库中也最少要生存256x64 = 16384个位棋盘。其余,横线、纵线和两条斜线的处置责罚要领各纷歧样,横线只需作简朴的“移位运算”就能够够了,而纵线和两条斜线都要用到“位棋盘改动”的手艺,为了提升运算效能,顺序的庞大水平是惊人的,细节能够参考《棋战顺序基本手艺》专题之《数据组织——改动的位棋盘》一文,文中作者屡次提醒读者用咖啡来提神,以完成啰嗦的顺序。】
  再举一个案例,若是在以后的棋盘上,你要发生白马的一切着法,那末你只需找到当与前职位相联系关系的“马能走到的格子”的位棋盘,并“与”(AND)上“一切被白方占有的格子”的位棋盘的补集(就是对这个位棋盘作“非”(NOT)运算),由于马的着法限制仅仅在于它不能去吃自身的子。【国际象棋对照简朴,而中国象棋中另有“绊马腿”的限制(另有象也是),这类状况该怎样运用位棋盘,也是我将要研讨的课题。】
  若是你想更详细地相识位棋盘(壹奔鼻细微详细一点而已),能够去看看形貌CHESS 4.5 (它是由美国西北大学开辟的)的美文——Peter Frey写的《人脑和计算机的象棋窍门》(Ches Skill in Man and Machine),现在最少以前出了两版了,离别出书于1977年和1981年。
  值得注重的事,到明天为止,险些还没有真正意义上运用64位处置责罚器的小我私家计算机,以是位棋盘的速率优势是要打折扣的。只管这样,位棋盘的手艺照样行之有用的。【苹果公司的Macintosh图形事情站听说是64位处置责罚器,但不知有无重点一定这类计算机的象棋软件。时隔4年,到我翻译这篇美文时,还没有甚么其余64位处置责罚器用在小我私家计算机上。由于究竟结果没这个需要,除非你专程用它来玩国际象棋。】
 
置换表
 
  在象棋里,有许多着法能够抵达一样的职位。譬喻,不论你先走 1. P-K4 ... 2. P-Q4也许1. P-Q4... 2.P-K4【这里K4Q4e4d4的,在实战中有这样的案例,1. e4 e6 2. d41. d4 e6, 2. e4是组成法兰西进攻一种变例的两种门路。】一炙刂势是一样的。有分歧的线路能够到达异样职位的,这类状况称为“置换”(Transposing)【在中国象棋中,置换状况越发普遍,一般用成语“异曲同工”来称谓这类状况。】
  若是你的顺序以前对1. P-Q4... 2.P-K4发生的效果竭尽努力作了搜索和评价,那末你最好记住这个效果,以免遇到1. P-K4... 2.P-Q4时再作异样的运算。自上世纪60年月Richard GreenblattMac Hack VI问世以来,一切的棋战顺序都邑吸纳“置换表”这一手艺,这就是缘由所在。
  置换表存储的是以前搜索过的效果,它一般运用相似于散列表(Hash Dictionary)的数据组织来到达最快的查询速率。在搜索某个局势时,效果(包孕局势剖析的值、搜索深度、最好着法等)就存储到置换内外。当搜索新的局势时,咱们先从置换内外找,若是以前有这类局势,那末就能够够应用它,省去一次又一次的搜索。
  这类处置责罚有以下许多有益之处:
 
  1. 加快速率。在置换状况发作得许多时(稀奇是残局局势里,棋盘上棋子很少时)90%上述的局势能够在表中找到。【在中国象棋中,这优势时越发显著,由于它的子力密度小,在残局阶段就有许多“异曲同工”的状况。】
  2. 恣意深度。假定你要求对某个局势搜索到一个指定的深度,譬喻4(也就是两个回合),若是置换内外有这个局势而且以前搜索了6步,那末你不只能够跳过此次搜索,还能够失掉比预期更准确的效果。
  3. 用途普遍。一般每一个象棋顺序都配有“残局库”(Opening Book),即包罗一些容易看到局势及其最好的着法,这些一般是从以前存在的纪录中提炼的【譬喻特级巨匠们写的“象棋残局大全”或“象棋残局手册”之类的书,而我自己更倾向于从少量对局纪录中提炼的效果】。有了残局库,顺序就没需要在残局阶段就做傻事了【由于先人以前做过有数次的盘算了】。如果残局库的支配历程和置换表是一样的(即搜索局势),那末为甚么不在棋局一最先就把残局库装入咱们的置换内外去呢?若是这样做,纵然棋局暂时脱离了残局库,厥后又回到残局库里的局势【要注重,这个局势能够是棋局历程当中显现的局势,但更多的状况是搜索顺序推演到的】,那末置换内外留下了这样的局势,咱们依旧无时机用到它。
 
  置换表唯一的瑕玷就是它贪心地占用着存储器,不论怎样它最少要求存储不可胜数个局势,百万以至上亿就更好了。若是每一个局势用16字节【用最松散的设施最少也要求32字节(MYCHESS这类小气的设施),然则这里能够寄存“散列键值”,下面会说到这个手艺】,那末在存储器紧缺的时刻这将成为很严重的问题。
  置换表另有其他用途。
  CHESS 4.5还用散列表来存储其他的局势盘算效果【指下面说到的兵型、子力平衡等】,这些盘算效果在少数状况下是不会更改的,譬喻:
  1. 兵型(Pawn Structure)。散列表只存储兵的职位,这要求较小的存储空间,由于兵的移动不会很频仍,以是99%的兵型局势能够在散列表中找到;【国际象棋的局势剖析中,要求斟酌连兵、叠兵、孤兵、通路兵等重点要点,这些盘算是相等费时的,而中国象棋就没有这个需要了。】
  2. 子力平衡(Material Balance),即棋盘上子力的一定强弱,它只在吃子或兵升变时更改。
  在CPU速率不快的明天,这些要领也许看来用途不是很大,然则它们照样有指点意义的,一些细微破费存储器的预处置责罚能够节约相等多的盘算。【由于寻址支配(稀奇指在若干M的大局限区域内寻址)所占用的时刻要远多于简朴的运算指令,若是哪天寻址支配的速率靠近于基本运算了,那末这类手艺将会对顺序运转速率有很大的选拔。】若是你注意研讨你的顺序,也许你会发现这方面是值得革新的。
 
为棋盘发生散列键值
 
  下面说到的置换表的组织,是由散列表来完成的,由此引发了以下课题:你怎样快速而有用地从棋盘来发生散列键值(Hash Key)
  以下是1970Zobrist的计划。
  1. 发生12x64N位的随机数(若是置换表能贮存2N个局势),并把他们做成一张表。每一个随机数只跟某个职位上的某种棋子有关(譬喻H4格的黑车),空的格子用零透露表现;【由于棋子总共有12种,棋盘总共有64格,故此是12x64个数,空的格子不用随机数而用0透露表现。】
  2. 先把散列键值设为零;
  3. 搜索悉数棋盘,每遇到一个子,就在正本的散列键值上“异或”(XOR)它所对应的随机数,一次又一次这个历程直到悉数棋盘被搜检一遍。
  这个计划有趣的一面在于,每走一步,散列键值的更新都异常随意纰漏,不要求重新搜索悉数棋盘。你知道“XOR图形处置责罚”(XOR-Graphics)吗?某个图形用XOR运算功用到配景上,然后再作异样一次运算,不就又回到配景了吗?这里也异样这么做。【若是你熟习图形支配中的手艺,就很容易体谅了,原文把这个历程比作“位图”(Bitmap)支配,12x64个棋子的状态就对应12x64张位图,正本的散列键值被比作“配景”(Background),只需在配景上作位图的粘贴支配(用的是XOR处置责罚)就能够够了。】举个H1格的白车吃掉了H4格的黑兵的案例,要发生这个散列键值,先XOR“在H1格的白车”这个随机数(把这个图形擦掉),然后是“在H4格的黑兵”(把这个图形也擦掉)和“在H4格的白车”(粘贴一个新的图形,象征新的车的职位)【事实上递次是无足轻重的】
  用一样的要领,分歧的随机数,能够发生第二个散列键值,或称“散列锁”(Hash Lock)【在英语中Lock()Key(钥匙)是对应的】,它是在置换表中存储的真正有用的信息。这个手艺是用来检测抵触的,若是恰巧有两个局势具有一样的散列键值,那末他们具有异样的散列锁的几率是微乎其微的。
 
历史表
 
  “历史启示”(History Heuristic)是“杀手着法”(Killer Move)【杀手着法指能发生截断的着法,以后的连载会说到的】手艺的衍生手艺。一篇研讨性的美文是这么注释的,历史表用来生存这些着法,在已往的搜中异常有意义(由于运用高效搜索手艺的而对它停止了很深的搜索),这个着法以后还能够用到。历史表由一个64x64的整数数组组成【着法的肇端格和抵达格,共有64x64种搭配】,纪录每种着法的数值,当搜索算法以为某个着法很有用时,它会让历史表增长这步的数值。表中的数值是用来对着法排序的,“历史上占优势”的着法会优先斟酌。
 
着法发生的预处置责罚
 
  着法的发生(即注定特定职位下那些着法是恰当的)和局势的预计一样,是象棋顺序设想中盘算量最大的局部。因而,在这个方面的一点预处剖析对提升速率大有资助。
  我小我私家喜欢Jean Goulet1984年写的《象棋的数据组织》(Data Structures for ChessMcGill大学出书社)一书中说到的计划,它归纳综合为:
 
  1. 出于着法发生的目的,棋子的颜色是无足轻重的,除了兵之外,它只朝劈面走;
  2. 关于基本的子力和它的职位,有64x5=320种搭配【指除了兵之外的5种棋子,依据上一条,这些棋子是不分是非的】,黑兵有48个格子能够放(他们前面一行是走不到的,而且一到第八行就会酿成其余棋子),白兵也有48个格子;
  3. 从某个格子沿某个偏向,能够一定一条着法“射线”,譬喻,后从H3格朝北走,这就是一条“射线”;
  4. 每一个格子上的每一个棋子,都有一定的几条射线能够走,譬喻位于中央的王能够朝8个偏向走,而位于盘角的象却只需一条逃生的路;
  5. 在最先游戏之前,要盘算数据库里在一切格子的一切棋子的一切射线,假定棋盘是空的(即着法只遭到棋盘边缘的限制,不受其他棋子的限制)
  6. 当你为某个格子的某个棋子发生着法时,朝每一个偏向搜索直到遇到棋子为止。若是是对方的棋子,最终一种着法就是吃子的着法,若是是本方的棋子,最终一种着法就是分歧适的。
 
  有了适当的数据库,着法的发生就酿成简朴得靠近于线性的寻找了,险些用不着甚么盘算。悉数事项就掌握在这么几千个字节里,只是置换表的一个零头。
 
  上陈说到的一切手艺(位棋盘、置换表、历史表和预处置责罚数据库)都邑回响反映在我自身的顺序中,当我写完这个连载以后就会公布出来。下个月我会详细引见着法发生的要领。
 
  François Dominic Laramée20006
 
  原文:http://www.gamedev.net/reference/programming/features/chess2/
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译加译注
  • 上一篇 国际象棋顺序设想():引言
  • 下一篇 国际象棋顺序设想():着法的发生
  • 返 回 象棋百科全书——计算机象棋
  • www.xqbase.com