每日算法 — 使用java实现2048：Zobrist哈希与置换表加速的Expectimax

一、2048 不是博弈，是“半个博弈”

2048 看起来像棋类游戏，但它的对手不是人，而是随机的方块生成器。玩家的操作是确定的（四个方向键），环境的响应是随机的（新块 90% 出 2、10% 出 4，位置均匀落在空格上）。这类“一方决策、一方随机”的模型属于马尔可夫决策过程（MDP），对应的搜索结构是 Expectimax，而不是 Minimax。

Expectimax 只有两种节点：

• MAX 层（玩家）：枚举四个方向，取最大值；
• CHANCE 层（环境）：枚举所有可能的生成位置与数值，按概率加权求期望。

麻烦在于 CHANCE 层的分支数。一个还剩 6 个空格的盘面，chance 层就有 6×2 = 12 个分支；深度 6 的搜索，节点数轻易破十万。而每一层都要做四次移位合并。于是瓶颈不再是“想得够不够深”，而是“重复计算了太多相同的盘面”。

解决重复计算的标准答案是置换表（transposition table），而置换表的前提是一个又快又均匀的状态哈希——Zobrist 哈希。本文把这两件事串起来，并用实测数据说明它到底省了多少。

二、状态表示：把一个盘面塞进一个 long

2048 的格子值只可能是 0（空）或 2^k。把“指数 k”存进 4 bit，一格 4 bit，一行 4 格 = 16 bit，四行 = 64 bit，正好一个 long。

位布局（从低位到高位）
row0: [c0:3..0][c1:7..4][c2:11..8][c3:15..12]
row1: [16..31]
row2: [32..47]
row3: [48..63]

这个表示不止省内存，更重要的是让操作全部变成位运算与查表：

1. 抽一行只需 (b >>> (16*r)) & 0xFFFF；
2. 一行只有 16 bit，取值空间 2^16 = 65,536，可以整表预先算好合并结果；
3. 四个方向不必写四套代码，一份“向左滑”就能覆盖全部。

行的压缩合并：查表化

/** 把 16 bit 的一行向左压缩合并，返回 {新行, 得分} */
static int[] moveRow(int row) {
    int[] vals = new int[4];
    int n = 0;
    for (int i = 0; i < 4; i++) {
        int v = (row >>> (4 * i)) & 0xF;
        if (v != 0) vals[n++] = v;         // 去零压缩，保持原顺序
    }
    int[] out = new int[4];
    int score = 0, k = 0;
    for (int i = 0; i < n; ) {
        if (i + 1 < n && vals[i] == vals[i + 1] && vals[i] < 15) {
            int merged = vals[i] + 1;      // 2^k + 2^k = 2^(k+1)
            out[k++] = merged;
            score += 1 << merged;          // 合并得分等于合并后的面值
            i += 2;
        } else {
            out[k++] = vals[i];
            i += 1;
        }
    }
    int nr = 0;
    for (int i = 0; i < 4; i++) nr |= out[i] << (4 * i);
    return new int[]{nr, score};
}

注意 vals[i] < 15 这个条件：4 bit 最大表示 15（面值 32768），再合并就溢出。真实对局几乎到不了，但库代码必须把边界写死，否则会出现“高位静默溢出导致估值突变”的诡异 bug。

另外必须强调：合并顺序是从靠边一侧开始，[2,2,2,0] 向左滑的结果是 [4,2,0,0] 而不是 [2,4,0,0]，得分 4。这一点与真实规则一致，写错了会整体偏差。

其余三个方向：转置 + 行反转

左右方向只需要“行内反转”，上下方向需要“转置”。那么只要有一份向左滑，其余三个方向都是复合：

转置不要用复杂的掩码公式——那是最容易写错的地方（我第一版就错在掩码上，且错了之后几乎看不出来，只是 AI 的上下判断变得莫名其妙）。用“沿对角线逐对交换 nibble”最稳，4×4 只有 6 对：

/** 4x4 nibble 矩阵转置 */
static long transpose(long x) {
    for (int r = 0; r < 4; r++) {
        for (int c = r + 1; c < 4; c++) {
            int s1 = 4 * (r * 4 + c);
            int s2 = 4 * (c * 4 + r);
            long a = (x >>> s1) & 0xF;
            long b = (x >>> s2) & 0xF;
            if (a != b) {                 // 相同则交换无意义，跳过省两次异或
                x ^= (a ^ b) << s1;
                x ^= (a ^ b) << s2;
            }
        }
    }
    return x;
}

行内反转同样查表最省事，一行 16 bit：

static long reverseRows(long b) {
    long out = 0;
    for (int r = 0; r < 4; r++) {
        int row = (int) ((b >>> (16 * r)) & 0xFFFF);
        int rev = ((row & 0xF) << 12) | ((row & 0xF0) << 4)
                | ((row & 0xF00) >>> 4) | ((row & 0xF000) >>> 12);
        out |= (long) rev << (16 * r);
    }
    return out;
}

这四个方向的正确性必须做对拍验证：写一份直观的二维数组实现，随机生成 500 个盘面，逐个比对四个方向的输出（盘面 + 得分）。这一步花十分钟，能省掉后面十小时的调试。

三、Zobrist 哈希：把盘面变成 64 位密钥

Zobrist 哈希的思路极其简单：为每个“格子 i 上放着指数 v”的组合预先分配一个随机 64 位数 Z[i][v]，盘面哈希就是所有非空格对应随机数的异或和。

static final long[][] Z = new long[16][16];

static {
    SplittableRandom rnd = new SplittableRandom(0x2048L);   // 固定种子，保证实验可复现
    for (int i = 0; i < 16; i++)
        for (int v = 1; v < 16; v++)
            Z[i][v] = rnd.nextLong() & 0x7FFFFFFFFFFFFFFFL;
}

static long hash(long b) {
    long h = 0;
    for (int i = 0; i < 16; i++) {
        int v = (int) ((b >>> (4 * i)) & 0xF);
        if (v != 0) h ^= Z[i][v];
    }
    return h;
}

为什么是异或而不是加法？ 因为异或自逆：h ^ a ^ a == h。这让增量更新变成一行代码——把 i 格从 oldV 改成 newV，只需 h ^= Z[i][oldV] ^ Z[i][newV]。2048 的每次合并、每次生成都是局部改动，理论上可以 O(1) 更新哈希。

但本文的实现仍然整盘重算，理由是：16 个格子的重算成本只有 16 次移位加异或，与“维护一个增量哈希并保证所有代码路径都不漏更新”相比，前者出错概率低得多。这是一个典型的工程取舍——当重算成本已经被压到常数级别，正确性优先于理论复杂度。增量版本在文末代码里以 hashUpdate 形式给出，供需要跨进程复用哈希的场景参考。

碰撞概率。 64 位空间下，N 个不同盘面发生碰撞的概率按生日问题约为 N²/2^65。N = 10^5 时约 2.7×10^-10，可以忽略。若要持久化表结构（存盘、跨进程共享），应在表项里额外存原始盘面 long 做二次校验，代价 8 字节换 100% 正确。

为什么不用 hashCode()？ 因为 Long.hashCode 只取低 32 位，四行高位的信息全丢，碰撞率会上升 2^32 倍。而且它没有随机盐，同样的盘面永远得到同样的哈希，容易被“构造对抗样本”打击。这不是理论洁癖——在置换表里，哈希质量直接决定命中率。

四、Expectimax 与置换表

static double expectimax(long b, int depth, boolean isMax,
                         Map<Long, Double> tt, int[] nodes) {
    nodes[0]++;
    if (depth == 0) return heuristic(b);

    if (isMax) {
        long key = hash(b) * 32 + depth;      // 哈希左移 5 位拼上剩余深度
        Double cached = tt.get(key);
        if (cached != null) return cached;

        double best = Double.NEGATIVE_INFINITY;
        for (int d = 0; d < 4; d++) {
            long[] mv = move(b, d);
            if (mv[0] == b) continue;         // 该方向无效，不消耗深度
            best = Math.max(best, mv[1] + expectimax(mv[0], depth - 1, false, tt, nodes));
        }
        if (best == Double.NEGATIVE_INFINITY) best = 0;
        tt.put(key, best);
        return best;
    }

    List<Integer> es = empties(b);
    if (es.isEmpty()) return heuristic(b);
    double sum = 0;
    for (int idx : es) {
        sum += 0.9 * expectimax(setCell(b, idx, 1), depth - 1, true, tt, nodes);
        sum += 0.1 * expectimax(setCell(b, idx, 2), depth - 1, true, tt, nodes);
    }
    return sum / es.size();                   // 位置均匀分布 => 直接取平均
}

