《对弈程序基本技术》专题
　
位棋盘(BitBoard)
　
作者：James Swafford
　
　　本文将试图回答下面这些有关位棋盘的问题：
　
什么是位棋盘？
位棋盘派什么用？
对位棋盘的基本操作
如何初始化位棋盘？
如何更新位棋盘？
　
什么是位棋盘？
　
　　位棋盘其实就是一个64位长度的变量，用来记录国际象棋棋盘上的某些布尔值。因为棋盘上有64格，所以64位正好对应它的64格。对于面向过程的编程语言例如C，你可以象下面这样来定义这个变量类型：
　
typedef unsigned __int64 BitBoard;
　
　　对于某些别的C编译器，你可能需要使用例如“unsigned long long”来定义它。
　
位棋盘派什么用？
　
　　位棋盘的全部作用就是记录国际象棋棋盘上的某些布尔条件。你可能会问：
　
那是什么类型的“条件”？
位棋盘是如何“描绘”这种“条件”的？
　
　　一旦你理解这些问题的答案，你就已经开了一个好头。
　　首先，那是什么类型的条件？嗯，就象上面提到的，就是布尔条件。换句话说，布尔条件就是“哪些格子上面符合 _____ (由你来填空)的条件。”例如：
　
“哪些格子上面有棋子？”
“哪些格子上面有白棋棋子？”
“哪些格子上面有车？”
“哪些格子上面有象或皇后”
“哪些格子受到F7格上的棋子的攻击？”(不用管格子上是否有棋子或是什么颜色的棋子，译者注。)
“如果有马在F3格上，哪些格子会受到它的攻击？”
　
　　你还可以列出许多许多这样的条件……
　　然后，位棋盘如何来“描绘”这种“条件”？就象上面说过的，“位棋盘”就是一个64位的字。国际象棋棋盘上有64格。这意味着棋盘上的每一格在位棋盘里都有对应的一位。
　　现在是关键部分——如果位棋盘中对应某一格的“位”是“1”，那么这一格上的条件就是“真”；如果是“0”，对应格上的条件就是假。我知道这句话可能让你困惑，让我说得更具体一些。
　　假如我们需要一个记录所有棋子位置的位棋盘“AllPieces”。“AllPieces”告诉我们棋盘上哪些格子有棋子，哪些没有。当棋子处于最初位置的时候，“AllPieces”看上去是这个样子的：
11111111 11111111 00000000 00000000 00000000 00000000 11111111 11111111
　　其最高位对应第63格(H1格)，最低位对应第0格(A8格)。
　　这样显示位棋盘可能更形象一点：
白棋
11111111
11111111
00000000
00000000
00000000
00000000
11111111
11111111
黑棋
　　那么记录白棋棋子初始位置的位棋盘“WhitePieces”是什么样子的呢？
11111111
11111111
00000000
00000000
00000000
00000000
00000000
00000000
　　记录(包括黑棋和白棋的)皇后和车的初始位置的位棋盘“RookQueens”是什么样子的呢？
10001001
00000000
00000000
00000000
00000000
00000000
00000000
10001001
　　好了，在读后续内容之前你必须确定已经理解了上面所讲的东西。假如我们创建了一个位棋盘数组“knight[64]”，那么“knight[0]”位棋盘就记录了当马在0格(即A8格)时，棋盘上所有受到它攻击的格子；“knight[63]”记录了当马在63格(H1格)时，棋盘上所有受到它攻击的格子。
　　“knight[0]”是这个样子的：
白棋
00000000
00000000
00000000
00000000
00000000
00000010
00000100
00000000
黑棋
　　正如你所看到的，当马在A8格时它仅攻击两个格子：10格(C7格) 和17格(B6格)。现在明白了吗？
　　你可能会发现建立全局数组 "BitBoard mask[64]" 会很有用，mask[0]是这样的：
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000001
　　mask[63] 是这样的：
10000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
　
对位棋盘的基本操作
　
　　要成功应用位棋盘你必须理解三种基本操作。他们是(1)与，(2)或，(3)异或。关键是这些位操作的速度！回忆以下高中几何学……还记得原理表吗？
　
与(&)
0 1 0 1
1 0 0 1
————
0 0 0 1
　　相“与”的两“位”必须都是1，结果才是1。
　
或(|)
0 1 0 1
1 0 0 1
————
1 1 0 1
　　相“或”的两“位”只要有一个是1，结果就是1；否则为0。
　
异或(^)
0 1 0 1
1 0 0 1
————
1 1 0 0
　　相“异或”的两“位”只要不同，结果就是1；否则为0。
　
　　好了，最后，即使不能算“位”操作，我仍然要把这个概念介绍给你。它就是“取补(~)”，你只要记住：如果 a = 0001，那么 ~a = 1110。
　
我该如何初始化位棋盘呢？
　
　　某些位棋盘从程序开始运行到结束都不会改变。还记得那个位棋盘数组“knight[64]”吗？(他实际上记录了当马在任意格子上时，它下一步可以走的格子。)这个数组将在程序开始执行的时候被初始化并且不再改变。其余的位棋盘将不断变化。例如“AllPieces”位棋盘。当国际象棋棋盘变化时，它也跟着变化。然而，他们的初始化方式相同。
　　我是这样初始化位棋盘的……
　　还记得“BitBoard mask[64]”数组吗？它应该被第一个初始化……
　
BitBoard b = 1;
for (int c = 0; c < 64; c ++) {
　mask[c] = b << c;
}
　
　　注意不要掉入下面的陷阱!!!
　
for (int c = 0; c < 64; c ++) {
　mask[c] = 1 << c;
}
　
　　这行不通!!! 因为“1”会被当作整型“int”, 而它在大多数计算机上是32位的!!!【编者注：不知道原作者有没有试过 mask[c] = (BitBoard) 1 << c;。】
　　接下去……
　　我用一个叫 CHESS_POSITION 的结构记录棋盘上某一状态的所有有用信息。它包含了一个整型数组 int piece_in_square[64]。还包含了一些位棋盘。
　
/* chess position structure */
struct CHESS_POSITION {
　BitBoard transrefkey;
　int piece_in_square[64];
　int player;
　/* 【编者注：“吃过路兵”的格子 】*/
　int epsquare;
　/* “王车易位”标志【编者注：应该包含4位，即FEN格式串中的KQkq。】*/
　int castles;
　int imbalance;
　/* 子力平衡，正数表示白方占优，负数表示黑方占优 */
　int wkingsq;
　int bkingsq;
　BitBoard whitepawns;　
　BitBoard blackpawns;
　BitBoard whiteknights;
　BitBoard blackknights;
　BitBoard bishopsqueens;
　BitBoard rooksqueens;
　BitBoard whitebishops;
　BitBoard blackbishops;
　BitBoard whiterooks;
　BitBoard blackrooks;
　BitBoard whitequeens;
　BitBoard blackqueens;
　BitBoard whitepieces;
　BitBoard blackpieces;
　BitBoard rotated90;
　BitBoard rotated45;
　BitBoard rotated315;
};
　
　　现在该初始化这个庞然大物了。不过这相当简单。首先，我初始化“piece_in_square[]”数组。
　
piece_in_square[0] = -rook;
piece_in_square[1] = -bishop;
…
piece_in_square[63] = rook;
　
　　现在我们准备好初始化一些位棋盘了。
　
for (c = 0; c < 64; c ++) {
　switch (piece_in_square[c]) {
　case -rook:
　　position.blackpieces |= mask[c];
　　position.blackrooks |= mask[c];
　　position.rooksqueens |= mask[c];
　　break;
　　…
　}
}
　
　　相当简单，对吗？确实简单。那么knight[64]位棋盘数组是如何初始化的呢？
　
/* initialize knight move boards */
BitBoard temp;
int knightsq[8] = {-17, -15, -6, 10, 17, 15, 6, -10};
for(c = 0;c < 64;c++) {
　temp = 0;
　for (k = 0; k < 8; k++) {
　　if (c + knightsq[k] >= 0 && c + knightsq[k] < 64) {
　　　/* 马所在的格子的行数/列数与它下一步可以走的格子的行数/列数之间的差须小于3 */
　　　if (distance(c, c + knightsq[k]) < 3) {
　　　　temp |= mask[c + knightsq[k]];
　　　}
　　}
　}
　knight[c] = temp;
}
如何更新位棋盘？
　
　　刚才说过，当棋盘变动后，某些位棋盘就需要被更新。例如记录白子所在位置的“WhitePieces”位棋盘。假如我们把 E1格的白车移动到E4格，吃掉黑棋的一个兵。
　　哪些位棋盘需要更新？嗯，我们来算一下……
　
whitepieces
whiterooks
rooksqueens
blackpieces
blackpawns
　
　　看上去有很多工作要做，其实并不多。首先，把whitepieces，whiterooks，和rooksqueens位棋盘的“E1”位清零，然后把他们的“E4”位置1。
　
/* clear a bit with the "XOR" operation */
position.whitepieces ^= mask[E1];
position.whiterooks ^= mask[E1];
position.rooksqueens ^= mask[E1];
/* set a bit with the "OR" operation */
position.whitepieces |= mask[E4];
position.whiterooks |= mask[E4];
position.rooksqueens |= mask[E4];
　
　　如果你想玩点花样，你可以仅用一步就完成清E1位、置E4位的工作!!! 回头看一下“异或”操作是怎么执行的……
　
/* clear and set with one operation */
BitBoard combo_board = mask[E1] | mask[E4];
position.whitepieces ^= combo_board;
position.whiterooks ^= combo_board;
position.rooksqueens ^= combo_board;
　
　　现在我们要将blackpieces和blackpawns位棋盘的E4位清除，因为那里的黑兵被吃掉了。
　
/* clear the captured piece */
position.blackpieces ^= mask[E4];
position.blackpawns ^= mask[E4];
　
　　出处：不详
　　译者：Allen Liu (http://lostboy.myrice.com/)
　　类型：不详
　　编辑：象棋百科全书网 (webmaster@xqbase.com)
  • 上一篇　数据结构——简介
  • 下一篇　数据结构——旋转的位棋盘
  • 返　回　象棋百科全书——电脑象棋
    •

    www.xqbase.com