其他策略——残局库.htm

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

  1</FONT><FONT color=#0000ff>】</FONT>，这个局面是杀棋，所以把它设为<FONT 
  face="Times New Roman">LOSS</FONT>。在我们要讨论的这个局面中，根本不能检查到什么。在主循环的第一次遍历中，会为“白王在<FONT 
  face="Times New Roman">g3</FONT>，黑王在<FONT 
  face="Times New Roman">g1</FONT>，白车在<FONT 
  face="Times New Roman">a2</FONT>”<FONT color=#0000ff>【</FONT><FONT 
  face="Times New Roman" color=#0000ff>8/8/8/8/8/6K1/R7/6k1 w - - 0 
  1</FONT><FONT color=#0000ff>】</FONT>产生所有着法，发现走了<FONT 
  face="Times New Roman">Rb2-b1</FONT>后就是<FONT 
  face="Times New Roman">LOSS</FONT>局面，根据规则这个局面就设为<FONT 
  face="Times New Roman">WIN</FONT>。下一步，为黑王在<FONT 
  face="Times New Roman">h1</FONT>的局面<FONT color=#0000ff>【</FONT><FONT 
  face="Times New Roman" color=#0000ff>8/8/8/8/8/6K1/R7/7k b - - 0 1</FONT><FONT 
  color=#0000ff>】</FONT>找后续局面，发现所有的后续局面都是<FONT 
  face="Times New Roman">WIN</FONT>局面<FONT 
  face="Times New Roman">(</FONT>这个局面的后续局面只有一个<FONT 
  face="Times New Roman">)</FONT>。最后把这个局面设成<FONT 
  face="Times New Roman">LOSS</FONT>，就得到了正确的结果。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>索引函数</STRONG></FONT> 
  <DT>　 
  <DT>　　索引函数对这个算法非常重要，你无法存储整个局面并对他们设定结果，因为结果只需要<FONT 
  face="Times New Roman">2</FONT>位，而整个局面需要用大量存储器来描述。如果你存储整个局面，你就会浪费大量的存储器。用了索引函数以后，你就能够简单地用一个数字来代表局面了，你不需要把结果和索引数字都记下来，而只需要以索引数字为数组的指标，只在数组中存储结果。那么如何才能找到符合上述性质的索引函数呢？看上去这是个很吓人的工作，实际上用简单的方法来构造索引函数是可行的。对于棋子各不相同的残局<FONT 
  face="Times New Roman">(</FONT>例如白王、白车和黑王<FONT 
  face="Times New Roman">)</FONT>，就非常简单，把格子标号为<FONT 
  face="Times New Roman">0</FONT>到<FONT 
  face="Times New Roman">63</FONT>，就可以写下这样的公式： 
  <DT>　 
  <DD><FONT size=3>index = wK_index + 64 * wR_index + 64 * 64 * bK_index;</FONT> 

  <DT>　 
  <DT>　　这个函数完成了局面到数字的转换，并且它是可逆的<FONT face="Times New Roman">(wK_index = index % 
  64, wR_index = (index / 64) % 64</FONT>，等等<FONT 
  face="Times New Roman">)</FONT>，但是它会产生一些不合理局面<FONT 
  face="Times New Roman">(</FONT>例如几个子在同一个格子上，或两个王紧挨着<FONT 
  face="Times New Roman">)</FONT>。这个函数也没有利用棋盘的对称性。这些细节问题是完全可以解决的，但是在这里我不想多说了。那么如果棋盘上有多于一个的相同棋子，例如王双车对王，怎么办呢？我们照样写： 

  <DT>　 
  <DD><FONT size=3>index = wK_index + 64 * wR1_index + 64 * 64 * wR2_index + 64 
  * 64 * 64 * bK_index; </FONT>
  <DT>　 
  <DT>　　这样当然很管用，但是非常愚笨，因为<FONT face="Times New Roman">1</FONT>号车在<FONT 
  face="Times New Roman"><EM>x</EM></FONT>格而<FONT 
  face="Times New Roman">2</FONT>号车在<FONT 
  face="Times New Roman"><EM>y</EM></FONT>格，情况跟<FONT 
  face="Times New Roman">2</FONT>号车在<FONT 
  face="Times New Roman"><EM>x</EM></FONT>格而<FONT 
  face="Times New Roman">1</FONT>号车在<FONT 
  face="Times New Roman"><EM>y</EM></FONT>格是一样的。这样我们的索引就比必要的数多了一倍！为了解决这个问题，我们用组合公式来表示<FONT 
  face="Times New Roman">2</FONT>个相同的子在<FONT 
  face="Times New Roman">64</FONT>个位置上的情况：在数学课上你肯定学过用<FONT 
  face="Times New Roman"><EM>N</EM> = 64 × 63 / 2</FONT>来做。因此我们可以写成： 
  <DD>　 
  <DD><FONT size=3>index = wK_index + 64 * combinedindex + 64 * N * bK_index; 
  </FONT>
  <DD>　 
  <DT>　　剩下来的问题就是由车的具体位置来计算“组合的车的索引”了，它是<FONT 
  face="Times New Roman">0</FONT>到<FONT face="Times New Roman">64 × 63 / 2 
  </FONT><FONT face=Symbol>-</FONT><FONT face="Times New Roman"> 
  1</FONT>之间的数。用<FONT face="Times New Roman"><EM>r</EM><SUB>1</SUB></FONT>和<FONT 
  face="Times New Roman"><EM>r</EM><SUB>2</SUB></FONT>表示两个车的位置，并且<FONT 
  face="Times New Roman"><EM>r</EM><SUB>1</SUB> &lt; 
  <EM>r</EM><SUB>2</SUB>(</FONT>这样就等同于除以<FONT 
  face="Times New Roman">2</FONT>了<FONT face="Times New Roman">!)</FONT>。我们有： 
  <DD>　 
  <DD><FONT size=3>combinedindex = bicoef(r1, 1) + bicoef(r2, 2);</FONT> 
  <DT>　 
  <DT>　　这里<FONT face="Times New Roman">bicoef(<EM>x</EM>, 
  <EM>y</EM>)</FONT>代表<FONT face="Times New Roman"><EM>x</EM></FONT>和<FONT 
  face="Times New Roman"><EM>y</EM>(<EM>x</EM> &gt; 
  <EM>y</EM>)</FONT>的二项式系数，即<FONT face="Times New Roman"><EM>x</EM>! × 
  <EM>y</EM>! / (<EM>x</EM> </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman"> 
  <EM>y</EM>)!</FONT>，任意数量的棋子都可以由这个组合索引公式产生。它的逆公式有点复杂，如果是<FONT 
  face="Times New Roman"><EM>k</EM></FONT>个子在<FONT 
  face="Times New Roman"><EM>n</EM></FONT>个格子上的组合索引，我们就必须用顺序搜索的办法来分析它的组成：因为组合索引的最后一项总是最大的，所以我们要依次计算<FONT 
  face="Times New Roman"><EM>i</EM> = <EM>n</EM> </FONT><FONT 
  face=Symbol>-</FONT><FONT face="Times New Roman"> 1, <EM>n</EM> </FONT><FONT 
  face=Symbol>-</FONT><FONT face="Times New Roman"> 2, ...</FONT>的<FONT 
  face="Times New Roman">bicoef(<EM>i</EM>, 
  <EM>k</EM>)</FONT>，直到比组合索引数小为止。一旦找到了<FONT 
  face="Times New Roman"><EM>i</EM></FONT>，我们就知道它在第<FONT 
  face="Times New Roman"><EM>i</EM></FONT>格上，然后在组合索引上减去<FONT 
  face="Times New Roman">bicoef(<EM>i</EM>, <EM>k</EM>)</FONT>。然后我们依次计算<FONT 
  face="Times New Roman"><EM>j</EM> = <EM>i</EM> </FONT><FONT 
  face=Symbol>-</FONT><FONT face="Times New Roman"> 1, <EM>i</EM> </FONT><FONT 
  face=Symbol>-</FONT><FONT face="Times New Roman"> 2, ...</FONT>的<FONT 
  face="Times New Roman">bicoef(<EM>j</EM>, <EM>k</EM> </FONT><FONT 
  face=Symbol>-</FONT><FONT face="Times New Roman"> 
  1)</FONT>，因为我们已经在建立索引函数的时候知道<FONT face="Times New Roman"><EM>j</EM> &lt; 
  <EM>i</EM></FONT>了。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>压缩</STRONG></FONT> 
  <DT>　 
  <DT>　　当你开始生成残局库时，你一定会马上意识到你要建立的残局库是非常庞大的。例如，<FONT 
  face="Times New Roman">8</FONT>子的西洋跳棋残局库如果没有压缩，就需要大约<FONT 
  face="Times New Roman">40GB</FONT>的磁盘空间。如果你需要在<FONT 
  face="Times New Roman">1GB</FONT>的<FONT 
  face="Times New Roman">RAM</FONT>的计算机上使用这个残局库，你就必须对它进行压缩。压缩这类残局库的标准方法是“行程编码”<FONT 
  face="Times New Roman">(RLE</FONT>，<FONT face="Times New Roman">Run-Length 
  Encoding)</FONT>：当你在查找后退式分析所产生的数组时，它看上去会是这样的： 
  <DD>　 
  <DD><FONT size=3>....WWWBWWLLDBDBDDDWLBLLLWWBDDD...</FONT> 
  <DT>　 
  <DT>　　这里<FONT 
  face="Times New Roman">WLDB</FONT>代表胜负和坏，坏的意思是局面不合理，使用有间隙的索引，或者不走棋的一方被将军了，这种情况就会发生。要对此进行压缩，我们首先注意到对坏的标志可以任意处理，因为它们没有用，因此我们将它们设定为最方便压缩的值： 

  <DD>　 
  <DD><FONT size=3>....WWWWWWLLDDDDDDDWLLLLLWWDDDD...</FONT> 
  <DT>　 
  <DT>　　行程编码存储的就是一对对数值和长度，上面的例子就转换为： 
  <DD>　 
  <DD><FONT size=3>(W,6) (L,2) (D,7) (W,1) (L,5) (W,2) (D,4)</FONT> 
  <DT>　 
  <DT>　　如果行程非常长<FONT face="Times New Roman">(</FONT>我没有耐心来造一个行程非常长的例子<FONT 
  face="Times New Roman">)</FONT>，那么这种压缩的效果就非常好。<FONT 
  face="Times New Roman">8</FONT>子的西洋跳棋残局库可以压缩到大约<FONT 
  face="Times New Roman">4GB</FONT>，压缩因子是<FONT face="Times New Roman">10</FONT>。 

  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>在搜索中读取数据库</STRONG></FONT> 
  <DT>　 
  <DT>　　压缩完残局库以后，你必须写一个飞跃式<FONT 
  face="Times New Roman">(on-the-fly)</FONT>的解压缩程序，根据局面找到结果。或许这还不够，如果残局库大到超过你的<FONT 
  face="Times New Roman">RAM</FONT>，你就必须为自己的残局库写一个存储器管理程序。你不会指望<FONT 
  face="Times New Roman">Windows(</FONT>或其他操作系统<FONT 
  face="Times New Roman">)</FONT>来帮你管理残局库，因为你自己写的程序是高效的。管理残局库的通常做法是把压缩的残局库分成一个个几千字节的块<FONT 
  face="Times New Roman">(Chunks)</FONT>，如果你需要知道某个局面的结果，就一次读取整个块。从磁盘读取<FONT 
  face="Times New Roman">1</FONT>字节或<FONT 
  face="Times New Roman">1</FONT>千字节是没有差别的，速度只取决于磁盘的寻找时间，而跟传输速度无关。一次读取整个块，就把很多相似的局面装入存储器，这些局面可能是你以后要用到的。一般来说，你会用“最近最少用到”<FONT 
  face="Times New Roman">(Least-Recently-Used)</FONT>的策略，来决定在装入一个块的时候哪个块应该被覆盖掉。即便你用了块，由于磁盘比起存储器来说实在太慢，你无法对所有局面都去查找残局库。通常你只会在第<FONT 
  face="Times New Roman"><EM>x</EM></FONT>层以外去读取磁盘上的残局库局面，而在<FONT 
  face="Times New Roman"><EM>x</EM></FONT>层以内你只会在存储器中查找这些局面。 
  <DT>　 
  <DT>　　原文：<A href="http://www.fierz.ch/strategy3.htm" target=_blank><FONT 
  face="Times New Roman">http://www.fierz.ch/strategy3.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_ponder.htm">其他策略——后台思考</A> 
<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/other_book.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>