《对弈程序基本技术》专题
 
重复检测
 
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