?? 解剖大象的眼睛——中國象棋程序設計探索(二):棋盤結構和著法生成器.htm
字號:
<!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><position.h>)</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"><position.cpp></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
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -