数据结构——0x88着法产生方法.htm

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

  <DT>　　而<FONT face="Times New Roman">0x88</FONT>机制恰恰可以解决这个问题。用一个<FONT 
  face="Times New Roman">16x8</FONT>的棋盘，就得到一个标志位，你就能知道棋子是否到了右边那个没用的棋盘上，因为在这个棋盘上<FONT 
  face="Times New Roman">0x08</FONT>位置为<FONT 
  face="Times New Roman">1</FONT>。例如<FONT 
  face="Times New Roman">h1</FONT>标号是<FONT 
  face="Times New Roman">7</FONT>，加<FONT face="Times New Roman">1</FONT>后就是<FONT 
  face="Times New Roman">8</FONT>，而<FONT 
  face="Times New Roman">0x08</FONT>位变成了<FONT 
  face="Times New Roman">1</FONT>。左边的实棋盘上没有一格的<FONT 
  face="Times New Roman">0x08</FONT>位是<FONT 
  face="Times New Roman">1</FONT>，而右边的虚棋盘每个格子的<FONT 
  face="Times New Roman">0x08</FONT>位都是<FONT 
  face="Times New Roman">1</FONT>。如果你在<FONT 
  face="Times New Roman">a3</FONT>并且要朝左走，你会到达<FONT 
  face="Times New Roman">p2</FONT>，这是在虚棋盘上，<FONT 
  face="Times New Roman">0x08</FONT>位是<FONT face="Times New Roman">1</FONT>。 
  <DT>　　可以把<FONT face="Times New Roman">0x08</FONT>的检测和<FONT 
  face="Times New Roman">0x80</FONT>的检测结合起来<FONT 
  face="Times New Roman">(</FONT>原来的<FONT 
  face="Times New Roman">0x40</FONT>变成了<FONT 
  face="Times New Roman">0x80</FONT>，因为现在棋盘变成<FONT 
  face="Times New Roman">128</FONT>个格子了<FONT 
  face="Times New Roman">)</FONT>，并且两次测试要同时完成。把<FONT 
  face="Times New Roman">0x80</FONT>和<FONT 
  face="Times New Roman">0x08</FONT>结合起来就是<FONT 
  face="Times New Roman">0x88</FONT>，这就是这套方案的名称。 
  <DT>　　如果你知道我在说什么，你就明白<FONT 
  face="Times New Roman">0x88</FONT>是怎样运作的。你的着法产生的循环就应该写成下面的样子： 
  <DD>　 
  <DD><FONT face=宋体>while (!(index &amp; 0x88)) {</FONT> 
  <DD>　<FONT face=宋体>GenerateMove(index);</FONT> 
  <DD>　<FONT face=宋体>index += delta;</FONT> 
  <DD><FONT face=宋体>}</FONT> 
  <DT>　 
  <DT>　　这就非常简洁了，你可以这么写： 
  <DD>　 
  <DD><FONT face=宋体>void GenerateMoves(int square, int * ptab) {</FONT> 
  <DD>　<FONT face=宋体>for (; *ptab; ptab++) {</FONT> 
  <DD>　　<FONT face=宋体>int index;</FONT> 
  <DD>　　<FONT face=宋体>for (index = square; !(index &amp; 0x88); index += *ptab) 
  {</FONT> 
  <DD>　　　<FONT face=宋体>GenerateMove(index);</FONT> 
  <DD>　　} 
  <DD>　<FONT face=宋体>}</FONT> 
  <DD><FONT face=宋体>}</FONT> 
  <DD><FONT face=宋体>int argdBishop[] = { 17, 15, -17, -15, 0 };</FONT> 
  <DD><FONT face=宋体>void GenerateBishopMoves(int square) {</FONT> 
  <DD>　<FONT face=宋体>GenerateMove(square, argdBishop);</FONT> 
  <DD><FONT face=宋体>}</FONT> 
  <DT>　 
  <DT>　　这样写就非常快了，并且代码很短。车或者后跟象的区别只是表中的数据不同罢了，因此你可以花很短的时间把其他棋子的代码加上，而且不需要任何改动。 
  <DT>　　当然，你仍然需要为兵和王车易位另写代码，但每个体系都得如此。<FONT 
  face="Times New Roman">0x88</FONT>体系能给你一点帮助，可是代码写出来仍然很丑。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>奖励</STRONG></FONT> 
  <DT>　 
  <DT>　　<FONT face="Times New Roman">0x88</FONT>体系还可以快速判断攻击，这就是要使用<FONT 
  face="Times New Roman">16x8</FONT>棋盘的另一个原因。如果你将两格子的号码相减，你会得到两个格子之间的关系。 
  <DT>　　例如，如果两个格子减下来是<FONT 
  face="Times New Roman">1</FONT>，那么第二个格子就在第一个格子的左边。如果减下来是<FONT 
  face="Times New Roman">16</FONT>，那么第二个格子就在第一个格子的上面。 
  <DT>　　这在<FONT face="Times New Roman">8x8</FONT>棋盘上是做不到的。<FONT 
  face="Times New Roman">d1 </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman"> c1 = 1</FONT>确实如此，但是<FONT face="Times New Roman">a2 - 
  h1</FONT>也是<FONT face="Times New Roman">1</FONT>。这个“回圈”问题可以在<FONT 
  face="Times New Roman">128</FONT>个格子的棋盘上解决。 
  <DT>　　你在写判断将军或者一个子是否在捉另一个子的函数时，可以利用以上这个技巧。 
  <DT>　　你可以用一个大约<FONT face="Times New Roman">257</FONT>个元素<FONT 
  face="Times New Roman">(</FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman">128 ~ 
  +128)</FONT>的数组，里面存放一些代表棋子的位域，来说明哪些棋子能在某两格间移动，而移动的增量就是数组的指标。你可以用少于<FONT 
  face="Times New Roman">257</FONT>个的元素，但是我没有尝试过。 
  <DT>　　例如在增量为<FONT face="Times New Roman">1</FONT>的元素里，应该有王、后、车的位置是置<FONT 
  face="Times New Roman">1</FONT>的。如果增量是<FONT 
  face="Times New Roman">17</FONT>，那么置<FONT 
  face="Times New Roman">1</FONT>的是王、后、象和白兵。 
  <DT>　　这样就可以写出比较快的检查将军的程序了。你把攻击子的格子和目标格子相减得到增量，加上<FONT 
  face="Times New Roman">128</FONT>以避免负的指标，然后去找预先计算好的攻击数组，看看是否符合这个攻击子的类型，以确认它有可能一步到达目标格。 

  <DT>　　如果你确认这个子可能到达目标格，那么你还要检查它是否是长兵器<FONT 
  face="Times New Roman">(</FONT>后、车或象<FONT 
  face="Times New Roman">)</FONT>。如果不是，那就完成判断了，否则你要沿着从攻击子到目标格的射线去找有没有阻挡的棋子。 
  <DT>　　我不想提供这个程序的代码，因为它很容易写。这个程序的速度是比较快的。 
  <DT>　 
  <DT>　　原文：<A href="http://www.seanet.com/~brucemo/topics/0x88.htm" 
  target=_blank><FONT 
  face="Times New Roman">http://www.seanet.com/~brucemo/topics/0x88.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/struct_movegen.htm">数据结构——着法生成器</A> 
<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/struct_zobrist.htm">数据结构——<FONT 
face="Times New Roman">Zobrist</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="数据结构——0x88着法产生方法_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>