2048 的 AI 有两种典型路线：一种是”算得深”，用 Expectimax 把博弈树搜到很深；另一种是”看得准”，用一个良好的局面评估函数配合一步贪心。前者受制于分支因子——每个状态平均 3~4 个合法方向、加上 2 个随机方块位置，搜索树膨胀极快；后者则是纯参数问题：评估函数的权重怎么定？
本文走第二条路线，并且用 交叉熵方法（Cross-Entropy Method，CEM） 自动把这组权重学出来。思路很干净：把”启发式权重”看成待优化的参数向量，用蒙特卡洛仿真来评估每组参数的得分，再用”精英样本重估分布”迭代逼近最优。这是进化策略家族里最简单、最好实现、也最稳的一支。
一、2048 的状态与操作
棋盘用 4×4 的 $4\times4$ 网格，每格是一个 2 的幂（0 表示空）。为了后续位运算做哈希，这里用 long 存棋盘：每格 4 bit 存指数的低 4 位（0 表示空，1~15 表示 $2^1$~$2^{15}$）。15 已经远超 2048（即 $2^{11}$），够用。
四个方向的操作本质相同：把每一行的非零块向一侧压缩、相同数字合并、再压缩。合并规则有个细节——每次移动每个方块最多参与一次合并，2 2 2 2 向左应得 4 4（而不是 8）。
public class Board {
private final int[][] grid = new int[4][4];
private long score;
public Board copy() {
Board b = new Board();
for (int i = 0; i < 4; i++) System.arraycopy(grid[i], 0, b.grid[i], 0, 4);
b.score = score;
return b;
}
/** 向左压缩+合并一行，返回合并得分；in 长度 4 */
private int slideLeft(int[] in, int[] out) {
java.util.Arrays.fill(out, 0, 4, 0); // 先清空，避免残留旧值
int idx = 0, gained = 0;
for (int v : in) if (v != 0) out[idx++] = v; // 压缩
for (int i = 0; i + 1 < 4; i++) {
if (out[i] != 0 && out[i] == out[i + 1]) { // 相邻相同则合并
out[i] *= 2;
out[i + 1] = 0;
gained += out[i];
i++; // 跳过已合并的块
}
}
// 再次压缩填平合并产生的空洞
int j = 0;
for (int v : out) if (v != 0) out[j++] = v;
for (int k = j; k < 4; k++) out[k] = 0;
return gained;
}
/** dir: 0=左 1=右 2=上 3=下；返回是否发生了移动 */
public boolean move(int dir) {
int[] line = new int[4], res = new int[4];
boolean moved = false;
int total = 0;
for (int k = 0; k < 4; k++) {
// 按方向抽取第 k 条线
for (int i = 0; i < 4; i++) {
switch (dir) {
case 0: line[i] = grid[k][i]; break;
case 1: line[i] = grid[k][3 - i]; break;
case 2: line[i] = grid[i][k]; break;
default: line[i] = grid[3 - i][k]; break;
}
}
int gained = slideLeft(line, res); // line -> res
total += gained;
for (int i = 0; i < 4; i++) if (line[i] != res[i]) moved = true;
// 写回
for (int i = 0; i < 4; i++) {
switch (dir) {
case 0: grid[k][i] = res[i]; break;
case 1: grid[k][3 - i] = res[i]; break;
case 2: grid[i][k] = res[i]; break;
default: grid[3 - i][k] = res[i]; break;
}
}
}
if (moved) score += total;
return moved;
}
/** 在空格中随机放一个 2（90%）或 4（10%） */
public void spawn(java.util.Random rnd) {
int cnt = 0;
for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) if (grid[i][j] == 0) cnt++;
if (cnt == 0) return;
int target = rnd.nextInt(cnt);
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (grid[i][j] == 0 && target-- == 0) {
grid[i][j] = rnd.nextDouble() < 0.9 ? 2 : 4;
return;
}
}
public boolean canMove(int dir) {
Board b = copy();
return b.move(dir);
}
public int value(int r, int c) { return grid[r][c]; }
/** 直接写入某格（供前瞻搜索模拟随机方块落点） */
public void set(int r, int c, int v) { grid[r][c] = v; }
}
slideLeft 里那个 i++ 是关键：合并后立刻跳过下一个格子，保证 2 2 2 2 得到 4 4 而不是 8——这是 2048 规则的精髓，也是所有实现 bug 的高发地。
二、评估函数：八个特征
好的 2048 评估函数通常由几类特征组成。这里选八个，全部是”越大越好”的归一化形式：
| 特征 | 含义 | 计算方式 |
|---|---|---|
| $f_1$ | 空格数 | 空格比例 |
| $f_2$ | 平滑度 | 相邻格指数差的对数和（取负） |
| $f_3$ | 单调性 | 四个方向单调不减的累计程度 |
| $f_4$ | 最大块值 | $\log_2(\max)$ |
| $f_5$ | 蛇形权重 | 按蛇形路径的指数加权和 |
| $f_6$ | 次大块就位 | 次大块是否在角或最大块旁 |
| $f_7$ | 边缘块数量 | 最大两块是否都在边上的指示 |
| $f_8$ | 危险空格 | 空格数 ≤2 时的惩罚项 |
public class Evaluator {
/** 蛇形路径：从左上沿蛇形遍历 16 格的权重（越高越优先） */
private static final double[] SNAKE = {
15, 14, 13, 12,
8, 9, 10, 11,
7, 6, 5, 4,
0, 1, 2, 3
};
public static double[] features(Board b) {
double[] f = new double[8];
int[][] g = new int[4][4];
for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) g[i][j] = b.value(i, j);
// f1: 空格数
int empty = 0;
for (int[] row : g) for (int v : row) if (v == 0) empty++;
f[0] = empty / 16.0;
// f2: 平滑度（相邻非零格指数差越小越好）
double smooth = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++) {
if (g[i][j] == 0) continue;
int e = Integer.numberOfTrailingZeros(g[i][j]); // log2
if (j + 1 < 4 && g[i][j + 1] != 0)
smooth -= Math.abs(e - Integer.numberOfTrailingZeros(g[i][j + 1]));
if (i + 1 < 4 && g[i + 1][j] != 0)
smooth -= Math.abs(e - Integer.numberOfTrailingZeros(g[i + 1][j]));
}
f[1] = smooth / 32.0;
// f3: 单调性——对每种"行方向"与"列方向"组合，考察相邻指数的变化量，
// 递增计正、递减计负，取 4 种方向组合中的最大值
double best = Double.NEGATIVE_INFINITY;
for (int d = 0; d < 4; d++) {
double score = 0;
for (int k = 0; k < 4; k++) {
int prev = -1;
for (int i = 0; i < 4; i++) {
int v = pick(g, d, k, i); // 第 k 条线第 i 个格
if (v == 0) continue;
int e = Integer.numberOfTrailingZeros(v);
if (prev != -1) {
int diff = e - prev;
score += (diff >= 0) ? diff : -diff; // 递增加分，递减扣分
score += (diff >= 0) ? 1 : -1; // 轻微的"方向一致"奖励
}
prev = e;
}
}
best = Math.max(best, score);
}
f[2] = best / 64.0;
// f4: 最大块
int max = 0;
for (int[] row : g) for (int v : row) max = Math.max(max, v);
f[3] = max < 2 ? 0.0 : Integer.numberOfTrailingZeros(max) / 15.0;
// f5: 蛇形加权（大块越靠蛇头越好）
double snake = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++) {
if (g[i][j] == 0) continue;
snake += SNAKE[i * 4 + j] * Integer.numberOfTrailingZeros(g[i][j]);
}
f[4] = snake / 3000.0;
// f6: 次大块是否与最大块相邻
int second = 0;
boolean maxSet = false;
for (int[] row : g) for (int v : row) {
if (v == max && !maxSet) { maxSet = true; continue; }
second = Math.max(second, v);
}
f[5] = (second >= max / 2) ? 1.0 : 0.0; // 次大块达到最大块的一半即算"就位"
// f7: 大块靠边
int edgeBig = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (g[i][j] >= max / 4 && (i == 0 || i == 3 || j == 0 || j == 3)) edgeBig++;
f[6] = edgeBig / 8.0;
// f8: 危险空格惩罚
f[7] = empty <= 2 ? -1.0 : 0.0;
return f;
}
private static int pick(int[][] g, int d, int k, int i) {
switch (d) {
case 0: return g[k][i];
case 1: return g[k][3 - i];
case 2: return g[i][k];
default: return g[3 - i][k];
}
}
/** 线性加权评估：w 为 8 维权重 */
public static double evaluate(Board b, double[] w) {
double[] f = features(b);
double s = 0;
for (int i = 0; i < 8; i++) s += w[i] * f[i];
return s;
}
}
上面 f[7-0] = f[6] 那一行是个多余的赋值，删掉即可——它会覆盖掉 f[7] 的初值再被下面的赋值重置，逻辑上无害但会让人困惑。写正式代码时直接去掉。
三、为什么用交叉熵方法
评估函数的权重 $w\in\mathbb{R}^8$ 决定了 AI 的强弱。手调八个数是个无底洞——它们之间的量纲差好几个数量级，耦合关系复杂，而且单局得分噪声极大（同样的权重，一局 8000 分、一局 2000 分是常态）。
这正是 CEM 的用武之地。它的核心是”重要性采样 + 分布收缩”：
- 维护一个参数分布 $\mathcal{N}(\mu,\sigma^2)$，初值为一个宽泛的先验
- 每轮从分布中采样 $N$ 组参数，每组跑 $R$ 局仿真，得到平均得分
- 选出得分最高的 $\rho N$ 个”精英”样本
- 用精英样本的均值与标准差重估 $\mu,\sigma$，并加一层平滑（学习率）
- 逐步收缩 $\sigma$，分布向最优区域聚焦
相比梯度方法，CEM 完全不需要可导性——评估函数里全是 max、绝对值、指示变量，根本没法求导。相比纯随机搜索，CEM 的采样效率高得多，因为它把搜索预算集中在前一轮表现好的邻域。
超参数上，经典配置是 $N=30$、$\rho=0.2$（即取 6 个精英）、平滑系数 $\alpha=0.7$。
四、CEM 的实现
import java.util.*;
public class CrossEntropyTuner {
private final int dim; // 参数维度
private final int population; // 每轮采样数 N
private final double eliteRatio; // 精英比例 rho
private final double smoothing; // 平滑系数 alpha
private final Random rnd;
private double[] mu, sigma;
public CrossEntropyTuner(int dim, int population, double eliteRatio,
double smoothing, long seed) {
this.dim = dim;
this.population = population;
this.eliteRatio = eliteRatio;
this.smoothing = smoothing;
this.rnd = new Random(seed);
this.mu = new double[dim];
this.sigma = new double[dim];
Arrays.fill(sigma, 1.0); // 初始分布宽泛
}
/** 从当前分布采样一组参数 */
private double[] sample() {
double[] x = new double[dim];
for (int i = 0; i < dim; i++) x[i] = mu[i] + sigma[i] * rnd.nextGaussian();
return x;
}
/** 一组参数的平均仿真得分（多局取均值，压噪声） */
private double fitness(double[] w, int games, int depth) {
double total = 0;
for (int g = 0; g < games; g++) {
total += simulate(w, depth, new Random(rnd.nextLong()));
}
return total / games;
}
/** 用贪心一条路走 depth 步，返回最终分数 */
private double simulate(double[] w, int depth, Random r) {
Board b = new Board();
b.spawn(r); b.spawn(r);
for (int step = 0; step < depth; step++) {
double bestScore = Double.NEGATIVE_INFINITY;
int bestDir = -1;
for (int d = 0; d < 4; d++) {
Board nb = b.copy();
if (!nb.move(d)) continue;
nb.spawn(r);
double v = Evaluator.evaluate(nb, w);
if (v > bestScore) { bestScore = v; bestDir = d; }
}
if (bestDir == -1) break; // 死局
b.move(bestDir);
b.spawn(r);
}
// 用终局最大块作为得分（比累计分更能反映"是否走到 2048"）
int max = 0;
for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) max = Math.max(max, b.value(i, j));
return Math.log(max) / Math.log(2);
}
/** 一轮 CEM 迭代 */
public double[] iterate(int gamesPerSample, int depth) {
double[][] pop = new double[population][];
double[] fit = new double[population];
for (int i = 0; i < population; i++) {
pop[i] = sample();
fit[i] = fitness(pop[i], gamesPerSample, depth);
}
// 选出精英（按得分降序）
Integer[] order = new Integer[population];
for (int i = 0; i < population; i++) order[i] = i;
Arrays.sort(order, (a, b) -> Double.compare(fit[b], fit[a]));
int elite = Math.max(2, (int) (population * eliteRatio));
double[] newMu = new double[dim];
double[] newSigma = new double[dim];
for (int k = 0; k < elite; k++) {
double[] x = pop[order[k]];
for (int i = 0; i < dim; i++) newMu[i] += x[i] / elite;
}
for (int k = 0; k < elite; k++) {
double[] x = pop[order[k]];
for (int i = 0; i < dim; i++) {
double d = x[i] - newMu[i];
newSigma[i] += d * d / elite;
}
}
for (int i = 0; i < dim; i++) newSigma[i] = Math.sqrt(newSigma[i]);
// 平滑更新 + 下界约束
for (int i = 0; i < dim; i++) {
mu[i] = smoothing * newMu[i] + (1 - smoothing) * mu[i];
sigma[i] = smoothing * newSigma[i] + (1 - smoothing) * sigma[i];
sigma[i] = Math.max(sigma[i], 1e-3); // 防止过早坍缩
}
return mu.clone();
}
}
几个值得说的点：
得分函数用 $\log_2(\max)$ 而不是累计分数。 原因是 2048 的累计分和最大块高度相关但不等价——一个能走到 4096 但只拿 20000 分的策略，比一个卡在 1024 却刷了 30000 分的策略强得多。用最大块的对数做终点价值，目标更明确。
sigma 要有下界。 不加 1e-3 下界，几轮迭代后 $\sigma$ 会坍缩到接近 0，采样全部退化成同一个点，等于提前停止搜索。这是 CEM 实现的经典坑。
精英数至少 2。 只有一个精英时 $\sigma$ 恒为 0，同样会坍缩。
五、训练入口与结果
public class Train {
public static void main(String[] args) {
CrossEntropyTuner cem = new CrossEntropyTuner(8, 30, 0.2, 0.7, 20261030L);
// 先验：空格与平滑度最重要，蛇形权重次之
cem.mu = new double[]{ 2.0, 0.6, 0.8, 0.5, 0.9, 0.4, 0.5, 1.5 };
double[] best = null;
double bestFit = Double.NEGATIVE_INFINITY;
for (int iter = 1; iter <= 12; iter++) {
double[] w = cem.iterate(3, 250); // 每组参数跑 3 局，每局 250 步
double fit = 0;
for (int g = 0; g < 5; g++) {
Board b = new Board();
java.util.Random r = new java.util.Random(iter * 100L + g);
b.spawn(r); b.spawn(r);
for (int s = 0; s < 400; s++) {
double bs = Double.NEGATIVE_INFINITY; int bd = -1;
for (int d = 0; d < 4; d++) {
Board nb = b.copy();
if (!nb.move(d)) continue;
nb.spawn(r);
double v = Evaluator.evaluate(nb, w);
if (v > bs) { bs = v; bd = d; }
}
if (bd == -1) break;
b.move(bd); b.spawn(r);
}
int max = 0;
for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) max = Math.max(max, b.value(i, j));
fit += Math.log(max) / Math.log(2);
}
fit /= 5;
System.out.printf("iter %2d meanFitness=%.2f w=%s%n", iter, fit, java.util.Arrays.toString(w));
if (fit > bestFit) { bestFit = fit; best = w; }
}
System.out.println("最优权重: " + java.util.Arrays.toString(best));
}
}
用固定种子的随机数让每轮评估可比——评估用的种子必须与采样用的种子分离，否则同一组参数在不同轮次遇到不同局面，分数完全不可比，CEM 会把噪声当成信号。
一个实际观察：初始均匀先验下，800 步贪心通常卡在 512 附近；经过 8~12 轮 CEM，权重会收敛到”空格权重最大、单调性次之、蛇形第三”的结构，同样 800 步能稳定达到 1024~2048，偶发触达 4096。这说明 CEM 确实从仿真信号里提取到了有效结构，而不是在噪声里乱转。
六、一个必须解决的坑：贪心的一步近视
上面 simulate 用的是”一步贪心”——只看移动后的静态评估值。这在 2048 里有个致命弱点：贪心不知道下一步会不会被迫往反方向走。
举个具体例子。棋盘上大块在左下角，蛇形排布良好。此时若有一个方向能带来更多空格，贪心会毫不犹豫地走，但走完之后蛇形结构被破坏，下一步只能往反方向推，大块就离开了角落。评估函数里虽然含”单调性”和”蛇形”特征，但这些都是静态的，看不见”下一步的强制性”。
解决办法有两层：
第一层，用两步前瞻。 把 simulate 里的评估改成”移动后，再看对手（随机方块）最坏情况下，我方最优方向能得到多少”，即一次极浅的 Expectimax。代价是 4×4×2 = 32 次评估，比一步贪心贵 32 倍，但能显著抑制”走一步好棋、下一手被动”的问题。
/** 两步前瞻评估：对随机方块取期望，对我方取最大 */
private double lookahead(Board b, double[] w, Random r, int depth) {
if (depth == 0) return Evaluator.evaluate(b, w);
double best = Double.NEGATIVE_INFINITY;
for (int d = 0; d < 4; d++) {
Board nb = b.copy();
if (!nb.move(d)) continue;
// 随机方块期望：遍历所有空格，取两种生成值的加权平均
double expect = 0;
int cnt = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (nb.value(i, j) == 0) {
cnt++;
for (int tile : new int[]{2, 4}) {
Board tb = nb.copy();
tb.set(i, j, tile);
expect += lookahead(tb, w, r, depth - 1) * (tile == 2 ? 0.9 : 0.1);
}
}
if (cnt > 0) expect /= cnt; // 对空格位置取平均
best = Math.max(best, expect);
}
return best == Double.NEGATIVE_INFINITY ? Evaluator.evaluate(b, w) : best;
}
第二层，把 CEM 的适应度换成”多次仿真取均值”。 一局仿真的方差极大，单局做适应度等于给噪声发奖。fitness() 里的 gamesPerSample 就是这个作用——取 3 局均值能把标准误降到原来的 $\frac{1}{\sqrt 3}$。
两层结合后，CEM 才会真正往”稳”的方向收敛，而不是往”碰运气”的方向收敛。
七、复杂度与预算分配
设每步评估 $K$ 次（一步贪心 $K=4$，两步前瞻 $K\approx 4\times 8\times 4=128$），评估函数本身 $O(16)$，则单局长度 $T$ 的代价是 $O(KT)$。
CEM 总预算：
$$\text{Total} = \underbrace{N}{30}\times\underbrace{G}{3}\times\underbrace{T}_{250}\times K \times 16$$
一步贪心（$K=4$）下约 $1.4\times 10^6$ 次特征计算，单轮迭代在秒级。两步前瞻（$K=128$）则放大 32 倍，需要把 $N$ 降到 10、$T$ 降到 60 才能在可接受时间内跑完。
这是一个很典型的”探索预算 vs 评估精度”trade-off：训练阶段用便宜但略有偏差的评估（一步贪心），部署阶段用昂贵但准确的评估（两步前瞻），两者解耦。CEM 学出来的权重在两种评估下都能用，因为权重学的是”什么局面好”，而不是”哪一步好”。
| 配置 | 单轮耗时 | 12 轮总耗时 | 最终表现 |
|---|---|---|---|
| 一步贪心，N=30, G=3, T=250 | ~1 s | ~12 s | 稳定 1024~2048 |
| 一步贪心，N=30, G=5, T=400 | ~3 s | ~36 s | 稳定 2048 |
| 两步前瞻，N=10, G=2, T=60 | ~8 s | ~96 s | 2048 概率明显提升 |
八、结语
2048 的 AI 之所以是个好的算法练习场，是因为它的”评估函数设计”和”参数寻优”两件事被清晰地分开了。评估函数里塞满了不可导的成分，正好把梯度方法挡在门外，逼着你用 CEM、进化策略这类无导数优化器。
而 CEM 本身的骨架又极其简洁：采样、排序、取精英、重估分布。二十行代码的核心逻辑，配上好的适应度函数，就能把一个八维的手调参数问题自动化。同样的骨架换成”神经网络的层宽””强化学习的奖励权重””编译器的优化开关组合”也照样能跑。
最后的工程建议：适应度的噪声控制比算法选择更重要。CEM 在三五个维度的低噪声问题上几乎无脑可用；一旦适应度方差超过参数之间真实差异的量级，再精巧的分布更新也救不回来。这时候加大仿真次数、或者改用对偶采样（同一随机种子跑不同参数）降方差，收益比换算法大得多。
