数据结构――位棋盘

作者：James Swafford

本文将试图回答下面这些有关位棋盘的问题：

什么是位棋盘?

位棋盘派什么用?

对位棋盘的基本操作

如何初始化位棋盘?

如何更新位棋盘?

什么是位棋盘？

位棋盘其实就是一个64位长度的变量，用来记录国际象棋棋盘上的某些布尔值。因为棋盘上有64格，所以64位正好对应它的64格。对于面向过程的编程语言例如C，你可以象下面这样来定义这个变量类型：

typedef unsigned __int64 BitBoard;

对于某些别的C编译器，你可能需要使用例如“unsigned long long”来定义它。

位棋盘派什么用？

位棋盘的全部作用就是记录国际象棋棋盘上的某些布尔条件。你可能会问：

那是什么类型的“条件”?

位棋盘是如何“描绘”这种“条件”的?

一旦你理解这些问题的答案，你就已经开了一个好头。

首先，那是什么类型的条件?嗯，就象上面提到的，就是布尔条件。换句话说，布尔条件就是“哪些格子上面符合_____ (由你来填空)的条件。”例如：

“哪些格子上面有棋子?”

“哪些格子上面有白棋棋子?”

“哪些格子上面有车?”

“哪些格子上面有象或皇后”

“哪些格子受到F7格上的棋子的攻击?”(不用管格子上是否有棋子或是什么颜色的棋子，译者注。)

“如果有马在F3格上，哪些格子会受到它的攻击?”

你还可以列出许多许多这样的条件……

然后，位棋盘如何来“描绘”这种“条件”?就象上面说过的，“位棋盘”就是一个64位的字。国际象棋棋盘上有64格。这意味着棋盘上的每一格在位棋盘里都有对应的一位。

现在是关键部分——如果位棋盘中对应某一格的“位”是“1”，那么这一格上的条件就是“真”;如果是“0”，对应格上的条件就是假。我知道这句话可能让你困惑，让我说得更具体一些。

假如我们需要一个记录所有棋子位置的位棋盘“AllPieces”。“AllPieces”告诉我们棋盘上哪些格子有棋子，哪些没有。当棋子处于最初位置的时候，“AllPieces”看上去是这个样子的：

其最高位对应第63格(H1格)，最低位对应第0格(A8格)。

这样显示位棋盘可能更形象一点：

那么记录白棋棋子初始位置的位棋盘“WhitePieces”是什么样子的呢?

记录(包括黑棋和白棋的)皇后和车的初始位置的位棋盘“RookQueens”是什么样子的呢?

好了，在读后续内容之前你必须确定已经理解了上面所讲的东西。假如我们创建了一个位棋盘数组“knight[64]”，那么“knight[0]”位棋盘就记录了当马在0格(即A8格)时，棋盘上所有受到它攻击的格子;“knight[63]”记录了当马在63格(H1格)时，棋盘上所有受到它攻击的格子。

“knight[0]”是这个样子的：

正如你所看到的，当马在A8格时它仅攻击两个格子：10格(C7格)和17格(B6格)。现在明白了吗?

你可能会发现建立全局数组"BitBoard mask[64]"会很有用，mask[0]是这样的：

mask[63]是这样的：

对位棋盘的基本操作

要成功应用位棋盘你必须理解三种基本操作。他们是(1)与，(2)或，(3)异或。关键是这些位操作的速度!回忆以下高中几何学……还记得原理表吗?

相“与”的两“位”必须都是1，结果才是1。

相“或”的两“位”只要有一个是1，结果就是1;否则为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位棋盘的“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 

类型：不详

编辑：象棋百科全书网