引言
在棋类AI和组合优化问题中，状态空间的表示效率直接决定了算法的搜索深度和速度。传统的二维数组表示棋盘状态虽然直观，但在生成合法走法、评估局面、拷贝状态时会产生大量的内存访问和对象创建开销。Bitboard（位棋盘）技术通过将棋盘状态压缩到一个或多个64位整数中，利用CPU原生支持的位运算指令在单个时钟周期内完成整行的操作，将状态处理速度提升一到两个数量级。
Bitboard最早在国际象棋程序中被广泛应用，Deep Blue和Stockfish等顶级引擎都大量使用了位棋盘技术。本文将深入讲解Bitboard的设计原理，并用Java实现一个完整的Bitboard框架，展示其在状态表示、移动生成和局面评估中的强大能力。
核心原理
位棋盘基本思想
对于一个8×8的棋盘，用一个64位long整数表示：第i位为1表示棋盘第i个格子上有棋子。例如，国际象棋有6种棋子类型×2种颜色=12种Bitboard，加上一些辅助位图，总共约15-20个long变量即可完整描述整个棋局。
棋盘位的编号（小端序，从右下角开始）：
56 57 58 59 60 61 62 63
48 49 50 51 52 53 54 55
40 41 42 43 44 45 46 47
32 33 34 35 36 37 38 39
24 25 26 27 28 29 30 31
16 17 18 19 20 21 22 23
8 9 10 11 12 13 14 15
0 1 2 3 4 5 6 7
核心位运算操作
| 操作 | Java表达式 | 应用场景 |
|---|---|---|
| 设置某位 | board \| (1L << sq) |
在格子sq放置棋子 |
| 清除某位 | board & ~(1L << sq) |
从格子sq移除棋子 |
| 测试某位 | (board >> sq) & 1 |
判断格子sq是否有棋子 |
| 提取最低位 | board & -board |
获取最低位的1的位置 |
| 清除最低位 | board & (board - 1) |
移除最低位的1 |
| 位计数 | Long.bitCount(board) |
计算棋子数量 |
| 水平移位 | board << 1 或 board >>> 1 |
棋子水平移动 |
| 垂直移位 | board << 8 或 board >>> 8 |
棋子垂直移动 |
预计算攻击位图
Bitboard的强大之处在于可以预计算每个棋子在每个格子的攻击范围。例如，车的攻击范围可以通过沿着四个方向射线扫描预计算，存储在一个64×64的数组中。在运行时，只需一次查表和位与操作即可得到所有合法攻击位置。
Java实现
基础Bitboard工具类
/**
* Bitboard位棋盘工具类
* 提供64位棋盘的基础操作、移动生成和局面评估
*/
public class BitboardUtils {
// 棋盘常量
public static final long FILE_A = 0x0101010101010101L;
public static final long FILE_B = 0x0202020202020202L;
public static final long FILE_H = 0x8080808080808080L;
public static final long RANK_1 = 0x00000000000000FFL;
public static final long RANK_8 = 0xFF00000000000000L;
public static final long DIAGONAL_A1H8 = 0x8040201008040201L;
public static final long DIAGONAL_A8H1 = 0x0102040810204080L;
// 所有格子的掩码
public static final long ALL_SQUARES = ~0L;
public static final long EMPTY = 0L;
/**
* 将行列坐标转换为位索引 (0-63)
*/
public static int square(int rank, int file) {
return rank * 8 + file;
}
/**
* 从位索引获取行号 (0-7)
*/
public static int rankOf(int sq) {
return sq >>> 3;
}
/**
* 从位索引获取列号 (0-7)
*/
public static int fileOf(int sq) {
return sq & 7;
}
/**
* 设置指定位
*/
public static long setBit(long board, int sq) {
return board | (1L << sq);
}
/**
* 清除指定位
*/
public static long clearBit(long board, int sq) {
return board & ~(1L << sq);
}
/**
* 测试指定位是否为1
*/
public static boolean testBit(long board, int sq) {
return (board & (1L << sq)) != 0;
}
/**
* 提取最低位的1的索引（LSB）
*/
public static int bitScanForward(long board) {
return Long.numberOfTrailingZeros(board);
}
/**
* 提取最高位的1的索引（MSB）
*/
public static int bitScanReverse(long board) {
return 63 - Long.numberOfLeadingZeros(board);
}
/**
* 清除最低位的1，返回新值
*/
public static long popLSB(long board) {
return board & (board - 1);
}
/**
* 获取最低位的1的掩码
*/
public static long getLSB(long board) {
return board & -board;
}
/**
* 计算1的位数（种群计数）
*/
public static int popCount(long board) {
return Long.bitCount(board);
}
/**
* 将位棋盘打印为8x8网格
*/
public static void printBoard(long board) {
System.out.println(" a b c d e f g h");
for (int rank = 7; rank >= 0; rank--) {
System.out.print((rank + 1) + " ");
for (int file = 0; file < 8; file++) {
int sq = square(rank, file);
System.out.print(testBit(board, sq) ? "1 " : ". ");
}
System.out.println();
}
System.out.println();
}
/**
* 遍历位棋盘上所有置位的索引
*/
public static void forEachBit(long board, java.util.function.IntConsumer action) {
while (board != 0) {
int sq = bitScanForward(board);
action.accept(sq);
board = popLSB(board);
}
}
/**
* 将位索引转换为代数坐标（如e4）
*/
public static String toAlgebraic(int sq) {
char file = (char) ('a' + fileOf(sq));
char rank = (char) ('1' + rankOf(sq));
return "" + file + rank;
}
/**
* 翻转整个棋盘（用于交换黑白视角）
*/
public static long flipVertical(long board) {
return Long.reverseBytes(board);
}
/**
* 水平翻转棋盘
*/
public static long flipHorizontal(long board) {
long k1 = 0x5555555555555555L;
long k2 = 0x3333333333333333L;
long k4 = 0x0f0f0f0f0f0f0f0fL;
board = ((board >>> 1) & k1) | ((board & k1) << 1);
board = ((board >>> 2) & k2) | ((board & k2) << 2);
board = ((board >>> 4) & k4) | ((board & k4) << 4);
return board;
}
/**
* 旋转90度（顺时针）
*/
public static long rotate90(long board) {
return flipHorizontal(Long.reverseBytes(board));
}
}
滑动棋子攻击生成
/**
* 预计算的滑动棋子攻击表
* 用于车、象、后的攻击范围生成
*/
public class SlidingAttacks {
// 车的攻击范围表 [square][occupancy_index]
private static final long[][] ROOK_ATTACKS = new long[64][4096];
private static final long[][] BISHOP_ATTACKS = new long[64][512];
// 每个格子的掩码（排除边缘位，用于生成索引）
private static final long[] ROOK_MASK = new long[64];
private static final long[] BISHOP_MASK = new long[64];
// 每个掩码的位数
private static final int[] ROOK_BITS = new int[64];
private static final int[] BISHOP_BITS = new int[64];
static {
initAttackTables();
}
private static void initAttackTables() {
for (int sq = 0; sq < 64; sq++) {
ROOK_MASK[sq] = generateRookMask(sq);
BISHOP_MASK[sq] = generateBishopMask(sq);
ROOK_BITS[sq] = BitboardUtils.popCount(ROOK_MASK[sq]);
BISHOP_BITS[sq] = BitboardUtils.popCount(BISHOP_MASK[sq]);
// 预计算所有可能的占用情况
int rookVariations = 1 << ROOK_BITS[sq];
for (int i = 0; i < rookVariations; i++) {
long occupancy = indexToOccupancy(i, ROOK_BITS[sq], ROOK_MASK[sq]);
ROOK_ATTACKS[sq][i] = generateRookAttacks(sq, occupancy);
}
int bishopVariations = 1 << BISHOP_BITS[sq];
for (int i = 0; i < bishopVariations; i++) {
long occupancy = indexToOccupancy(i, BISHOP_BITS[sq], BISHOP_MASK[sq]);
BISHOP_ATTACKS[sq][i] = generateBishopAttacks(sq, occupancy);
}
}
}
/**
* 生成车的攻击掩码（不含边缘）
*/
private static long generateRookMask(int sq) {
long mask = 0L;
int rank = BitboardUtils.rankOf(sq);
int file = BitboardUtils.fileOf(sq);
// 水平方向（不含端点）
for (int f = file + 1; f < 7; f++) mask = BitboardUtils.setBit(mask, BitboardUtils.square(rank, f));
for (int f = file - 1; f > 0; f--) mask = BitboardUtils.setBit(mask, BitboardUtils.square(rank, f));
// 垂直方向（不含端点）
for (int r = rank + 1; r < 7; r++) mask = BitboardUtils.setBit(mask, BitboardUtils.square(r, file));
for (int r = rank - 1; r > 0; r--) mask = BitboardUtils.setBit(mask, BitboardUtils.square(r, file));
return mask;
}
/**
* 生成象的攻击掩码（不含边缘）
*/
private static long generateBishopMask(int sq) {
long mask = 0L;
int rank = BitboardUtils.rankOf(sq);
int file = BitboardUtils.fileOf(sq);
// 四个对角方向（不含端点）
for (int r = rank + 1, f = file + 1; r < 7 && f < 7; r++, f++)
mask = BitboardUtils.setBit(mask, BitboardUtils.square(r, f));
for (int r = rank + 1, f = file - 1; r < 7 && f > 0; r++, f--)
mask = BitboardUtils.setBit(mask, BitboardUtils.square(r, f));
for (int r = rank - 1, f = file + 1; r > 0 && f < 7; r--, f++)
mask = BitboardUtils.setBit(mask, BitboardUtils.square(r, f));
for (int r = rank - 1, f = file - 1; r > 0 && f > 0; r--, f--)
mask = BitboardUtils.setBit(mask, BitboardUtils.square(r, f));
return mask;
}
/**
* 将索引转换为占用位图
*/
private static long indexToOccupancy(int index, int bits, long mask) {
long occupancy = 0L;
for (int i = 0; i < bits; i++) {
int sq = BitboardUtils.bitScanForward(mask);
mask = BitboardUtils.popLSB(mask);
if ((index & (1 << i)) != 0) {
occupancy = BitboardUtils.setBit(occupancy, sq);
}
}
return occupancy;
}
/**
* 生成车的攻击范围（含阻挡）
*/
private static long generateRookAttacks(int sq, long occupancy) {
long attacks = 0L;
int rank = BitboardUtils.rankOf(sq);
int file = BitboardUtils.fileOf(sq);
// 四个方向射线扫描
int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
for (int[] d : directions) {
for (int r = rank + d[0], f = file + d[1]; r >= 0 && r < 8 && f >= 0 && f < 8; r += d[0], f += d[1]) {
int target = BitboardUtils.square(r, f);
attacks = BitboardUtils.setBit(attacks, target);
if (BitboardUtils.testBit(occupancy, target)) break;
}
}
return attacks;
}
private static long generateBishopAttacks(int sq, long occupancy) {
long attacks = 0L;
int rank = BitboardUtils.rankOf(sq);
int file = BitboardUtils.fileOf(sq);
int[][] directions = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
for (int[] d : directions) {
for (int r = rank + d[0], f = file + d[1]; r >= 0 && r < 8 && f >= 0 && f < 8; r += d[0], f += d[1]) {
int target = BitboardUtils.square(r, f);
attacks = BitboardUtils.setBit(attacks, target);
if (BitboardUtils.testBit(occupancy, target)) break;
}
}
return attacks;
}
/**
* 获取车的攻击范围（使用预计算表）
*/
public static long getRookAttacks(int sq, long occupancy) {
long masked = occupancy & ROOK_MASK[sq];
int index = (int)((masked * ROOK_MAGIC[sq]) >>> (64 - ROOK_BITS[sq]));
return ROOK_ATTACKS[sq][index];
}
/**
* 获取象的攻击范围（使用预计算表）
*/
public static long getBishopAttacks(int sq, long occupancy) {
long masked = occupancy & BISHOP_MASK[sq];
int index = (int)((masked * BISHOP_MAGIC[sq]) >>> (64 - BISHOP_BITS[sq]));
return BISHOP_ATTACKS[sq][index];
}
// 魔数（简化版，实际应使用优化的魔数）
private static final long[] ROOK_MAGIC = generateMagics(ROOK_MASK, ROOK_BITS);
private static final long[] BISHOP_MAGIC = generateMagics(BISHOP_MASK, BISHOP_BITS);
private static long[] generateMagics(long[] masks, int[] bits) {
long[] magics = new long[64];
for (int i = 0; i < 64; i++) {
// 简化：使用一个固定的好魔数
magics[i] = 0x1040010400104001L;
}
return magics;
}
}
非滑动棋子攻击表
/**
* 非滑动棋子的预计算攻击表
* 马、王的攻击范围只与位置有关，与棋盘占用无关
*/
public class LeaperAttacks {
// 马的偏移量：(dx, dy)
private static final int[][] KNIGHT_OFFSETS = {
{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2},
{1, -2}, {1, 2}, {2, -1}, {2, 1}
};
// 王的偏移量
private static final int[][] KING_OFFSETS = {
{-1, -1}, {-1, 0}, {-1, 1}, {0, -1},
{0, 1}, {1, -1}, {1, 0}, {1, 1}
};
public static final long[] KNIGHT_ATTACKS = new long[64];
public static final long[] KING_ATTACKS = new long[64];
static {
for (int sq = 0; sq < 64; sq++) {
KNIGHT_ATTACKS[sq] = generateAttacks(sq, KNIGHT_OFFSETS);
KING_ATTACKS[sq] = generateAttacks(sq, KING_OFFSETS);
}
}
private static long generateAttacks(int sq, int[][] offsets) {
long attacks = 0L;
int rank = BitboardUtils.rankOf(sq);
int file = BitboardUtils.fileOf(sq);
for (int[] off : offsets) {
int nr = rank + off[0];
int nf = file + off[1];
if (nr >= 0 && nr < 8 && nf >= 0 && nf < 8) {
attacks = BitboardUtils.setBit(attacks, BitboardUtils.square(nr, nf));
}
}
return attacks;
}
public static long getKnightAttacks(int sq) {
return KNIGHT_ATTACKS[sq];
}
public static long getKingAttacks(int sq) {
return KING_ATTACKS[sq];
}
}
完整的Bitboard棋局表示
/**
* 使用Bitboard表示的棋局状态
* 演示完整的棋盘管理和走法生成
*/
public class BitboardPosition {
// 各棋子类型的位棋盘（白色）
private long whitePawns, whiteKnights, whiteBishops, whiteRooks, whiteQueens, whiteKing;
// 各棋子类型的位棋盘（黑色）
private long blackPawns, blackKnights, blackBishops, blackRooks, blackQueens, blackKing;
// 所有白色/黑色棋子
private long whitePieces, blackPieces, allPieces;
// 当前走棋方：true=白方，false=黑方
private boolean whiteToMove;
public BitboardPosition() {
// 初始化标准开局位置
initStandardPosition();
}
private void initStandardPosition() {
// 白色棋子在第1-2行
whitePawns = 0x000000000000FF00L;
whiteRooks = 0x0000000000000081L;
whiteKnights = 0x0000000000000042L;
whiteBishops = 0x0000000000000024L;
whiteQueen = 0x0000000000000008L;
whiteKing = 0x0000000000000010L;
// 黑色棋子在第7-8行
blackPawns = 0x00FF000000000000L;
blackRooks = 0x8100000000000000L;
blackKnights = 0x4200000000000000L;
blackBishops = 0x2400000000000000L;
blackQueen = 0x0800000000000000L;
blackKing = 0x1000000000000000L;
updateAggregates();
whiteToMove = true;
}
private void updateAggregates() {
whitePieces = whitePawns | whiteKnights | whiteBishops | whiteRooks | whiteQueens | whiteKing;
blackPieces = blackPawns | blackKnights | blackBishops | blackRooks | blackQueens | blackKing;
allPieces = whitePieces | blackPieces;
}
/**
* 生成当前方所有马的合法走法目标位图
*/
public long generateKnightMoves() {
long knights = whiteToMove ? whiteKnights : blackKnights;
long ownPieces = whiteToMove ? whitePieces : blackPieces;
long moves = 0L;
while (knights != 0) {
int sq = BitboardUtils.bitScanForward(knights);
knights = BitboardUtils.popLSB(knights);
// 马的攻击范围减去己方棋子占据的格子
moves |= LeaperAttacks.getKnightAttacks(sq) & ~ownPieces;
}
return moves;
}
/**
* 生成当前方所有王的合法走法目标位图
*/
public long generateKingMoves() {
long king = whiteToMove ? whiteKing : blackKing;
long ownPieces = whiteToMove ? whitePieces : blackPieces;
int sq = BitboardUtils.bitScanForward(king);
return LeaperAttacks.getKingAttacks(sq) & ~ownPieces;
}
/**
* 计算当前局面中当前方的棋子总价值（简化评估函数）
*/
public int evaluate() {
int score = 0;
// 兵=100，马=320，象=330，车=500，后=900，王=20000
score += BitboardUtils.popCount(whitePawns) * 100;
score += BitboardUtils.popCount(whiteKnights) * 320;
score += BitboardUtils.popCount(whiteBishops) * 330;
score += BitboardUtils.popCount(whiteRooks) * 500;
score += BitboardUtils.popCount(whiteQueens) * 900;
score -= BitboardUtils.popCount(blackPawns) * 100;
score -= BitboardUtils.popCount(blackKnights) * 320;
score -= BitboardUtils.popCount(blackBishops) * 330;
score -= BitboardUtils.popCount(blackRooks) * 500;
score -= BitboardUtils.popCount(blackQueens) * 900;
return whiteToMove ? score : -score;
}
public void print() {
System.out.println(" a b c d e f g h");
for (int rank = 7; rank >= 0; rank--) {
System.out.print((rank + 1) + " ");
for (int file = 0; file < 8; file++) {
int sq = BitboardUtils.square(rank, file);
char piece = '.';
if (BitboardUtils.testBit(whitePawns, sq)) piece = 'P';
else if (BitboardUtils.testBit(whiteKnights, sq)) piece = 'N';
else if (BitboardUtils.testBit(whiteBishops, sq)) piece = 'B';
else if (BitboardUtils.testBit(whiteRooks, sq)) piece = 'R';
else if (BitboardUtils.testBit(whiteQueens, sq)) piece = 'Q';
else if (BitboardUtils.testBit(whiteKing, sq)) piece = 'K';
else if (BitboardUtils.testBit(blackPawns, sq)) piece = 'p';
else if (BitboardUtils.testBit(blackKnights, sq)) piece = 'n';
else if (BitboardUtils.testBit(blackBishops, sq)) piece = 'b';
else if (BitboardUtils.testBit(blackRooks, sq)) piece = 'r';
else if (BitboardUtils.testBit(blackQueens, sq)) piece = 'q';
else if (BitboardUtils.testBit(blackKing, sq)) piece = 'k';
System.out.print(piece + " ");
}
System.out.println();
}
System.out.println((whiteToMove ? "White" : "Black") + " to move");
System.out.println("Evaluation: " + evaluate());
}
}
测试用例
public class BitboardDemo {
public static void main(String[] args) {
System.out.println("=== Bitboard基础操作 ===");
long board = 0L;
board = BitboardUtils.setBit(board, BitboardUtils.square(0, 0)); // a1
board = BitboardUtils.setBit(board, BitboardUtils.square(7, 7)); // h8
board = BitboardUtils.setBit(board, BitboardUtils.square(3, 4)); // e4
System.out.println("设置a1, h8, e4后的棋盘:");
BitboardUtils.printBoard(board);
System.out.println("a1有棋子: " + BitboardUtils.testBit(board, BitboardUtils.square(0, 0)));
System.out.println("b1有棋子: " + BitboardUtils.testBit(board, BitboardUtils.square(0, 1)));
System.out.println("棋子数量: " + BitboardUtils.popCount(board));
System.out.println("\n=== 马的攻击范围 ===");
int knightSq = BitboardUtils.square(4, 4); // e5
System.out.println("e5位置的马可以攻击:");
BitboardUtils.printBoard(LeaperAttacks.getKnightAttacks(knightSq));
System.out.println("=== 王的攻击范围 ===");
int kingSq = BitboardUtils.square(0, 4); // e1
System.out.println("e1位置的王可以移动:");
BitboardUtils.printBoard(LeaperAttacks.getKingAttacks(kingSq));
System.out.println("=== 棋盘翻转 ===");
System.out.println("原棋盘:");
BitboardUtils.printBoard(board);
System.out.println("垂直翻转:");
BitboardUtils.printBoard(BitboardUtils.flipVertical(board));
System.out.println("\n=== 完整棋局 ===");
BitboardPosition pos = new BitboardPosition();
pos.print();
System.out.println("\n白方马的合法移动目标:");
BitboardUtils.printBoard(pos.generateKnightMoves());
}
}
复杂度分析
| 操作 | 数组实现 | Bitboard实现 | 加速比 |
|---|---|---|---|
| 生成马走法 | O(n) | O(1) | 10-100x |
| 生成王走法 | O(1) | O(1) | 相当 |
| 生成车/象走法 | O(n) | O(1) | 50-200x |
| 局面拷贝 | O(n²) | O(1-20) | 100-1000x |
| 棋子计数 | O(n²) | O(1) | 100x |
| 攻击检测 | O(n) | O(1) | 10-50x |
其中n为棋盘维度（通常为8）。Bitboard将棋盘操作从循环遍历转化为位运算，充分发挥了现代CPU的并行位处理能力。
应用场景
- 棋类AI引擎：Stockfish、Leela Chess Zero等顶级引擎的核心技术
- 棋盘游戏：围棋、五子棋、跳棋等游戏的状态表示与搜索
- 组合优化：子集枚举、集合运算的高效实现
- 数据库索引：位图索引（Bitmap Index）用于OLAP查询
- 图形处理：像素掩码、碰撞检测的位图表示
总结
Bitboard技术将棋盘状态压缩到64位整数中，利用位运算的并行性实现了极高的操作效率。本文实现了完整的Bitboard工具集，包含基础位操作、滑动棋子攻击生成、非滑动棋子预计算表以及完整的棋局管理类。掌握Bitboard的设计思想，不仅能提升棋类AI的性能，也能为各类需要高效集合操作的算法问题提供新的解决思路。
