📄 数据结构——简介.htm

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 HTM
📖 第 1 页 / 共 3 页
字号:
上一页 1 23
  <DD>1 0 1 0 0 0 0 1 
  <DD>0 0 0 0 0 0 0 0 
  <DD>0 0 0 0 0 0 0 0 
  <DT>　 
  <DT>　　参照兵走一格的方法，可以找到兵走两格的着法，即再左移<FONT 
  face="Times New Roman">8</FONT>位，“与”上没有子的格子，再“与”上一个只有第四行都占满的常数棋盘<FONT 
  face="Times New Roman">(</FONT>这是兵走两格能到达的唯一一行<FONT 
  face="Times New Roman">)</FONT>： 
  <DT>　 
  <DD>0 0 0 0 0 0 0 0 
  <DD>0 0 0 0 0 0 0 0 
  <DD>0 0 0 0 0 0 0 0 
  <DD>0 0 0 0 0 0 0 0 
  <DD>1 1 1 1 1 1 1 1 
  <DD>0 0 0 0 0 0 0 0 
  <DD>0 0 0 0 0 0 0 0 
  <DD>0 0 0 0 0 0 0 0 
  <DT>　 
  <DT>　　值得注意的是，这个常数棋盘是在编译的时候生成的，而不需要在每次着法生成的时候再计算出来。兵吃子的情况也类似，先左移<FONT 
  face="Times New Roman">7</FONT>位或<FONT 
  face="Times New Roman">9</FONT>位，再“与”上一个常数棋盘以过滤左边线或右边线的格子<FONT 
  color=#0000ff>【对于左移</FONT><FONT face="Times New Roman" 
  color=#0000ff>7</FONT><FONT 
  color=#0000ff>位产生吃右边子时，需要考虑子在右边线的情况，此时左移</FONT><FONT face="Times New Roman" 
  color=#0000ff>7</FONT><FONT 
  color=#0000ff>位是同一行的左边线，因此需要排除这个格子，即“与”上一个常数棋盘，代表除左边线以外的所有格子】</FONT>，最后“与”上<FONT 
  face="Times New Roman">bOcc</FONT><FONT 
  color=#0000ff>【前面提到过这个棋盘，代表黑子所占的格子】</FONT>。 
  <DT>　　位棋盘这个技术不能简化代码，但是它能一次就产生兵的所有着法，而不是一次只产生一个着法。此外，这个过程中有些表达式需要多次反复使用<FONT 
  face="Times New Roman">(</FONT>例如<FONT 
  face="Times New Roman">bOcc)</FONT>，但只要计算一次就可以了。因此，位棋盘最终变得非常高效，在棋子数比国际象棋少的棋类中，我想位棋盘的效果会更好。 

  <DT>　　有个复杂的问题产生了：计算位棋盘中有多少非零位，或者找到<FONT 
  color=#0000ff>【最低或最高的】</FONT>一个非零位<FONT 
  face="Times New Roman">(</FONT>例如把兵可以到达的位棋盘转化为一系列着法)，这些操作往往非常重要。计算位数的操作可以一次计算一个字节，做一个长度为<FONT 
  face="Times New Roman">256</FONT>的数组，每个元素代表它的指标所含有多少个非零位，然后通过查表来完成。在找到一个非零位的计算中有个技巧：<FONT 
  face="Times New Roman"><EM>x</EM> ^ (<EM>x</EM> </FONT><FONT 
  face=Symbol>-</FONT><FONT face="Times New Roman"> 1)(</FONT>“<FONT 
  face="Times New Roman">^</FONT>”代表异或<FONT 
  face="Times New Roman">)</FONT>，会得到一个二进制为<FONT 
  face="Times New Roman">...000111...</FONT>的数，<FONT 
  face="Times New Roman"><EM>x</EM> ^ (<EM>x</EM> </FONT><FONT 
  face=Symbol>-</FONT><FONT face="Times New Roman"> 1)</FONT>的第一位就是<FONT 
  face="Times New Roman"><EM>x</EM></FONT>的最后一位非零位。如果要求得这个数字<FONT 
  color=#0000ff>【</FONT><FONT face="Times New Roman" color=#0000ff><EM>x</EM> ^ 
  (<EM>x</EM> </FONT><FONT face=Symbol color=#0000ff>-</FONT><FONT 
  face="Times New Roman" color=#0000ff> 1)</FONT><FONT 
  color=#0000ff>，即型如</FONT><FONT face="Times New Roman" 
  color=#0000ff>...000111...</FONT><FONT 
  color=#0000ff>的数】</FONT>的第一位，就把它对某个特定的数<FONT 
  face="Times New Roman">M</FONT>取余数<FONT 
  face="Times New Roman">(</FONT>不同的<FONT 
  face="Times New Roman">...000111...</FONT>这样的数对<FONT 
  face="Times New Roman">M</FONT>取余数必须不同<FONT 
  face="Times New Roman">)</FONT>，然后去查表。例如，以下的代码可以找到一个字节的最后一个非零位： 
  <DD>　 
  <DD>int T = { -1, 0, 7, 1, 3, -1, 6, 2, 5, 4, -1, -1 }; 
  <DD>int last_bit(unsigned char b) { 
  <DD>　return T[(b^(b-1)) % 11]; 
  <DD>} 
  <DT>　 
  <DT>　　<FONT color=#0000ff>【把原作者提到的这个技巧扩展到</FONT><FONT face="Times New Roman" 
  color=#0000ff>16</FONT><FONT color=#0000ff>位或</FONT><FONT 
  face="Times New Roman" color=#0000ff>32</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> 

  <DT><FONT color=#0000ff>　　</FONT><FONT face="Times New Roman" 
  color=#0000ff>(1) </FONT><FONT color=#0000ff>求一个</FONT><FONT 
  face="Times New Roman" color=#0000ff>32</FONT><FONT 
  color=#0000ff>位数中有几位非零位的运算——</FONT><FONT face="Times New Roman" 
  color=#0000ff>Count32</FONT><FONT color=#0000ff>操作：</FONT> 
  <DD>　 
  <DD><FONT color=#0000ff>int Count32(unsigned long Arg) {</FONT> 
  <DD><FONT color=#0000ff>　Arg = ((Arg &gt;&gt; 1) &amp; 0x55555555) + (Arg 
  &amp; 0x55555555);</FONT> 
  <DD><FONT color=#0000ff>　Arg = ((Arg &gt;&gt; 2) &amp; 0x33333333) + (Arg 
  &amp; 0x33333333);</FONT> 
  <DD><FONT color=#0000ff>　Arg = ((Arg &gt;&gt; 4) &amp; 0x0f0f0f0f) + (Arg 
  &amp; 0x0f0f0f0f);</FONT> 
  <DD><FONT color=#0000ff>　Arg = ((Arg &gt;&gt; 8) &amp; 0x00ff00ff) + (Arg 
  &amp; 0x00ff00ff);</FONT> 
  <DD><FONT color=#0000ff>　return (Arg &gt;&gt; 16) + (Arg &amp; 
  0x0000ffff);</FONT> 
  <DD><FONT color=#0000ff>}</FONT> 
  <DT>　 
  <DT><FONT color=#0000ff>　　</FONT><FONT face="Times New Roman" 
  color=#0000ff>(2) </FONT><FONT color=#0000ff>求最低位非零位是第几位的运算——</FONT><FONT 
  face="Times New Roman" color=#0000ff>Lsb32</FONT><FONT 
  color=#0000ff>操作</FONT><FONT face="Times New Roman" color=#0000ff>(LSB = Least 
  Significant Bit)</FONT><FONT color=#0000ff>：</FONT> 
  <DD>　 
  <DD><FONT color=#0000ff>int Lsb32(unsigned long Arg) {</FONT> 
  <DD><FONT color=#0000ff>　int RetVal = 31;</FONT> 
  <DD><FONT color=#0000ff>　if (Arg &amp; 0x0000ffff) { RetVal -= 16; Arg &amp;= 
  0x0000ffff; }</FONT> 
  <DD><FONT color=#0000ff>　if (Arg &amp; 0x00ff00ff) { RetVal -= 8; Arg &amp;= 
  0x00ff00ff; }</FONT> 
  <DD><FONT color=#0000ff>　if (Arg &amp; 0x0f0f0f0f) { RetVal -= 4; Arg &amp;= 
  0x0f0f0f0f; }</FONT> 
  <DD><FONT color=#0000ff>　if (Arg &amp; 0x33333333) { RetVal -= 2; Arg &amp;= 
  0x33333333; }</FONT> 
  <DD><FONT color=#0000ff>　if (Arg &amp; 0x55555555) RetVal -=1;</FONT> 
  <DD><FONT color=#0000ff>　return RetVal;</FONT> 
  <DD><FONT color=#0000ff>}</FONT> 
  <DT>　 
  <DT><FONT color=#0000ff>　　</FONT><FONT face="Times New Roman" 
  color=#0000ff>(3) </FONT><FONT color=#0000ff>求最高位非零位是第几位的运算——</FONT><FONT 
  face="Times New Roman" color=#0000ff>Msb32</FONT><FONT 
  color=#0000ff>操作</FONT><FONT face="Times New Roman" color=#0000ff>(MSB = Most 
  Significant Bit)</FONT><FONT color=#0000ff>：</FONT> 
  <DD>　 
  <DD><FONT color=#0000ff>int Msb32(unsigned long Arg) {</FONT> 
  <DD><FONT color=#0000ff>　int RetVal = 0;</FONT> 
  <DD><FONT color=#0000ff>　if (Arg &amp; 0xffff0000) { RetVal += 16; Arg &amp;= 
  0xffff0000; }</FONT> 
  <DD><FONT color=#0000ff>　if (Arg &amp; 0xff00ff00) { RetVal += 8; Arg &amp;= 
  0xff00ff00; }</FONT> 
  <DD><FONT color=#0000ff>　if (Arg &amp; 0xf0f0f0f0) { RetVal += 4; Arg &amp;= 
  0xf0f0f0f0; }</FONT> 
  <DD><FONT color=#0000ff>　if (Arg &amp; 0xcccccccc) { RetVal += 2; Arg &amp;= 
  0xcccccccc; }</FONT> 
  <DD><FONT color=#0000ff>　if (Arg &amp; 0xaaaaaaaa) RetVal += 1;</FONT> 
  <DD><FONT color=#0000ff>　return RetVal;</FONT> 
  <DD><FONT color=#0000ff>}</FONT> 
  <DT>　 
  <DT><FONT color=#0000ff>　　对</FONT><FONT face="Times New Roman" 
  color=#0000ff>64</FONT><FONT color=#0000ff>位数字进行操作，把它分解成两个</FONT><FONT 
  face="Times New Roman" color=#0000ff>32</FONT><FONT 
  color=#0000ff>位字，分别对两个字调用上面的函数就可以了。如果程序能运行在</FONT><FONT face="Times New Roman" 
  color=#0000ff>64</FONT><FONT color=#0000ff>位的处理器上，只要对上面三个函数略加改动就可以了。】</FONT> 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>如何撤消着法？</STRONG></FONT> 
  <DT>　 
  <DT>　　还记得吗？我们说过在棋盘表示方法中需要涉及撤消着法的操作。现在有两种解决方案：<FONT face="Times New Roman">(1) 
  </FONT>用一个堆栈来保存棋盘，执行一个着法前先将棋盘压入堆栈，撤消着法就从堆栈弹出棋盘，恐怕这太慢了…… <FONT 
  face="Times New Roman">(2) 
  </FONT>用一个堆栈来保存着法，执行一个着法前先将该着法及其相关信息压入堆栈，撤消着法就根据该着法还原棋盘及其相关信息。例如，在国际象棋中只要保存被吃的棋子<FONT 
  face="Times New Roman">(</FONT>如果吃子的话<FONT 
  face="Times New Roman">)</FONT>，以及王车易位和吃过路兵的权利等信息。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>重复检测</STRONG></FONT> 
  <DT>　 
  <DT>　　某些棋类在发生重复局面时要用到特殊的规则，如围棋和国际象棋<FONT 
  face="Times New Roman">(</FONT>在国际象棋中，第三次出现重复局面时，制造重复局面的一方就有权宣布和棋<FONT 
  face="Times New Roman">)</FONT>。那么如何知道是否出现重复局面呢？答案很简单：用散列函数把局面转换成一个相当大的数<FONT 
  face="Times New Roman">(</FONT>我们以后要谈到这个问题，因为这个技术还可以加快搜索速度<FONT 
  face="Times New Roman">)</FONT>，然后保存一系列前面出现过的局面的散列值，从这些值里面找就是了。一个典型的散列函数，先随机产生一张<FONT 
  face="Times New Roman">64x13</FONT>的表，如果棋子<FONT 
  face="Times New Roman"><EM>y</EM></FONT>在位置<FONT 
  face="Times New Roman"><EM>x</EM></FONT>上，就把表中<FONT 
  face="Times New Roman">[<EM>x</EM>, <EM>y</EM>]</FONT>这个数加到散列值上<FONT 
  face="Times New Roman">(</FONT>忽略溢出<FONT 
  face="Times New Roman">)[</FONT>即<FONT 
  face="Times New Roman">Zobrist</FONT>值<FONT 
  face="Times New Roman">]</FONT>。值得注意的是，当棋子<FONT 
  face="Times New Roman"><EM>y</EM></FONT>从位置<FONT 
  face="Times New Roman"><EM>x</EM></FONT>走到位置<FONT 
  face="Times New Roman"><EM>z</EM></FONT>时，可以快速地更新散列值：减去<FONT 
  face="Times New Roman">[<EM>x</EM>, <EM>y</EM>]</FONT>并加上<FONT 
  face="Times New Roman">[<EM>z</EM>, <EM>y</EM>]</FONT>即可。 
  <DT>　 
  <DT>　　原文：<A href="http://www.ics.uci.edu/~eppstein/180a/970408.html" 
  target=_blank><FONT 
  face="Times New Roman">http://www.ics.uci.edu/~eppstein/180a/970408.html</FONT></A> 

  <DT>　　译者：黄晨 <FONT face="Times New Roman">(</FONT><A 
  href="mailto:webmaster@elephantbase.net"><FONT 
  face="Times New Roman">webmaster@elephantbase.net</FONT></A><FONT 
  face="Times New Roman">)</FONT> 
  <DT>　　类型：全译加译注 </DT></DL>
<DIR>
<LI>上一篇　<A href="http://www.elephantbase.net/computer/outline.htm">概述</A> 
<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/struct_bitboard.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>
上一页 1 23
💿 文件大小 859 K
👤 上传用户 Emouse
📂 所属分类文件格式
🏷️ 相关标签

#程序设计 #程序 #编写
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -