解剖大象的眼睛——中国象棋程序设计探索(六)：并行搜索技术探索.htm

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

  face="Times New Roman">false</FONT>表示未加锁，<FONT 
  face="Times New Roman">true</FONT>表示加锁。加锁时只要用<FONT 
  face="Times New Roman">true</FONT>和加锁标志交换，换出<FONT 
  face="Times New Roman">false</FONT>就表示加锁成功<FONT 
  face="Times New Roman">(</FONT>原来加锁标志是<FONT 
  face="Times New Roman">false</FONT>，交换后变成<FONT 
  face="Times New Roman">true)</FONT>，该线程就获得对共享单元的操作权，换出<FONT 
  face="Times New Roman">true</FONT>则表示加锁失败<FONT 
  face="Times New Roman">(</FONT>原来加锁标志是<FONT 
  face="Times New Roman">true</FONT>，交换后仍旧是<FONT 
  face="Times New Roman">true)</FONT>。对共享单元操作完毕后，再将加锁标志设成<FONT 
  face="Times New Roman">false</FONT>来解锁。 
  <DT>　　并行计算的博弈程序会偶尔出现一种情况，即两个线程同时存取同一置换表项，为避免错误可以使用加锁技术： 
  <DD>　 
  <DD>struct HashRecord { 
  <DD>　volatile int Lock; 
  <DD>　…… 
  <DD>}; 
  <DD>　 
  <DD>void RecordHash / ProbeHash (……) { 
  <DD>　HashRecord *HashPtr = HashList + ZobristKey % HashSize; 
  <DD>　while (Exchange(&amp;HashPtr-&gt;Lock, true)) { 
  <DD>　} 
  <DD>　…… 
  <DD>　HashPtr-&gt;Lock = false; 
  <DD>} 
  <DT>　 
  <DT>　　但是，并行国际象棋程序的典范<FONT 
  face="Times New Roman">Crafty</FONT>并没有这样做，而是采用了不加锁的技术，来避免置换表的存取冲突。简而言之，该算法的思想是当置换表项的校验码存取正确时，必须保证局面信息也存取正确<FONT 
  face="Times New Roman">(</FONT>但允许校验码存取不正确，此时探索置换表的例程就会跳过以后的操作而不会引发错误<FONT 
  face="Times New Roman">)</FONT>。 
  <DT>　　为此<FONT face="Times New Roman">Crafty</FONT>的<FONT 
  face="Times New Roman">128</FONT>位置换表项定义为两个<FONT 
  face="Times New Roman">64</FONT>位数<FONT face="Times New Roman">W1</FONT>和<FONT 
  face="Times New Roman">W2</FONT>，<FONT 
  face="Times New Roman">W1</FONT>是局面信息，而<FONT 
  face="Times New Roman">W2</FONT>存储了<FONT 
  face="Times New Roman">W1</FONT>和校验码的异或值，探测置换表项时，校验码必须由<FONT 
  face="Times New Roman">W1</FONT>和<FONT 
  face="Times New Roman">W2</FONT>的异或值求得，这样一旦<FONT 
  face="Times New Roman">W1</FONT>读取错误，就得不到正确的校验码，换句话说，校验码的正确就保证了局面信息的正确。 
  <DT>　　<FONT face="Times New Roman">Crafty</FONT>的这种不加锁算法是针对<FONT 
  face="Times New Roman">64</FONT>位处理器而设计的，这种技术当然也适用于<FONT 
  face="Times New Roman">32</FONT>位处理器，而笔者认为<FONT 
  face="Times New Roman">32</FONT>位处理器还有更为简单的处理方式，即设计如下的置换表项： 
  <DD>　 
  <DD>struct HashRecord { 
  <DD>　long CheckSum1, PositionInfo1, PositionInfo2, CheckSum2; 
  <DD>}; 
  <DT>　 
  <DT>　　以上<FONT face="Times New Roman">128</FONT>位的置换表项由<FONT 
  face="Times New Roman">4</FONT>个<FONT 
  face="Times New Roman">32</FONT>位单元组成，存取置换表时四个单元依次读取或写入。只要位于首尾的校验码都能存取正确，就确保了中间两个局面信息单元的正确。 

  <DT>　 
  <DT><FONT face=Arial size=4><STRONG>6.3 </STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG>搜索树的分割策略</STRONG></FONT> 
  <DT>　 
  <DT>　　<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索是递归式的，因此作并行计算时可以仿照上面提到的<FONT 
  face="Times New Roman">Fibonacci()</FONT>递归的例子，但这里有两个问题需要解决，一是某个子线程产生<FONT 
  face="Times New Roman">Beta</FONT>截断时，如何通知其他子线程中止搜索，二是考虑什么样的结点需要分割，什么样的结点不需要分割。这两个问题都是并行搜索技术的难点，为此<FONT 
  face="Times New Roman">Crafty</FONT>花了大量的代码来解决这些问题，其作者<FONT 
  face="Times New Roman">Robert Hyatt</FONT>对<FONT 
  face="Times New Roman">Crafty</FONT>的并行算法<FONT 
  face="Times New Roman">DTS(Dynamic Tree Split</FONT>，即搜索树的动态分割算法<FONT 
  face="Times New Roman">)</FONT>有专门的介绍。这里笔者只简单地介绍第二个问题，即搜索树的分割策略。 
  <DT>　　通常<FONT face="Times New Roman">Alpha-Beta</FONT>搜索树的结点可分为三个类型，即<FONT 
  face="Times New Roman">PV</FONT>结点、<FONT 
  face="Times New Roman">Beta</FONT>结点和<FONT 
  face="Times New Roman">Alpha</FONT>结点，并且有明确的定义——搜索值在窗口<FONT 
  face="Times New Roman">(Alpha, Beta)</FONT>之间的是<FONT 
  face="Times New Roman">PV</FONT>结点<FONT 
  face="Times New Roman">(</FONT>根据最小<FONT 
  face="Times New Roman">-</FONT>最大原理，最佳着法的搜索值必须落在窗口内<FONT 
  face="Times New Roman">)</FONT>，搜索值达到或超过<FONT 
  face="Times New Roman">Beta(</FONT>即高出边界<FONT 
  face="Times New Roman">)</FONT>的是<FONT 
  face="Times New Roman">Beta</FONT>结点<FONT 
  face="Times New Roman">(</FONT>仅需要有一个着法超过<FONT 
  face="Times New Roman">Beta</FONT>即可<FONT 
  face="Times New Roman">)</FONT>，搜索值未能超过<FONT 
  face="Times New Roman">Alpha(</FONT>即低出边界<FONT 
  face="Times New Roman">)</FONT>的是<FONT 
  face="Times New Roman">Alpha</FONT>结点<FONT 
  face="Times New Roman">(</FONT>所有着法都不能超过<FONT 
  face="Times New Roman">Alpha)</FONT>。由此可以看出，<FONT 
  face="Times New Roman">PV</FONT>结点和<FONT 
  face="Times New Roman">Alpha</FONT>结点都需要搜索所有的着法，而<FONT 
  face="Times New Roman">Beta</FONT>结点在最好的情况下只要搜索一个着法即可。 
  <DT>　　如果能在搜索之前预测出结点的类型，就可以决定是否对该结点作分割了，在<FONT 
  face="Times New Roman">Crafty</FONT>及其相关论文中，预测的三类结点命名为<FONT 
  face="Times New Roman">PV</FONT>结点、<FONT 
  face="Times New Roman">Cut</FONT>结点和<FONT 
  face="Times New Roman">All</FONT>结点，分别对应刚才提到的<FONT 
  face="Times New Roman">PV</FONT>结点、<FONT 
  face="Times New Roman">Beta</FONT>结点和<FONT 
  face="Times New Roman">Alpha</FONT>结点。显然，<FONT 
  face="Times New Roman">PV</FONT>结点和<FONT 
  face="Times New Roman">All</FONT>结点是有分割价值的，只要预测正确，这些结点下的全部着法都要搜索，不会因为产生截断而浪费搜索时间，而对<FONT 
  face="Times New Roman">Cut</FONT>结点作分割是没有意义的，因为目前的搜索技术使得<FONT 
  face="Times New Roman">Cut</FONT>结点的第一着法截断率高达<FONT 
  face="Times New Roman">80%</FONT>以上，对结点作分割只会浪费处理器资源。 
  <DT>　　至于如何来预测结点类型，在<FONT 
  face="Times New Roman">Crafty</FONT>及其相关论文也有介绍，但是另一个国际象棋程序<FONT 
  face="Times New Roman">Fruit</FONT>则描绘得更加明确，其分类策略是： 
  <DT>　　<FONT face="Times New Roman">(1) </FONT>根结点总是<FONT 
  face="Times New Roman">PV</FONT>结点。 
  <DT>　　<FONT face="Times New Roman">(2) PV</FONT>结点采用<FONT 
  face="Times New Roman">PVS</FONT>算法，即第一个着法以后首先尝试零窗口的搜索，由于期望每个着法都低出边界<FONT 
  face="Times New Roman">(</FONT>即子结点都高出边界<FONT 
  face="Times New Roman">)</FONT>，所以预测这些零窗口的结点为<FONT 
  face="Times New Roman">Cut</FONT>结点。 
  <DT>　　<FONT face="Times New Roman">(3) Cut</FONT>结点和<FONT 
  face="Times New Roman">All</FONT>结点是互相交替的，即<FONT 
  face="Times New Roman">Cut</FONT>结点的子结点是<FONT 
  face="Times New Roman">All</FONT>结点，<FONT 
  face="Times New Roman">All</FONT>结点的子结点是<FONT 
  face="Times New Roman">Cut</FONT>结点，空着裁剪同样这么处理。 
  <DT>　　<FONT face="Times New Roman">(4) Cut</FONT>结点的第一个子结点<FONT 
  face="Times New Roman">(All</FONT>结点<FONT 
  face="Times New Roman">)</FONT>如果不能产生截断，就说明原来预测的<FONT 
  face="Times New Roman">Cut</FONT>结点是错的，应该是<FONT 
  face="Times New Roman">All</FONT>结点，那么以后的子结点都预测为<FONT 
  face="Times New Roman">Cut</FONT>结点。换句话说，不管预测是否正确，<FONT 
  face="Times New Roman">Cut</FONT>结点的第一个子结点<FONT 
  face="Times New Roman">(</FONT>不包括空着裁剪<FONT 
  face="Times New Roman">)</FONT>是<FONT 
  face="Times New Roman">All</FONT>结点，其余的结点<FONT 
  face="Times New Roman">(</FONT>如果有必要搜索的话<FONT 
  face="Times New Roman">)</FONT>仍旧是<FONT face="Times New Roman">Cut</FONT>结点。 
  <DT>　　<FONT face="Times New Roman">(5) PV</FONT>结点不采用各种形式的向前裁剪<FONT 
  face="Times New Roman">(Null-Move</FONT>、<FONT 
  face="Times New Roman">History</FONT>、<FONT 
  face="Times New Roman">Futility</FONT>等<FONT face="Times New Roman">)</FONT>。 
  <DT>　　由于<FONT face="Times New Roman">Fruit</FONT>不支持并行搜索，所以<FONT 
  face="Times New Roman">Cut</FONT>结点和<FONT 
  face="Times New Roman">All</FONT>结点没有区别，但给并行搜索留下了伏笔。 
  <DT>　　我们关注的是<FONT face="Times New Roman">PV</FONT>结点的分割，显然<FONT 
  face="Times New Roman">PV</FONT>结点是有必要分割的，因为分割越早，新的线程所处理的搜索树就越大，并行效率就越高。<FONT 
  face="Times New Roman">(</FONT>注意<FONT 
  face="Times New Roman">Fibonacci()</FONT>递归的例子，为保证效率只有参数充分大时才会分割，<FONT 
  face="Times New Roman">Alpha-Beta</FONT>递归也一样。<FONT 
  face="Times New Roman">)</FONT>但是<FONT 
  face="Times New Roman">PV</FONT>结点的分割会遇到一个问题——窗口宽度可能会变窄，如果让所有的子结点都作相同窗口的搜索，就无法体现<FONT 
  face="Times New Roman">Alpha-Beta</FONT>算法的效率了。为此，<FONT 
  face="Times New Roman">Crafty</FONT>对根结点的迭代加深过程用了期望窗口<FONT 
  face="Times New Roman">(Aspiration 
  Window)</FONT>，即让所有的子结点都搜索一个较窄的窗口，这要比直接分割<FONT 
  face="Times New Roman">(</FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman">MATE_VALUE, MATE_VALUE)</FONT>有效得多。而另一个极端的做法是<FONT 
  face="Times New Roman">MTD(<EM>f</EM>)</FONT>的零窗口，根结点从一开始就预测为<FONT 
  face="Times New Roman">Cut</FONT>或<FONT 
  face="Times New Roman">All</FONT>结点，即可实施有效的分割，这就是<FONT 
  face="Times New Roman">MTD(<EM>f</EM>)</FONT>算法在并行计算上的优势。 </DT></DL>
<DIR>
<LI>上一篇　<A 
href="http://www.elephantbase.net/computer/eleeye_horizon.htm">中国象棋程序设计探索<FONT 
face="Times New Roman">(</FONT>五<FONT 
face="Times New Roman">)</FONT>：克服水平线效应</A> 
<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/eleeye_book.htm">中国象棋程序设计探索<FONT 
face="Times New Roman">(</FONT>七<FONT face="Times New Roman">)</FONT>：开局库</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>