《棋战顺序基本手艺》专题
 
改动的位棋盘
 
作者:James Swafford
 
  “位棋盘”能够纪录的最有用的棋盘状态之一就是“棋盘上哪些格子遭到某一特定棋子的进击”。侥幸的是,这样的盘算耗时不多。关于那些运动才气不强的棋子,这能够说异常随意纰漏(请看上节“位棋盘”) 。缘由是:当马,国王或兵在特定格子上时,不论周围状况怎样转变,所进击的格子数目稳定。你不用管那些格子上是否是有棋子也许周围是否是有稀奇状况。
马在D5格能够进击到的格子 国王在D5格能够进击到的格子 黑棋的兵在D5格能够进击到的格子
  然则关于车,象和皇后,事项就不那末简朴了。譬喻,车进击横线偏向和竖线偏向上的格子,直到在这两个偏向遇到第一个有棋子的格子为止(包孕这个有棋子的格子);若是没有遇到有棋子的格子,则到棋盘界限为止。也就是说,车所在横线和竖线上的棋子散布状况分歧,遭到这个车进击的格子的数目也纷歧样。由于每条横线或竖线都有8个格子,每一个格子又有2种状态(有棋子也许没有棋子),以是每条横线或竖线都邑有28(256)种棋子散布状态。
 
用改动的位棋盘盘算受车进击的格子
 
  怎样取得知数棋盘上遭到某个车进击的格子呢?最简朴的要领是:先盘算出一个位棋盘纪录车所在横线上受其进击的格子,在盘算出其余一个位棋盘纪录车所在竖线上受其进击的格子,最终用“逻辑或”把这两个位棋盘“联系”到一同。
OR =
  悉数支配的重点在于“预先盘算”。关于64格中的每一格,都预先盘算出当车在这一格时,分歧情况下横线上遭到进击的格子(256种状况)和分歧情况下竖线上遭到进击的格子(也是256)。当要寻找某一状况下受车进击的格子时,用横线(或竖线)上的“棋子散布状态”作索引从预先盘算出来的位棋盘数组中取得。
  以是,第一步:预先盘算出数组rank_attacks[64][256]file_attacks[64][256]
 
/* 车或后横向移动的预先盘算 */
for (棋盘上的每一格)(0-63) {
 for (每行的棋子散布状态)(0-255) {
  盘算该状态下被占的格子
  盘算从这个格子朝左走的着法
  盘算从这个格子朝右走的着法
  rank_attacks[格子][横线状态] = attack_board;
 }
}
/* 车或后纵向移动的预先盘算 */
for (棋盘上的每一格)(0-63) {
 for (每条纵线的棋子散布状态)(0-255) {
  盘算该状态下被占的格子
  盘算从这个格子朝上走的着法
  盘算从这个格子朝下走的着法
  file_attacks[格子][纵线状态] = attack_board;
 }
}
 
  第二步:索引rank_attacks[64][256],数组的第一个索引号为车所在格的编号。第二个索引号为车所外行上的“棋子散布状态”。
  请看下面这个案例:
车在E6格能够进击到的格子
  第一个索引号是E6格的编号。在我的顺序里,它的编号是20。第二个索引号是棋盘上第六行的棋子散布状态。
0 1 0 1 0 0 1 0
  【编者注:在James Swafford的顺序里,由于A8格编号为0,以是这串数据的递次正好和棋盘相反,跟黑方看上去的递次一样。】
  要星散出下面这个数字,咱们要求对位棋盘执行一个“位移(shift)”和一个“逻辑与”指令。在我的顺序中,A8格的编号为0。若是车在第8行的恣意格子上则不要求执行位移;若在第7行则要右移8位;在第6行要右移16位;以此类推。
要求右移的位数
0 0 0 0 0 0 0 0
8 8 8 8 8 8 8 8
16 16 16 16 16 16 16 16
24 24 24 24 24 24 24 24
32 32 32 32 32 32 32 32
40 40 40 40 40 40 40 40
48 48 48 48 48 48 48 48
56 56 56 56 56 56 56 56
  咱们要求第6行的棋子散布状况(从第16位到第23位),就右移16位,现在它被右移到了最低的8位,咱们把它与255(0xff)做逻辑与运算。所失掉的器械即是咱们要求作为rank_attacks的第二个索引号的数字。
 
  第三步:索引数组file_attacks[64][256]
  怎样盘算出file_attacks位棋盘呢?照样经由历程索引数组。和下面一样,第一个索引号是车所在格的编号。第二个索引号是车所在列的棋子散布状态。
