《棋战顺序基本手艺》专题
 
一次又一次检测
 
Bruce Moreland /
 
一次又一次检测为甚么那末主要
 
  咱们有需要提一下一次又一次和局的问题。若是棋局势(统一方走的状况下)一次又一次三次,就能够够宣布和棋。若是顺序抢先一个车然则它堕入长将,那将长短常糟糕的,对手会在你即将取得胜利的时刻宣布和棋。
  要处置责罚这个问题,就必需检测之前显现过的局势,并接纳对策。若是顺序晓得一次又一次,它就能够够依据盘面上形势的要求,来钻营一次又一次或制止一次又一次。若是顺序即将输棋,那末它应当试图寻找长将,相回响反映当制止。
  【译注:中国象棋显现一次又一次局势时,要依据双方的着法来剖断输赢(譬喻片面长将一方要被判负),划定礼貌异常庞大,因而战略也会分歧。】
 
一个相等贫苦的选择
 
  有两种局势能够会一次又一次:棋局的历史局势,即在棋局中盘面上走过的局势;搜索树局势,即顺序搜索的线路上显现的局势,它们没有在盘面上显现过,然则顺序的思索中会络续地吊销和执行着法。
  很显著,搜索树中的一次又一次局势应当能被马上检测出,而且会失掉处置责罚。一样寻常来说会前往一个和局分值,然则我听说很多若干顺序会在中局遇到长将时,若是顺序一方在将军,就有意前往一个正值。这是为了说明,若是你能找到长将,那末局势一般会好些。若是搜索树中的一次又一次没有被处置责罚,那末顺序就不会发现长将或其他一次又一次和局的状况。
  关于搜索树与棋局中局势显现的一次又一次局势,该怎样处置责罚就不清晰了。若是某个局势在棋局中显现两次,在搜索中显现一次,那末应当看成和局处置责罚,由于棋局中再显现一次就会和了。难题在于某个局势只在棋局中显现一次,在搜索树中也显现一次。
  许多顺序把这些局势看成和局处置责罚。这可以使得顺序在堕入逆境或对手试图制造一次又一次局势时,能有用地经由历程一次又一次检测来一定是否是到达和局,瑕玷是顺序有时会走出一些纷歧样寻常的着法。【若是顺序只检测到两次一次又一次局势(即棋局中的一次和搜索树中的一次,也许两次都在搜索树中)就前往和局分值,那末对搜索效能是有所提升的,由于顺序节约了第二次到第三次一次又一次之间的线路,这样就最少在搜索树的一般中央分枝上增加了4层。】
  我看过一些竞赛的案例,其中一盘是GNUChess对阵我的顺序。有个能赢的王兵残局被GNUChessWinBoard自带的顺序,源代码是公然的】错过了,这两个顺序就进入一系列和局局势。最终,他们又走回谁人被GNUChess错过的能赢的局势。我的顺序很愉快发现这个一次又一次局势,由于它是作为和局来评分的(它以前显现在棋局的历史局势中)。固然,第二次GNUChess找到了失利的门路。【第二次一次又一次不会被判和棋(只管原作者的顺序以为以前和了),要到第三次一次又一次才判和棋。】
  另有一盘棋是我的顺序对阵一位叫Greg Kennedy的人类巨匠。Kennedy抢先两个兵,然则他走了一步臭棋能够致使对手一马踏双,并能让对手得回一个兵。Kennedy发现他的王被将军了,必需走他的王,他就把王走到正本待过的中央。然则我的顺序走回了上一步,让局势回到两步前的样子容貌,而没有经由历程吃兵来到达仅落伍一个兵的局势。一次又一次问题使得顺序期待Kennedy会把王走回来离去,而且让顺序再对他一马踏双【这样他的王就第三次回到正本的职位上了】。固然他不会这么做,这样就让他连续抢先两个兵了。
  其他假定也是有能够的。一个很强的人类棋手发起了压服性的进攻,然则厥后没走好而让顺序逃掉了王,因而人类棋手就只需长将了,由于他子力落伍并没有杀棋。顺序会喜欢把王走回逃窜前正本的职位,由于这些职位是一次又一次的而且会失掉和局。【被长将会致使和局,把王走回正本危险的职位也被顺序以为是和局,若是顺序选择了后者,就给了对手第二次实验杀棋的时机。】
  我以前在我的顺序里做了修正,疏忽棋局中显现一次而且搜索树中显现一次的一次又一次局势。这样就处置责罚了下面说到的问题,然则带来了新的问题。
  顺序会把一个局势一次又一次频频,这使得棋局有时异常啰嗦。这能够会滋扰人类对手,也许在计算机国际象棋竞赛中滋扰对手,由于棋局抵达庞大残局时,能够不会有希望,而且能够周旋很长时刻,从而离50回合限制越来越近。【人类棋手在棋局没有希望时,第二次显现一次又一次局势就会握手言和,而使用这类战略的顺序则不愿提和,这会让他的对手感应不恬逸。】
  选择哪种要领,是要求琢磨的。【从效能上说,第二次一次又一次就前往和局分值的要领对照好,然则这类要领给了对手一个时机,当对手第一次出毛病时,第二次就无时机纠正了。】
 
能够的完成
 
  有许多要领能够检测一次又一次。其中一个在Tom KerriganTSCP中运用,他把这个要领归功于John Stanback。在他的代码中他声清楚明晰这一点,然则没有任何详细的信息来通知咱们这是怎样做的,因而我也不知道。若是你想知道它,就不能不到TSCP的源顺序中寻找。
  我能知道的完成要领以前在“Zobrist键值”一文中说到。若是你要完成“置换散列表”,那末你应领先完成Zobrist键值,这才气让置换表得以完成。你要求对Zobrist键值作处置责罚,从搜索树确以后局势往回找,看有无和以后局势相等的键值。
  一个完成要领就是依据以后线路竖立一个先进后出的客栈,把键值加到历史局势中。为了检测一次又一次,就要一层层地读取客栈,对照其中的键值,以确认以后键值是否是以前存在于客栈中。
  没有需要找遍悉数列表,只需往回找,直到遇到进兵或吃子的着法,由于这些着法在棋局中是弗成逆的。你不能够在最终一次吃子或进兵的前面找到一次又一次局势。
  这样做看上去有点花时刻,生怕是吧,然则我置信很多若干顺序就是这么做的。
  在我写国际象棋顺序的早期,我在Usenet上问了个关于散列手艺的问题,失掉Belle(尤物)作者Ken Thompson的回覆。【贝尔执行室的Ken Thompson,多是滋扰力仅次于John Von Nouma(-诺依曼)的盘算机专业研究人员了,他是C言语的前身B言语的发现者,Unix系统的建立者之一,有关他在计算机国际象棋上作出的孝敬,可参阅译文《计算机国际象棋简史》。】他通知我他用置换表来检测一次又一次局势,他是这样做的:
  当探测置换表时,在表项中设置“翻开”符号。这个符号一直被设置着,直到不再搜索这个局势为止,即从局势前往时才关闭。任什么时候时刻刻翻开的结点不是历史局势就是在搜索树确以后线路上,因而若是探讨散列表时遇到一个翻开的结点,就一定是前面发作过的局势。
  这类要领具有数据组织上的优势,由于这样的数据组织在模范的国际象棋中都用到,然则这个头脑有一些问题。当进入一个结点时,必需写入散列项,因而要求运用“一直替换” 的战略。关于Thompson来说这不是问题,由于他的战略包罗了“一直替换”的散列表,然则其他替换战略就没有设施运用这类要领。其余一个问题显现在散列表项抵触的状况下,这个问题必需失掉处置责罚。当两个局势具有一样的64位键值时,我不议论散列键值的抵触问题。现在我议论过两个局势共用一个散列项时,应当留下哪一个。若是两个翻开的结点要占用统一个散列项,除了要检测第二个局势是否是一次又一次之外,要做甚么其实不清晰。能够这个问题要经由历程重新散列的战略来处置责罚,然则这个要领跟散列表的主要用途没有相干,以是要加这个功用对照贫苦【重新散列(Re-Hashing)是一个处置责罚散列抵触的经常使用要领,然则在国际象棋顺序中其实不经常使用】。最终一个问题就是怎样习惯多处置责罚器搜索,由于许多线程能够会读取一个散列表。遇到翻开的结点时,能够基础就不是一次又一次局势,由于它能够属于其余一个处置责罚器的搜索线路。这个问题处置责罚起来看上去很庞大。【译者以为,能够在散列项中纪录一个被翻开的处置责罚器号,每一个处置责罚器只对自身翻开的结点作一次又一次检测。】
  其余一个简朴的战略就是用一个很小的散列表【若是斟酌50回合限着(100个着法),那末100200个散列项就足够了】。进入结点时探测散列表,若是以后局势的Zobrist键值以前在散列内外,就前往平手分值。否则就加入这个键值。当结点加入时,键值就删除。这看上去很直观,而且散列项的抵触处置责罚起来很随意纰漏,由于散列表不是满的,散列项以先进后出的递次存入和取出,也不存在替换战略的问题。
  我不愿说这个要领比其他要领好,由于究竟结果有Ken Thompson的要领。我的这个要领有一些问题,由于它要求靠分外的数据组织和分外的函数的支持。
  当顺序改成多处置责罚器搜索时,这类要领有点使人耽忧,然则比起Thompson的战略在这方面遇到的问题,我的这个问题看上去不那末严重。
  若是你们想看这个第二散列表的战略,就去搜检Gerbil的源顺序。这里我禁绝备列出源代码的示例,这只是完成上的问题而已。
  【中国象棋顺序也能够经由历程探测散列表停止一次又一次检测,然则不能马上前往平手分值。当检测出一次又一次局势时,必需逐一剖析两次一次又一次局势之间的着法,依据着法的性子来剖断输赢,这一点比国际象棋贫苦很多。】
 
  原文:http://www.seanet.com/~brucemo/topics/repetition.htm
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译加译注
  • 上一篇 其他战略——主要变例的取得
  • 下一篇 其他战略——轻视因子
  • 返 回 象棋百科全书——计算机象棋
  • www.xqbase.com