?? 解剖大象的眼睛——中國象棋程序設(shè)計探索(二)：棋盤結(jié)構(gòu)和著法生成器.htm

?? 象棋程序設(shè)計全資料集(介紹編寫象棋程序的方法思路）
?? HTM
?? 第 1 頁 / 共 5 頁
字號:
12 3 4 5 下一頁
<!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>解剖大象的眼睛——中國象棋程序設(shè)計探索(二)：棋盤結(jié)構(gòu)和著法生成器</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=解剖大象的眼睛——中國象棋程序設(shè)計探索(二)：棋盤結(jié)構(gòu)和著法生成器_files/background.gif>
<DL>
  <DIV align=center>
  <CENTER>
  <DT><FONT face=隸書 size=6>解剖大象的眼睛</FONT><FONT 
  size=6><STRONG>——</STRONG></FONT><FONT face=隸書 size=6>中國象棋程序設(shè)計探索</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>聯(lián)系地址：復(fù)旦大學(xué)化學(xué)系表面化學(xué)實驗室，<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>棋盤結(jié)構(gòu)和著法生成器</STRONG></FONT> 

  <DT>　 
  <DT>　　在閱讀本章前，建議讀者先閱讀《<A href="http://www.elephantbase.net/" 
  target=_blank>象棋百科全書</A>》網(wǎng)站中《<A 
  href="http://www.elephantbase.net/computer/outline.htm" 
  target=_blank>對弈程序基本技術(shù)</A>》專題的以下幾篇譯文： 
  <DT>　　<FONT face="Times New Roman">(1) </FONT><A 
  href="http://www.elephantbase.net/computer/struct_intro.htm" 
  target=_blank>數(shù)據(jù)結(jié)構(gòu)——簡介</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>數(shù)據(jù)結(jié)構(gòu)——位棋盤</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>數(shù)據(jù)結(jié)構(gòu)——旋轉(zhuǎn)的位棋盤</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>數(shù)據(jù)結(jié)構(gòu)——著法生成器</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>數(shù)據(jù)結(jié)構(gòu)——<FONT face="Times New Roman">0x88</FONT>著法產(chǎn)生方法</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>數(shù)據(jù)結(jié)構(gòu)——<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>　　局面是象棋程序的核心數(shù)據(jù)結(jié)構(gòu)，除了要包括棋盤、棋子、哪方要走、著法生成的輔助結(jié)構(gòu)、</FONT><FONT 
  face="Times New Roman" size=3>Zobrist</FONT><FONT 
  size=3>鍵值等，還要包含一些歷史著法，來判斷重復(fù)局面。</FONT><FONT face="Times New Roman" 
  size=3>ElephantEye</FONT><FONT size=3>的局面結(jié)構(gòu)很龐大</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>這個結(jié)構(gòu)記錄了四個信息：<FONT 
  face="Times New Roman">(1) </FONT>著法的起始格<FONT 
  face="Times New Roman">(Src)</FONT>，<FONT face="Times New Roman">(2) 
  </FONT>著法的目標(biāo)格<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>。有意思的是，每個部分都只占一個字節(jié)，后兩個部分<FONT 
  face="Times New Roman">(Cpt</FONT>和<FONT 
  face="Times New Roman">Chk)</FONT>與其說有特殊作用，不如說是為了湊一個<FONT 
  face="Times New Roman">32</FONT>位整數(shù)。在<FONT 
  face="Times New Roman">MoveStruct</FONT>出現(xiàn)的很多地方<FONT 
  face="Times New Roman">(</FONT>置換表、殺手著法表、著法生成表<FONT 
  face="Times New Roman">)</FONT>里，這兩項都是沒作用的，而只有在<FONT 
  face="Times New Roman">PositionStruct</FONT>結(jié)構(gòu)的記錄歷史著法的堆棧中才有意義。 
  <DT>　　<FONT face="Times New Roman">Cpt</FONT>一項主要用在撤消著法上，它可以用來還原被吃的棋子，而<FONT 
  face="Times New Roman">Chk</FONT>一項則可以記錄當(dāng)前局面是否處于將軍狀態(tài)。<FONT 
  face="Times New Roman">ElephantEye</FONT>是用<FONT 
  face="Times New Roman">MakeMove()</FONT>函數(shù)來走棋的，每走完一步棋就做兩次將軍判斷：第一次判斷走完子的一方是否被將軍，即<FONT 
  face="Times New Roman">Checked(sdPlayer)</FONT>，如果被將則立即撤消著法，并返回走子失敗的信息；第二次判斷要走的一方是否被將軍，由于交換了走子方<FONT 
  face="Times New Roman">(</FONT>即執(zhí)行了<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>就表示當(dāng)前局面是否被將軍。 
  <DT>　 
  <DT><FONT face=Arial size=4><STRONG>2.2 </STRONG></FONT><FONT face=楷體_GB2312 
  size=4><STRONG>循環(huán)著法的檢測</STRONG></FONT> 
  <DT>　 
  <DT>　　<FONT face="Times New Roman">Cpt</FONT>和<FONT 
  face="Times New Roman">Chk</FONT>的另一個作用就是判斷循環(huán)著法：<FONT 
  face="Times New Roman">ElephantEye</FONT>判斷循環(huán)著法時，依次從堆棧頂往前讀，讀到吃過子的著法<FONT 
  face="Times New Roman">(Cpt</FONT>不為零<FONT 
  face="Times New Roman">)</FONT>就結(jié)束；而是否有單方面長將的情況，則是通過每個著法的<FONT 
  face="Times New Roman">Chk</FONT>一項來判斷的。 
  <DT>　　在循環(huán)著法的檢測中，我們感興趣的不是<FONT face="Times New Roman">Cpt</FONT>和<FONT 
  face="Times New Roman">Chk</FONT>，而是<FONT 
  face="Times New Roman">RepHash</FONT>結(jié)構(gòu)，這是一個微型的置換表，用來記錄歷史局面。<FONT 
  face="Times New Roman">ElephantEye</FONT>在做循環(huán)著法的判斷這之前，先去探測這個置換表，如果命中置換表，則說明可能存在重復(fù)局面<FONT 
  face="Times New Roman">(</FONT>由于置換表可能有沖突，所以只是有這個可能<FONT 
  face="Times New Roman">)</FONT>，因而做循環(huán)檢測；如果沒有命中則肯定沒有重復(fù)局面。 
  <DT>　　<FONT 
  face="Times New Roman">ElephantEye</FONT>使用“歸位檢測法”來判斷循環(huán)著法，即從最后一個著法開始，依次向前撤消著法，并記錄每個移動過的棋子所在的格子。如果所有移動過的棋子同時歸位，那么循環(huán)著法就出現(xiàn)了。因此<FONT 
  face="Times New Roman">&lt;position.cpp&gt;</FONT>中的<FONT 
  face="Times New Roman">IsRep()</FONT>函數(shù)建立了兩個歸位數(shù)組，第一個記錄了棋子的原始位置，第二個記錄了新的位置，當(dāng)兩個位置重合時，說明棋子歸位。 

  <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>棋子聯(lián)系數(shù)組</STRONG></FONT> 
  <DT>　 
  <DT>　　眾所周知，棋盤的表示有兩種方法。一是做一個棋盤數(shù)組<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>；二是做一個棋子數(shù)組<FONT 
  face="Times New Roman">(</FONT>例如<FONT 
  face="Times New Roman">Pieces[2][16])</FONT>，每個元素記錄棋子的位置<FONT 
  face="Times New Roman">(</FONT>包括被吃的狀態(tài)<FONT 
  face="Times New Roman">)</FONT>。如果一個程序同時使用這兩個數(shù)組，那么著法生成的速度就可以快很多。這就是“棋盤<FONT 
  face="Times New Roman">-</FONT>棋子聯(lián)系數(shù)組”，它的技術(shù)要點是： 
  <DT>　　<FONT face="Times New Roman">(1) 
  </FONT>同時用棋盤數(shù)組和棋子數(shù)組表示一個局面，棋盤數(shù)組和棋子數(shù)組之間可以互相轉(zhuǎn)換。 
  <DT>　　<FONT face="Times New Roman">(2) </FONT>隨時保持這兩個數(shù)組之間的聯(lián)系，棋子移動時必須同時更新這兩個數(shù)組。 

  <DT>　　根據(jù)這兩個原則，棋盤<FONT face="Times New Roman">-</FONT>棋子聯(lián)系數(shù)組可以定義為： 
  <DD>　 
  <DD>struct PositionStruct { 
  <DD>　int Squares[90]; 
  <DD>　int Pieces[32]; 
  <DD>}; 
  <DT>　 
  <DT>　　在棋盤上刪除一個棋子，需要做兩個操作<FONT 
  face="Times New Roman">(</FONT>分別修改棋盤數(shù)組和棋子數(shù)組<FONT 
  face="Times New Roman">)</FONT>。同樣，添加一個棋子時也需要兩個操作。執(zhí)行一個著法時有三個步驟： 
  <DT>　　<FONT face="Times New Roman">(1) </FONT>如果目標(biāo)格上已經(jīng)有棋子，就要先把它從棋盤上拿走<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>把棋子放在目標(biāo)格上。 
  <DT>　　<FONT face="Times New Roman">ElephantEye</FONT>用一個函數(shù)<FONT 
  face="Times New Roman">MovePiece()</FONT>來完成這項任務(wù)，它除了修改棋盤數(shù)組和棋子數(shù)組外，還修改<FONT 
  face="Times New Roman">Zobrist</FONT>鍵值、位行和位列等信息。 
  <DT>　　“棋盤<FONT 
  face="Times New Roman">-</FONT>棋子聯(lián)系數(shù)組”最大的優(yōu)勢是：移動一步只需要有限的運算。對于著法產(chǎn)生過程，可以逐一查找棋子數(shù)組，如果該子沒有被吃掉，就產(chǎn)生該子的所有合理著法，由于需要查找的棋子數(shù)組的數(shù)量<FONT 
  face="Times New Roman">(</FONT>每方只有<FONT 
  face="Times New Roman">16</FONT>個棋子能走<FONT 
  face="Times New Roman">)</FONT>比棋盤格子的數(shù)量<FONT 
  face="Times New Roman">(90</FONT>個格子<FONT 
  face="Times New Roman">)</FONT>少得多，因此聯(lián)系數(shù)組的速度要比單純的棋盤數(shù)組快很多。可以說，“棋盤<FONT 
  face="Times New Roman">-</FONT>棋子聯(lián)系數(shù)組”是所有著法生成器的基礎(chǔ)，位行和位列、位棋盤等其他方法都只是輔助手段。 
  <DT>　 
  <DT><FONT face=Arial size=4><STRONG>2.4 </STRONG></FONT><FONT face=楷體_GB2312 
  size=4><STRONG>擴展的棋盤數(shù)組和棋子數(shù)組</STRONG></FONT> 
  <DT>　 
  <DT>　　如今，很少有程序使用<FONT face="Times New Roman">Squares[90]</FONT>和<FONT 
  face="Times New Roman">Pieces[32]</FONT>這樣的數(shù)組了，浪費一些存儲空間以換取速度是流行的做法，例如<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
12 3 4 5 下一頁
?? 文件大小 859 K
?? 上傳用戶 Emouse
?? 所屬分類文件格式
??? 相關(guān)標(biāo)簽

#程序設(shè)計 #程序 #編寫
?? 快捷鍵說明

復(fù)制代碼 Ctrl + C
搜索代碼 Ctrl + F
全屏模式 F11
切換主題 Ctrl + Shift + D
顯示快捷鍵 ?
增大字號 Ctrl + =
減小字號 Ctrl + -
亚洲欧美第一页_禁久久精品乱码_粉嫩av一区二区三区免费野_久草精品视频

?? 解剖大象的眼睛——中國象棋程序設(shè)計探索(二)：棋盤結(jié)構(gòu)和著法生成器.htm

?? 快捷鍵說明