1
0
0
0
0
1
0
1【编者注:异样原理,这是黑方看上去的职位。】
  要星散出这个索引号比星散rank_attacks的要庞大一些。仅执行“位移”和“与”指令是没有设施做到的。首先,咱们要把棋盘右转90【编者注:即顺时针转90度。】。因而现在它看上去应当是这个样子容貌:
右转90度后的棋盘
  这个改动后的棋盘是怎样失掉的?你能够在最先做下一层搜索的时刻构建这个棋盘,也许简朴地在“走”下一步棋或“恢复”上一步棋的时刻逐渐更新它。下面的要领演示了怎样在最先做下一层搜索时构建它。(代码其实不那末庸俗,但较易体谅……)
 
int r90R_map[64] = {
 H8, H7, H6, H5, H4, H3, H2, H1,
 G8, G7, G6, G5, G4, G3, G2, G1,
 F8, F7, F6, F5, F4, F3, F2, F1,
 E8, E7, E6, E5, E4, E3, E2, E1,
 D8, D7, D6, D5, D4, D3, D2, D1,
 C8, C7, C6, C5, C4, C3, C2, C1,
 B8, B7, B6, B5, B4, B3, B2, B1,
 A8, A7, A6, A5, A4, A3, A2, A1
};
BitBoard Rotated90R = 0;
for (棋盘上的每一格)(0-63) {
 if (格子被占)
  Rotated90R |= mask[r90R_map[square]];
}
 
  这样,正本在A8格上的棋子被“映照”到H8格上,正本在H8格上的棋子则被“映照”到H1格上……
  现在,咱们能够对这个改动后的位棋盘执行“位移”和“与”支配了。
 
  第四步:取得rook_attacks位棋盘。
  失掉rank_attacksfile_attacks位棋盘后,你只需简朴的对这两个位棋盘执行“与”运算就取得了纪录了一切遭到谁人车进击的格子的位棋盘了。
 
rook_attack = rank_attack | file_attack;
 
用改动的位棋盘盘算受象进击的格子
 
  盘算受象进击的格子的要领与车相似。对应于车的把横线与竖线做“或”运算,这里咱们工具所在的两条斜线做“或”运算。咱们把第一条斜线(就是执白时,从左上到右下这条斜线)叫做diag_A8H1;其余一条斜线叫做diag_H8A1。一定车这里还多了一步,缘由是每条斜线的长度分歧。先预先盘算出数组diag_A8H1_attacks[64][256]diag_H8A1_attacks[64][256]A8格编号为0H8格为7A1格为56H1格为63
 
int length_A8H1_diag[64] = {
 8, 7, 6, 5, 4, 3, 2, 1,
 7, 8, 7, 6, 5, 4, 3, 2,
 6, 7, 8, 7, 6, 5, 4, 3,
 5, 6, 7, 8, 7, 6, 5, 4,
 4, 5, 6, 7, 8, 7, 6, 5,
 3, 4, 5, 6, 7, 8, 7, 6,
 2, 3, 4, 5, 6, 7, 8, 7,
 1, 2, 3, 4, 5, 6, 7, 8
};
int length_H8A1_diag[64] = {
 1, 2, 3, 4, 5, 6, 7, 8,
 2, 3, 4, 5, 6, 7, 8, 7,
 3, 4, 5, 6, 7, 8, 7, 6,
 4, 5, 6, 7, 8, 7, 6, 5,
 5, 6, 7, 8, 7, 6, 5, 4,
 6, 7, 8, 7, 6, 5, 4, 3,
 7, 8, 7, 6, 5, 4, 3, 2,
 8, 7, 6, 5, 4, 3, 2, 1
};
/* 象或后在A8-H1偏向移动的预先盘算 */
for (棋盘上的每一格)(0-63) {
 /* 状态数会随对角线长度而转变 */
 for (每条对角线的棋子散布状态)(0-(2^对角线长-1)) {
  盘算该状态下被占的格子(注重某些状态不要把8个格子都斟酌出来)
  盘算从这个格子朝左上方走的着法
  盘算从这个格子朝右下方走的着法
  diag_A8H1_attacks[格子][状态] = attack_board;
 }
}
/* 象或后在H8-A1偏向移动的预先盘算 */
for (棋盘上的每一格)(0-63) {
 /* 状态数会随对角线长度而转变 */
 for (每条对角线的棋子散布状态)(0-(2^diag length)-1) {
  盘算该状态下被占的格子(注重某些状态不要把8个格子都斟酌出来)
  盘算从这个格子朝右上方走的着法
  盘算从这个格子朝左下方走的着法
  diag_H8A1_attacks[square][diag state] = attack_board;
 }
}
 
  索引 diag_A8H1_attacks[64][256] 数组。
  不说你也应当知道,第一个索引号是象所在格的编号。第二个索引号是它所在A8->H1偏向斜线上的棋子散布状况。很正确,接下去又要改动位棋盘,位移,最终用“逻辑与”星散出咱们要求的东西。为了对齐 A8->H1 斜线上的格子,咱们要把棋盘左转45度。(现在我推荐你去拿罐可乐,外加一些提神的药物……)
 