四个关键设计点：

第一，键里必须带深度。 同一个盘面“还剩 3 层”和“还剩 5 层”的估值完全不同。只用哈希做键会串味，症状是“搜索越深，走法反而越差”。hash*32+depth 把深度塞进低 5 位，depth ≤ 32 足够。

第二，只给 MAX 层建表。 CHANCE 层是期望值，其值完全由子节点决定，且与父节点的空格集合强耦合，存表命中率低、语义容易混乱。只给 MAX 层建表，最省事也最不容易错。

第三，无效方向要跳过。 若某方向盘面不变（没有任何格子移动、没有合并），它就不是一个合法动作。若照常递归，会白白消耗一层深度并返回一个大估值，AI 会误以为“原地不动最安全”。

第四，chance 层直接取算术平均。 新块位置在空格上均匀分布，每种位置概率 1/|empty|；数值 2 与 4 的条件概率 0.9 / 0.1。所以期望就是 Σ(0.9·V(2) + 0.1·V(4)) / |empty|，不需要权重表。

估值函数：三个特征就够用

static double heuristic(long b) {
    int[][] g = new int[4][4];
    int empty = 0;
    for (int r = 0; r < 4; r++)
        for (int c = 0; c < 4; c++) {
            g[r][c] = cell(b, r * 4 + c);
            if (g[r][c] == 0) empty++;
        }

    // 单调性：行/列上数值要么单调增、要么单调减，避免"夹心饼干"
    long[] dir = new long[4];
    for (int r = 0; r < 4; r++)
        for (int i = 0; i < 3; i++) {
            int a = g[r][i], c2 = g[r][i + 1];
            if (a > c2) dir[0] += c2 - a; else dir[1] += a - c2;
        }
    for (int c = 0; c < 4; c++)
        for (int i = 0; i < 3; i++) {
            int a = g[i][c], c2 = g[i + 1][c];
            if (a > c2) dir[2] += c2 - a; else dir[3] += a - c2;
        }
    long mono = Math.max(dir[0], dir[1]) + Math.max(dir[2], dir[3]);

    // 平滑度：相邻非零格面值差越小越好
    long smooth = 0;
    for (int r = 0; r < 4; r++)
        for (int c = 0; c < 4; c++) {
            if (g[r][c] == 0) continue;
            if (c < 3 && g[r][c + 1] != 0) smooth -= Math.abs(g[r][c] - g[r][c + 1]);
            if (r < 3 && g[r + 1][c] != 0) smooth -= Math.abs(g[r][c] - g[r + 1][c]);
        }

    return 27.0 * empty + 10.0 * mono + 3.0 * smooth;
}

三个权重（27 / 10 / 3）的顺序很重要：空格数是生存指标，一旦无空格且无可合并，游戏立刻结束；单调性是增长指标，把大数沿一个角排成一个“蛇形”，才能持续合并；平滑度是辅助，让相邻格容易凑对。

五、实测：置换表省了多少

固定盘面（首行 2/4/8/16、次行 32/64）、同一估值函数，深度从 3 扫到 6：

三件事值得注意：

第一，估值完全一致。 置换表不改变搜索语义，只复用已算子树，这是它相对“启发式剪枝”的最大优势——它不会因为参数调错而给出错误答案。

第二，浅层完全没有收益。 深度 3、4 时比例正好是 1.000。原因很直白：搜索太浅，同一个盘面还没被第二次访问。置换表的收益随深度超线性增长，这是它最值得记住的特性，也是“要不要上置换表”的判断依据——深度 5 以下不必折腾，深度 7 以上必须有。

第三，节省比例随深度上升。 0.494 → 0.353，说明深层搜索中重复盘面的占比在提高，这正是 chance 层“多路径到达同一盘面”的直接体现。

同一盘面在深度 5 下的四个方向估值（左、上无效，因为首行已满且左侧无零）：

右移略优，符合直觉：保持大数在上方、空位留在下方，为后续合并预留空间。

六、复杂度分析

记玩家分支 b ≤ 4，chance 层平均分支 e（空格数 × 2）。

• 时间：无表时 O(b^(d/2) · e^(d/2))，d 为深度；有表时正比于搜索触及的不同 (盘面, 深度) 对数。实测深度 6 从 164,255 降到 57,961。
• 单节点成本：4 次方向尝试 × 4 行查表 + 1 次哈希（16 次位运算）+ 估值（约 100 次基本运算）。位棋盘 + 表的组合把每层常数压到几十纳秒量级——这是 Expectimax 能在手机上实时跑深度 6 的原因。
• 空间：置换表 O(|S|)，每项 8 字节键 + 8 字节值。深度 6 实测 5.7 万个表项，约 1 MB，可控。若要跑深度 8，需要换成有容量上限的“深度优先淘汰”策略（按剩余深度淘汰最浅项）。

七、完整可运行项目

game-2048/
├── pom.xml
└── src/main/java/com/daily/algorithm/Game2048.java

<project xmlns="http://maven.apache.org/POM/4.0.0">
  <modelVersion>4.0.0</modelVersion>
  <groupId>com.daily</groupId>
  <artifactId>game-2048</artifactId>
  <version>1.0</version>
  <properties>
    <maven.compiler.source>17</maven.compiler.source>
    <maven.compiler.target>17</maven.compiler.target>
  </properties>
</project>

package com.daily.algorithm;

import java.util.*;

public class Game2048 {

    static final int[][] ROW_TABLE = new int[1 << 16][2];   // {新行, 得分}
    static final long[][] Z = new long[16][16];

    static {
        for (int r = 0; r < (1 << 16); r++) ROW_TABLE[r] = moveRow(r);
        SplittableRandom rnd = new SplittableRandom(0x2048L);
        for (int i = 0; i < 16; i++)
            for (int v = 1; v < 16; v++)
                Z[i][v] = rnd.nextLong() & 0x7FFFFFFFFFFFFFFFL;
    }

    /* ==================== 行操作 ==================== */

    static int[] moveRow(int row) {
        int[] vals = new int[4];
        int n = 0;
        for (int i = 0; i < 4; i++) {
            int v = (row >>> (4 * i)) & 0xF;
            if (v != 0) vals[n++] = v;
        }
        int[] out = new int[4];
        int score = 0, k = 0;
        for (int i = 0; i < n; ) {
            if (i + 1 < n && vals[i] == vals[i + 1] && vals[i] < 15) {
                int merged = vals[i] + 1;
                out[k++] = merged;
                score += 1 << merged;
                i += 2;
            } else {
                out[k++] = vals[i];
                i += 1;
            }
        }
        int nr = 0;
        for (int i = 0; i < 4; i++) nr |= out[i] << (4 * i);
        return new int[]{nr, score};
    }

    static long transpose(long x) {
        for (int r = 0; r < 4; r++) {
            for (int c = r + 1; c < 4; c++) {
                int s1 = 4 * (r * 4 + c);
                int s2 = 4 * (c * 4 + r);
                long a = (x >>> s1) & 0xF;
                long b = (x >>> s2) & 0xF;
                if (a != b) {
                    x ^= (a ^ b) << s1;
                    x ^= (a ^ b) << s2;
                }
            }
        }
        return x;
    }

    static long reverseRows(long b) {
        long out = 0;
        for (int r = 0; r < 4; r++) {
            int row = (int) ((b >>> (16 * r)) & 0xFFFF);
            int rev = ((row & 0xF) << 12) | ((row & 0xF0) << 4)
                    | ((row & 0xF00) >>> 4) | ((row & 0xF000) >>> 12);
            out |= (long) rev << (16 * r);
        }
        return out;
    }

    static long[] slideLeft(long b) {
        long out = 0, score = 0;
        for (int r = 0; r < 4; r++) {
            int row = (int) ((b >>> (16 * r)) & 0xFFFF);
            out |= (long) ROW_TABLE[row][0] << (16 * r);
            score += ROW_TABLE[row][1];
        }
        return new long[]{out, score};
    }

    /** dir: 0=左 1=右 2=上 3=下；返回 {新盘面, 得分} */
    static long[] move(long b, int dir) {
        switch (dir) {
            case 0 -> { return slideLeft(b); }
            case 1 -> {
                long[] t = slideLeft(reverseRows(b));
                return new long[]{reverseRows(t[0]), t[1]};
            }
            case 2 -> {
                long[] t = slideLeft(transpose(b));
                return new long[]{transpose(t[0]), t[1]};
            }
            default -> {
                long[] t = slideLeft(reverseRows(transpose(b)));
                return new long[]{transpose(reverseRows(t[0])), t[1]};
            }
        }
    }

    /* ==================== 基础访问 ==================== */

    static int cell(long b, int idx) { return (int) ((b >>> (4 * idx)) & 0xF); }

    static long setCell(long b, int idx, int v) {
        int sh = 4 * idx;
        return (b & ~(0xFL << sh)) | ((long) v << sh);
    }

    static List<Integer> empties(long b) {
        List<Integer> list = new ArrayList<>(16);
        for (int i = 0; i < 16; i++) if (cell(b, i) == 0) list.add(i);
        return list;
    }

    /* ==================== Zobrist 哈希 ==================== */

    static long hash(long b) {
        long h = 0;
        for (int i = 0; i < 16; i++) {
            int v = cell(b, i);
            if (v != 0) h ^= Z[i][v];
        }
        return h;
    }

    /** 增量更新：单格从 oldV 变为 newV，O(1) */
    static long hashUpdate(long h, int idx, int oldV, int newV) {
        if (oldV != 0) h ^= Z[idx][oldV];
        if (newV != 0) h ^= Z[idx][newV];
        return h;
    }

    /* ==================== 估值 ==================== */

    static double heuristic(long b) {
        int[][] g = new int[4][4];
        int empty = 0;
        for (int r = 0; r < 4; r++)
            for (int c = 0; c < 4; c++) {
                g[r][c] = cell(b, r * 4 + c);
                if (g[r][c] == 0) empty++;
            }
        long[] dir = new long[4];
        for (int r = 0; r < 4; r++)
            for (int i = 0; i < 3; i++) {
                int a = g[r][i], d = g[r][i + 1];
                if (a > d) dir[0] += d - a; else dir[1] += a - d;
            }
        for (int c = 0; c < 4; c++)
            for (int i = 0; i < 3; i++) {
                int a = g[i][c], d = g[i + 1][c];
                if (a > d) dir[2] += d - a; else dir[3] += a - d;
            }
        long mono = Math.max(dir[0], dir[1]) + Math.max(dir[2], dir[3]);

        long smooth = 0;
        for (int r = 0; r < 4; r++)
            for (int c = 0; c < 4; c++) {
                if (g[r][c] == 0) continue;
                if (c < 3 && g[r][c + 1] != 0) smooth -= Math.abs(g[r][c] - g[r][c + 1]);
                if (r < 3 && g[r + 1][c] != 0) smooth -= Math.abs(g[r][c] - g[r + 1][c]);
            }
        return 27.0 * empty + 10.0 * mono + 3.0 * smooth;
    }

    /* ==================== 搜索 ==================== */

    static double expectimax(long b, int depth, boolean isMax,
                             Map<Long, Double> tt, int[] nodes) {
        nodes[0]++;
        if (depth == 0) return heuristic(b);

        if (isMax) {
            long key = isMax ? hash(b) * 32 + depth : hash(b);
            Double c = (tt == null) ? null : tt.get(key);
            if (c != null) return c;

            double best = Double.NEGATIVE_INFINITY;
            for (int d = 0; d < 4; d++) {
                long[] mv = move(b, d);
                if (mv[0] == b) continue;
                double v = mv[1] + expectimax(mv[0], depth - 1, false, tt, nodes);
                if (v > best) best = v;
            }
            if (best == Double.NEGATIVE_INFINITY) best = 0;
            if (tt != null) tt.put(key, best);
            return best;
        }

        List<Integer> es = empties(b);
        if (es.isEmpty()) return heuristic(b);
        double sum = 0;
        for (int idx : es) {
            sum += 0.9 * expectimax(setCell(b, idx, 1), depth - 1, true, tt, nodes);
            sum += 0.1 * expectimax(setCell(b, idx, 2), depth - 1, true, tt, nodes);
        }
        return sum / es.size();
    }

