《对弈程序基本技术》专题

　

重复检测

　

Bruce Moreland / 文

　

重复检测为什么那么重要

　

　　我们有必要提一下重复和局的问题。如果棋局面(同一方走的情况下)重复三次，就可以宣布和棋。如果程序领先一个车但是它陷入长将，那将是非常糟糕的，对手会在你即将取得胜利的时候宣布和棋。

　　要解决这个问题，就必须检测以前出现过的局面，并采取对策。如果程序懂得重复，它就可以根据盘面上局势的需要，来谋求重复或避免重复。如果程序即将输棋，那么它应该试图寻找长将，反之应该避免。

　　【译注：中国象棋出现重复局面时，要根据双方的着法来判断胜负(例如单方面长将一方要被判负)，规则非常复杂，因此策略也会不同。】

　

一个相当麻烦的选择

　

　　有两种局面可能会重复：棋局的历史局面，即在棋局中盘面上走过的局面；搜索树局面，即程序搜索的路线上出现的局面，它们没有在盘面上出现过，但是程序的思考中会不断地撤消和执行着法。

　　很明显，搜索树中的重复局面应该能被立即检测出，并且会得到处理。一般来说会返回一个和局分值，但是我听说有些程序会在中局遇到长将时，如果程序一方在将军，就故意返回一个正值。这是为了说明，如果你能找到长将，那么局面通常会好些。如果搜索树中的重复没有被处理，那么程序就不会看到长将或其他重复和局的情况。

　　对于搜索树与棋局中局面出现的重复局面，该怎么做就不清楚了。如果某个局面在棋局中出现两次，在搜索中出现一次，那么应该当作和局处理，因为棋局中再出现一次就会和了。困难在于某个局面只在棋局中出现一次，在搜索树中也出现一次。

　　很多程序把这些局面当作和局处理。这可以使得程序在陷入困境或对手试图制造重复局面时，能有效地通过重复检测来确定是否达到和局，缺点是程序有时会走出一些不正常的着法。【如果程序只检测到两次重复局面(即棋局中的一次和搜索树中的一次，或者两次都在搜索树中)就返回和局分值，那么对搜索效率是有所提高的，因为程序节省了第二次到第三次重复之间的线路，这样就至少在搜索树的局部分枝上减少了4层。】

　　我看过一些比赛的例子，其中一盘是GNUChess对阵我的程序。有个能赢的王兵残局被GNUChess【WinBoard自带的程序，源代码是公开的】错过了，这两个程序就进入一系列和局局面。最后，他们又走回那个被GNUChess错过的能赢的局面。我的程序很高兴看到这个重复局面，因为它是作为和局来评分的(它已经出现在棋局的历史局面中)。当然，第二次GNUChess找到了获胜的途径。【第二次重复不会被判和棋(尽管原作者的程序认为已经和了)，要到第三次重复才判和棋。】

　　还有一盘棋是我的程序对阵一位叫Greg Kennedy的人类大师。Kennedy领先两个兵，但是他走了一步臭棋可以导致对手一马踏双，并能让对手得回一个兵。Kennedy看到他的王被将军了，必须走他的王，他就把王走到原来待过的地方。然而我的程序走回了上一步，让局面回到两步前的样子，而没有通过吃兵来达到仅落后一个兵的局面。重复问题使得程序期待Kennedy会把王走回来，并且让程序再对他一马踏双【这样他的王就第三次回到原来的位置上了】。当然他不会这么做，这样就让他继续领先两个兵了。

　　其他假设也是有可能的。一个很强的人类棋手发动了压倒性的进攻，但是后来没走好而让程序逃掉了王，因此人类棋手就只有长将了，因为他子力落后并没有杀棋。程序会乐于把王走回逃跑前原来的位置，因为这些位置是重复的并且会得到和局。【被长将会导致和局，把王走回原来危险的位置也被程序认为是和局，如果程序选择了后者，就给了对手第二次尝试杀棋的机会。】

　　我已经在我的程序里做了修改，忽略棋局中出现一次并且搜索树中出现一次的重复局面。这样就解决了上面提到的问题，但是带来了新的问题。

　　程序会把一个局面重复几次，这使得棋局有时非常烦琐。这可能会干扰人类对手，或者在电脑国际象棋比赛中干扰对手，因为棋局到达复杂残局时，可能不会有进展，并且可能周旋很长时间，从而离50回合限制越来越近。【人类棋手在棋局没有进展时，第二次出现重复局面就会握手言和，而采用这种策略的程序则不肯提和，这会让他的对手感到不舒服。】

　　选择哪种做法，是需要斟酌的。【从效率上说，第二次重复就返回和局分值的做法比较好，然而这种做法给了对手一个机会，当对手第一次犯错误时，第二次就有机会纠正了。】

　

可能的实现

　

