?? 數據結構——位棋盤.htm
字號:
<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">00000000</FONT> </CENTER>
<DIV></DIV>
<DT>
<DT><FONT face=楷體_GB2312 size=4><STRONG>對位棋盤的基本操作</STRONG></FONT>
<DT>
<DT> 要成功應用位棋盤你必須理解三種基本操作。他們是<FONT face="Times New Roman">(1)</FONT>與，<FONT
face="Times New Roman">(2)</FONT>或，<FONT
face="Times New Roman">(3)</FONT>異或。關鍵是這些位操作的速度！回憶以下高中幾何學……還記得原理表嗎？
<DT>
<DIV align=center>
<CENTER></DIV>
<DT>與<FONT face="Times New Roman">(&)</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">0 1 0 1</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">1 0 0 1</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT>———— </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">0 0 0 1</FONT> </CENTER>
<DIV></DIV>
<DT> 相“與”的兩“位”必須都是<FONT face="Times New Roman">1</FONT>，結果才是<FONT
face="Times New Roman">1</FONT>。
<DT>
<DIV align=center>
<CENTER></DIV>
<DT>或<FONT face="Times New Roman">(|)</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">0 1 0 1</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">1 0 0 1</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT>———— </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">1 1 0 1</FONT> </CENTER>
<DIV></DIV>
<DT> 相“或”的兩“位”只要有一個是<FONT face="Times New Roman">1</FONT>，結果就是<FONT
face="Times New Roman">1</FONT>；否則為<FONT face="Times New Roman">0</FONT>。
<DT>
<DIV align=center>
<CENTER></DIV>
<DT>異或<FONT face="Times New Roman">(^)</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">0 1 0 1</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">1 0 0 1</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT>———— </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman">1 1 0 0</FONT> </CENTER>
<DIV></DIV>
<DT> 相“異或”的兩“位”只要不同，結果就是<FONT face="Times New Roman">1</FONT>；否則為<FONT
face="Times New Roman">0</FONT>。
<DT>
<DT> 好了，最后，即使不能算“位”操作，我仍然要把這個概念介紹給你。它就是“取補<FONT
face="Times New Roman">(~)</FONT>”，你只要記住：如果 <FONT face="Times New Roman">a =
0001</FONT>，那么 <FONT face="Times New Roman">~a = 1110</FONT>。
<DT>
<DT><FONT face=楷體_GB2312 size=4><STRONG>我該如何初始化位棋盤呢？</STRONG></FONT>
<DT>
<DT> 某些位棋盤從程序開始運行到結束都不會改變。還記得那個位棋盤數組“<FONT
face="Times New Roman">knight[64]</FONT>”嗎？<FONT
face="Times New Roman">(</FONT>他實際上記錄了當馬在任意格子上時，它下一步可以走的格子。<FONT
face="Times New Roman">)</FONT>這個數組將在程序開始執行的時候被初始化并且不再改變。其余的位棋盤將不斷變化。例如“<FONT
face="Times New Roman">AllPieces</FONT>”位棋盤。當國際象棋棋盤變化時，它也跟著變化。然而，他們的初始化方式相同。
<DT> 我是這樣初始化位棋盤的……
<DT> 還記得“<FONT face="Times New Roman">BitBoard
mask[64]</FONT>”數組嗎？它應該被第一個初始化……
<DT>
<DD>BitBoard b = 1;
<DD>for (int c = 0; c < 64; c ++) {
<DD> mask[c] = b << c;
<DD>}
<DT>
<DT> 注意不要掉入下面的陷阱<FONT face="Times New Roman">!!!</FONT>
<DT>
<DD>for (int c = 0; c < 64; c ++) {
<DD> mask[c] = 1 << c;
<DD>}
<DT>
<DT> 這行不通<FONT face="Times New Roman">!!! </FONT>因為“<FONT
face="Times New Roman">1</FONT>”會被當作整型“<FONT
face="Times New Roman">int</FONT>”<FONT face="Times New Roman">,
</FONT>而它在大多數計算機上是<FONT face="Times New Roman">32</FONT>位的<FONT
face="Times New Roman">!!!</FONT><FONT color=#0000ff>【編者注：不知道原作者有沒有試過
</FONT><FONT face="Times New Roman" color=#0000ff>mask[c] = (BitBoard) 1
<< c;</FONT><FONT color=#0000ff>。】</FONT>
<DT> 接下去……
<DT> 我用一個叫 <FONT face="Times New Roman">CHESS_POSITION
</FONT>的結構記錄棋盤上某一狀態的所有有用信息。它包含了一個整型數組 <FONT face="Times New Roman">int
piece_in_square[64]</FONT>。還包含了一些位棋盤。
<DT>
<DD>/* chess position structure */
<DD>struct CHESS_POSITION {
<DD> BitBoard transrefkey;
<DD> int piece_in_square[64];
<DD> int player;
<DD> /* <FONT color=#0000ff>【編者注：“吃過路兵”的格子 】</FONT>*/
<DD> int epsquare;
<DD> /* “王車易位”標志<FONT color=#0000ff>【編者注：應該包含4位，即FEN格式串中的KQkq。】</FONT>*/
<DD> int castles;
<DD> int imbalance;
<DD> /* 子力平衡，正數表示白方占優，負數表示黑方占優 */
<DD> int wkingsq;
<DD> int bkingsq;
<DD> BitBoard whitepawns;
<DD> BitBoard blackpawns;
<DD> BitBoard whiteknights;
<DD> BitBoard blackknights;
<DD> BitBoard bishopsqueens;
<DD> BitBoard rooksqueens;
<DD> BitBoard whitebishops;
<DD> BitBoard blackbishops;
<DD> BitBoard whiterooks;
<DD> BitBoard blackrooks;
<DD> BitBoard whitequeens;
<DD> BitBoard blackqueens;
<DD> BitBoard whitepieces;
<DD> BitBoard blackpieces;
<DD> BitBoard rotated90;
<DD> BitBoard rotated45;
<DD> BitBoard rotated315;
<DD>};
<DT>
<DT> 現在該初始化這個龐然大物了。不過這相當簡單。首先，我初始化“<FONT
face="Times New Roman">piece_in_square[]</FONT>”數組。
<DT>
<DD>piece_in_square[0] = -rook;
<DD>piece_in_square[1] = -bishop;
<DD>…
<DD>piece_in_square[63] = rook;
<DT>
<DT> 現在我們準備好初始化一些位棋盤了。
<DD>
<DD>for (c = 0; c < 64; c ++) {
<DD> switch (piece_in_square[c]) {
<DD> case -rook:
<DD> position.blackpieces |= mask[c];
<DD> position.blackrooks |= mask[c];
<DD> position.rooksqueens |= mask[c];
<DD> break;
<DD> …
<DD> }
<DD>}
<DT>
<DT> 相當簡單，對嗎？確實簡單。那么<FONT
face="Times New Roman">knight[64]</FONT>位棋盤數組是如何初始化的呢？
<DT>
<DD>/* initialize knight move boards */
<DD>BitBoard temp;
<DD>int knightsq[8] = {-17, -15, -6, 10, 17, 15, 6, -10};
<DD>for(c = 0;c < 64;c++) {
<DD> temp = 0;
<DD> for (k = 0; k < 8; k++) {
<DD> if (c + knightsq[k] >= 0 && c + knightsq[k] < 64) {
<DD> /* 馬所在的格子的行數/列數與它下一步可以走的格子的行數/列數之間的差須小于3 */
<DD> if (distance(c, c + knightsq[k]) < 3) {
<DD> temp |= mask[c + knightsq[k]];
<DD> }
<DD> }
<DD> }
<DD> knight[c] = temp;
<DD>} </DD></DL>
<DL>
<DT><FONT face=楷體_GB2312 size=4><STRONG>如何更新位棋盤</STRONG></FONT><FONT
face=楷體_GB2312 size=5><STRONG>？</STRONG></FONT>
<DT>
<DT> 剛才說過，當棋盤變動后，某些位棋盤就需要被更新。例如記錄白子所在位置的“<FONT
face="Times New Roman">WhitePieces</FONT>”位棋盤。假如我們把 <FONT
face="Times New Roman">E1</FONT>格的白車移動到<FONT
face="Times New Roman">E4</FONT>格，吃掉黑棋的一個兵。
<DT> 哪些位棋盤需要更新？嗯，我們來算一下……
<DT>
<DD>whitepieces
<DD>whiterooks
<DD>rooksqueens
<DD>blackpieces
<DD>blackpawns
<DT>
<DT> 看上去有很多工作要做，其實并不多。首先，把<FONT
face="Times New Roman">whitepieces</FONT>，<FONT
face="Times New Roman">whiterooks</FONT>，和<FONT
face="Times New Roman">rooksqueens</FONT>位棋盤的“<FONT
face="Times New Roman">E1</FONT>”位清零，然后把他們的“<FONT
face="Times New Roman">E4</FONT>”位置<FONT face="Times New Roman">1</FONT>。
<DT>
<DD>/* clear a bit with the "XOR" operation */
<DD>position.whitepieces ^= mask[E1];
<DD>position.whiterooks ^= mask[E1];
<DD>position.rooksqueens ^= mask[E1];
<DD>/* set a bit with the "OR" operation */
<DD>position.whitepieces |= mask[E4];
<DD>position.whiterooks |= mask[E4];
<DD>position.rooksqueens |= mask[E4];
<DT>
<DT> 如果你想玩點花樣，你可以僅用一步就完成清<FONT face="Times New Roman">E1</FONT>位、置<FONT
face="Times New Roman">E4</FONT>位的工作<FONT face="Times New Roman">!!!
</FONT>回頭看一下“異或”操作是怎么執行的……
<DD>
<DD>/* clear and set with one operation */
<DD>BitBoard combo_board = mask[E1] | mask[E4];
<DD>position.whitepieces ^= combo_board;
<DD>position.whiterooks ^= combo_board;
<DD>position.rooksqueens ^= combo_board;
<DT>
<DT> 現在我們要將<FONT face="Times New Roman">blackpieces</FONT>和<FONT
face="Times New Roman">blackpawns</FONT>位棋盤的<FONT
face="Times New Roman">E4</FONT>位清除，因為那里的黑兵被吃掉了。
<DD>
<DD>/* clear the captured piece */
<DD>position.blackpieces ^= mask[E4];
<DD>position.blackpawns ^= mask[E4];
<DT>
<DT> 出處：不詳
<DT> 譯者：<FONT face="Times New Roman">Allen Liu (</FONT><A
href="mailto:ditch_u@yahoo.com"><FONT
face="Times New Roman">ditch_u@yahoo.com</FONT></A>，<A
href="http://lostboy.myrice.com/home.htm" target=_blank><FONT
face="Times New Roman"
color=#0000ff>http://lostboy.myrice.com/</FONT></A><FONT
face="Times New Roman">)</FONT>
<DT> 類型：不詳
<DT> 編輯：黃晨 <FONT face="Times New Roman">(</FONT><A
href="mailto:webmaster@elephantbase.net"><FONT
face="Times New Roman">webmaster@elephantbase.net</FONT></A><FONT
face="Times New Roman">)</FONT> </DT></DL>
<DIR>
<LI>上一篇 <A
href="http://www.elephantbase.net/computer/struct_intro.htm">數據結構——簡介</A>
<LI>下一篇 <A
href="http://www.elephantbase.net/computer/struct_rotation.htm">數據結構——旋轉的位棋盤</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="數據結構——位棋盤_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>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -