?? 數據結構——位棋盤.htm
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0056)http://www.elephantbase.net/computer/struct_bitboard.htm -->
<HTML><HEAD><TITLE>數據結構——位棋盤</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.2759" name=GENERATOR></HEAD>
<BODY background=數據結構——位棋盤_files/background.gif>
<DL>
<DIV align=center>
<CENTER>
<DT><FONT size=3>《對弈程序基本技術》專題</FONT> </CENTER></DT></DIV>
<DT>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face=隸書 size=6>位棋盤</FONT><FONT face=Arial
size=6><STRONG>(BitBoard)</STRONG></FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT>作者:<FONT face="Times New Roman">James Swafford (</FONT><A
href="mailto:james_swafford@hotmail.com"><FONT
face="Times New Roman">james_swafford@hotmail.com</FONT></A><FONT
face="Times New Roman">)</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT> </CENTER>
<DIV></DIV>
<DT> 本文將試圖回答下面這些有關位棋盤的問題:
<DT>
<DD>什么是位棋盤?
<DD>位棋盤派什么用?
<DD>對位棋盤的基本操作
<DD>如何初始化位棋盤?
<DD>如何更新位棋盤?
<DT>
<DT><FONT face=楷體_GB2312 size=4><STRONG>什么是位棋盤?</STRONG></FONT>
<DT>
<DT> 位棋盤其實就是一個<FONT
face="Times New Roman">64</FONT>位長度的變量,用來記錄國際象棋棋盤上的某些布爾值。因為棋盤上有<FONT
face="Times New Roman">64</FONT>格,所以<FONT
face="Times New Roman">64</FONT>位正好對應它的<FONT
face="Times New Roman">64</FONT>格。對于面向過程的編程語言例如<FONT
face="Times New Roman">C</FONT>,你可以象下面這樣來定義這個變量類型:
<DT>
<DD>typedef unsigned __int64 BitBoard;
<DT>
<DT> 對于某些別的<FONT face="Times New Roman">C</FONT>編譯器,你可能需要使用例如“<FONT
face="Times New Roman">unsigned long long</FONT>”來定義它。
<DT>
<DT><FONT face=楷體_GB2312 size=4><STRONG>位棋盤派什么用?</STRONG></FONT>
<DT>
<DT> 位棋盤的全部作用就是記錄國際象棋棋盤上的某些布爾條件。你可能會問:
<DT>
<DD>那是什么類型的“條件”?
<DD>位棋盤是如何“描繪”這種“條件”的?
<DT>
<DT> 一旦你理解這些問題的答案,你就已經開了一個好頭。
<DT> 首先,那是什么類型的條件?嗯,就象上面提到的,就是布爾條件。換句話說,布爾條件就是“哪些格子上面符合 <FONT
face="Times New Roman">_____ (</FONT>由你來填空<FONT
face="Times New Roman">)</FONT>的條件。”例如:
<DT>
<DD>“哪些格子上面有棋子?”
<DD>“哪些格子上面有白棋棋子?”
<DD>“哪些格子上面有車?”
<DD>“哪些格子上面有象或皇后”
<DD>“哪些格子受到<FONT face="Times New Roman">F7</FONT>格上的棋子的攻擊?”<FONT
face="Times New Roman">(</FONT>不用管格子上是否有棋子或是什么顏色的棋子,譯者注。<FONT
face="Times New Roman">)</FONT>
<DD>“如果有馬在<FONT face="Times New Roman">F3</FONT>格上,哪些格子會受到它的攻擊?”
<DD>
<DT> 你還可以列出許多許多這樣的條件……
<DT> 然后,位棋盤如何來“描繪”這種“條件”?就象上面說過的,“位棋盤”就是一個<FONT
face="Times New Roman">64</FONT>位的字。國際象棋棋盤上有<FONT
face="Times New Roman">64</FONT>格。這意味著棋盤上的每一格在位棋盤里都有對應的一位。
<DT> 現在是關鍵部分——如果位棋盤中對應某一格的“位”是“<FONT
face="Times New Roman">1</FONT>”,那么這一格上的條件就是“真”;如果是“<FONT
face="Times New Roman">0</FONT>”,對應格上的條件就是假。我知道這句話可能讓你困惑,讓我說得更具體一些。
<DT> 假如我們需要一個記錄所有棋子位置的位棋盤“<FONT
face="Times New Roman">AllPieces</FONT>”。“<FONT
face="Times New Roman">AllPieces</FONT>”告訴我們棋盤上哪些格子有棋子,哪些沒有。當棋子處于最初位置的時候,“<FONT
face="Times New Roman">AllPieces</FONT>”看上去是這個樣子的:
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">11111111 11111111 00000000 00000000 00000000
00000000 11111111 11111111</FONT> </CENTER>
<DIV></DIV>
<DT> 其最高位對應第<FONT face="Times New Roman">63</FONT>格<FONT
face="Times New Roman">(H1</FONT>格<FONT
face="Times New Roman">)</FONT>,最低位對應第<FONT
face="Times New Roman">0</FONT>格<FONT face="Times New Roman">(A8</FONT>格<FONT
face="Times New Roman">)</FONT>。
<DT> 這樣顯示位棋盤可能更形象一點:
<DIV align=center>
<CENTER></DIV>
<DT>白棋 </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">11111111</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">11111111</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">11111111</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">11111111</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT>黑棋 </CENTER>
<DIV></DIV>
<DT> 那么記錄白棋棋子初始位置的位棋盤“<FONT
face="Times New Roman">WhitePieces</FONT>”是什么樣子的呢?
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">11111111</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">11111111</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DT> 記錄<FONT face="Times New Roman">(</FONT>包括黑棋和白棋的<FONT
face="Times New Roman">)</FONT>皇后和車的初始位置的位棋盤“<FONT
face="Times New Roman">RookQueens</FONT>”是什么樣子的呢?
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">10001001</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">10001001</FONT> </CENTER>
<DIV></DIV>
<DT> 好了,在讀后續內容之前你必須確定已經理解了上面所講的東西。假如我們創建了一個位棋盤數組“<FONT
face="Times New Roman">knight[64]</FONT>”,那么“<FONT
face="Times New Roman">knight[0]</FONT>”位棋盤就記錄了當馬在<FONT
face="Times New Roman">0</FONT>格<FONT face="Times New Roman">(</FONT>即<FONT
face="Times New Roman">A8</FONT>格<FONT
face="Times New Roman">)</FONT>時,棋盤上所有受到它攻擊的格子;“<FONT
face="Times New Roman">knight[63]</FONT>”記錄了當馬在<FONT
face="Times New Roman">63</FONT>格<FONT face="Times New Roman">(H1</FONT>格<FONT
face="Times New Roman">)</FONT>時,棋盤上所有受到它攻擊的格子。
<DT> “<FONT face="Times New Roman">knight[0]</FONT>”是這個樣子的:
<DIV align=center>
<CENTER></DIV>
<DT>白棋 </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000010</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000100</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT>黑棋 </CENTER>
<DIV></DIV>
<DT> 正如你所看到的,當馬在<FONT face="Times New Roman">A8</FONT>格時它僅攻擊兩個格子:<FONT
face="Times New Roman">10</FONT>格<FONT face="Times New Roman">(C7</FONT>格<FONT
face="Times New Roman">) </FONT>和<FONT face="Times New Roman">17</FONT>格<FONT
face="Times New Roman">(B6</FONT>格<FONT
face="Times New Roman">)</FONT>。現在明白了嗎?
<DT> 你可能會發現建立全局數組 <FONT face="Times New Roman">"BitBoard mask[64]"
</FONT>會很有用,<FONT face="Times New Roman">mask[0]</FONT>是這樣的:
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000000</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">00000001</FONT> </CENTER>
<DIV></DIV>
<DT> <FONT face="Times New Roman">mask[63] </FONT>是這樣的:
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">10000000</FONT> </CENTER>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -