一、游戏场景：2048 的难点是”随机性”
2048 的规则十行字就能说完：上下左右滑动，相同数字合并翻倍，每次滑动后随机在空格生成一个 2（90%）或 4（10%）。但要做 AI，难点立刻显现：
- 动作空间是确定的（4 个方向），但结果是不确定的（新方块位置与数值随机）；
- 深度不可控：一局可能走几百步，穷举整棵博弈树不可能；
- 评估很重要：在浅层搜索里，”这一步滑得好不好”几乎完全由评估函数决定。
已有的经典解法是 Expectimax：对 max 层（玩家选方向）取最大，对 chance 层（随机生成方块）取期望。它正确但昂贵——每步要展开 4 × (空格数 × 2) 个子节点，深度 4 就到了几十万节点。本文实现另一条路线：束搜索（Beam Search）。核心思想是：
与其把整层所有子节点都留着，不如只留评估值最高的
K个（束宽K），让搜索深度可以堆得很深，而内存与时间只随K线性增长。
这是”用评估函数换搜索宽度”的经典取舍，在自然语言生成、路径规划里都极常见。我们把它移植到 2048，并给出可量化的收益分析。
二、把 2048 抽象成搜索问题
2.1 状态与转移
棋盘用 16 个格子表示，每格存”指数”（即 log2 值：0 空、1 表示 2、2 表示 4、11 表示 2048）。这样：
- 合并判定只需比较整数；
- 分值计算变成
1 << level； - 整个棋盘能塞进一个
long（4 bit/格，16 格 = 64 bit），为 Zobrist 哈希与去重提供便利。
对某个方向 d，转移 slide(state, d) 是确定性的：
if 该方向滑动后有任何格子的值发生变化:
newState = 合并结果，score += 合并产生的分数
chance 层：在 newState 的每个空格上分别放置 2（0.9）或 4（0.1）
注意”不变则非法”这条规则：滑动后棋盘没变化的方向不能作为动作，否则 AI 会在原地打转。
2.2 为什么束搜索够用
关键观察：2048 的局面评估高度局部化。一个棋盘好不好，主要看四件事——
- 空格数量（空格越多越安全）；
- 最大块是否落在角落（角落策略是 2048 的核心经验）；
- 行的单调性（数字沿一个方向递增/递减，便于合并）；
- 相邻格数值平滑度（相邻数字接近则容易合并）。
这些指标都能在 O(16) 内算完。也就是说：评估函数便宜、可靠；而精确前瞻昂贵。当”评估便宜”遇上”前瞻昂贵”，束搜索就是最自然的选择——4 个方向 × 束宽 K，深度 D，总节点数 O(K·4·D)。
2.3 束搜索在 2048 里的两个特殊处理
- chance 层用”期望”而非纯采样：对每个候选按
0.9/0.1折算生成 2 与 4 的期望，比随机采样稳定得多； - 去重：不同决策序列可能收敛到同一棋盘，用 Zobrist 哈希去重能省掉大量重复展开。
三、位压缩棋盘
package com.algodaily.g2048;
/**
* 2048 棋盘：16 个格子各占 4 bit，整体塞进一个 long。
* 格子存指数（0 空、1 表示 2、k 表示 2^k），最大 15（32768）。
*/
public final class Board2048 {
private static final int BITS = 4;
private static final int MASK = 0xF;
private long bits;
private int score;
private int emptyCount;
/** 方向 */
public enum Dir { UP, DOWN, LEFT, RIGHT }
public Board2048() {
this.bits = 0L;
this.score = 0;
this.emptyCount = 16;
}
private Board2048(long bits, int score) {
this.bits = bits;
this.score = score;
recomputeEmpty();
}
public Board2048 copy() { return new Board2048(bits, score); }
public long rawBits() { return bits; }
public int score() { return score; }
public int emptyCount() { return emptyCount; }
/** level = 0..15，r/c = 0..3 */
public int get(int r, int c) { return (int) ((bits >>> ((r * 4 + c) * BITS)) & MASK); }
public void set(int r, int c, int level) {
int shift = (r * 4 + c) * BITS;
bits &= ~((long) MASK << shift);
bits |= ((long) level & MASK) << shift;
recomputeEmpty();
}
/** 由 16 个指数构造（便于初始化与测试） */
public static Board2048 of(int... levels) {
Board2048 b = new Board2048();
for (int i = 0; i < 16; i++) {
b.bits |= ((long) levels[i] & MASK) << (i * BITS);
}
b.recomputeEmpty();
return b;
}
private void recomputeEmpty() {
int cnt = 0;
for (int i = 0; i < 16; i++) {
if (((bits >>> (i * BITS)) & MASK) == 0) cnt++;
}
this.emptyCount = cnt;
}
// ---------- 滑动与合并 ----------
/** 在指定方向滑动一次；该方向非法（棋盘无变化）时返回 null */
public Board2048 slide(Dir dir) {
int[] before = extractLines(dir);
int[] after = new int[16];
int gained = 0;
// 逐行处理并累计得分
for (int i = 0; i < 4; i++) {
int[] line = {before[i * 4], before[i * 4 + 1], before[i * 4 + 2], before[i * 4 + 3]};
int[] gainBox = new int[1];
int[] merged = mergeLine(line, gainBox);
gained += gainBox[0];
for (int k = 0; k < 4; k++) after[i * 4 + k] = merged[k];
}
boolean changed = false;
for (int i = 0; i < 16; i++) {
if (before[i] != after[i]) { changed = true; break; }
}
if (!changed) return null;
Board2048 nb = placeLines(after, dir);
nb.score = this.score + gained;
return nb;
}
/** 把棋盘按方向拆成 4 条"从滑动方向起点开始"的一维线 */
private int[] extractLines(Dir dir) {
int[] out = new int[16];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
out[i * 4 + j] = cellAt(flatIndex(dir, i, j));
}
}
return out;
}
private int flatIndex(Dir dir, int i, int j) {
switch (dir) {
case LEFT: return i * 4 + j;
case RIGHT: return i * 4 + (3 - j);
case UP: return j * 4 + i;
case DOWN: return (3 - j) * 4 + i;
default: throw new IllegalStateException();
}
}
private int cellAt(int flatIdx) { return (int) ((bits >>> (flatIdx * BITS)) & MASK); }
/** 由一维线还原回位压缩棋盘 */
private Board2048 placeLines(int[] lines, Dir dir) {
Board2048 nb = new Board2048();
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
int idx = flatIndex(dir, i, j);
nb.bits |= ((long) lines[i * 4 + j] & MASK) << (idx * BITS);
}
}
nb.recomputeEmpty();
return nb;
}
/** 行合并核心：压缩 → 合并（同一块一次滑行内只合并一次）→ 再压缩 */
private int[] mergeLine(int[] line, int[] gainBox) {
int[] comp = new int[4];
int p = 0;
for (int v : line) if (v != 0) comp[p++] = v;
for (int i = 0; i + 1 < p; i++) {
if (comp[i] == comp[i + 1] && comp[i] != 0) {
comp[i] = comp[i] + 1;
comp[i + 1] = 0;
gainBox[0] += (1 << comp[i]); // 合并后数值 = 2^(k+1)
i++; // 跳过下一个，防止连锁合并
}
}
int[] res = new int[4];
int q = 0;
for (int v : comp) if (v != 0) res[q++] = v;
return res;
}
/** 在空格中随机放入 2（90%）或 4（10%） */
public void spawn(java.util.Random rnd) {
if (emptyCount == 0) return;
int[] emptyIdx = new int[emptyCount];
int k = 0;
for (int i = 0; i < 16; i++) {
if (((bits >>> (i * BITS)) & MASK) == 0) emptyIdx[k++] = i;
}
int pos = emptyIdx[rnd.nextInt(emptyCount)];
int level = (rnd.nextInt(100) < 90) ? 1 : 2;
bits |= ((long) level) << (pos * BITS);
emptyCount--;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int r = 0; r < 4; r++) {
for (int c = 0; c < 4; c++) {
int v = get(r, c);
sb.append(v == 0 ? " ." : String.format("%6d", 1 << v));
}
sb.append('\n');
}
return sb.toString();
}
}
三个实现细节值得停留一下：
mergeLine需要一个”得分出口”（gainBox），因为 Java 不能像 C++ 那样通过引用返回两个值，用一个长度 1 的数组是最轻量的做法；flatIndex把”方向 + 行列”统一映射成一位扁平下标，避免为上/下/左/右写四套几乎相同的代码；set里每次都recomputeEmpty，是为了让emptyCount永远与位串一致——棋盘对象在搜索里会被大量复制，缓存不一致比慢一点危险得多。
四、四维评估函数
package com.algodaily.g2048;
/**
* 2048 局面评估：空格数、行列单调性、相邻平滑度、最大块贴角。
* 权重是经验值，可通过交叉熵方法等做参数自搜。
*/
public final class Heuristics {
/** 权重容器，便于参数搜索时整体替换 */
public static final class Weights {
public double empty = 3.0;
public double monotonic = 1.0;
public double smooth = 0.8;
public double corner = 2.0;
public double maxLevel = 1.0;
public double merge = 0.5;
public Weights() {}
public Weights(double empty, double monotonic, double smooth,
double corner, double maxLevel, double merge) {
this.empty = empty;
this.monotonic = monotonic;
this.smooth = smooth;
this.corner = corner;
this.maxLevel = maxLevel;
this.merge = merge;
}
}
private final Weights w;
public Heuristics() { this(new Weights()); }
public Heuristics(Weights w) { this.w = w; }
/** 综合评估：越大越好 */
public double evaluate(Board2048 b) {
return w.empty * emptyScore(b)
+ w.monotonic * monotonicity(b)
+ w.smooth * smoothness(b)
+ w.corner * cornerBonus(b)
+ w.maxLevel * maxLevel(b)
+ w.merge * mergePotential(b);
}
/** 空格数是"生存空间"，用 log 抑制线性膨胀，避免评估只堆空格不打高分 */
public double emptyScore(Board2048 b) { return Math.log1p(b.emptyCount()); }
/** 单调性：每行每列分别算"递增/递减"的差值，取更优方向 */
public double monotonicity(Board2048 b) {
double total = 0.0;
for (int r = 0; r < 4; r++) total += lineMonotonic(row(b, r));
for (int c = 0; c < 4; c++) total += lineMonotonic(col(b, c));
return total;
}
private double lineMonotonic(int[] line) {
double inc = 0.0, dec = 0.0;
for (int i = 0; i + 1 < line.length; i++) {
inc += line[i] - line[i + 1];
dec += line[i + 1] - line[i];
}
// 取两个方向中更"单调"的那个：差值越接近 0 越好，因此返回负的较小者
return -Math.min(inc, dec);
}
/** 平滑度：相邻非空格数值差异越小越好 */
public double smoothness(Board2048 b) {
double penalty = 0.0;
for (int r = 0; r < 4; r++) {
for (int c = 0; c < 4; c++) {
int v = b.get(r, c);
if (v == 0) continue;
if (c + 1 < 4 && b.get(r, c + 1) != 0) penalty += Math.abs(v - b.get(r, c + 1));
if (r + 1 < 4 && b.get(r + 1, c) != 0) penalty += Math.abs(v - b.get(r + 1, c));
}
}
return -penalty;
}
/** 角落奖励：最大块落在四角之一时加分 */
public double cornerBonus(Board2048 b) {
int max = maxLevel(b);
if (max == 0) return 0.0;
int[][] corners = {{0, 0}, {0, 3}, {3, 0}, {3, 3}};
for (int[] p : corners) {
if (b.get(p[0], p[1]) == max) return max * 1.0;
}
return 0.0;
}
public int maxLevel(Board2048 b) {
int m = 0;
for (int i = 0; i < 16; i++) {
int v = b.get(i / 4, i % 4);
if (v > m) m = v;
}
return m;
}
/** 可合并对数：手工"预告"一步合并收益 */
public double mergePotential(Board2048 b) {
int cnt = 0;
for (int r = 0; r < 4; r++) {
for (int c = 0; c < 4; c++) {
int v = b.get(r, c);
if (v == 0) continue;
if (c + 1 < 4 && b.get(r, c + 1) == v) cnt++;
if (r + 1 < 4 && b.get(r + 1, c) == v) cnt++;
}
}
return cnt;
}
private int[] row(Board2048 b, int r) {
return new int[]{b.get(r, 0), b.get(r, 1), b.get(r, 2), b.get(r, 3)};
}
private int[] col(Board2048 b, int c) {
return new int[]{b.get(0, c), b.get(1, c), b.get(2, c), b.get(3, c)};
}
}
一个容易被忽视的设计点：maxLevel 与 cornerBonus 是耦合的。如果把 corner 权重调得太高，AI 会宁可保住角落的大块也不去合并升级，结果被”卡死”在 512；调得太低，大块会到处乱跑，很快把棋盘填满。这正是实践中必须做参数搜索的原因——这些权重没有理论最优值，只有”针对某个搜索深度/束宽的最优值”。
五、Zobrist 哈希与去重
package com.algodaily.g2048;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
/**
* Zobrist 哈希：为每个 (格子位置, 等级) 预生成随机 long，
* 棋盘哈希 = 所有非空格对应随机值的异或。
* 用于束搜索中"同一棋盘去重"，避免重复展开。
*/
public final class Zobrist {
private static final long[][] TABLE = new long[16][16];
static {
Random rnd = new Random(0x2048_2026L);
for (int i = 0; i < 16; i++) {
for (int v = 0; v < 16; v++) TABLE[i][v] = rnd.nextLong();
}
}
public static long hash(long bits) {
long h = 0L;
for (int i = 0; i < 16; i++) {
int v = (int) ((bits >>> (i * 4)) & 0xF);
if (v != 0) h ^= TABLE[i][v];
}
return h;
}
public static long hash(Board2048 b) { return hash(b.rawBits()); }
/** 去重集合：哈希 → 原始位串（用于碰撞二次校验） */
public static final class SeenSet {
private final Map<Long, Long> map = new HashMap<>();
/** 已存在返回 false；否则登记并返回 true */
public boolean addIfAbsent(Board2048 b) {
long h = Zobrist.hash(b);
Long prev = map.get(h);
if (prev != null && prev == b.rawBits()) return false; // 真是同一局面
// 哈希碰撞但局面不同：允许插入（不同 key 不会互相覆盖，因为用 rawBits 作值）
map.put(h, b.rawBits());
return true;
}
public void clear() { map.clear(); }
public int size() { return map.size(); }
}
}
严格来说
Map<Long, Long>在哈希碰撞且局面不同的情况下会覆盖旧值，从而把两个不同局面误认为”已存在”或”未存在”。工程上的稳妥做法是Map<Long, Set<Long>>或直接用rawBits本身作 key（long位串本身就是无损标识，16 格 × 4 bit 正好 64 bit，没有碰撞）。这里保留 Zobrist 是为了说明”棋盘可以被压缩成一个可哈希的指纹”这一普遍技巧。
六、束搜索主循环
束的状态是”若干待评估棋盘 + 累计启发式收益”，每轮对它们做 4 方向扩展，再用评估函数裁剪到前 K 个。
package com.algodaily.g2048;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
/**
* 束搜索 AI。
*
* 每一层：
* 1) 对束中每个状态尝试 4 个方向（非法方向返回 null 被丢弃）
* 2) 用 chance 层的期望把新状态细化一层（2/4 按 0.9/0.1 折算）
* 3) 用工评估函数打分，取前 beamWidth 个进入下一层
* 最终返回第一步应走的动作。
*/
public final class BeamSearchAI {
private final Heuristics heuristic;
private final int beamWidth;
private final int depth;
private final java.util.Random rnd;
private final Zobrist.SeenSet seen = new Zobrist.SeenSet();
public BeamSearchAI(Heuristics heuristic, int beamWidth, int depth, long seed) {
this.heuristic = heuristic;
this.beamWidth = beamWidth;
this.depth = depth;
this.rnd = new java.util.Random(seed);
}
/** 束内候选：棋盘 + 从根出发的第一步 + 累计收益 + 深度 */
private static final class Candidate {
final Board2048 board;
final Board2048.Dir firstMove;
final double g;
final int d;
Candidate(Board2048 board, Board2048.Dir firstMove, double g, int d) {
this.board = board;
this.firstMove = firstMove;
this.g = g;
this.d = d;
}
}
/** 选择当前最优动作；全非法（终局）时返回 null */
public Board2048.Dir decide(Board2048 root) {
seen.clear();
List<Candidate> beam = new ArrayList<>();
for (Board2048.Dir dir : Board2048.Dir.values()) {
Board2048 nb = root.slide(dir);
if (nb == null) continue;
beam.add(new Candidate(nb, dir, 0.0, 1));
}
if (beam.isEmpty()) return null;
for (int level = 1; level < depth && !beam.isEmpty(); level++) {
List<Candidate> next = new ArrayList<>(beam.size() * 4);
for (Candidate cur : beam) {
for (Board2048.Dir dir : Board2048.Dir.values()) {
Board2048 nb = cur.board.slide(dir);
if (nb == null) continue;
double expected = chanceValue(nb); // chance 层期望
next.add(new Candidate(nb, cur.firstMove, cur.g + expected, level + 1));
}
}
if (next.isEmpty()) break;
// 打分裁剪 + 去重
next.sort(Comparator.comparingDouble(c -> -score(c)));
List<Candidate> kept = new ArrayList<>(beamWidth);
for (Candidate c : next) {
if (!seen.addIfAbsent(c.board)) continue;
kept.add(c);
if (kept.size() >= beamWidth) break;
}
beam = kept;
}
// 汇总：同一 firstMove 取最高分，选出全局最优第一步
double[] best = new double[Board2048.Dir.values().length];
Arrays.fill(best, Double.NEGATIVE_INFINITY);
Board2048.Dir chosen = null;
for (Candidate c : beam) {
int idx = c.firstMove.ordinal();
double s = score(c);
if (s > best[idx]) { best[idx] = s; chosen = c.firstMove; }
}
return chosen;
}
/** 候选综合打分：已累计收益 + 当前局面评估 */
private double score(Candidate c) { return c.g + heuristic.evaluate(c.board); }
/**
* chance 层期望：在 nb 的空格上，按 0.9/0.1 生成 2/4 后局面评估的期望。
* 为控制开销，随机抽取至多 2 个代表格近似。
*/
private double chanceValue(Board2048 nb) {
if (nb.emptyCount() == 0) return heuristic.evaluate(nb);
int[] empties = new int[nb.emptyCount()];
int k = 0;
for (int i = 0; i < 16; i++) {
if ((int) ((nb.rawBits() >>> (i * 4)) & 0xF) == 0) empties[k++] = i;
}
int samples = Math.min(2, empties.length);
double sum = 0.0;
for (int s = 0; s < samples; s++) {
int pos = empties[rnd.nextInt(empties.length)];
int r = pos / 4, c = pos % 4;
for (int level = 1; level <= 2; level++) {
double p = (level == 1) ? 0.9 : 0.1;
Board2048 tmp = nb.copy();
tmp.set(r, c, level);
sum += p * heuristic.evaluate(tmp);
}
}
return sum / samples;
}
}
七、精确期望基线：Expectimax
package com.algodaily.g2048;
/**
* Expectimax：max 层（玩家选方向）取最大，chance 层（随机生成）取期望。
* 作为精度基线——深度浅但精确，用来衡量束搜索的近似损失。
*/
public final class ExpectimaxAI {
private final Heuristics heuristic;
private final int maxDepth;
private final long nodeBudget;
private long visited;
public ExpectimaxAI(Heuristics heuristic, int maxDepth, long nodeBudget) {
this.heuristic = heuristic;
this.maxDepth = maxDepth;
this.nodeBudget = nodeBudget;
}
public Board2048.Dir decide(Board2048 root) {
visited = 0;
Board2048.Dir bestDir = null;
double bestVal = Double.NEGATIVE_INFINITY;
for (Board2048.Dir dir : Board2048.Dir.values()) {
Board2048 nb = root.slide(dir);
if (nb == null) continue;
double v = chanceNode(nb, 1);
if (v > bestVal) { bestVal = v; bestDir = dir; }
}
return bestDir;
}
/** chance 层：对所有空格 × {2,4} 求期望 */
private double chanceNode(Board2048 b, int depth) {
visited++;
if (depth >= maxDepth || visited > nodeBudget || b.emptyCount() == 0) {
return heuristic.evaluate(b);
}
double expected = 0.0;
int empties = b.emptyCount();
for (int i = 0; i < 16; i++) {
if ((int) ((b.rawBits() >>> (i * 4)) & 0xF) != 0) continue;
int r = i / 4, c = i % 4;
for (int level = 1; level <= 2; level++) {
double p = (level == 1) ? 0.9 : 0.1;
Board2048 tmp = b.copy();
tmp.set(r, c, level);
expected += p / empties * maxNode(tmp, depth + 1);
}
if (visited > nodeBudget) break;
}
return expected;
}
/** max 层：玩家选最优方向 */
private double maxNode(Board2048 b, int depth) {
visited++;
if (depth >= maxDepth || visited > nodeBudget) return heuristic.evaluate(b);
double best = Double.NEGATIVE_INFINITY;
for (Board2048.Dir dir : Board2048.Dir.values()) {
Board2048 nb = b.slide(dir);
if (nb == null) continue;
best = Math.max(best, chanceNode(nb, depth + 1));
if (visited > nodeBudget) break;
}
return (best == Double.NEGATIVE_INFINITY) ? heuristic.evaluate(b) : best;
}
}
八、自对弈与统计
package com.algodaily.g2048;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Random;
/** 入口：让束搜索 AI 自对弈若干局，统计最大方块分布、平均步数与得分 */
public final class Game2048App {
public static void main(String[] args) {
int games = 20;
Map<Integer, Integer> maxTileDist = new LinkedHashMap<>();
int totalSteps = 0, totalScore = 0;
System.out.println("束宽 = 8，深度 = 3");
for (int g = 0; g < games; g++) {
Result r = playOne(new Random(20261101L + g));
maxTileDist.merge(r.maxLevel, 1, Integer::sum);
totalSteps += r.steps;
totalScore += r.score;
System.out.printf("局 %2d：最大块 = %5d，步数 = %4d，得分 = %6d%n",
g + 1, 1 << r.maxLevel, r.steps, r.score);
}
System.out.println("最大块分布（2^等级 → 局数）= " + maxTileDist);
System.out.printf("平均步数 = %.2f，平均得分 = %.2f%n",
(double) totalSteps / games, (double) totalScore / games);
}
private static final class Result {
int maxLevel;
int steps;
int score;
}
private static Result playOne(Random rnd) {
Board2048 b = new Board2048();
b.spawn(rnd);
b.spawn(rnd);
Heuristics h = new Heuristics();
BeamSearchAI ai = new BeamSearchAI(h, 8, 3, rnd.nextLong());
Result res = new Result();
int lastMax = 0;
int stall = 0;
for (int step = 0; step < 3000; step++) {
Board2048.Dir dir = ai.decide(b);
if (dir == null) break; // 无合法动作 => 终局
b = b.slide(dir);
b.spawn(rnd);
res.steps++;
int curMax = h.maxLevel(b);
if (curMax == lastMax) stall++;
else { stall = 0; lastMax = curMax; }
if (stall > 400) break; // 长时间无进展，提前收尾
}
res.maxLevel = h.maxLevel(b);
res.score = b.score();
return res;
}
}
九、束宽与深度：收益/成本的定量权衡
跑一批局后，会看到一个很稳定的趋势：
| 束宽 K | 深度 D | 单步节点数（约） | 达到 2048 的比例 | 平均得分 |
|---|---|---|---|---|
| 1（等价贪心） | 1 | 4 | 低 | 低 |
| 4 | 2 | 32 | 中 | 中 |
| 8 | 3 | 96 | 高 | 高 |
| 16 | 4 | 256 | 略优 | 略优（边际递减） |
三条可验证的结论：
K和D不是同一种资源。加深深度给的是”看得更远”，加宽束给的是”不丢好分支”。2048 里后者更重要——评估函数对”某一步是否埋下死路”判断很准，但浅层搜索会把某些”先吃亏后大赚”的分支直接砍掉。- 边际收益急剧衰减。从
K=1到K=8是质变，从K=8到K=16只提升几个百分点而时间翻倍。选择束宽的方法应当是”二分到性价比拐点”，而不是凭感觉定一个漂亮数字。 - chance 层的近似比 max 层更值得花预算。把
chanceValue的采样从 1 格提到 2 格，对最终决策的影响常常大于把束宽从 8 提到 12。原因很简单：2048 的随机性主要在”生成位置”，而不是”生成数值”。
十、实现细节里的三个坑
slide必须严格”非法则返回 null”。如果返回原棋盘，束搜索会把无效动作当成合法候选，AI 就原地不动。这是实现 2048 AI 最常见的一处 bug。- 一条线一次滑行内只能合并一次。
[2,2,2,2]向左滑，正确结果是[4,4]（得 8 分）而不是[8]。mergeLine里的i++就是为此。 - 位压缩的移位必须用
long。(long) MASK << shift中若MASK是int，shift超过 31 会静默错位。这类错误在小棋盘上不显眼，一旦等级超过 8 就会算错评估分。
十一、束搜索的通用性
把 2048 换掉，束搜索的骨架一行不用改：
- 机器翻译 / 文本生成：beam search 就是早期 SMT 与 NMT 的标配解码器，
K即 beam size（通常 4～10）； - Anytime 路径规划：束宽就是内存预算，随时可以停下并给出”当前最优”；
- 拼图 / 滑块类游戏：把评估函数换成曼哈顿距离 + 线性冲突，就是同一套东西。
它相对 A/IDA 的真正差别是：A* 要求启发式可采纳（永不高估）才保证最优；束搜索完全不要求，只承诺”在预算内给一个足够好的答案”。当最优解本身不重要、或者根本不可计算（2048 一局的得分上限取决于随机序列），这个”放弃最优性保证”的交换就是划算的。
