⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 解剖大象的眼睛——中国象棋程序设计探索(二)：棋盘结构和着法生成器.htm

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 HTM
📖 第 1 页 / 共 5 页
字号:
🔍
12345 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0054)http://www.elephantbase.net/computer/eleeye_struct.htm -->
<HTML><HEAD><TITLE>解剖大象的眼睛——中国象棋程序设计探索(二)：棋盘结构和着法生成器</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.536" name=GENERATOR></HEAD>
<BODY background=解剖大象的眼睛——中国象棋程序设计探索(二)：棋盘结构和着法生成器_files/background.gif>
<DL>
  <DIV align=center>
  <CENTER>
  <DT><FONT face=隶书 size=6>解剖大象的眼睛</FONT><FONT 
  size=6><STRONG>——</STRONG></FONT><FONT face=隶书 size=6>中国象棋程序设计探索</FONT> 
  </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT>　 </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT>黄晨 <FONT face="Times New Roman">*</FONT>　<FONT 
  face="Times New Roman">2005</FONT>年<FONT 
  face="Times New Roman">6</FONT>月初稿，<FONT 
  face="Times New Roman">2005</FONT>年<FONT face="Times New Roman">11</FONT>月修订 
  </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT><FONT face="Times New Roman">( * </FONT>联系地址：复旦大学化学系表面化学实验室，<FONT 
  face="Times New Roman">eMail</FONT>：<A 
  href="mailto:webmaster@elephantbase.net"><FONT 
  face="Times New Roman">webmaster@elephantbase.net</FONT></A><FONT 
  face="Times New Roman">)</FONT> </CENTER></DT></DIV>
  <DT>　 
  <DT><FONT face=Arial size=5><STRONG>(</STRONG></FONT><FONT face=楷体_GB2312 
  size=5><STRONG>二</STRONG></FONT><FONT face=Arial size=5><STRONG>) 
  </STRONG></FONT><FONT face=楷体_GB2312 size=5><STRONG>棋盘结构和着法生成器</STRONG></FONT> 

  <DT>　 
  <DT>　　在阅读本章前，建议读者先阅读《<A href="http://www.elephantbase.net/" 
  target=_blank>象棋百科全书</A>》网站中《<A 
  href="http://www.elephantbase.net/computer/outline.htm" 
  target=_blank>对弈程序基本技术</A>》专题的以下几篇译文： 
  <DT>　　<FONT face="Times New Roman">(1) </FONT><A 
  href="http://www.elephantbase.net/computer/struct_intro.htm" 
  target=_blank>数据结构——简介</A><FONT face="Times New Roman">(David 
  Eppstein)</FONT>； 
  <DT>　　<FONT face="Times New Roman">(2) </FONT><A 
  href="http://www.elephantbase.net/computer/struct_bitboard.htm" 
  target=_blank>数据结构——位棋盘</A><FONT face="Times New Roman">(James 
  Swafford)</FONT>； 
  <DT>　　<FONT face="Times New Roman">(3) </FONT><A 
  href="http://www.elephantbase.net/computer/struct_rotation.htm" 
  target=_blank>数据结构——旋转的位棋盘</A><FONT face="Times New Roman">(James 
  Swafford)</FONT>； 
  <DT>　　<FONT face="Times New Roman">(4) </FONT><A 
  href="http://www.elephantbase.net/computer/struct_movegen.htm" 
  target=_blank>数据结构——着法生成器</A><FONT face="Times New Roman">(James 
  Swafford)</FONT>； 
  <DT>　　<FONT face="Times New Roman">(5) </FONT><A 
  href="http://www.elephantbase.net/computer/struct_0x88.htm" 
  target=_blank>数据结构——<FONT face="Times New Roman">0x88</FONT>着法产生方法</A><FONT 
  face="Times New Roman">(Bruce Moreland)</FONT>； 
  <DT>　　<FONT face="Times New Roman">(6) </FONT><A 
  href="http://www.elephantbase.net/computer/struct_zobrist.htm" 
  target=_blank>数据结构——<FONT face="Times New Roman">Zobrist</FONT>键值</A><FONT 
  face="Times New Roman">(Bruce Moreland)</FONT>； 
  <DT>　 
  <DT><FONT face=Arial size=4><STRONG>2.1 </STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG>局面和着法的表示</STRONG></FONT> 
  <DT>　 
  <DT><FONT size=3>　　局面是象棋程序的核心数据结构，除了要包括棋盘、棋子、哪方要走、着法生成的辅助结构、</FONT><FONT 
  face="Times New Roman" size=3>Zobrist</FONT><FONT 
  size=3>键值等，还要包含一些历史着法，来判断重复局面。</FONT><FONT face="Times New Roman" 
  size=3>ElephantEye</FONT><FONT size=3>的局面结构很庞大</FONT><FONT 
  face="Times New Roman" size=3>(</FONT><FONT size=3>见</FONT><FONT 
  face="Times New Roman" size=3>&lt;position.h&gt;)</FONT><FONT 
  size=3>，其中大部分存储空间是用来记录历史局面的。</FONT> 
  <DD>　 
  <DD><FONT size=3>struct PositionStruct {</FONT> 
  <DD><FONT size=3>　……</FONT> 
  <DD><FONT size=3>　int nMoveNum;</FONT> 
  <DD><FONT size=3>　MoveStruct mvMoveList[MAX_MOVE_NUM]; 　// MAX_MOVE_NUM = 
  256</FONT> 
  <DD><FONT size=3>　unsigned char ucRepHash[REP_HASH_LEN]; // REP_HASH_LEN = 
  1024</FONT> 
  <DD><FONT size=3>　……</FONT> 
  <DD><FONT size=3>}</FONT> 
  <DT>　 
  <DT>　　其中<FONT face="Times New Roman">MoveStruct</FONT>这个结构记录了四个信息：<FONT 
  face="Times New Roman">(1) </FONT>着法的起始格<FONT 
  face="Times New Roman">(Src)</FONT>，<FONT face="Times New Roman">(2) 
  </FONT>着法的目标格<FONT face="Times New Roman">(Dst)</FONT>，<FONT 
  face="Times New Roman">(3) </FONT>着法吃掉的棋子<FONT 
  face="Times New Roman">(Cpt)</FONT>，<FONT face="Times New Roman">(4) 
  </FONT>着法是否将军<FONT 
  face="Times New Roman">(Chk)</FONT>。有意思的是，每个部分都只占一个字节，后两个部分<FONT 
  face="Times New Roman">(Cpt</FONT>和<FONT 
  face="Times New Roman">Chk)</FONT>与其说有特殊作用，不如说是为了凑一个<FONT 
  face="Times New Roman">32</FONT>位整数。在<FONT 
  face="Times New Roman">MoveStruct</FONT>出现的很多地方<FONT 
  face="Times New Roman">(</FONT>置换表、杀手着法表、着法生成表<FONT 
  face="Times New Roman">)</FONT>里，这两项都是没作用的，而只有在<FONT 
  face="Times New Roman">PositionStruct</FONT>结构的记录历史着法的堆栈中才有意义。 
  <DT>　　<FONT face="Times New Roman">Cpt</FONT>一项主要用在撤消着法上，它可以用来还原被吃的棋子，而<FONT 
  face="Times New Roman">Chk</FONT>一项则可以记录当前局面是否处于将军状态。<FONT 
  face="Times New Roman">ElephantEye</FONT>是用<FONT 
  face="Times New Roman">MakeMove()</FONT>函数来走棋的，每走完一步棋就做两次将军判断：第一次判断走完子的一方是否被将军，即<FONT 
  face="Times New Roman">Checked(sdPlayer)</FONT>，如果被将则立即撤消着法，并返回走子失败的信息；第二次判断要走的一方是否被将军，由于交换了走子方<FONT 
  face="Times New Roman">(</FONT>即执行了<FONT face="Times New Roman">sdPlayer = 1 
  </FONT><FONT face=Symbol>-</FONT><FONT face="Times New Roman"> 
  sdPlayer)</FONT>，所以仍旧是<FONT 
  face="Times New Roman">Checked(sdPlayer)</FONT>，如果被将则<FONT 
  face="Times New Roman">Chk</FONT>置为<FONT 
  face="Times New Roman">TRUE</FONT>，这个着法被压入历史着法堆栈。因此<FONT 
  face="Times New Roman">LastMove().Chk</FONT>就表示当前局面是否被将军。 
  <DT>　 
  <DT><FONT face=Arial size=4><STRONG>2.2 </STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG>循环着法的检测</STRONG></FONT> 
  <DT>　 
  <DT>　　<FONT face="Times New Roman">Cpt</FONT>和<FONT 
  face="Times New Roman">Chk</FONT>的另一个作用就是判断循环着法：<FONT 
  face="Times New Roman">ElephantEye</FONT>判断循环着法时，依次从堆栈顶往前读，读到吃过子的着法<FONT 
  face="Times New Roman">(Cpt</FONT>不为零<FONT 
  face="Times New Roman">)</FONT>就结束；而是否有单方面长将的情况，则是通过每个着法的<FONT 
  face="Times New Roman">Chk</FONT>一项来判断的。 
  <DT>　　在循环着法的检测中，我们感兴趣的不是<FONT face="Times New Roman">Cpt</FONT>和<FONT 
  face="Times New Roman">Chk</FONT>，而是<FONT 
  face="Times New Roman">RepHash</FONT>结构，这是一个微型的置换表，用来记录历史局面。<FONT 
  face="Times New Roman">ElephantEye</FONT>在做循环着法的判断这之前，先去探测这个置换表，如果命中置换表，则说明可能存在重复局面<FONT 
  face="Times New Roman">(</FONT>由于置换表可能有冲突，所以只是有这个可能<FONT 
  face="Times New Roman">)</FONT>，因而做循环检测；如果没有命中则肯定没有重复局面。 
  <DT>　　<FONT 
  face="Times New Roman">ElephantEye</FONT>使用“归位检测法”来判断循环着法，即从最后一个着法开始，依次向前撤消着法，并记录每个移动过的棋子所在的格子。如果所有移动过的棋子同时归位，那么循环着法就出现了。因此<FONT 
  face="Times New Roman">&lt;position.cpp&gt;</FONT>中的<FONT 
  face="Times New Roman">IsRep()</FONT>函数建立了两个归位数组，第一个记录了棋子的原始位置，第二个记录了新的位置，当两个位置重合时，说明棋子归位。 

  <DT>　 
  <DT><FONT face=Arial size=4><STRONG>2.3 </STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG>棋盘</STRONG></FONT><FONT face=Arial 
  size=4><STRONG>-</STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG>棋子联系数组</STRONG></FONT> 
  <DT>　 
  <DT>　　众所周知，棋盘的表示有两种方法。一是做一个棋盘数组<FONT face="Times New Roman">(</FONT>例如<FONT 
  face="Times New Roman">Squares[10][9])</FONT>，每个元素记录棋子的类型<FONT 
  face="Times New Roman">(</FONT>包括空格<FONT 
  face="Times New Roman">)</FONT>；二是做一个棋子数组<FONT 
  face="Times New Roman">(</FONT>例如<FONT 
  face="Times New Roman">Pieces[2][16])</FONT>，每个元素记录棋子的位置<FONT 
  face="Times New Roman">(</FONT>包括被吃的状态<FONT 
  face="Times New Roman">)</FONT>。如果一个程序同时使用这两个数组，那么着法生成的速度就可以快很多。这就是“棋盘<FONT 
  face="Times New Roman">-</FONT>棋子联系数组”，它的技术要点是： 
  <DT>　　<FONT face="Times New Roman">(1) 
  </FONT>同时用棋盘数组和棋子数组表示一个局面，棋盘数组和棋子数组之间可以互相转换。 
  <DT>　　<FONT face="Times New Roman">(2) </FONT>随时保持这两个数组之间的联系，棋子移动时必须同时更新这两个数组。 

  <DT>　　根据这两个原则，棋盘<FONT face="Times New Roman">-</FONT>棋子联系数组可以定义为： 
  <DD>　 
  <DD>struct PositionStruct { 
  <DD>　int Squares[90]; 
  <DD>　int Pieces[32]; 
  <DD>}; 
  <DT>　 
  <DT>　　在棋盘上删除一个棋子，需要做两个操作<FONT 
  face="Times New Roman">(</FONT>分别修改棋盘数组和棋子数组<FONT 
  face="Times New Roman">)</FONT>。同样，添加一个棋子时也需要两个操作。执行一个着法时有三个步骤： 
  <DT>　　<FONT face="Times New Roman">(1) </FONT>如果目标格上已经有棋子，就要先把它从棋盘上拿走<FONT 
  face="Times New Roman">(</FONT>吃子的过程<FONT face="Times New Roman">)</FONT>； 
  <DT>　　<FONT face="Times New Roman">(2) </FONT>把棋子从起始格上拿走； 
  <DT>　　<FONT face="Times New Roman">(3) </FONT>把棋子放在目标格上。 
  <DT>　　<FONT face="Times New Roman">ElephantEye</FONT>用一个函数<FONT 
  face="Times New Roman">MovePiece()</FONT>来完成这项任务，它除了修改棋盘数组和棋子数组外，还修改<FONT 
  face="Times New Roman">Zobrist</FONT>键值、位行和位列等信息。 
  <DT>　　“棋盘<FONT 
  face="Times New Roman">-</FONT>棋子联系数组”最大的优势是：移动一步只需要有限的运算。对于着法产生过程，可以逐一查找棋子数组，如果该子没有被吃掉，就产生该子的所有合理着法，由于需要查找的棋子数组的数量<FONT 
  face="Times New Roman">(</FONT>每方只有<FONT 
  face="Times New Roman">16</FONT>个棋子能走<FONT 
  face="Times New Roman">)</FONT>比棋盘格子的数量<FONT 
  face="Times New Roman">(90</FONT>个格子<FONT 
  face="Times New Roman">)</FONT>少得多，因此联系数组的速度要比单纯的棋盘数组快很多。可以说，“棋盘<FONT 
  face="Times New Roman">-</FONT>棋子联系数组”是所有着法生成器的基础，位行和位列、位棋盘等其他方法都只是辅助手段。 
  <DT>　 
  <DT><FONT face=Arial size=4><STRONG>2.4 </STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG>扩展的棋盘数组和棋子数组</STRONG></FONT> 
  <DT>　 
  <DT>　　如今，很少有程序使用<FONT face="Times New Roman">Squares[90]</FONT>和<FONT 
  face="Times New Roman">Pieces[32]</FONT>这样的数组了，浪费一些存储空间以换取速度是流行的做法，例如<FONT 
  face="Times New Roman">ElephantEye</FONT>就用了<FONT 
  face="Times New Roman">ucpcSquares[256]</FONT>和<FONT 
  face="Times New Roman">ucsqPieces[48]</FONT>。把棋盘做成<FONT 
  face="Times New Roman">16x16</FONT>的大小，得到行号和列号就可以用<FONT 
  face="Times New Roman">16</FONT>除，这要比用<FONT 
  face="Times New Roman">9</FONT>或<FONT 
  face="Times New Roman">10</FONT>除快得多。<FONT 
  face="Times New Roman">16x16</FONT>的棋盘还有更大的好处，它可以防止棋子走出棋盘边界。 </DT></DL>
