数据结构——简介.htm

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

        face="Times New Roman"><STRONG>103</STRONG></FONT></TD></TR>
    <TR>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>80</STRONG></FONT></TD>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>81</STRONG></FONT></TD>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>82</STRONG></FONT></TD>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>83</STRONG></FONT></TD>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>84</STRONG></FONT></TD>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>85</STRONG></FONT></TD>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>86</STRONG></FONT></TD>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>87</STRONG></FONT></TD></TR>
    <TR>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>64</STRONG></FONT></TD>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>65</STRONG></FONT></TD>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>66</STRONG></FONT></TD>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>67</STRONG></FONT></TD>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>68</STRONG></FONT></TD>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>69</STRONG></FONT></TD>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>70</STRONG></FONT></TD>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>71</STRONG></FONT></TD></TR>
    <TR>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>48</STRONG></FONT></TD>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>49</STRONG></FONT></TD>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>50</STRONG></FONT></TD>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>51</STRONG></FONT></TD>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>52</STRONG></FONT></TD>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>53</STRONG></FONT></TD>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>54</STRONG></FONT></TD>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>55</STRONG></FONT></TD></TR>
    <TR>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>32</STRONG></FONT></TD>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>33</STRONG></FONT></TD>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>34</STRONG></FONT></TD>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>35</STRONG></FONT></TD>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>36</STRONG></FONT></TD>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>37</STRONG></FONT></TD>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>38</STRONG></FONT></TD>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>39</STRONG></FONT></TD></TR>
    <TR>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>16</STRONG></FONT></TD>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>17</STRONG></FONT></TD>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>18</STRONG></FONT></TD>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>19</STRONG></FONT></TD>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>20</STRONG></FONT></TD>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>21</STRONG></FONT></TD>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>22</STRONG></FONT></TD>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>23</STRONG></FONT></TD></TR>
    <TR>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>0</STRONG></FONT></TD>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>1</STRONG></FONT></TD>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>2</STRONG></FONT></TD>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>3</STRONG></FONT></TD>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>4</STRONG></FONT></TD>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>5</STRONG></FONT></TD>
      <TD align=middle bgColor=#000000><FONT face="Times New Roman" 
        color=#ffffff><STRONG>6</STRONG></FONT></TD>
      <TD align=middle bgColor=#ffffff><FONT 
        face="Times New Roman"><STRONG>7</STRONG></FONT></TD></TR></TBODY></TABLE>
  <DT>　 
  <DT>　　这样，格子<FONT face="Times New Roman"><EM>i</EM></FONT>的左边一格是<FONT 
  face="Times New Roman"><EM>i</EM> </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman"> 1</FONT>，右边是<FONT face="Times New Roman"><EM>i</EM> + 
  1</FONT>，上边是<FONT face="Times New Roman"><EM>i</EM> + 16</FONT>，下边是<FONT 
  face="Times New Roman"><EM>i</EM> </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman"> 16</FONT>，等等。棋盘被表示为<FONT 
  face="Times New Roman">128</FONT>个格子的数组<FONT 
  face="Times New Roman">(</FONT>其中<FONT 
  face="Times New Roman">64</FONT>格代表棋盘上存在的格子<FONT 
  face="Times New Roman">)</FONT>，这种表示的优势在于：<FONT face="Times New Roman">(1) 
  </FONT>数组仅用<FONT face="Times New Roman">1</FONT>个指标，这样写的程序要比用<FONT 
  face="Times New Roman">2</FONT>个指标快；<FONT face="Times New Roman">(2) 
  </FONT>可以快速简单地判断某个格子<FONT 
  face="Times New Roman"><EM>i</EM></FONT>是否在棋盘上——当且仅当<FONT 
  face="Times New Roman">(i &amp; 0x88) == 0</FONT>时<FONT 
  face="Times New Roman"><EM>i</EM></FONT>在棋盘上。<FONT 
  face="Times New Roman">(</FONT>因为列超出范围时<FONT face="Times New Roman"><EM>i</EM> 
  &amp; 0x08</FONT>不为零，而行超出范围时<FONT face="Times New Roman"><EM>i</EM> &amp; 
  0x80</FONT>不为零。<FONT face="Times New Roman">)</FONT>这是一个非常有效而且常用的技巧。 
  <DT>　 
  <DT>　　<FONT face=楷体_GB2312 size=4><STRONG>四、位棋盘</STRONG></FONT> 
  <DT>　　我必须在这里多花些笔墨，因为这个技术还不被人所熟悉，但是我认为它可能会很好用的。以前用一个格子数组，每个元素含有一个棋子，现在取而代之的是一个棋子数组，每个元素代表棋盘上哪几个格子有这个棋子，按位压缩表示。由于棋盘上有<FONT 
  face="Times New Roman">64</FONT>个格子，所以棋盘可以压缩成一个<FONT 
  face="Times New Roman">64</FONT>位的字<FONT 
  face="Times New Roman">(</FONT>即两个<FONT 
  face="Times New Roman">32</FONT>位的字<FONT 
  face="Times New Roman">)</FONT>。这种表示最大的优势在于，可以通过布尔操作<FONT 
  face="Times New Roman">(</FONT>位操作<FONT 
  face="Times New Roman">)</FONT>来加快局面评估和着法生成操作的速度。试想一下，如此烦琐的事情可以用压缩的字运算来解决，例如下面的局面： 

  <DT>　 
  <DIV align=center>
  <CENTER></DIV>
  <DT><IMG height=256 src="数据结构——简介_files/struct_intro.gif" width=256> </CENTER>
  <DIV></DIV>
  <DT>　 
  <DT>　　白方的兵<FONT face="Times New Roman">(</FONT>这个<FONT 
  face="Times New Roman">64</FONT>位数字记作<FONT 
  face="Times New Roman">wP)</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 1 0 0 
  <DD>0 0 0 0 0 1 0 0 
  <DD>0 0 0 0 1 0 0 0 
  <DD>0 0 0 0 0 0 0 0 
  <DD>1 1 1 0 0 0 0 1 
  <DD>0 0 0 0 0 0 0 0 
  <DT>　 
  <DT>　　而被黑方占据的格子可以用下面的公式来计算： 
  <DT>　 
  <DD>bOcc = bP | bN | bB | bR | bQ | bK 
  <DT>　 
  <DT>　　<FONT face="Times New Roman">(</FONT>这里<FONT 
  face="Times New Roman">bP</FONT>等等代表黑方不同兵种的棋子<FONT 
  face="Times New Roman">)</FONT>，类似地可以计算白方占据的格子，还可以把这两个格子作“或”运算得到所有被占的格子。这些白兵前进一格可能到达的格子，可以用下面的公式计算： 

  <DT>　 
  <DD>single_pawn_moves = (wP &lt;&lt; 8) &amp; ~occupied 
  <DT>　 
  <DT>　　现在仔细看一下过程，先将<FONT face="Times New Roman">wP</FONT>左移<FONT 
  face="Times New Roman">8</FONT>位，来产生每个兵前面的格子： 
  <DT>　 
  <DD>0 0 0 0 0 0 0 0 
  <DD>0 0 0 0 0 1 0 0 
  <DD>0 0 0 0 0 1 0 0 
  <DD>0 0 0 0 1 0 0 0 
  <DD>0 0 0 0 0 0 0 0 
  <DD>1 1 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>　　然后求被占格子的“非”运算得到空的格子： 
  <DT>　 
  <DD>0 0 1 1 0 0 1 0 
  <DD>1 0 1 0 1 0 0 0 
  <DD>1 1 1 0 0 0 1 1 
  <DD>1 0 1 1 1 0 1 1 
  <DD>1 0 1 1 0 1 1 1 
  <DD>1 0 1 1 1 0 1 1 
  <DD>0 0 0 1 1 1 1 0 
  <DD>0 1 0 1 0 0 1 0 
  <DT>　 
  <DT>　　对以上两个位棋盘按位作“与”运算，就得到这些兵前面的没有被占的格子了： 
  <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 1 0 0 0 
  <DD>0 0 0 0 0 0 0 0