    static int bestMove(long b, int depth) {
        int bestDir = -1;
        double bestVal = Double.NEGATIVE_INFINITY;
        for (int d = 0; d < 4; d++) {
            long[] mv = move(b, d);
            if (mv[0] == b) continue;
            double v = mv[1] + expectimax(mv[0], depth - 1, false, new HashMap<>(), new int[]{0});
            System.out.printf("  dir=%d 估值=%.1f%n", d, v);
            if (v > bestVal) { bestVal = v; bestDir = d; }
        }
        return bestDir;
    }

    public static void main(String[] args) {
        long b = 0;
        int[][] init = {{1, 2, 3, 4}, {5, 6, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}};
        for (int r = 0; r < 4; r++)
            for (int c = 0; c < 4; c++)
                b = setCell(b, r * 4 + c, init[r][c]);

        System.out.println("盘面编码 : 0x" + Long.toHexString(b));
        System.out.println("Zobrist  : 0x" + Long.toHexString(hash(b)));

        for (int depth = 3; depth <= 6; depth++) {
            int[] n1 = {0};
            double v1 = expectimax(b, depth, true, null, n1);

            int[] n2 = {0};
            Map<Long, Double> tt = new HashMap<>();
            double v2 = expectimax(b, depth, true, tt, n2);

            System.out.printf("depth=%d  无表=%,6d  有表=%,6d  比例=%.3f  估值=%.1f%n",
                    depth, n1[0], n2[0], n2[0] * 1.0 / n1[0], v2);
            if (Math.abs(v1 - v2) > 1e-9) System.out.println("  !! 两版估值不一致，置换表逻辑有误");
        }

        System.out.println("候选走法（depth=5）:");
        System.out.println("最佳方向 = " + bestMove(b, 5) + "  (0左 1右 2上 3下)");
    }
}

实测输出（JDK 17，单线程）：

盘面编码 : 0x654321
Zobrist  : 0x2c8f1a6d05e7b394
depth=3  无表=   180  有表=   180  比例=1.000  估值=192.6
depth=4  无表= 2,694  有表= 2,694  比例=1.000  估值=149.1
depth=5  无表=11,603  有表= 5,731  比例=0.494  估值=194.3
depth=6  无表=164,255 有表=57,961  比例=0.353  估值=151.6
候选走法（depth=5）:
  dir=1 估值=194.3
  dir=3 估值=185.4
最佳方向 = 1  (0左 1右 2上 3下)

（Zobrist 值随种子而定，换种子就变；节点数与估值是稳定的。）

八、踩坑清单

第一，move 返回的得分千万别丢。 有人为了简单，把 MAX 层写成“只看子节点估值、不加本步合并得分”，结果 AI 变得极不爱合并——因为合并带来的分数被丢掉了。合并得分必须显式加进 Q 值。

第二，转置不要迷信掩码技巧。 上面那套 0xF0F00F0F... 的掩码公式看起来很优雅，但只要有一个 nibble 位置写错，转置就变成“错位的洗牌”，而症状只是 AI 上下判断变差，极难定位。用 6 对交换的循环版，慢一点但可验证。

第三，置换表键需要带深度，且 CHANCE 层不要存。 这是 Expectimax 上最常见的两个错误，症状都是“加深搜索反而变差”。

第四，chance 层的概率必须归一。 0.9 + 0.1 = 1，且对空格取平均而不是求和。写成求和会让深度越深估值的量级越大，跨深度不同盘面之间就没法比较了。

小结

2048 是“把随机性纳入搜索”的最佳练手题，它逼着你同时解决三件事：状态表示（位棋盘 + 查表合并）、状态索引（Zobrist 哈希）、状态复用（置换表）。三者叠加，深度 6 的搜索从 16.4 万节点降到 5.8 万，估值零损失。

更有价值的是它给出的两条可迁移经验：第一，哈希函数的成本必须远小于它要替代的计算，否则置换表是净亏损；第二，置换表的收益随搜索深度上升，浅层不必上，深层必须有。这两条在棋类引擎、规划系统、乃至编译器的等价状态判定里都成立。