2048 自动化优化：从启发式搜索到 Expectimax 的公式推导与实例验算

这篇文章不是 2048 的通关攻略，而是一份“算法论文式”的拆解：先用一个直观局面说明问题，再给出严格的问题建模与 Bellman 方程，推导有限深度 Expectimax 的递归与最优性证明，最后用项目里的真实评估函数逐步验算一个 2×2 棋盘。

如果你还没玩过我在 Playground 里做的版本，可以先打开 2048 霓光 · 合成挑战，点“AI 托管”看它自己玩。想亲手观察搜索树，可以打开 2048 搜索树实验室。

1 引言：一个看似简单、实则需要搜索的问题

2048 的规则只有四条：

1. 每次向上下左右滑动，所有方块整体移动；
2. 相同数字相邻时合并为两倍，得分增加合并后的数值；
3. 每次移动后，系统在空位随机生成方块，90% 概率生成 2，10% 概率生成 4；
4. 棋盘无法再移动时游戏结束。

规则简单，但“选哪个方向”并不简单，因为随机生成让未来不是一条确定的路径，而是一棵概率树。先看一个直观的例子。

下面两个 2×2 局面包含完全相同的方块：一个 2、一个 4、一个 8，以及一个空位：

局面 A        局面 B
8   4         4   8
2   ·         2   ·

两个局面都无法立即合并，得分都是 0。但绝大多数人会认为 B 更好：8 锁在角落，4 贴着它，2 再贴着 4，数字沿边缘“阶梯式下降”，未来更容易连续合并。问题是：这种直觉能不能被量化？

用我们后面会推导的启发式函数 $h(s)$ 计算，两个局面的得分分别是：

$$h(A)=12.07,\qquad h(B)=12.1533$$

B 只高 0.08 左右，但足够让搜索算法在无数相似局面中稳定地偏向“结构更好”的一方。本文要解释的，正是这个数字是怎么来的、为什么要这样算、以及它如何被放进一棵搜索树里。

2 问题建模：从游戏规则到 Bellman 方程

先把 2048 抽象成标准的随机决策问题。记：

