引言
国际象棋是计算机博弈领域的经典测试平台。要实现一个高效的象棋引擎，棋盘表示方案是性能的核心瓶颈。传统二维数组表示虽然直观，但在生成走法时效率低下。本文介绍位棋盘（Bitboard）表示法——利用64位长整型直接映射8×8棋盘，配合魔数（Magic Bitboard）技术，将滑动棋子（车、象、后）的攻击生成转化为几次位运算，达到O(1)的生成速度。
位棋盘基本原理
国际象棋棋盘有64格，恰好对应Java的long类型64位。每个棋子类型维护一个位棋盘，某位为1表示该格存在此棋子。例如白车的位棋盘0x0000000000000081L，表示a1和h1两格各有一只白车。
位运算的优势在于并行性：一次&或|操作即可同时处理64格状态，极大加速了走法生成、局面评估等核心流程。
魔数滑动攻击生成
滑动棋子（车、象、后）的攻击线会被其他棋子阻挡。预计算所有可能遮挡状态的攻击表不现实（2^64种状态）。魔数技术的核心思想是：对每条棋盘线（行、列、对角线），用一个64位魔数将遮挡位图哈希到紧凑索引，再查预计算表获取攻击位图。
import java.util.*;
/**
* 国际象棋位棋盘引擎核心：魔数滑动攻击生成
*/
public class ChessBitboardEngine {
// 棋盘枚举：a1=0, b1=1, ..., h8=63
public enum Square {
A1, B1, C1, D1, E1, F1, G1, H1,
A2, B2, C2, D2, E2, F2, G2, H2,
A3, B3, C3, D3, E3, F3, G3, H3,
A4, B4, C4, D4, E4, F4, G4, H4,
A5, B5, C5, D5, E5, F5, G5, H5,
A6, B6, C6, D6, E6, F6, G6, H6,
A7, B7, C7, D7, E7, F7, G7, H7,
A8, B8, C8, D8, E8, F8, G8, H8
}
// 每个格子的位掩码
public static final long[] SQUARE_BB = new long[64];
static {
for (int i = 0; i < 64; i++) {
SQUARE_BB[i] = 1L << i;
}
}
// 预计算的 rook/bishop 攻击掩码（不含边界，因为边界不会被阻挡）
public static final long[] ROOK_MASK = new long[64];
public static final long[] BISHOP_MASK = new long[64];
// 魔数与位移量
public static final long[] ROOK_MAGIC = new long[64];
public static final long[] BISHOP_MAGIC = new long[64];
public static final int[] ROOK_SHIFT = new int[64];
public static final int[] BISHOP_SHIFT = new int[64];
// 魔数攻击表
public static long[][] ROOK_ATTACKS;
public static long[][] BISHOP_ATTACKS;
// 非滑动棋子攻击表
public static final long[] KNIGHT_ATTACKS = new long[64];
public static final long[] KING_ATTACKS = new long[64];
public static final long[] PAWN_ATTACKS_WHITE = new long[64];
public static final long[] PAWN_ATTACKS_BLACK = new long[64];
/**
* 初始化所有攻击表（引擎启动时调用一次）
*/
public static void init() {
initKnightAttacks();
initKingAttacks();
initPawnAttacks();
initRookMasks();
initBishopMasks();
initMagicNumbers(); // 简化：使用预计算魔数
initRookAttacks();
initBishopAttacks();
}
/**
* 计算马的所有攻击格
*/
static void initKnightAttacks() {
int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};
for (int sq = 0; sq < 64; sq++) {
int x = sq % 8, y = sq / 8;
long attacks = 0;
for (int i = 0; i < 8; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < 8 && ny >= 0 && ny < 8) {
attacks |= SQUARE_BB[ny * 8 + nx];
}
}
KNIGHT_ATTACKS[sq] = attacks;
}
}
/**
* 计算王的所有攻击格
*/
static void initKingAttacks() {
int[] dx = {-1, 0, 1, -1, 1, -1, 0, 1};
int[] dy = {-1, -1, -1, 0, 0, 1, 1, 1};
for (int sq = 0; sq < 64; sq++) {
int x = sq % 8, y = sq / 8;
long attacks = 0;
for (int i = 0; i < 8; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < 8 && ny >= 0 && ny < 8) {
attacks |= SQUARE_BB[ny * 8 + nx];
}
}
KING_ATTACKS[sq] = attacks;
}
}
/**
* 计算兵的吃子攻击格（白兵向上，黑兵向下）
*/
static void initPawnAttacks() {
for (int sq = 0; sq < 64; sq++) {
int x = sq % 8, y = sq / 8;
long white = 0, black = 0;
// 白兵从第1行向上吃
if (y < 7) {
if (x > 0) white |= SQUARE_BB[(y + 1) * 8 + (x - 1)];
if (x < 7) white |= SQUARE_BB[(y + 1) * 8 + (x + 1)];
}
// 黑兵从第6行向下吃
if (y > 0) {
if (x > 0) black |= SQUARE_BB[(y - 1) * 8 + (x - 1)];
if (x < 7) black |= SQUARE_BB[(y - 1) * 8 + (x + 1)];
}
PAWN_ATTACKS_WHITE[sq] = white;
PAWN_ATTACKS_BLACK[sq] = black;
}
}
/**
* 生成车的滑动掩码（排除当前格和边界格，因为边界不存在阻挡问题）
*/
static void initRookMasks() {
for (int sq = 0; sq < 64; sq++) {
int x = sq % 8, y = sq / 8;
long mask = 0;
// 向右（不含边界h）
for (int i = x + 1; i < 7; i++) mask |= SQUARE_BB[y * 8 + i];
// 向左（不含边界a）
for (int i = x - 1; i > 0; i--) mask |= SQUARE_BB[y * 8 + i];
// 向上（不含边界8）
for (int i = y + 1; i < 7; i++) mask |= SQUARE_BB[i * 8 + x];
// 向下（不含边界1）
for (int i = y - 1; i > 0; i--) mask |= SQUARE_BB[i * 8 + x];
ROOK_MASK[sq] = mask;
}
}
/**
* 生成象的滑动掩码（对角线，排除边界）
*/
static void initBishopMasks() {
for (int sq = 0; sq < 64; sq++) {
int x = sq % 8, y = sq / 8;
long mask = 0;
// 四个对角方向，都不含边界
for (int i = x + 1, j = y + 1; i < 7 && j < 7; i++, j++) mask |= SQUARE_BB[j * 8 + i];
for (int i = x + 1, j = y - 1; i < 7 && j > 0; i++, j--) mask |= SQUARE_BB[j * 8 + i];
for (int i = x - 1, j = y + 1; i > 0 && j < 7; i--, j++) mask |= SQUARE_BB[j * 8 + i];
for (int i = x - 1, j = y - 1; i > 0 && j > 0; i--, j--) mask |= SQUARE_BB[j * 8 + i];
BISHOP_MASK[sq] = mask;
}
}
/**
* 预计算的魔数（简化版，实际需通过随机搜索生成）
* 魔数要求：对 occupancy 右移后乘魔数再右移，能唯一映射到攻击表索引
*/
static void initMagicNumbers() {
for (int sq = 0; sq < 64; sq++) {
// rook 掩码位数决定位移量
ROOK_SHIFT[sq] = 64 - Long.bitCount(ROOK_MASK[sq]);
BISHOP_SHIFT[sq] = 64 - Long.bitCount(BISHOP_MASK[sq]);
// 使用简化占位魔数（生产环境应使用搜索验证的魔数）
ROOK_MAGIC[sq] = generateMagic(ROOK_MASK[sq]);
BISHOP_MAGIC[sq] = generateMagic(BISHOP_MASK[sq]);
}
}
/**
* 生成候选魔数：需满足对 occupancy 的乘法哈希无碰撞
* 实际生产代码会预计算并硬编码已验证的魔数
*/
static long generateMagic(long mask) {
Random rand = new Random(mask);
long magic;
do {
magic = rand.nextLong() & rand.nextLong() & rand.nextLong();
} while (Long.bitCount((mask * magic) & 0xFF00000000000000L) < 6);
return magic;
}
/**
* 枚举 mask 的所有子集（ occupancy 变体）
*/
static List<Long> enumerateSubsets(long mask) {
List<Long> subsets = new ArrayList<>();
long subset = 0;
do {
subsets.add(subset);
subset = (subset - mask) & mask;
} while (subset != 0);
subsets.add(0L); // 确保包含空集
return subsets;
}
/**
* 计算 rook 在 sq 的攻击位图，给定 occupancy
*/
static long rookAttacksOnTheFly(int sq, long occupancy) {
int x = sq % 8, y = sq / 8;
long attacks = 0;
// 四个方向射线扫描，遇到棋子停止（包含该格）
for (int i = x + 1; i < 8; i++) {
attacks |= SQUARE_BB[y * 8 + i];
if ((occupancy & SQUARE_BB[y * 8 + i]) != 0) break;
}
for (int i = x - 1; i >= 0; i--) {
attacks |= SQUARE_BB[y * 8 + i];
if ((occupancy & SQUARE_BB[y * 8 + i]) != 0) break;
}
for (int i = y + 1; i < 8; i++) {
attacks |= SQUARE_BB[i * 8 + x];
if ((occupancy & SQUARE_BB[i * 8 + x]) != 0) break;
}
for (int i = y - 1; i >= 0; i--) {
attacks |= SQUARE_BB[i * 8 + x];
if ((occupancy & SQUARE_BB[i * 8 + x]) != 0) break;
}
return attacks;
}
/**
* 计算 bishop 在 sq 的攻击位图，给定 occupancy
*/
static long bishopAttacksOnTheFly(int sq, long occupancy) {
int x = sq % 8, y = sq / 8;
long attacks = 0;
for (int i = x + 1, j = y + 1; i < 8 && j < 8; i++, j++) {
attacks |= SQUARE_BB[j * 8 + i];
if ((occupancy & SQUARE_BB[j * 8 + i]) != 0) break;
}
for (int i = x + 1, j = y - 1; i < 8 && j >= 0; i++, j--) {
attacks |= SQUARE_BB[j * 8 + i];
if ((occupancy & SQUARE_BB[j * 8 + i]) != 0) break;
}
for (int i = x - 1, j = y + 1; i >= 0 && j < 8; i--, j++) {
attacks |= SQUARE_BB[j * 8 + i];
if ((occupancy & SQUARE_BB[j * 8 + i]) != 0) break;
}
for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--) {
attacks |= SQUARE_BB[j * 8 + i];
if ((occupancy & SQUARE_BB[j * 8 + i]) != 0) break;
}
return attacks;
}
/**
* 预计算所有 rook 魔数攻击表
*/
static void initRookAttacks() {
ROOK_ATTACKS = new long[64][];
for (int sq = 0; sq < 64; sq++) {
long mask = ROOK_MASK[sq];
int bits = Long.bitCount(mask);
int size = 1 << bits;
ROOK_ATTACKS[sq] = new long[size];
List<Long> subsets = enumerateSubsets(mask);
for (long subset : subsets) {
int index = (int) ((subset * ROOK_MAGIC[sq]) >>> ROOK_SHIFT[sq]);
ROOK_ATTACKS[sq][index] = rookAttacksOnTheFly(sq, subset);
}
}
}
/**
* 预计算所有 bishop 魔数攻击表
*/
static void initBishopAttacks() {
BISHOP_ATTACKS = new long[64][];
for (int sq = 0; sq < 64; sq++) {
long mask = BISHOP_MASK[sq];
int bits = Long.bitCount(mask);
int size = 1 << bits;
BISHOP_ATTACKS[sq] = new long[size];
List<Long> subsets = enumerateSubsets(mask);
for (long subset : subsets) {
int index = (int) ((subset * BISHOP_MAGIC[sq]) >>> BISHOP_SHIFT[sq]);
BISHOP_ATTACKS[sq][index] = bishopAttacksOnTheFly(sq, subset);
}
}
}
// ========== 快速查询接口 ==========
/**
* O(1) 查询 rook 攻击位图
*/
public static long getRookAttacks(int sq, long occupancy) {
long masked = occupancy & ROOK_MASK[sq];
int index = (int) ((masked * ROOK_MAGIC[sq]) >>> ROOK_SHIFT[sq]);
return ROOK_ATTACKS[sq][index];
}
/**
* O(1) 查询 bishop 攻击位图
*/
public static long getBishopAttacks(int sq, long occupancy) {
long masked = occupancy & BISHOP_MASK[sq];
int index = (int) ((masked * BISHOP_MAGIC[sq]) >>> BISHOP_SHIFT[sq]);
return BISHOP_ATTACKS[sq][index];
}
/**
* 后的攻击 = 车攻击 | 象攻击
*/
public static long getQueenAttacks(int sq, long occupancy) {
return getRookAttacks(sq, occupancy) | getBishopAttacks(sq, occupancy);
}
/**
* 打印位棋盘可视化
*/
public static void printBitboard(long bb) {
for (int y = 7; y >= 0; y--) {
for (int x = 0; x < 8; x++) {
System.out.print(((bb & SQUARE_BB[y * 8 + x]) != 0) ? "1 " : ". ");
}
System.out.println();
}
System.out.println();
}
/**
* 主程序：演示魔数攻击生成
*/
public static void main(String[] args) {
long start = System.currentTimeMillis();
init();
long initTime = System.currentTimeMillis() - start;
System.out.println("初始化耗时: " + initTime + "ms");
// 演示：d4格(索引27)的 rook 攻击
// 在 occupancy 中放置几个阻挡子
long occupancy = SQUARE_BB[Square.D2.ordinal()] // d2
| SQUARE_BB[Square.F4.ordinal()] // f4
| SQUARE_BB[Square.D7.ordinal()]; // d7
System.out.println("Occupancy:");
printBitboard(occupancy);
int sq = Square.D4.ordinal();
System.out.println("Rook attacks from D4:");
printBitboard(getRookAttacks(sq, occupancy));
System.out.println("Bishop attacks from D4:");
printBitboard(getBishopAttacks(sq, occupancy));
// 性能测试：百万次查询
long occ = 0x123456789ABCDEF0L;
long trials = 10_000_000;
start = System.nanoTime();
for (long i = 0; i < trials; i++) {
long r = getRookAttacks(27, occ ^ i);
long b = getBishopAttacks(27, occ ^ (i >> 1));
}
long ns = System.nanoTime() - start;
System.out.println("魔数攻击生成性能: " + (trials * 1_000_000_000.0 / ns) + " 次/秒");
}
}
魔数搜索原理
魔数不是任意的64位整数，它必须满足完美哈希性质：对于同一格子、同一棋子类型的所有可能遮挡状态（occupancy），经过 (occupancy & mask) * magic >>> shift 后得到的索引互不冲突。搜索过程如下：
- 对当前格子生成所有可能的遮挡子集（
2^bits个，bits通常为5-12） - 随机生成候选魔数
- 测试每个子集哈希后是否碰撞
- 若全部无碰撞，则该魔数可用
现代引擎如Stockfish都使用预计算魔数，启动时直接加载，无需在线搜索。
复杂度分析
| 操作 | 传统数组 | 位棋盘+魔数 |
|---|---|---|
| 滑动攻击生成 | O(n) 射线扫描 | O(1) 位运算+查表 |
| 生成全部走法 | 数万次循环 | 数千次位运算 |
| 内存占用 | 较小 | 约1MB攻击表 |
| 局面评估并行性 | 无 | 64格并行处理 |
魔数技术用空间换时间，在评估函数和搜索中带来数量级提升。
总结
位棋盘将棋盘状态压缩为原生64位整数，配合Java的long类型和位运算，实现了极高的并行度。魔数技术通过巧妙的乘法哈希，将滑动攻击生成简化为几次CPU指令。这套表示方案是现代国际象棋引擎的基础，也是理解计算机博弈的绝佳入口。
