引言
2048是一款风靡全球的数字拼图游戏，玩家通过上下左右滑动，使相同数字的方块合并，最终目标是得到2048甚至更高的数字。对于AI求解器而言，每秒需要评估成千上万个局面，传统的二维数组表示方式效率低下。本文介绍一种高效的状态表示方法——Bitboard（位棋盘），利用64位长整型将4×4棋盘的所有信息压缩存储，通过位运算实现瞬间移动与合并。
核心算法原理
1. Bitboard状态表示
4×4棋盘中，每个格子可以存放的数字为0（空）、2、4、8、…、最大到65536（即 $2^{16}$），对应指数范围为0到15。每个格子需要4个比特位存储，16个格子共需64位，恰好可以用一个 long 类型存储：
long board;
// 每个格子占4位，从低位到高位依次对应格子(0,0),(0,1)...(3,3)
// 存储的是数字的指数：0表示空，1表示2，2表示4，...，15表示32768
2. 位运算移动与合并
以左移为例，每一行独立处理。对于一行16位（4个格子×4位），可以通过预计算的查找表（Lookup Table）在O(1)时间内完成该行的左移合并操作。
查表法的核心思想：一行只有16位，最多 $2^{16} = 65536$ 种状态。预先计算每种状态的左移、右移结果，运行时直接查表。
3. 行变换与列变换
对于上下移动，需要先将列数据提取成行格式，处理后再写回。这通过位掩码和移位操作完成。
Java实现
import java.util.*;
/**
* 2048 Bitboard实现
* 使用64位长整型存储4x4棋盘，通过位运算和查表实现高效移动
*/
public class Game2048Bitboard {
// 预计算的左移查表: key = 一行16位的原始状态, value = 左移合并后的16位结果
private static final int[] LEFT_TABLE = new int[1 << 16];
private static final int[] RIGHT_TABLE = new int[1 << 16];
private static final int[] SCORE_TABLE = new int[1 << 16]; // 该行左移产生的分数
// 方向常量
public static final int UP = 0, RIGHT = 1, DOWN = 2, LEFT = 3;
static {
buildTables();
}
/**
* 预计算所有65536种行状态的移动结果
*/
private static void buildTables() {
for (int row = 0; row < (1 << 16); row++) {
int[] cells = new int[4];
// 解析一行的4个格子
for (int i = 0; i < 4; i++) {
cells[i] = (row >> (i * 4)) & 0xF;
}
// 左移合并逻辑
int[] leftResult = moveLineLeft(cells);
int leftRow = 0;
for (int i = 0; i < 4; i++) {
leftRow |= (leftResult[i] << (i * 4));
}
LEFT_TABLE[row] = leftRow;
// 右移：反转、左移、再反转
int[] rev = new int[]{cells[3], cells[2], cells[1], cells[0]};
int[] rightResult = moveLineLeft(rev);
int rightRow = 0;
for (int i = 0; i < 4; i++) {
rightRow |= (rightResult[i] << (i * 4));
}
// 反转回原始顺序存储
int reversedRight = 0;
for (int i = 0; i < 4; i++) {
reversedRight |= ((rightRow >> (i * 4)) & 0xF) << ((3 - i) * 4);
}
RIGHT_TABLE[row] = reversedRight;
// 计算左移得分
SCORE_TABLE[row] = calculateScore(cells, leftResult);
}
}
/**
* 对一行4个格子执行左移合并
* 返回合并后的新行
*/
private static int[] moveLineLeft(int[] cells) {
int[] result = new int[4];
int idx = 0;
// 步骤1: 将所有非零数字左移紧凑排列
int[] compact = new int[4];
int compactIdx = 0;
for (int cell : cells) {
if (cell != 0) {
compact[compactIdx++] = cell;
}
}
// 步骤2: 合并相邻相同数字
int i = 0;
while (i < compactIdx) {
if (i + 1 < compactIdx && compact[i] == compact[i + 1]) {
result[idx++] = compact[i] + 1; // 指数加1，如2+2=4，指数1+1=2
i += 2;
} else {
result[idx++] = compact[i];
i++;
}
}
return result;
}
private static int calculateScore(int[] original, int[] result) {
int score = 0;
int[] origCompact = new int[4];
int[] resCompact = new int[4];
int oi = 0, ri = 0;
for (int c : original) if (c != 0) origCompact[oi++] = c;
for (int c : result) if (c != 0) resCompact[ri++] = c;
// 找到被合并的数字（相邻相同数字合并会产生一个指数+1的数）
int i = 0, j = 0;
while (i < oi && j < ri) {
if (i + 1 < oi && origCompact[i] == origCompact[i + 1]) {
score += (1 << origCompact[i]) * 2; // 合并得分 = 合并后的数字值
i += 2;
j++;
} else {
i++;
j++;
}
}
return score;
}
private long board; // 64位棋盘状态
private int score;
private Random random;
public Game2048Bitboard() {
this.board = 0L;
this.score = 0;
this.random = new Random();
spawnTile();
spawnTile();
}
public Game2048Bitboard(long board, int score) {
this.board = board;
this.score = score;
this.random = new Random();
}
/**
* 获取指定位置的格子值（指数）
*/
public int getCell(int row, int col) {
int shift = (row * 4 + col) * 4;
return (int) ((board >> shift) & 0xFL);
}
/**
* 设置指定位置的格子值
*/
private void setCell(int row, int col, int value) {
int shift = (row * 4 + col) * 4;
long mask = ~(0xFL << shift);
board = (board & mask) | ((long)(value & 0xF) << shift);
}
/**
* 提取一行的16位数据
*/
private int extractRow(int row) {
return (int) ((board >> (row * 16)) & 0xFFFFL);
}
/**
* 将处理后的16位数据写回指定行
*/
private void writeRow(int row, int rowData) {
long mask = ~(0xFFFFL << (row * 16));
board = (board & mask) | ((long)(rowData & 0xFFFF) << (row * 16));
}
/**
* 提取一列并转换为行格式（用于上下移动）
*/
private int extractColumnAsRow(int col) {
int result = 0;
for (int row = 0; row < 4; row++) {
int cell = getCell(row, col);
result |= (cell << (row * 4));
}
return result;
}
/**
* 将行格式的数据写回列
*/
private void writeColumnFromRow(int col, int colData) {
for (int row = 0; row < 4; row++) {
int cell = (colData >> (row * 4)) & 0xF;
setCell(row, col, cell);
}
}
/**
* 执行移动操作
* @return true如果棋盘发生了变化
*/
public boolean move(int direction) {
long oldBoard = board;
switch (direction) {
case LEFT:
for (int row = 0; row < 4; row++) {
int rowData = extractRow(row);
int newRow = LEFT_TABLE[rowData];
score += SCORE_TABLE[rowData];
writeRow(row, newRow);
}
break;
case RIGHT:
for (int row = 0; row < 4; row++) {
int rowData = extractRow(row);
int newRow = RIGHT_TABLE[rowData];
score += SCORE_TABLE[rowData];
writeRow(row, newRow);
}
break;
case UP:
for (int col = 0; col < 4; col++) {
int colData = extractColumnAsRow(col);
int newCol = LEFT_TABLE[colData]; // 上移等价于列数据的左移
score += SCORE_TABLE[colData];
writeColumnFromRow(col, newCol);
}
break;
case DOWN:
for (int col = 0; col < 4; col++) {
int colData = extractColumnAsRow(col);
int newCol = RIGHT_TABLE[colData]; // 下移等价于列数据的右移
score += SCORE_TABLE[colData];
writeColumnFromRow(col, newCol);
}
break;
}
if (board != oldBoard) {
spawnTile();
return true;
}
return false;
}
/**
* 在随机空位置生成2(90%)或4(10%)
*/
private void spawnTile() {
List<int[]> empty = new ArrayList<>();
for (int r = 0; r < 4; r++) {
for (int c = 0; c < 4; c++) {
if (getCell(r, c) == 0) {
empty.add(new int[]{r, c});
}
}
}
if (empty.isEmpty()) return;
int[] pos = empty.get(random.nextInt(empty.size()));
int value = random.nextDouble() < 0.9 ? 1 : 2; // 指数：1=2, 2=4
setCell(pos[0], pos[1], value);
}
/**
* 判断游戏是否结束
*/
public boolean isGameOver() {
// 检查是否有空格
for (int r = 0; r < 4; r++) {
for (int c = 0; c < 4; c++) {
if (getCell(r, c) == 0) return false;
}
}
// 检查是否有相邻相同数字可以合并
for (int r = 0; r < 4; r++) {
for (int c = 0; c < 4; c++) {
int val = getCell(r, c);
if (c < 3 && getCell(r, c + 1) == val) return false;
if (r < 3 && getCell(r + 1, c) == val) return false;
}
}
return true;
}
/**
* 获取当前棋盘的最大数字
*/
public int getMaxTile() {
int max = 0;
for (int r = 0; r < 4; r++) {
for (int c = 0; c < 4; c++) {
max = Math.max(max, getCell(r, c));
}
}
return 1 << max; // 将指数转换为实际值
}
public void printBoard() {
System.out.println("Score: " + score);
for (int r = 0; r < 4; r++) {
for (int c = 0; c < 4; c++) {
int val = getCell(r, c);
if (val == 0) {
System.out.printf("%6s", ".");
} else {
System.out.printf("%6d", 1 << val);
}
}
System.out.println();
}
System.out.println();
}
public long getBoard() { return board; }
public int getScore() { return score; }
public static void main(String[] args) {
Game2048Bitboard game = new Game2048Bitboard();
game.printBoard();
Scanner scanner = new Scanner(System.in);
Map<String, Integer> dirMap = Map.of(
"w", UP, "d", RIGHT, "s", DOWN, "a", LEFT
);
while (!game.isGameOver()) {
System.out.print("Move (w/a/s/d): ");
String input = scanner.nextLine().trim().toLowerCase();
if (!dirMap.containsKey(input)) continue;
game.move(dirMap.get(input));
game.printBoard();
}
System.out.println("Game Over! Max tile: " + game.getMaxTile());
}
}
复杂度分析
- 状态存储：使用一个64位
long存储整个棋盘，空间复杂度 $O(1)$。 - 移动操作：每次移动只需对4行（或4列）各执行一次查表操作，时间复杂度 $O(1)$。
- 查表预处理：$O(65536 \times 4)$，仅在类加载时执行一次。
- 局面评估：在AI搜索中，Bitboard表示使得局面的哈希、拷贝、比较都变为 $O(1)$ 操作，大幅提升了搜索效率。
总结
Bitboard是棋类游戏AI中经典的状态压缩技术。2048的4×4棋盘恰好适配64位整型，每个格子4位存储数字指数。通过65536项的查表预计算，移动和合并操作从多层循环简化为常数时间的数组访问。这种表示法不仅节省内存，更使每秒局面评估数提升数十倍，为后续引入Expectimax或蒙特卡洛搜索奠定了性能基础。