int r45L_map[64] = {
 28, 21, 15, 10, 6, 3, 1, 0,
 36, 29, 22, 16, 11, 7, 4, 2,
 43, 37, 30, 23, 17, 12, 8, 5,
 49, 44, 38, 31, 24, 18, 13, 9,
 54, 50, 45, 39, 32, 25, 19, 14,
 58, 55, 51, 46, 40, 33, 26, 20,
 61, 59, 56, 52, 47, 41, 34, 27,
 63, 62, 60, 57, 53, 48, 42, 35
};
 
  注重每一个格子的映照序次,是从右上往左下的。这样映照后的位棋盘就会顺着A8-H1斜线对齐了(一切的斜线都是顺着这个偏向走的)
 
BitBoard Rotated45L = 0;
for (棋盘上的每一格)(0-63) {
 if square is not empty
 otated45L |= mask[r45L_map[square]];
}
 
  现在“右移”这个棋盘,然则移动几位呢?

要求右移的位数

28 21 15 10 6 3 1 0
36 28 21 15 10 6 3 1
43 36 28 21 15 10 6 3
49 43 36 28 21 15 10 6
54 49 43 36 28 21 15 10
58 54 49 43 36 28 21 15
61 58 54 49 43 36 28 21
63 61 58 54 49 43 36 28
  位移完成后,最终一步就是用“屏障模版”将要求的数据星散出来。“屏障模版”依据斜线的长度分歧而转变。
 
Mask_Length = (2 ^ diag_length) - 1;
 
  依照这个公式,当斜线的长度为7时,屏障模版即是127(二进制:1111111b)。若是斜线的长度为1时屏障模版也为1。在顺序中你能够用这个公式,然则运用查询表会更快一些。
 
  索引 diag_H8A1_attacks[64][256] 数组。
  为了对齐H8->A1偏向的斜线,咱们要把棋盘向右改动45度。(再来一杯可乐?)
 
int r45R_map[64] = {
 0, 1, 3, 6, 10, 15, 21, 28,
 2, 4, 7, 11, 16, 22, 29, 36,
 5, 8, 12, 17, 23, 30, 37, 43,
 9, 13, 18, 24, 31, 38, 44, 49,
 14, 19, 25, 32, 39, 45, 50, 54,
 20, 26, 33, 40, 46, 51, 55, 58,
 27, 34, 41, 47, 52, 56, 59, 61,
 35, 42, 48, 53, 57, 60, 62, 63
};
BitBoard Rotated45R = 0;
for (棋盘上的每一格)(0-63) {
 if square is not empty
  Rotated45R |= mask[r45R_map[square]];
}

要求右移的位数

0 1 3 6 10 15 21 28
1 3 6 10 15 21 28 36
3 6 10 15 21 28 36 43
6 10 15 21 28 36 43 49
10 15 21 28 36 43 49 54
15 21 28 36 43 49 54 58
21 28 36 43 49 54 58 61
28 36 43 49 54 58 61 63
  最终,像对第一根斜线所做的那样,星散出所需数据。
  对这两个位棋盘做“逻辑或”,便失掉纪录受象进击的格子的位棋盘。
 
bishop_attack = diag_A8H1_attacks | diag_H8A1_attacks;
 
  最终,要失掉受皇后进击的格子的位棋盘,只需把受车进击的格子“或”上受象进击的格子:
 
queen_attack = rook_attack | bishop_attack;
 
  出处:不详
  译者:Allen Liu (http://lostboy.myrice.com/)
  类型:不详
  编纂:象棋百科全书网 (webmaster@xqbase.com)
  • 上一篇 数据组织——位棋盘
  • 下一篇 数据组织——着法天生器
  • 返 回 象棋百科全书——计算机象棋
  • www.xqbase.com