• $s$：一个局面，由棋盘上每个格子的数值或空位组成；
• $A(s)$：局面 $s$ 下的合法方向集合；
• $a\in A(s)$：一次滑动；
• $s'$：执行 $a$ 并随机生成新方块后的局面；
• $P(s'\mid s,a)$：从 $(s,a)$ 转移到 $s'$ 的概率；
• $r(s,a)$：本次滑动合并产生的得分；
• $T$：游戏结束时刻。

一个策略 $\pi$ 告诉 AI 在每个局面该选哪个方向。策略 $\pi$ 在初始局面 $s$ 上的期望总分为：

$$V^\pi(s)=\mathbb{E}\left[\sum_{t=0}^{T-1} r(S_t,A_t)\;\middle|\;S_0=s,\;\pi\right]$$

最优策略对应的最优价值函数为：

$$V^*(s)=\max_{\pi} V^\pi(s)$$

对最优价值函数做一步展开，就得到 Bellman 方程：

$$V^*(s)=\max_{a\in A(s)}\sum_{s'} P(s'\mid s,a)\left[r(s,a)+V^*(s')\right]\tag{1}$$

它的推导只有三步：

1. 当前局面 $s$ 下先选一个动作 $a$；
2. 动作执行后，系统以概率 $P(s'\mid s,a)$ 进入 $s'$，并立刻产生奖励 $r(s,a)$；
3. 从 $s'$ 开始，如果后续仍按最优策略走，期望收益就是 $V^*(s')$。

由于奖励是线性相加的，期望也可以线性拆开，所以“动作 $a$ 的总期望收益”是：

$$Q(s,a)=\sum_{s'} P(s'\mid s,a)\left[r(s,a)+V^*(s')\right]$$

而最优动作当然要选 $Q(s,a)$ 最大的那个，于是得到式 (1)。

式 (1) 是理论上的精确解，但它要求遍历直到终局的整棵状态树。2048 的树有多大？下一节算给你看。

3 启发式搜索：为什么必须截断与近似

先估计 2048 搜索树的分支因子。每层 MAX 节点最多有 4 个合法方向；每个方向执行后，假设棋盘上还有 $E$ 个空位，那么每个空位都有“生成 2”和“生成 4”两种可能。因此一次“玩家移动 + 系统生成”的完整循环，最多有：

$$B_{\max}=4\times 2E\tag{2}$$

当 $E=10$ 时，$B_{\max}=80$。连续看 $d$ 个这样的循环，节点数上界约为：

$$B_{\max}^{d}=80^{d}$$

具体数字：

循环数 $d$	节点数上界	直观大小
1	80	一页纸
2	6,400	一个班级
3	512,000	一座小城
4	40,960,000	四千万

完整搜到终局是完全不现实的。实用 AI 的做法是：只向下搜索有限深度 $d$，在叶子处用一个经验评估函数 $h(s)$ 代替真实的 $V^*(s)$，然后按同样的递归关系向上回溯。这就是启发式搜索。

更准确地说，我们定义有限深度的价值函数：

$$\hat V_0(s)=h(s)$$ $$\hat V_d(s)=\max_{a\in A(s)}\sum_{s'} P(s'\mid s,a)\left[r(s,a)+\hat V_{d-1}(s')\right]\tag{3}$$

整个决策流水线如下：

这里的核心问题是：$h(s)$ 应该怎么设计？式 (3) 为什么是对的？下面分别回答。

4 从 Minimax 到 Expectimax：随机性应该取期望，而不是取最坏

最早的一批 2048 AI 借用国际象棋的 Minimax，把“系统生成方块”当成一个故意使坏的对手。若把一次生成可能到达的局面记为 $s'_1,\dots,s'_n$，Minimax 在环境节点上计算：

$$V_{\min}(s)=\min_i V(s'_i)$$

但 2048 的随机生成并不是对手。它只是按固定概率分布抽样。对任意一组取值，都有一个基本不等式：

$$\min_i V(s'_i)\;\le\;\sum_i P_i V(s'_i)\;\le\;\max_i V(s'_i)$$

所以 Minimax 给出的是期望收益的下界，会系统性地低估“运气好”的分支。Expectimax 则直接按概率取期望：

$$V_{\exp}(s)=\sum_i P_i V(s'_i)$$

其中 $P_i=0.9$ 对应生成 2，$P_i=0.1$ 对应生成 4。于是完整的 Expectimax 搜索树是 MAX 层和 EXP 层交替：

用第 8 节的数字可以直观看到区别。某个动作的两个生成结果是 $9.1667$ 和 $9.9033$，那么：

$$\text{Expectimax}=0.9\times 9.1667+0.1\times 9.9033=9.2403$$ $$\text{Minimax}=\min(9.1667,\;9.9033)=9.1667$$

Expectimax 不会因为“最坏情况”而放弃一个大概率很好、小概率一般的动作。这也是为什么 nneonneo 在 Stack Overflow 上明确指出：Expectimax 不像 Minimax 那样能被 Alpha-beta 剪枝，只能通过概率阈值等方式剪掉极不可能的分支。

5 启发式评估函数：公式是怎么构造出来的

本节给出本项目实际使用的启发式函数。它的每一个分量都对应一种可解释的结构直觉，最后用线性加权组合成一个标量。

5.1 记号

设棋盘为 $n\times n$，$v_i$ 表示格子 $i$ 上的数值，空位记为 0。用 $\langle i,j\rangle$ 表示一对相邻格子。

5.2 五个分量

空位数。空位是“容错空间”，越多越不容易立刻死亡：

$$E(s)=\sum_{i=1}^{n^2}\mathbf{1}[v_i=0]\tag{4}$$

平滑度。两个相邻非空方块数值差越小，未来越容易通过“靠近—合并”形成大数。为了不让大数之间的绝对差主导惩罚，我们用对数归一化：

$$S(s)=\sum_{\langle i,j\rangle}\frac{|v_i-v_j|}{\log_2 v_i+\log_2 v_j}\tag{5}$$

单调性。对一行 $x_1,\dots,x_n$，先定义“从左到右的逆序惩罚”：

$$L(x)=\sum_{i=2}^{n}\max(0,\;x_i-x_{i-1})\tag{6}$$

单调性要求方向既可以是从左到右递减，也可以是从右到左递减，因此取两个方向里较小的那个：

$$M_{\text{line}}(x)=\min\bigl(L(x),\;L(x^{\text{rev}})\bigr)$$

整个棋盘的单调性惩罚是每一行和每一列的 $M_{\text{line}}$ 之和。

最大方块贴角。最大数放在角落时，它的活动空间最可控；放在边缘次之；放在内部最差：

$$C(s)=v_{\max}\cdot\begin{cases}1.2,& v_{\max}\text{ 在角落}\\[2pt]0.9,& v_{\max}\text{ 在边缘}\\[2pt]0.5,& v_{\max}\text{ 在内部}\end{cases}\tag{7}$$

合并潜力。相邻两个等值方块是“还没兑现的合并”，应当给予正向激励：

$$M(s)=\sum_{\langle i,j\rangle} v_i\cdot\mathbf{1}[v_i=v_j]\tag{8}$$

5.3 总公式

把五个分量线性加权：

$$h(s)=2.7E(s)-0.1S(s)-1.0\sum M_{\text{line}}(s)+1.0C(s)+0.15M(s)\tag{9}$$

为什么是这些权重？两个来源：一是人工经验，二是用 CMA-ES 这类元优化算法在大量自对局中自动搜索权重。nneonneo 的 AI 正是靠加入“单调性惩罚 + 合并潜力”并把权重交给 CMA-ES 优化，才把 16384 达成率从约 13% 提升到 90% 以上。

5.4 这些公式的“推导动机”

严格说，式 (9) 不是从游戏规则“证明”出来的唯一最优评估函数，因为 2048 没有已知的封闭解。但它可以从一个关键事实推导出动机：

要合成 $2^{k+1}$，必须有两个相邻的 $2^k$；每发生一次合并，得分增加 $2^{k+1}$。

因此，未来得分的潜力可以分解为：

1. 相邻等值方块是否已经就位 → 式 (8) 直接奖励；
2. 数值接近的方块是否靠近 → 式 (5) 用对数距离惩罚；
3. 大数之间是否被小数隔开 → 式 (6) 惩罚逆序与“阻塞”；
4. 有没有足够的空位让方块移动 → 式 (4)；
5. 最大数是否在稳定的角落坐标系里 → 式 (7)。

这五个分量分别回答“能不能合并”“好不好合并”“会不会被卡住”“有没有空间”“锚点稳不稳”。它们不是玄学，而是把人类策略转写成可微、可加、可搜索的数值。

6 有限深度 Expectimax 的递归推导与最优性证明

现在证明第 3 节给出的递归式 (3) 确实是“有限视野下的最优”。

先引入一个算子。对任意叶子函数 $h$，定义：

$$(\mathcal{T}V)(s)=\max_{a\in A(s)}\sum_{s'}P(s'\mid s,a)\left[r(s,a)+V(s')\right]\tag{10}$$

于是式 (3) 可以写成：

$$\hat V_d=\mathcal{T}^{d}h$$

即从 $h$ 开始，反复作用 $d$ 次 Bellman 算子。

引理（单调性）：如果 $V\le W$，那么 $\mathcal{T}V\le \mathcal{T}W$。

证明：对固定的 $a$，概率加权和是单调的；对 $a$ 取最大值也是单调的。因此 Bellman 算子保持偏序。$\blacksquare$

定理（有限深度最优性）：设 $h$ 是叶子处的终止收益函数。对任意 $d\ge 0$，$\hat V_d=\mathcal{T}^d h$ 是所有“最多走 $d$ 步玩家动作，然后按 $h$ 结算”的策略中，期望收益的最大值；并且每一步按

$$a_d(s)=\arg\max_{a\in A(s)}\sum_{s'}P(s'\mid s,a)\left[r(s,a)+\hat V_{d-1}(s')\right]\tag{11}$$

选取动作，就能达到这个最大值。

证明（对 $d$ 归纳）：

• 当 $d=0$：没有剩余步数，策略只能直接拿 $h(s)$，所以 $\hat V_0=h$ 显然是最优的。
• 假设 $d-1$ 时成立。在状态 $s$，第一步若选 $a$，则立即得到 $r(s,a)$，随后以概率 $P(s'\mid s,a)$ 进入 $s'$。从 $s'$ 开始还剩 $d-1$ 步，由归纳假设，最优后续收益是 $\hat V_{d-1}(s')$。于是“先走 $a$、再最优续走”的期望是：

$$\sum_{s'}P(s'\mid s,a)\left[r(s,a)+\hat V_{d-1}(s')\right]$$

任意策略的第一步都只能选某个 $a$，所以它的总价值不可能超过上式对所有 $a$ 取最大值，也就是 $\hat V_d(s)$；而按式 (11) 选 $a$ 能达到该上界。归纳完成。$\blacksquare$

推导路线可以概括为下面这张图：

需要诚实说明一点：$\hat V_d$ 是“以 $h$ 为终止收益”的有限深度最优，不是完整 2048 的全局最优。$h$ 与真实 $V^*$ 之间的误差会通过递归向后传播；但深度越大、$h$ 越准，$\hat V_d$ 就越接近 $V^*$。这正是“搜索深度决定上限，评估函数决定近似质量”的原因。

7 伪代码

把上面的递归写成代码，核心只有两个函数：MAX 层负责取最大值，EXP 层负责按概率取期望。

function expectimax(grid, depth):
    if depth <= 0:
        return evaluate(grid)

    children = []
    for dir in [上, 下, 左, 右]:
        if move(grid, dir) 合法:
            children.add({ dir, grid: movedGrid, h: evaluate(movedGrid) })

    if children 为空:
        return evaluate(grid)

    children.sort(按 h 降序)
    best = -∞
    for child in children[0..k):          # Top-K 剪枝
        best = max(best, chanceEval(child.grid, depth - 1))
    return best

function chanceEval(grid, depth):
    if depth <= 0:
        return evaluate(grid)

    empties = 随机采样(空位列表, sample)   # 空位采样
    total = 0
    for cell in empties:
        total += 0.9 * expectimax(spawn(grid, cell, 2), depth - 1)
        total += 0.1 * expectimax(spawn(grid, cell, 4), depth - 1)
    return total / len(empties)

注意 chanceEval 里的期望计算：

$$\hat V_{\text{exp}}=\frac{1}{|C|}\sum_{c\in C}\Bigl(0.9\,\hat V_{\text{max}}(s'_{c,2})+0.1\,\hat V_{\text{max}}(s'_{c,4})\Bigr)$$

其中 $C$ 是被采样到的空位集合。如果 $|C|$ 等于全部空位数，这就是精确期望；如果 $|C|$ 小于全部空位数，则是无偏采样估计。

8 数字验算：一个 2×2 棋盘完整走一遍

理论讲得再多，不如拿真实数字算一遍。下面用项目里实际使用的 evaluateGrid 函数，逐步验算一个 2×2 局面。

初始局面：

$$s_0=\begin{matrix}2&4\\[2pt]\cdot&8\end{matrix}$$

其中 $\cdot$ 表示空位。先算 $s_0$ 自身的启发式分量：

分量	原始值	权重	贡献
空位数 $E$	1	$+2.7$	$+2.7000$
平滑度 $S$	1.4667	$-0.1$	$-0.1467$
单调性 $\sum M_{\text{line}}$	0	$-1.0$	$0$
最大贴角 $C$	9.6	$+1.0$	$+9.6000$
合并潜力 $M$	0	$+0.15$	$0$
合计 $h(s_0)$			12.1533

这个局面只有“向下”和“向左”两个合法方向（上、右不会改变棋盘）。

8.1 选择“向下”

执行向下后，棋盘变为：

$$\begin{matrix}\cdot&4\\[2pt]2&8\end{matrix}$$

空位只有一个，位于 $(0,0)$。如果生成 2：

$$\begin{matrix}2&4\\[2pt]2&8\end{matrix},\qquad h=9.6033$$

如果生成 4：

$$\begin{matrix}4&4\\[2pt]2&8\end{matrix},\qquad h=9.9033$$

按 90%/10% 取期望：

$$V_{\text{down}}=0.9\times 9.6033+0.1\times 9.9033=9.6333$$

8.2 选择“向左”

执行向左后，棋盘变为：

$$\begin{matrix}2&4\\[2pt]8&\cdot\end{matrix}$$

空位在 $(1,1)$。生成 2：

$$\begin{matrix}2&4\\[2pt]8&2\end{matrix},\qquad h=9.1667$$

生成 4：

$$\begin{matrix}2&4\\[2pt]8&4\end{matrix},\qquad h=9.9033$$

期望值：

$$V_{\text{left}}=0.9\times 9.1667+0.1\times 9.9033=9.2403$$

8.3 决策

由于 $9.6333>9.2403$，一层 Expectimax 会选择 向下。两个动作都没有立即得分，但“向下”把 8 放到了角落、把 2 和 4 排在了同一列，结构上明显更顺。

这个例子也回应了第 1 节的直观案例：启发式函数把“结构好不好”变成了可比较的数字，而搜索把这些数字放进概率树里做期望。

9 剪枝与采样：公式背后的工程数学

即使有了式 (3)，直接展开仍然太慢。工程上还有四类压缩。

9.1 Top-K 候选裁剪

MAX 层本来要展开最多 4 个方向。改为只保留启发式初筛最高的 $K$ 个方向后，搜索树每一层的宽度从 $\le 4$ 降为 $K$。代价是有可能漏掉“初看一般、深看很强”的走法。

9.2 空位采样

EXP 层空位很多时，随机抽 $n$ 个空位代替全部 $E$ 个空位。设每个空位 $c$ 的条件期望为：

$$q_c=0.9\,\hat V(s'_{c,2})+0.1\,\hat V(s'_{c,4})$$

那么完整期望是 $\frac{1}{E}\sum_c q_c$，采样估计是 $\frac{1}{n}\sum_{c\in C}q_c$。只要采样是均匀的，估计就是无偏的：

$$\mathbb{E}\left[\frac{1}{n}\sum_{c\in C}q_c\right]=\frac{1}{E}\sum_{c=1}^{E}q_c$$

但方差会随 $n$ 减小而增大，所以采样数量是“速度 vs 稳定性”的权衡。

9.3 累计概率阈值

一条搜索路径的累计概率等于沿途所有生成事件的概率乘积：

$$p_{\text{path}}=\prod_{t}P(\text{spawn}_t)$$

例如连续出现 6 个 4 的概率是 $0.1^6=10^{-6}$。当 $p_{\text{path}}$ 低于阈值 $\epsilon$ 时直接停止并返回当前启发值，这类分支对期望的贡献极小。

9.4 底层优化

最后是“把搜索变快”的工程层：64 位位板编码、65536 大小的移动/评分查找表、转置表、迭代加深、Web Worker / WebAssembly 并行。nneonneo 的 C++ 实现用这些手段达到每秒搜索上千万个局面，才在 100ms 内完成 4~8 个玩家决策的深度。

10 实验结果：搜索深度与评估质量

10.1 外部经典数据

nneonneo 在 Stack Overflow 回答中报告过 100 局测试数据：

指标	结果
至少合成 2048	100%
至少合成 4096	100%
至少合成 8192	100%
至少合成 16384	94%
至少合成 32768	36%
中位分数	387222

腾讯云文章里的 WebAssembly 并行版（深度 7）则是：8192 达成率 98%、16384 达成率 85%、32768 达成率 12%。

10.2 本博客 TS 实现的实测

我也用项目里的 ai2048.ts 在 Node 里跑了三组真实对局：

配置	局数	中位分数	1024+	2048+	4096+
贪心基线（只看一步）	100	6820	9%	0%	0%
深度 4 + 采样 2 + Top-1	100	6064	4%	0%	0%
深度 6 + 采样 3 + Top-2	20	15760	75%	25%	10%

两个结论：只看一步很难突破 1024；深度 6 后 2048 开始稳定出现。同时，深度 4 + 采样 2 + Top-1 反而略低于贪心，说明过度剪枝会让期望估计带上噪声。搜索强度不是“深度越大就一定越强”，而是评估质量、搜索深度、剪枝精度三者的平衡。

11 验算脚本

第 8 节的所有数字都可以用下面这段 Node 脚本复现。它直接调用博客 2048 游戏使用的同一套 moveGrid 和 evaluateGrid：

import { moveGrid, evaluateGrid } from './src/scripts/ai2048.ts';

const s0 = [[2, 4], [null, 8]];

for (const dir of ['up', 'down', 'left', 'right']) {
  const r = moveGrid(s0, dir);
  if (!r.moved) continue;

  const cells = [];
  for (let i = 0; i < 2; i++) {
    for (let j = 0; j < 2; j++) {
      if (r.grid[i][j] == null) cells.push([i, j]);
    }
  }

  let total = 0;
  for (const [i, j] of cells) {
    const h2 = evaluateGrid(withTile(r.grid, i, j, 2));
    const h4 = evaluateGrid(withTile(r.grid, i, j, 4));
    total += 0.9 * h2 + 0.1 * h4;
  }

  console.log(dir, (total / cells.length).toFixed(4));
}

function withTile(grid, i, j, v) {
  const copy = grid.map((row) => row.slice());
  copy[i][j] = v;
  return copy;
}

12 结论

2048 自动化优化的完整逻辑链是：

1. 建模：2048 是随机环境下的序列决策问题，最优价值满足 Bellman 方程 $V^*=\max_a\mathbb{E}[r+V^*]$；
2. 截断：状态树太大，用深度 $d$ 截断，叶子用启发式 $h$ 代替真实价值；
3. 搜索：MAX 层取最大值、EXP 层按 90%/10% 取期望，得到有限深度最优的 $\hat V_d$；
4. 评估：空位、平滑度、单调性、贴角、合并潜力五个分量把“结构好坏”变成可计算数字；
5. 工程化：Top-K、空位采样、概率阈值、位板、转置表、并行化决定 AI 能看多深、算多快。

这套框架不止适用于 2048。任何“规则简单、随机性强、状态爆炸”的决策问题，都可以套用：建模 → 启发式评估 → 有限深度搜索 → 剪枝采样 → 底层加速。

如果你想亲手验证，可以在 2048 搜索树实验室 里拖拽深度、Top-K 和采样数，观察搜索树如何展开与剪枝；也可以在 2048 游戏 里打开 AI 托管看它实际决策。

参考资料

1. What is the optimal algorithm for the game 2048? nneonneo · Stack Overflow
2. 2048-ai: AI for the 2048 game nneonneo · GitHub
3. 2048 Solver — course report Columbia University · Fall 2024
4. 2048-AI 程序算法分析 Leo_wl · 博客园
5. 对弈类游戏的人工智能(5)——2048 游戏 AI 的解读 mumuxinfei · 博客园
6. 再探游戏《2048》——AI 方法——缘起、缘灭（3）——游戏 AI 解法设计篇 xyz · 博客园
7. 2048 游戏 AI 实现，轻松达到 8192 井九 · 腾讯云开发者社区