📄 数据结构——位棋盘.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 + -