<DIV align=center>
<CENTER>
<TABLE border=1>
  <TBODY>
  <TR>
    <TD align=middle bgColor=#ff00ff><FONT 
      face=Arial><STRONG>00</STRONG></FONT></TD>
    <TD align=middle bgColor=#ff00ff><FONT 
      face=Arial><STRONG>01</STRONG></FONT></TD>
    <TD align=middle bgColor=#ff00ff><FONT 
      face=Arial><STRONG>02</STRONG></FONT></TD>
    <TD align=middle bgColor=#ff00ff><FONT 
      face=Arial><STRONG>03</STRONG></FONT></TD>
    <TD align=middle bgColor=#ff00ff><FONT 
      face=Arial><STRONG>04</STRONG></FONT></TD>
    <TD align=middle bgColor=#ff00ff><FONT 
      face=Arial><STRONG>05</STRONG></FONT></TD>
    <TD align=middle bgColor=#ff00ff><FONT 
      face=Arial><STRONG>06</STRONG></FONT></TD>
    <TD align=middle bgColor=#ff00ff><FONT 
      face=Arial><STRONG>07</STRONG></FONT></TD>
    <TD align=middle bgColor=#ff00ff><FONT 
      face=Arial><STRONG>08</STRONG></FONT></TD>
    <TD align=middle bgColor=#ff00ff><FONT 
      face=Arial><STRONG>09</STRONG></FONT></TD>
    <TD align=middle bgColor=#ff00ff><FONT 
      face=Arial><STRONG>0a</STRONG></FONT></TD>
    <TD align=middle bgColor=#ff00ff><FONT 
      face=Arial><STRONG>0b</STRONG></FONT></TD>
    <TD align=middle bgColor=#ff00ff><FONT 
      face=Arial><STRONG>0c</STRONG></FONT></TD>
    <TD align=middle bgColor=#ff00ff><FONT 
      face=Arial><STRONG>0d</STRONG></FONT></TD>
    <TD align=middle bgColor=#ff00ff><FONT 
      face=Arial><STRONG>0e</STRONG></FONT></TD>
    <TD align=middle bgColor=#ff00ff><FONT 
      face=Arial><STRONG>0f</STRONG></FONT></TD></TR>
  <TR>
    <TD align=middle bgColor=#ff00ff><FONT 
      face=Arial><STRONG>10</STRONG></FONT></TD>
    <TD align=middle bgColor=#ff00ff><FONT 
      face=Arial><STRONG>11</STRONG></FONT></TD>
    <TD align=middle bgColor=#ff00ff><FONT
12345

⌨️ 快捷键说明

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