俄罗斯方块 AI 进化史：从贪心落子到束搜索、MCTS 与深度强化学习

这篇文章不讲“怎么玩俄罗斯方块”，而是把俄罗斯方块当作一个标准的人工智能试验场，完整拆解一条算法进化路线：从最朴素的“普通匹配/贪心落子”，到四维启发式评分、一步前瞻、全路径状态搜索、多步束搜索、蒙特卡洛树搜索，再到深度强化学习。每一代算法都会讲清楚它解决什么问题、怎么实现、复杂度如何、瓶颈在哪，并用 SVG 示意图把思路画出来。文末还有一组“分步骤”的 SVG 图解，把最难理解的两个部分——侧滑插入和束搜索——逐步拆开。

如果你还没玩过我在 Playground 里的版本，可以先打开 俄罗斯方块 · 霓虹堆叠，点「AI 托管」看它自己玩；再看这篇文章，很多概念会立刻落到实处。

0 引言：为什么俄罗斯方块是 AI 的完美试验场

先花 300 字把问题本身定义清楚，后面所有算法都建立在同一个抽象上。

俄罗斯方块的规则人尽皆知：10 列 × 20 行的井；七种方块 I、O、T、S、Z、J、L；方块从顶部出现，可以左右移动、旋转、软降、硬降；落定后锁定，一行填满就消除；游戏堆到顶部就结束。我们使用的版本还有一个关键规则——7 袋发牌（7-bag）：系统把七种方块洗成一个袋子，按顺序逐一出牌，发完一袋再洗下一袋。这意味着 AI 永远知道接下来若干块是什么，这在后面会成为“序列决策”算法的巨大优势。

把游戏形式化：

• 状态 $s$：当前棋盘（每个格子的占用情况）+ 当前活动方块 + 下一块队列；
• 动作 $a$：对一个方块，所有“旋转 + 横向移动 + 硬降”组合出来的落点，本质上是一个四元组（方块类型、旋转方向、目标列、插入路径）；
• 转移 $s' = T(s, a)$：方块落定、消行、弹出下一块；
• 收益 $r$：消行数、得分、生存时间，或者三者组合；
• 目标：让期望收益最大——通常是“活得最久、消得最多”。

一句话：俄罗斯方块 AI = 在每个状态选择一个动作，使得未来收益最大。 所有算法的差异，只在于“未来”被看到了多深、被建模得有多准。

下面按“代数”展开这条进化路线。每一代不是简单替换，而是在上一代的基础上补上它最缺的那块拼图。

1 第 0 代：普通匹配与贪心策略

“普通匹配”是很多入门 AI 的第一版：不考虑未来，只看当前这一块，用一条很简单的规则选落点。听起来很幼稚，但它是理解后面所有算法的地基——任何高级算法，最终都要回答同一个问题：这一块放在哪里？

1.1 随机落子：最朴素的基线

最原始的版本是随机：从所有合法落点里随便挑一个。

function randomMove(piece, board) {
  const moves = enumeratePlacements(piece, board); // 所有旋转×列
  return moves[Math.floor(Math.random() * moves.length)];
}

它的行为完全不可控：可能一直堆中间、可能留下大量空洞、可能把井口封死。但它有一个非常重要的价值——基线。任何后续算法的效果，都要先跟“随机落子”比：随机平均能活几十行，启发式能活几百行，束搜索能活上千行，差距一目了然。

1.2 单目标贪心：最矮列、最高列、消行优先

第一代“智能”通常是一句大白话：“把方块放到能让局面看起来最舒服的地方。”什么算舒服？最常见的三种定义：

1. 最矮列贪心：把方块放在最终列高最低的位置。它的动机是“别把某根柱子堆太高”，因为顶到天花板就死了。
2. 最高列贪心：把方块放在现有最高柱子的旁边，动机是“填平深坑”，让表面更整齐。
3. 消行优先贪心：优先选择能立即消行的落点，消不了再退而求其次。

这三种策略各有一个致命伤：

• 最矮列贪心会疯狂地把方块铺到最矮的地方，结果整张棋盘“平原化”，永远凑不齐一行；
• 最高列贪心反过来，会把所有方块都堆到同一根柱子附近，制造一座高塔，死得最快；
• 消行优先贪心只看“这一手消没消”，经常为了消一行把棋盘挖出一个永远填不上的洞。

更本质的问题在于：这些规则都只看“当前这手棋造成的一个数字”，而这个数字与“未来能不能消行”之间没有可靠的因果关系。 最矮列可能在造一个巨大的凹槽，最高列可能在制造悬崖，消行可能只是在拆东墙补西墙。

1.3 普通匹配的代码形态

所谓“普通匹配”，在工程上通常长这样：先枚举所有合法落点，再给每个落点算一个目标值，最后选目标值最大的。它已经具备高级 AI 的骨架——枚举 + 评估 + 选择——只是评估函数太粗糙：

