《棋战顺序基本手艺》专题
 
位棋盘(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
 
  看上去有许多事情要做,事实上其实不多。首先,把whitepieceswhiterooks,和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;
 
  现在咱们要将blackpiecesblackpawns位棋盘的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