其他策略——重复检测.htm

象棋程序设计全资料集(介绍编写象棋程序的方法思路）

  target=_blank><FONT 
  face="Times New Roman">Zobrist</FONT>键值</A>”一文中提到。如果你要实现“<A 
  href="http://www.elephantbase.net/computer/search_hashing.htm" 
  target=_blank>置换散列表</A>”，那么你应该先实现<FONT 
  face="Times New Roman">Zobrist</FONT>键值，这才能让置换表得以实现。你需要对<FONT 
  face="Times New Roman">Zobrist</FONT>键值作处理，从搜索树的当前局面往回找，看有没有和当前局面相等的键值。 
  <DT>　　一个实现方法就是根据当前路线建立一个先进后出的堆栈，把键值加到历史局面中。为了检测重复，就要一层层地读取堆栈，比较其中的键值，以确认当前键值是否已经存在于堆栈中。 

  <DT>　　没有必要找遍整个列表，只要往回找，直到遇到进兵或吃子的着法，因为这些着法在棋局中是不可逆的。你不可能在最后一次吃子或进兵的前面找到重复局面。 
  <DT>　　这样做看上去有点花时间，恐怕是吧，但是我相信有些程序就是这么做的。 
  <DT>　　在我写国际象棋程序的早期，我在<FONT 
  face="Times New Roman">Usenet</FONT>上问了个关于散列技术的问题，得到<FONT 
  face="Times New Roman">Belle(</FONT>尤物<FONT 
  face="Times New Roman">)</FONT>作者<FONT face="Times New Roman">Ken 
  Thompson</FONT>的回答。<FONT color=#0000ff>【贝尔实验室的</FONT><FONT 
  face="Times New Roman" color=#0000ff>Ken Thompson</FONT><FONT 
  color=#0000ff>，可能是影响力仅次于</FONT><FONT face="Times New Roman" color=#0000ff>John 
  Von Nouma(</FONT><FONT color=#0000ff>冯</FONT><FONT face="Times New Roman" 
  color=#0000ff>-</FONT><FONT color=#0000ff>诺依曼</FONT><FONT 
  face="Times New Roman" color=#0000ff>)</FONT><FONT 
  color=#0000ff>的计算机科学家了，他是</FONT><FONT face="Times New Roman" 
  color=#0000ff>C</FONT><FONT color=#0000ff>语言的前身</FONT><FONT 
  face="Times New Roman" color=#0000ff>B</FONT><FONT 
  color=#0000ff>语言的发明者，</FONT><FONT face="Times New Roman" 
  color=#0000ff>Unix</FONT><FONT 
  color=#0000ff>系统的创立者之一，有关他在电脑国际象棋上作出的贡献，可参阅译文《</FONT><A 
  href="http://www.elephantbase.net/computer/history.htm" target=_blank><FONT 
  color=#0000ff>电脑国际象棋简史</FONT></A><FONT 
  color=#0000ff>》。】</FONT>他告诉我他用置换表来检测重复局面，他是这样做的： 
  <DT>　　当探测置换表时，在表项中设置“打开”标志。这个标志一直被设置着，直到不再搜索这个局面为止，即从局面返回时才关闭。任何时刻打开的结点不是历史局面就是在搜索树的当前路线上，因此如果探索散列表时遇到一个打开的结点，就一定是前面发生过的局面。 

  <DT>　　这种方法具有数据结构上的优势，因为这样的数据结构在典型的国际象棋中都用到，但是这个思想有一些问题。当进入一个结点时，必须写入散列项，因此需要使用“<A 
  href="http://www.elephantbase.net/computer/search_hashing.htm#replacement" 
  target=_blank>始终替换</A>” 的策略。对于<FONT 
  face="Times New Roman">Thompson</FONT>来说这不是问题，因为他的策略包含了“始终替换”的散列表，但是其他替换策略就无法使用这种方法。另一个问题出现在散列表项冲突的情况下，这个问题必须得到处理。当两个局面具有相同的<FONT 
  face="Times New Roman">64</FONT>位键值时，我不讨论散列键值的冲突问题。现在我讨论过两个局面共用一个散列项时，应该保留哪一个。如果两个打开的结点要占用同一个散列项，除了要检测第二个局面是否重复以外，要做什么并不清楚。可能这个问题要通过重新散列的策略来解决，但是这个方法跟散列表的主要用途没有关系，所以要加这个功能比较麻烦<FONT 
  color=#0000ff>【重新散列</FONT><FONT face="Times New Roman" 
  color=#0000ff>(Re-Hashing)</FONT><FONT 
  color=#0000ff>是一个解决散列冲突的常用方法，但是在国际象棋程序中并不常用】</FONT>。最后一个问题就是如何适应多处理器搜索，因为很多线程可能会读取一个散列表。遇到打开的结点时，可能根本就不是重复局面，因为它可能属于另一个处理器的搜索路线。这个问题解决起来看上去很复杂。<FONT 
  color=#0000ff>【译者认为，可以在散列项中记录一个被打开的处理器号，每个处理器只对自己打开的结点作重复检测。】</FONT> 
  <DT>　　另一个简单的策略就是用一个很小的散列表<FONT color=#0000ff>【如果考虑</FONT><FONT 
  face="Times New Roman" color=#0000ff>50</FONT><FONT 
  color=#0000ff>回合限着</FONT><FONT face="Times New Roman" 
  color=#0000ff>(</FONT><FONT color=#0000ff>即</FONT><FONT face="Times New Roman" 
  color=#0000ff>100</FONT><FONT color=#0000ff>个着法</FONT><FONT 
  face="Times New Roman" color=#0000ff>)</FONT><FONT 
  color=#0000ff>，那么</FONT><FONT face="Times New Roman" 
  color=#0000ff>100</FONT><FONT color=#0000ff>到</FONT><FONT 
  face="Times New Roman" color=#0000ff>200</FONT><FONT 
  color=#0000ff>个散列项就足够了】</FONT>。进入结点时探测散列表，如果当前局面的<FONT 
  face="Times New Roman">Zobrist</FONT>键值已经在散列表里，就返回平局分值。否则就加入这个键值。当结点退出时，键值就删除。这看上去很直观，并且散列项的冲突处理起来很容易，因为散列表不是满的，散列项以先进后出的顺序存取，也不存在替换策略的问题。 

  <DT>　　我不愿说这个方法比其他方法好，因为毕竟有<FONT face="Times New Roman">Ken 
  Thompson</FONT>的方法。我的这个方法有一些问题，因为它需要靠额外的数据结构和额外的函数的支持。 
  <DT>　　当程序改成多处理器搜索时，这种方法有点令人担忧，但是比起<FONT 
  face="Times New Roman">Thompson</FONT>的策略在这方面遇到的问题，我的这个问题看上去不那么严重。 
  <DT>　　如果你们想看这个第二散列表的策略，就去检查<FONT 
  face="Times New Roman">Gerbil</FONT>的源程序。这里我不准备列出源代码的示例，这只是实现上的问题罢了。 
  <DT><FONT 
  color=#0000ff>　　【中国象棋程序也可以通过探测散列表进行重复检测，但是不能立即返回平局分值。当检测出重复局面时，必须逐个分析两次重复局面之间的着法，根据着法的性质来判定胜负，这一点比国际象棋麻烦得多。】</FONT> 

  <DT>　 
  <DT>　　原文：<A href="http://www.seanet.com/~brucemo/topics/repetition.htm" 
  target=_blank><FONT 
  face="Times New Roman">http://www.seanet.com/~brucemo/topics/repetition.htm</FONT></A> 

  <DT>　　译者：黄晨 <FONT face="Times New Roman">(</FONT><A 
  href="mailto:[e-mail]"><FONT 
  face="Times New Roman">[e-mail]</FONT></A><FONT 
  face="Times New Roman">)</FONT> 
  <DT>　　类型：全译加译注 </DT></DL>
<DIR>
<LI>上一篇　<A 
href="http://www.elephantbase.net/computer/other_pvcollect.htm">其他策略——主要变例的获取</A> 

<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/other_contempt.htm">其他策略——藐视因子</A> 
<LI>返　回　<A href="http://www.elephantbase.net/computer.htm">象棋百科全书——电脑象棋</A> 
</LI></DIR>
<DIV align=center>
<CENTER>
<TABLE border=0>
  <TBODY>
  <TR>
    <TD>
      <P align=center><A href="http://www.elephantbase.net/" target=_blank><IMG 
      height=31 src="其他策略——重复检测_files/elephantbase.gif" width=88 
      border=0></A></P></TD></TR>
  <TR>
    <TD><A href="http://www.elephantbase.net/" target=_blank><FONT face=Arial 
      size=2><STRONG>www.elephantbase.net</STRONG></FONT></A></TD></TR></TBODY></TABLE></CENTER></DIV></BODY></HTML>