function greedyPlacement(piece, board) {
  let best = null, bestScore = -Infinity;
  for (const move of enumeratePlacements(piece, board)) {
    const next = simulate(board, move);
    const score = -next.columnHeights.max(); // 例如：最高列越低越好
    if (score > bestScore) { bestScore = score; best = move; }
  }
  return best;
}

这段代码之后会反复出现：高级算法改的从来不是这个框架，而是 simulate 之后的评分函数，以及“评分时看到几步棋”。

2 第 1 代：四维启发式评分

既然单个数字不可靠，那就把“局面的健康程度”拆成多个维度，每个维度都能解释，再用加权和把它们合并。这就是四维启发式（El-Tetris 一系的核心思想）。

2.1 四个特征的定义

假设我们拿到了一个落子后的棋盘，可以统计四个量：

① 总高度（Aggregate Height）

每一列的高度 = 从底部到该列最高格子的距离。总高度就是 10 列高度之和：

$$H(s) = \sum_{c=0}^{9} h_c$$

总高度越低，说明离天花板越远，生存空间越大。但它不能只看总量：10 根 5 格高的柱子（H=50）和 1 根 50 格高的柱子（H=50）同样是 50，危险程度完全不同，所以还需要平整度。

② 空洞（Holes）

一个空格如果上方至少有一个方块，就称为空洞：

$$\text{holes}(s) = \sum_{c}\ |\{r : s[r][c]=\text{空} \land \exists r'<r,\ s[r'][c]=\text{块}\}|$$

空洞是“永远填不回去的坑”。因为方块只能从上方落下，被盖住的洞除非整行消掉，否则无法填补。空洞越多，棋盘越容易迅速恶化。

③ 平整度（Bumpiness）

相邻两列的高度差绝对值之和：

$$B(s) = \sum_{c=0}^{8} |h_c - h_{c+1}|$$

平整度描述“表面是否崎岖”。崎岖的表面会制造两种后果：低洼处被上面落下的方块盖成洞，高处又让方块难以滑入低处。

④ 消行数（Complete Lines）

当前棋盘里已经满行的行数。这是唯一一个“直接收益”特征——消行是俄罗斯方块唯一真正的正反馈。

2.2 线性评分与权重直觉

把四个特征加权求和：

$$h(s) = w_H \cdot H(s) + w_{\text{holes}} \cdot \text{holes}(s) + w_B \cdot B(s) + w_L \cdot \text{lines}(s)$$

一组被广泛使用的权重（El-Tetris 系）大约是：

特征	权重	直觉
总高度	−0.51	高度越高，离死亡越近
空洞	−0.36	一个洞是一个永久伤口
平整度	−0.18	表面越崎岖，越容易造洞
消行	+0.76	消行是唯一直接收益

注意一个细节：空洞的权重比平整度更狠，因为洞几乎不可逆；平整度的惩罚比高度轻，因为崎岖还有机会被后面的方块抹平。这些数字不是拍脑袋——后面会讲到它们可以用遗传算法自动搜索。

2.3 从“一个落点”到“枚举所有落点”

有了评分函数，第 1 代 AI 就完整了：