　　有很多方法可以检测重复。其中一个在Tom Kerrigan的TSCP中使用，他把这个方法归功于John Stanback。在他的代码中他声明了这一点，但是没有任何详细的信息来告诉我们这是如何做的，因此我也不知道。如果你想知道它，就不得不到TSCP的源程序中挖掘。

　　我能知道的实现方法已经在“Zobrist键值”一文中提到。如果你要实现“置换散列表”，那么你应该先实现Zobrist键值，这才能让置换表得以实现。你需要对Zobrist键值作处理，从搜索树的当前局面往回找，看有没有和当前局面相等的键值。

　　一个实现方法就是根据当前路线建立一个先进后出的堆栈，把键值加到历史局面中。为了检测重复，就要一层层地读取堆栈，比较其中的键值，以确认当前键值是否已经存在于堆栈中。

　　没有必要找遍整个列表，只要往回找，直到遇到进兵或吃子的着法，因为这些着法在棋局中是不可逆的。你不可能在最后一次吃子或进兵的前面找到重复局面。

　　这样做看上去有点花时间，恐怕是吧，但是我相信有些程序就是这么做的。

　　在我写国际象棋程序的早期，我在Usenet上问了个关于散列技术的问题，得到Belle(尤物)作者Ken Thompson的回答。【贝尔实验室的Ken Thompson，可能是影响力仅次于John Von Nouma(冯-诺依曼)的计算机科学家了，他是C语言的前身B语言的发明者，Unix系统的创立者之一，有关他在电脑国际象棋上作出的贡献，可参阅译文《电脑国际象棋简史》。】他告诉我他用置换表来检测重复局面，他是这样做的：

　　当探测置换表时，在表项中设置“打开”标志。这个标志一直被设置着，直到不再搜索这个局面为止，即从局面返回时才关闭。任何时刻打开的结点不是历史局面就是在搜索树的当前路线上，因此如果探索散列表时遇到一个打开的结点，就一定是前面发生过的局面。

　　这种方法具有数据结构上的优势，因为这样的数据结构在典型的国际象棋中都用到，但是这个思想有一些问题。当进入一个结点时，必须写入散列项，因此需要使用“始终替换” 的策略。对于Thompson来说这不是问题，因为他的策略包含了“始终替换”的散列表，但是其他替换策略就无法使用这种方法。另一个问题出现在散列表项冲突的情况下，这个问题必须得到处理。当两个局面具有相同的64位键值时，我不讨论散列键值的冲突问题。现在我讨论过两个局面共用一个散列项时，应该保留哪一个。如果两个打开的结点要占用同一个散列项，除了要检测第二个局面是否重复以外，要做什么并不清楚。可能这个问题要通过重新散列的策略来解决，但是这个方法跟散列表的主要用途没有关系，所以要加这个功能比较麻烦【重新散列(Re-Hashing)是一个解决散列冲突的常用方法，但是在国际象棋程序中并不常用】。最后一个问题就是如何适应多处理器搜索，因为很多线程可能会读取一个散列表。遇到打开的结点时，可能根本就不是重复局面，因为它可能属于另一个处理器的搜索路线。这个问题解决起来看上去很复杂。【译者认为，可以在散列项中记录一个被打开的处理器号，每个处理器只对自己打开的结点作重复检测。】

　　另一个简单的策略就是用一个很小的散列表【如果考虑50回合限着(即100个着法)，那么100到200个散列项就足够了】。进入结点时探测散列表，如果当前局面的Zobrist键值已经在散列表里，就返回平局分值。否则就加入这个键值。当结点退出时，键值就删除。这看上去很直观，并且散列项的冲突处理起来很容易，因为散列表不是满的，散列项以先进后出的顺序存取，也不存在替换策略的问题。

　　我不愿说这个方法比其他方法好，因为毕竟有Ken Thompson的方法。我的这个方法有一些问题，因为它需要靠额外的数据结构和额外的函数的支持。

　　当程序改成多处理器搜索时，这种方法有点令人担忧，但是比起Thompson的策略在这方面遇到的问题，我的这个问题看上去不那么严重。

　　如果你们想看这个第二散列表的策略，就去检查Gerbil的源程序。这里我不准备列出源代码的示例，这只是实现上的问题罢了。

　　【中国象棋程序也可以通过探测散列表进行重复检测，但是不能立即返回平局分值。当检测出重复局面时，必须逐个分析两次重复局面之间的着法，根据着法的性质来判定胜负，这一点比国际象棋麻烦得多。】

　

　　原文：http://www.seanet.com/~brucemo/topics/repetition.htm

　　译者：象棋百科全书网 (webmaster@xqbase.com)

　　类型：全译加译注

上一篇　其他策略——主要变例的获取

下一篇　其他策略——藐视因子

返　回　象棋百科全书——电脑象棋

www.xqbase.com