《对弈程序基本技术》专题
　
旋转的位棋盘
　
作者：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_attacks和file_attacks位棋盘后，你只要简单的对这两个位棋盘执行“与”运算就获得了记录了所有受到那个车攻击的格子的位棋盘了。
　
rook_attack = rank_attack | file_attack;
　
用旋转的位棋盘计算受象攻击的格子
　
　　计算受象攻击的格子的方法与车类似。对应于车的把横线与竖线做“或”运算，这里我们对象所在的两条斜线做“或”运算。我们把第一条斜线(就是执白时，从左上到右下这条斜线)叫做diag_A8H1；另一条斜线叫做diag_H8A1。相对车这里还多了一步，原因是每条斜线的长度不同。先预先计算出数组diag_A8H1_attacks[64][256]和diag_H8A1_attacks[64][256]。A8格编号为0，H8格为7，A1格为56，H1格为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