1. 枚举当前方块的所有旋转（I、O、T、S、Z、J、L 分别有 4/1/4/4/4/4/4 个旋转态）；
2. 对每个旋转，枚举所有可以落定的列；
3. 把方块放上去，模拟消行，得到新棋盘；
4. 用 $h(s')$ 给每个落点评分；
5. 选分数最高的落点执行。

它的复杂度是 $O(\text{旋转数} \times \text{列数} \times \text{棋盘格子数})$，大约 $O(4 \times 10 \times 200)$，在任何设备上都是微秒级。这一代已经能稳定活过几百行，远超人类初学者。

但它仍然有一个根本缺陷：评分只看“放完这一块之后的静态局面”，完全不知道下一块是什么。 一个现在看起来平整的落点，可能让下一块 T 无处可去；一个现在看起来有点崎岖的落点，可能刚好给下一块 I 留出四连消的井。这个缺陷，正是第 2 代要解决的。

3 第 2 代：一步前瞻（El-Tetris 的核心思想）

第 1 代 AI 的评分只看“当前块放完之后”的静态局面。第 2 代只加了一件事：把下一块也放进评分里。

3.1 想法：与其评估局面，不如评估“两步之后的局面”

俄罗斯方块有一个特性：当前块落下后，下一块立刻从顶部出现。所以“当前这块放哪”的价值，很大程度上取决于“下一块能不能接得住”。一个聪明的落点，应该让下一块有好的去处；一个糟糕的落点，会让下一块只能制造空洞。

一步前瞻的做法是：对当前块的每个候选落点 $p_1$，我们不直接给“放完 $p_1$ 的局面”打分，而是继续枚举下一块的所有候选落点 $p_2$，把“放完 $p_2$ 的局面”中最优的那个分数，作为 $p_1$ 的分数：

$$\text{score}(p_1) = \max_{p_2 \in \text{moves}(\text{next}, s')} h(s'')$$

其中 $s'$ 是放完当前块后的局面，$s''$ 是继续放完下一块后的局面。也就是说：当前块的每一步，都要预演一遍下一块的最优回应。

3.2 算法骨架

function onePlyLookahead(piece, nextPiece, board) {
  let best = null, bestScore = -Infinity;
  for (const m1 of enumeratePlacements(piece, board)) {
    const board1 = simulate(board, m1);
    let score = -Infinity;
    for (const m2 of enumeratePlacements(nextPiece, board1)) {
      const board2 = simulate(board1, m2);
      score = Math.max(score, evaluate(board2)); // 只看下一步最优
    }
    if (score > bestScore) { bestScore = score; best = m1; }
  }
  return best;
}

外层循环是“当前块的落点”，内层循环是“下一块的最优应对”。复杂度大约从 $O(40)$ 次模拟涨到 $O(40 \times 40)=O(1600)$ 次模拟。每次模拟只需要拷贝 200 个格子的棋盘并做一次消行检查，毫秒级完成，完全可以在浏览器里实时运行。

3.3 这一步为什么这么强

El-Tetris 使用的正是“四维启发式 + 1 步前瞻”。它的公开数据能稳定存活 100 行以上，在简单规则下表现远超绝大多数人类玩家。原因可以这样理解：

一步前瞻相当于让 AI 记住了“下一块是什么”，所以它会在当前这步主动为下一块“留位置”。比如下一块是 I，AI 就会倾向于在当前落点中保留一条竖直的井；下一块是 S/Z，AI 就会避免把边缘堆成恰好卡死 S/Z 的形状。

3.4 局限

一步前瞻仍然看不到“下下块”。真正的高手会做“三块规划”：现在留的井，可能是给两块之后的 I 用的。这种跨多步的配合，必须靠第 5 代的束搜索才能实现。另外，这一步前瞻还有两个隐藏问题：

1. 它默认方块只能从顶部直落。 真实玩家会先下落再横移，插入到直落进不去的缺口里——这需要把“动作”从“目标列”扩展成“完整轨迹”；
2. 下一块已知，但下下一块未必（在非 7-bag 规则下）。 我们使用的 7-bag 让多步前瞻成为可能，这是规则带来的红利。

4 第 3 代：全路径状态搜索与“最后一帧横移”

先看一个具体场景。假设棋盘右侧有一个“倒 L”缺口：一条竖直的窄槽，底部向右多出一格。你想把一个 L 形方块插进去——但 L 形方块比窄槽宽，从顶部直落永远进不去。人类的做法是：先让方块沿窄槽落到底，在最后一帧向右横移一格，再落进底部的口袋。

第 1、2 代 AI 的枚举都是“从顶部选一列，然后直落”，所以它们天生看不到这种落点。第 3 代要做的是把动作空间从“目标列”升级为“完整轨迹”。

4.1 把方块当作一个状态机

活动方块在任何时刻可以用三元组表示：

$$\text{state} = (r,\ c,\ \text{rot})$$

行、列、旋转角。从这个状态出发，有四种基本动作：

• 左移：$(r, c-1, \text{rot})$；
• 右移：$(r, c+1, \text{rot})$；
• 旋转：$(r, c, \text{rot}\pm1)$（带踢墙偏移）；
• 下落：$(r+1, c, \text{rot})$。

只要目标位置不与已有方块重叠、不越界，这个动作就合法。于是问题变成了一个标准的图搜索：从出生状态出发，BFS 所有可达状态；凡是“再往下走一步就会撞到东西”的状态，都是一个合法落点。

function searchPlacements(piece, board, start) {
  const visited = new Set();
  const queue = [start];
  const placements = [];
  while (queue.length) {
    const st = queue.shift();
    if (visited.has(key(st))) continue;
    visited.add(key(st));
    const canDown = valid(board, st.r + 1, st.c, st.rot, piece);
    if (!canDown) placements.push(st);      // 落定状态
    for (const next of [moveLeft(st), moveRight(st), rotate(st), ...(canDown ? [moveDown(st)] : [])]) {
      if (valid(board, next) && !visited.has(key(next))) queue.push(next);
    }
  }
  return placements;
}

注意一个细节：即使当前状态已经“落定”（不能再往下），我们仍然允许它左右移动。 这正是“最后一帧横移”的数学来源——方块坐在底上时还可以贴着地面滑进旁边的缺口，滑过去之后如果下面还有空间，就继续下落。整个搜索空间很小：$20 \times 10 \times 4 = 800$ 个状态，BFS 一次只需要几毫秒。

4.2 从搜索到执行

BFS 找到落点之后，还要把它翻译成可执行的动作序列。做法是标准的 parent 回溯：每个状态记录“我是从哪个状态、通过哪个动作来的”，找到目标落点后沿着 parent 链一路回溯，就得到一串 L/R/CW/CCW/D 指令，AI 按顺序执行，最后硬降锁定。

这条路径可能长这样（真实来自我们的实现）：

DDDDDDDDD R DD

含义是：下落 9 格，最后一帧右移 1 格，再下落 2 格。这正是图 4 里“落定 → 滑入 → 落点 B”的执行版本。

4.3 这一代解决的和没解决的

解决了：动作空间问题——AI 现在能做和人类一样的“先落再横移”操作，可以插入到任何直落进不去的缺口。

没解决：决策深度问题。全路径搜索只是让“每一个落点”计算得更完整，但它仍然只评估“这一块放完后的局面”。下一块、下下块怎么配合，还需要把第 2 代的前瞻和第 4 代的路径搜索结合起来，也就是第 5 代的束搜索。

5 第 4 代：多步前瞻与束搜索（7-bag 序列规划）

第 2 代只前瞻 1 块，第 3 代把单块的动作做全了。第 4 代把两件事合起来：用全路径搜索生成落点，用多步前瞻规划序列。

5.1 7-bag 发牌带来的红利

很多俄罗斯方块实现用的是“完全随机发牌”，AI 只知道当前块，不知道下一块。但我们的版本使用 7-bag：七种方块先洗牌成一袋，再逐一出牌。这意味着 AI 永远知道接下来 3 块、5 块甚至整袋是什么。

这个信息对决策质量的影响是决定性的。设想一个局面：你手里是 T，下一块是 S，再下一块是 I。一步前瞻只会为 S 留位置；真正的高手会为 I 留一条竖直的井——而这个决定必须现在（T 这一步）就做。只有多步前瞻才能做出这种“跨块预留”。

5.2 朴素多步前瞻的组合爆炸

直接把一步前瞻扩展成三步：

$$\text{score}(p_1) = \max_{p_2}\ \max_{p_3}\ h(s''')$$

每个方块大约有 30～40 个合法落点，三层就是 $40^3 = 64{,}000$ 个组合。虽然单次模拟很便宜，但每走一步棋都要算 6 万次棋盘模拟，浏览器就会明显卡顿；五层就是 1 亿次，完全不可行。

5.3 束搜索：剪掉明显不行的分支

束搜索（beam search）的核心观察是：大部分中间局面一眼看去就很差，不值得为它们继续展开。 所以每一层只保留评分最高的 $K$ 个局面（$K$ 叫束宽，beam width），然后只从这 $K$ 个局面继续放下一块。

function beamSearch(pieces, board, depth, beam) {
  let states = [{ board, first: null }];
  for (let d = 0; d < depth; d++) {
    const expanded = [];
    for (const st of states) {
      for (const move of searchPlacements(pieces[d], st.board)) {
        const next = simulate(st.board, move);
        expanded.push({ board: next, first: st.first ?? move });
      }
    }
    expanded.sort((a, b) => score(b.board) - score(a.board));
    states = expanded.slice(0, beam);   // 只留束宽个候选
  }
  return states[0].first;               // 返回当前块真正要走的落点
}

复杂度从 $O(C^D)$ 降为 $O(D \times \text{beam} \times C)$，其中 $C$ 是每块的平均落点数。深度 3、束宽 6 时，每步大约只需模拟 $3 \times 6 \times 40 \approx 720$ 个局面，浏览器里十几毫秒就算完。

5.4 模拟时要真实消行

一个很容易踩的坑：多步前瞻模拟时，如果只把方块“叠”上去而不消行，评分会被满行严重污染——明明下一步就该消掉的四行，会被算成“超高柱子的灾难局面”。所以束搜索的 simulate 必须真实执行消行：检查满行、移除、顶部补空行，然后才评分。

这也是为什么束搜索的效果比“把一步前瞻重复三遍”好得多：它在每一步都处理了真实的消行反馈，评分函数看到的是真正会发生的局面。

5.5 效果与局限

深度 3、束宽 6 的束搜索已经能稳定打出千行级的水平，并且会主动做出“现在留井、两块之后用 I 四连消”这类跨块规划。在我们的实现里，它每块棋只需要十几毫秒，完全实时。

局限主要有两个：

1. 剪枝可能剪掉最优解。 束宽是启发式的：早期看起来差的局面，理论上有可能在后面翻盘（比如它恰好给未来的 I 留了一条井）。束宽越大越接近穷举，但代价是计算量；
2. 权重仍然需要调。 束搜索只是把“评估”用得更充分，评估函数本身的权重仍然是手工/搜索出来的。这个问题留给第 7 代的遗传算法和第 8 代的强化学习。

5.6 束宽与深度怎么选

束搜索有两个旋钮：深度 $D$ 和束宽 $K$。它们的作用完全不同：

• 深度决定“看得多远”。 深度 1 只能为下一块留位置；深度 3 才能完成“现在留井、第三块用 I 四连消”这种跨块规划；深度 5 以上基本可以覆盖一整袋（7 块）的配合，但收益会边际递减——因为后面的序列太长，前面几步的细微差异会被后续决策抹平。
• 束宽决定“每一层保留多少可能性”。 束宽 1 就是纯贪心：每层只留最好的那个局面，任何“暂时差但能翻盘”的候选都被丢掉；束宽 6 到 16 是性价比最高的区间，再往上提升有限，计算量却线性上涨。

一个实用的经验是：先固定束宽，逐步加深深度，观察“每加深一层，平均消行数提升多少”。当提升从几百行骤降到几十行时，就说明已经看到了信息量最大的那几块，继续加深只是在给噪声花钱。我们的小游戏选择深度 3、束宽 6，正是这个经验的产物：在 7-bag 下，三块前瞻已经能覆盖一次“留井 + 配合”的完整周期，而每步计算时间仍然控制在十几毫秒。

另外还有一个容易被忽略的细节：束搜索的评分对象是“模拟消行后的棋盘”，所以深度加深时，消行反馈会被更准确地计入——这比单纯增大束宽更重要。换句话说，深度管“会不会规划”，束宽管“规划时会不会漏掉关键分支”，两者缺一不可。

6 第 5 代：对抗随机性与蒙特卡洛树搜索

如果发牌不是 7-bag，而是完全随机的，那么“下一块”就是不确定的。这时候决策问题从“在已知序列里选最优”变成“在随机序列下选期望最优”。

6.1 期望最大（Expectimax）

标准做法是期望最大搜索：决策节点取最大，机会节点取期望。对当前落点 $p$，其价值是：

$$V(p) = \sum_{\text{piece } q} P(q) \cdot \max_{p'} V(p')$$

如果七种方块等概率，$P(q)=1/7$。每一步都按“所有可能的下一块”加权平均，AI 选择的动作就是在所有随机序列下的期望最优。2048 的 Expectimax 也是同一套思想。

6.2 MCTS：用随机模拟代替精确期望

当搜索树太大（俄罗斯方块的状态树几乎是无限的），精确枚举不可行，蒙特卡洛树搜索（MCTS）登场。它不再展开所有分支，而是反复执行四步：

1. 选择（Selection）：从根出发，用 UCT 公式挑选“探索价值高”的孩子节点，直到叶子；
2. 扩展（Expansion）：给叶子加一个孩子节点；
3. 模拟（Simulation/Rollout）：从新节点开始，用随机策略或快速启发式玩到游戏结束（或固定步数）；
4. 回溯（Backpropagation）：把模拟结果沿路径回传，更新每个节点的访问次数 $N$ 和平均价值 $V$。

UCT 公式是：

$$\text{UCT}(v) = V(v) + c \sqrt{\frac{\ln N(\text{parent})}{N(v)}}$$

第一项是“这个节点目前有多好”，第二项是“我还没怎么探索过它”。$c$ 控制探索与利用的平衡。

6.3 MCTS 的适用场景

MCTS 适合“规则明确、状态巨大、很难写出好启发式”的游戏——围棋是它的成名作。对俄罗斯方块来说，它的价值取决于规则：

• 如果是随机发牌，MCTS 的随机模拟恰好能覆盖各种未来序列，比确定性束搜索更稳健；
• 如果是 7-bag，未来序列基本已知，束搜索的确定性规划通常更高效，MCTS 的优势被削弱。

这也是为什么我们最终在博客的小游戏里选择了“全路径搜索 + 束搜索”：针对 7-bag 规则，这是计算效率与棋力性价比最高的组合。 但为了讲完整条进化路线，下面仍然要介绍两种“调参/学习”路线：遗传算法和深度强化学习——它们解决的是同一个问题：权重从哪来。

补充一个概念区分：Expectimax 和 MCTS 都在处理“机会节点”，但建模方式不同。Expectimax 显式写出每种下一块的概率并求加权平均，适合概率分布已知、分支可控的场景；MCTS 不做显式概率建模，而是用“反复随机抽样”隐式逼近期望。在 7-bag 规则下，下一块不是随机变量而是确定已知，这两类算法都失去了部分用武之地——这也是为什么确定性束搜索成了我们的主力。

7 第 6 代（调参篇）：遗传算法搜索权重

前面所有算法的评分函数都是

$$h(s) = w_H H + w_{\text{holes}} \text{holes} + w_B B + w_L \text{lines}$$

四个权重 $w_H, w_{\text{holes}}, w_B, w_L$ 决定了 AI 的“性格”：它更怕死还是更贪消行，更怕空洞还是更怕崎岖。手工调参的问题是：四个权重互相影响，而且“最优权重”高度依赖规则细节（发牌方式、计分规则、是否允许 hold）。与其靠手感，不如让算法自己找。

7.1 把权重编码成“基因”

遗传算法的第一步是把一组权重当作一个个体：

个体 = [w_H, w_holes, w_B, w_L] = [−0.51, −0.36, −0.18, 0.76]

一个种群就是几十个这样的四维向量。适应度怎么算？很简单：让这个权重跑 N 局俄罗斯方块，取平均消行数（或平均存活行数）。 分数越高，说明这组权重越强。

7.2 进化循环

每一代做四件事：

1. 评估：种群里的每个个体各跑若干局，得到适应度；
2. 选择：用锦标赛选择挑出适应度高的个体——随机抽几个比一比，赢家进入“父母池”；
3. 交叉：两个父母的权重向量做混合（例如按随机掩码取父母各一半，或加权平均），生成孩子；
4. 变异：给孩子的每个权重以一定概率加上高斯噪声，防止种群过早收敛到局部最优。

function evolve(population) {
  const scored = population.map(genes => ({ genes, fitness: playNTimes(genes, 20) }));
  const parents = tournamentSelect(scored, 20);
  const children = [];
  while (children.length < population.length) {
    const [a, b] = pickTwo(parents);
    children.push(mutate(crossover(a.genes, b.genes)));
  }
  return children;
}

7.3 遗传算法解决了什么、没解决什么

它解决了“权重从哪来”的问题，而且经常能找到人类想不到的组合——例如“空洞惩罚远高于平整度”“消行奖励比直觉更高”。但它没有改变决策结构：AI 仍然只看固定深度、用固定特征。 如果四个特征本身表达力不够（例如无法表达“这条井是为 I 准备的”），权重再优化也有上限。

想要突破特征表达的上限，就需要让机器自己学“什么特征重要”——这就是深度强化学习的舞台。

8 第 7 代：强化学习与深度神经网络

8.1 从线性评分到可学习价值函数

第 2 代的评分函数 $h(s)=w^T\phi(s)$ 其实已经是一个“线性价值函数”：$\phi(s)$ 是特征向量（高度、空洞、平整度、消行），$w$ 是权重。强化学习换了一个问法：与其手工设计 $w$，不如让 AI 通过不断试错，用回报信号自动更新 $w$。

最经典的更新是时序差分（TD）：

$$w \leftarrow w + \alpha \big( r + \gamma V(s') - V(s) \big) \nabla_w V(s)$$

其中 $r + \gamma V(s')$ 是“实际观察到的回报 + 对未来的估计”，$V(s)$ 是原来的估计，两者之差叫 TD 误差。这个公式的意义是：如果 AI 落子后发现局面比预期好（TD 误差为正），就上调刚才那个局面及其特征对应的权重；反之则下调。

俄罗斯方块 AI 历史上最重要的实验之一就是线性 TD 与特征工程：用十几个精心设计的特征 + TD(λ)，AI 能达到数百万行水平。它证明了“自举式学习”的威力——不需要任何人类示范，只需要奖励信号（消行、死亡）。

8.2 DQN：用神经网络逼近 Q 函数

线性价值函数只能表达特征的线性组合。DQN（Deep Q-Network）用神经网络代替 $w^T\phi(s)$：

• 输入：当前棋盘（可以编码成 20×10 的图像，每个格子一个通道，或者 4 个特征图）；
• 网络：几层卷积 + 全连接；
• 输出：每个候选动作（落点）的 Q 值 $Q(s,a)$。

训练时使用经验回放：把（状态、动作、奖励、下一状态）存进回放池，随机采样小批量更新网络，打破样本之间的时间相关性；再用一个目标网络定期同步，稳定训练。

奖励设计在这里极其关键。如果只把“得分”当作奖励，AI 会学到一种短视行为：疯狂追求单次消行，却不在乎留下多少个洞。常见的做法是把奖励拆成多分量：单行消行 +100、双行 +300、四连消 +800，同时对“高度超过阈值”或“产生新洞”施加负奖励。这本质上又回到了启发式的那四个特征——只不过现在它们不是被手工加权，而是被神经网络隐式地重新组合。强化学习没有取消特征工程，而是把“特征组合”这件事交给了优化器。

// DQN 一步更新（伪代码）
const batch = replayBuffer.sample(32);
for (const { s, a, r, sNext, done } of batch) {
  const target = done ? r : r + gamma * targetNet.maxQ(sNext);
  const loss = (qNet(s)[a] - target) ** 2;
  optimizer.step(loss);            // 梯度下降更新 Q 网络
}
if (step % 1000 === 0) targetNet.copyFrom(qNet);

8.3 AlphaZero 思路：让搜索和学习互相增强

再进一步就是 AlphaZero 式的方法：MCTS 负责搜索，神经网络负责给搜索“指路”。网络有两个输出头：

• 策略头：对每个候选落点输出一个先验概率，告诉 MCTS“哪里值得多探索”；
• 价值头：输出当前局面的胜率/期望回报，替代随机 rollout，让模拟又快又准。

AI 自对弈生成数据，再用数据训练网络，网络变强后又指导更好的搜索，循环往复。这个架构在围棋、国际象棋上超越了人类，在俄罗斯方块上也有 AlphaZero-Tetris 这样的复现项目。它的代价是训练成本极高——通常需要 GPU、几十万局自对弈。

8.4 为什么小游戏页面里最终没用深度强化学习

不是它不强，而是工程成本不匹配：

1. 训练需要大量对局与算力，浏览器里实时训练不可行；
2. 训练好的网络动辄几 MB，与单页小游戏的体积目标冲突；
3. 我们的规则是 7-bag 且未来方块已知，束搜索已经把“已知信息”用到了极致，性价比最高。

所以最终落地到 俄罗斯方块 · 霓虹堆叠 的组合是：全路径状态搜索（生成所有可达落点，含侧滑插入）+ 3 步前瞻束搜索（用 7-bag 信息规划序列）+ 四维启发式评分。下面一章直接看代码，看这些算法是怎么从“普通匹配”一步步长成现在这个样子的。

9 实战：我们的 AI 是怎么一步步长出来的

这一章把前面所有概念落到真实代码上。我们仓库里的 tetris.astro 经历了四个版本，正好对应本文的第 0 代到第 4 代。

9.1 v0：普通匹配（基线）

第一版只有“枚举 + 打分 + 选择”三行骨架，评分用一个最粗糙的目标：落完后最高列尽量低。

function bestForV0(type) {
  let best = null;
  for (const rot of rotations(type)) {
    for (let col = 0; col < 10; col++) {
      const r = landingRow(type, rot, col);     // 从顶部直落
      const next = place(board, type, rot, r, col);
      const score = -maxColumnHeight(next);      // 最高列越低越好
      if (score > best.score) best = { rot, col, score };
    }
  }
  return best;
}

它能玩，但非常脆弱：最高列这个目标会让 AI 把所有方块堆到同一个低洼处，或者为了压低柱子而拒绝消行。

9.2 v1：四维启发式

把“一个目标”换成“四个特征”，评分函数变成：

function evaluateBoard(b) {
  let agg = 0, holes = 0, bump = 0, complete = 0;
  for (let c = 0; c < 10; c++) {
    let h = 0;
    for (let r = 0; r < 20; r++) if (b[r][c]) { h = 20 - r; break; }
    agg += h;
    let seen = false;
    for (let r = 0; r < 20; r++) {
      if (b[r][c]) seen = true;
      else if (seen) holes++;
    }
  }
  for (let r = 0; r < 20; r++) if (b[r].every(x => x)) complete++;
  for (let c = 1; c < 10; c++) bump += Math.abs(height(c) - height(c - 1));
  return -0.51 * agg - 0.36 * holes - 0.18 * bump + complete * 760;
}

这一版 AI 第一次有了“性格”：怕空洞、怕崎岖、喜欢消行。但它依然只会从顶部直落，并且只看一步。

9.3 v2：全路径状态搜索

我们把“动作”从“目标列”升级成“完整轨迹”：以 $(r,c,\text{rot})$ 为状态，BFS 左右/旋转/下落，所有“不能再往下”的状态都是候选落点。核心代码只有十几行：

function searchPlacements(board, type, start, withPaths) {
  const visited = new Map();
  const queue = [start];
  const placements = [];
  while (queue.length) {
    const st = queue.shift();
    const k = stateKey(st);
    if (visited.has(k)) continue;
    visited.set(k, parentInfo);
    const canDown = validOn(board, st.r + 1, st.c, st.rot, type);
    if (!canDown) placements.push(st);          // 落定状态也是候选
    // 左/右/旋转永远可以尝试；能下落时才加入下落分支
    for (const next of [left(st), right(st), rotateCW(st), rotateCCW(st), ...(canDown ? [down(st)] : [])]) {
      if (validOn(board, next) && !visited.has(stateKey(next))) queue.push(next);
    }
  }
  return placements;
}

关键就在注释那一句：“落定状态仍然可以左右移动。” 这让 AI 学会了最后一帧横移。执行时沿着 parent 链回溯，得到一串 L/R/CW/CCW/D 指令，最后硬降。

9.4 v3：3 步前瞻束搜索

最后，把全路径搜索放进束搜索里：对当前块的每个落点，模拟放好并真实消行；然后对接下来 3 块反复“展开 → 排序 → 保留前 6 个”，最后选当前这一步的最佳落点：

function bestMoveWithLookahead(type) {
  const placements = searchPlacements(board, type, currentState);
  let beam = placements.map((p, i) => ({
    board: placeAndClear(board, type, p),
    first: i,
    score: scoreBoard(placeAndClear(board, type, p)),
  }));
  beam.sort((a, b) => b.score - a.score).slice(0, 6);
  for (let d = 0; d < 3 && queue[d]; d++) {
    beam = expandBeam(beam, queue[d]);   // 下一块 → 展开 → 保留 6
  }
  return placements[beam[0].first];      // 映射回当前块的落点
}

AI 面板上会实时显示它选择了哪种策略：直落 / 平移落点 / 侧滑插入，以及“前瞻 3”。如果它选择了侧滑插入，说明搜索器发现了一条必须“先下落、再横移”才能到达的最优落点。

实测：在一个人为构造的“倒 L 缺口”棋盘上，AI 给出的路径是 DDDDDDDDDRDD——先沿窄槽落 9 格，最后一帧右移，再落 2 格，正好把 L 形插进口袋。2400 帧的完整对局模拟只耗时约 468ms，完全实时。

10 总结：一张表看懂七代算法

代数	算法	决策深度	是否利用 7-bag	是否支持侧滑插入	每步复杂度	典型水平
第 0 代	随机 / 单目标贪心	0 步	否	否	$O(C)$	几十行
第 1 代	四维启发式	0 步	否	否	$O(C \cdot 200)$	几百行
第 2 代	一步前瞻（El-Tetris）	1 步	部分	否	$O(C^2 \cdot 200)$	千行级
第 3 代	全路径状态搜索	0 步但动作全	否	是	$O(800)$	插入技巧
第 4 代	多步前瞻束搜索	2～5 步	是	是	$O(D \cdot K \cdot C)$	千行以上
第 5 代	Expectimax / MCTS	任意	可选	可选	高	视算力
第 6 代	遗传算法调参	取决于宿主	可选	可选	离线训练	权重更优
第 7 代	深度强化学习（DQN/AlphaZero）	学习得到	可选	可选	训练成本高	最高

如果用一句话概括这条进化路线：

普通匹配只会“放”，启发式学会“挑”，一步前瞻学会“留”，全路径搜索学会“钻”，束搜索学会“规划一串”，MCTS 学会“应对不确定”，强化学习学会“自己定义什么叫好”。

每一代都在回答前一代答不了的问题：该放哪 → 什么是好局面 → 下一块怎么办 → 直落进不去怎么办 → 未来三块怎么办 → 未来不确定怎么办 → 特征和权重从哪来。算法没有绝对优劣，只有“与规则和算力是否匹配”。

11 附录：分步骤 SVG 示意图

下面把全文中最重要的五个过程，用“分步骤”的 SVG 图画出来。每张图从左到右就是算法的完整执行顺序。

11.1 步骤图 A：一次启发式评分

11.2 步骤图 B：L 形方块侧滑插入倒 L 缺口

这是全路径搜索最经典的战例。六步看完“直落枚举永远找不到”的落点是怎么被发现的：

11.3 步骤图 C：束搜索展开

11.4 步骤图 D：MCTS 一轮迭代

11.5 步骤图 E：DQN 的一次参数更新

11.6 总览：一条进化时间线

12 结语

回到最初的问题：俄罗斯方块 AI 到底是怎么从“普通匹配”走到“高级算法”的？

答案是它走了一条非常典型的 AI 进化路径：先用最简单的规则建立基线，再用特征工程把“直觉”变成可计算的数字，然后一步步加深决策深度——从 0 步到 1 步，从直落到任意轨迹，从单块到三块序列，从确定序列到随机序列，最后把“定义好坏”这件事也交给机器学习。每一代都在前一代的框架上打一个补丁，而补丁的内容，永远是对同一个问题的追问：我看得还不够远，或者我看得还不够全。

如果只能带走一个结论，我希望是这一条：算法的“高级”不在于它用了多少数学符号，而在于它有没有诚实地回答“我看得多远、我看得多全、我凭什么说这个局面好”这三个问题。 随机落子三个问题都不回答；贪心只回答第三个，而且回答得很粗糙；启发式把第三个回答得更精细；前瞻和束搜索开始回答第一个；全路径搜索回答第二个；MCTS 在不确定性下重新回答第一个；强化学习则把第三个问题的答案也变成了学习对象。把这套“追问框架”记在心里，你再去读任何游戏 AI、机器人规划甚至大模型推理的论文，都会发现它们只是在这三个问题上选择了不同的取舍。

如果你想亲手验证这些算法，最直接的方式是打开 俄罗斯方块 AI 托管，观察面板上的策略标签：看到「侧滑插入」时，说明全路径搜索正在工作；看到「前瞻 3」时，说明束搜索正在为三块之后做规划。也可以读一读 tetris.astro 的源码，把 AI_DEPTH 从 3 改成 1 或 5，亲身体会“看得远一点”对棋力的影响。

下一篇预告：同样的思路——从贪心到搜索到学习——几乎可以原封不动地搬到 2048、推箱子、扫雷和吃豆人上。我们在 游乐场 里的每个 AI 演示，都是这条进化路线的一个切片。