只有上下左右四个方向,为什么这个 2048 AI 背后塞进了这么多算法?
如果让你写一个会玩 2048 的程序,你会怎么做?
最直接的办法大概是写几条规则:大数字尽量放角落、不要轻易打乱顺序、空格越多越好。这样的程序确实能玩,甚至可能比不少随手乱划的人更稳定。但问题很快就会出现——当棋盘被挤得只剩几个空位时,到底该向左,还是向下?眼前两步都能合并,哪一步会让十几步之后的局面更舒服?
人类会说“凭感觉”。
程序没有感觉。它只能把“感觉”拆成数字,把“未来”拆成一棵搜索树,然后在有限时间里尽可能多算一些可能性。
GitHub 上的 ziap/2048-ai 做的就是这件事。它不是给 2048 套一层“AI”名头,而是认真做了一套针对这个游戏的搜索引擎:用 Expectimax 判断下一步,用 bitboard 压缩棋盘,用查表和缓存减少重复计算,再把核心逻辑编译成 WebAssembly,直接在浏览器里开多个 worker 并行搜索。
结果也很直观:按照项目 README 的说明,它大多数时候可以打到 16384,有时甚至能摸到 32768。
更有意思的是,它不需要后端服务器替你算,也不需要浏览器自动化脚本假装真人点按键。搜索就发生在你自己的浏览器里,手机也能跑。
这个项目真正值得看的地方,其实不是“它会玩 2048”,而是:一个规则如此简单的小游戏,怎样被做成一场关于搜索、数据表示、缓存、内存和并行计算的性能工程。
2048 看起来简单,真正麻烦的是“未来太多”
2048 的操作只有四个:上、下、左、右。
这听起来几乎不像一个需要复杂算法的游戏。但程序真正做决策时,面对的并不是“四选一”。
假设当前还有 8 个空格。你向左滑动后,新方块可能出现在 8 个位置中的任意一个,而且生成的既可能是 2,也可能是 4。新方块出现后,你又有最多四种移动方向;移动完成,又会产生下一轮随机方块。
于是问题从:
“这一手向哪边滑?”
迅速变成:
“如果向左,之后各种随机情况分别会怎样?如果向下呢?把这些未来都算进去,哪一个方向的长期结果更好?”
搜索深度每增加一层,分支都会继续扩张。
所以 2048 AI 最难处理的并不是游戏规则,而是可能性爆炸。
2048-ai 的核心思路可以概括成一句话:
既然不可能把未来全部算完,那就想办法在有限预算里,比别人更快地算更多有价值的局面。
这也是后面所有优化存在的理由。
它不是在猜下一步,而是在计算“这一步之后的平均未来”
这个项目的核心搜索算法是 Expectimax。
如果你以前听说过 Minimax,可以先把两者区别抓住。
Minimax 常用于象棋、五子棋这类有明确对手的游戏。你下一步棋后,对手也会做选择,而且我们通常假设对手会故意选择对你最不利的一步。
2048 不一样。
你向左滑完以后,游戏并没有一个“对手”在思考怎样坑你。它只是随机挑一个空位置,再按照概率生成新方块。
所以这里更适合问的不是:
“对手最坏会怎么走?”
而是:
“各种随机情况按照它们出现的概率加权以后,这一步的平均前景怎么样?”
这就是 Expectimax 中 “Expect” 的含义。
可以把搜索树想象成两种节点交替出现。
第一种是 Max 节点:轮到 AI 做决定。它可以比较上、下、左、右几个合法动作,然后选择评分最高的方向。
第二种是 Expect 节点:轮到游戏随机生成方块。程序不能“选择”新方块出现在哪里,只能把所有可能情况都考虑进去,再按照概率计算期望值。
项目源码里的逻辑非常直接:新方块为 2 的权重是 0.9,为 4 的权重是 0.1。如果还有多个空格,这些概率还要继续分摊到各个可能出现的位置。
举个缩小后的例子。
假设“向左”以后只有两个空格,而为了方便说明,我们暂时只考虑生成 2:
- 新
2出现在 A 位置,后续局面评分 100; - 新
2出现在 B 位置,后续局面评分 60。
如果两个位置等概率,那么这个动作的期望评分就是:
100 × 0.5 + 60 × 0.5 = 80再对“向右”“向上”“向下”分别做同样的事情,AI 就能比较哪个动作拥有更好的长期期望。
当然,真实搜索远比这个例子复杂。它要继续向后推演很多层,而每多看几步,状态数量都会迅速膨胀。
所以接下来的问题比 Expectimax 本身还重要:
怎么让它算得足够快?
棋盘只有 16 格,但项目并没有老老实实用一个二维数组
很多人第一次实现 2048,会自然地写出一个 4 × 4 数组。
这当然没问题。
但如果一个棋盘状态需要被复制十次、比较一百次、移动一千次,那也没什么问题;如果搜索过程中这些操作要发生几百万、几千万次,表示方法本身就开始决定性能。
2048-ai 的 Board.zig 里,核心棋盘直接是一句:
data: u64,也就是说,一整个 4×4 棋盘被压进了一个 64 位整数。
每个格子占 4 bit,也就是一个 nibble。16 个格子刚好:
16 × 4 bit = 64 bit这里存的并不是方块表面的数字本身,而是它的“等级”。例如可以把 2 看成等级 1、4 看成等级 2、8 看成等级 3……这样一个 4 bit 小格就足以覆盖搜索所需的大量状态。
这类表示通常被叫作 bitboard。
它的好处不是“看起来很极客”,而是很多关键操作都变得特别便宜。
判断棋盘是否相同?比较一个 64 位整数。
复制棋盘?复制一个 64 位整数。
计算哈希?直接围绕这个整数做乘法和位移。
找空格?源码甚至通过连续的位运算,把“哪些 nibble 是 0”直接变成一个掩码。
再往下,行列转置也不是构建新数组逐格交换,而是通过掩码、异或和移位完成。
当这些操作位于搜索树最内层时,少创建几个对象、少跑几层循环,累积起来就是非常实际的性能差距。
连“滑动一行”都不想现场计算:65536 种情况提前算完
bitboard 之后,还有一个更典型的性能优化:lookup table,查找表。
想象一行 2048:
2 2 4 0向右移动时,需要做压缩、判断相邻数字、合并、再次排列。
这些规则本身并不复杂,但搜索树会一次又一次处理各种行。如果每遇到一行都重新跑完整逻辑,时间就被大量重复的小计算吃掉了。
项目干脆把一行的所有可能状态提前算好。
一行有 4 个格子,每个格子 4 bit,因此一整行就是 16 bit。
16 bit 一共有:
2^16 = 65536种可能。
于是 Board.MoveTable 直接准备了两个长度为 65536 的表:正向移动表和反向移动表。初始化时把所有行的移动结果算一遍,真正搜索时遇到某一行,直接拿这 16 bit 当索引查答案。
这有点像背乘法表。
你当然可以每次遇到 8 × 7 都从 8 + 8 + 8... 开始算,但当同样的题会出现几百万次时,提前记住答案显然更划算。
项目在计算整块棋盘四个方向的移动时,也是把行和转置后的列切成 16 bit,再从表里取结果。
这就是为什么一个看似普通的“移动方块”动作,在高性能搜索里也值得单独设计。
AI 怎么判断一个局面“好不好”?
搜索不可能无限进行。
总会来到某一层,程序必须停下来问:
“好,现在不继续算了。这个棋盘本身到底值多少分?”
负责回答这个问题的就是 heuristic,启发式评估函数。
Heuristic.zig 里的评分不是只看游戏当前分数,而是把几个与长期生存能力有关的因素揉在一起。
其中一个很直观:空格数量。
空格越多,后面越容易腾挪。棋盘完全挤满时,哪怕当前数字很大,也很容易下一手直接结束。
第二个是可合并机会。
如果一行里存在相同等级的相邻或可接近方块,说明后续还有压缩空间。
第三个是单调性。
玩过 2048 的人通常会形成类似习惯:把最大数字压在一个角落,然后尽量让数字从大到小沿某个方向排列。原因很简单,如果大数字散得到处都是,后面往往很难重新拼在一起。
源码会分别计算一行向左、向右的单调性破坏程度,并把更合理的一侧纳入评分。
而且这些东西同样被做成了查表:所有 16 bit 行的评分预先存进 score_table。评估整张棋盘时,只要查四行和四列,再累加即可。
所以在搜索树最深处,AI 并没有临时运行一大堆复杂分析;许多东西早已变成数组索引。
有些“合法动作”,它干脆不想浪费时间
高分 2048 局面往往有明显结构。
比如最大的几块数字被固定在角落附近,逐级向外展开。一旦一个随手的移动把这个结构打散,短期可能没死,长期却很难重新整理回来。
项目里的 Formation.zig 专门处理这件事。
它会关注较大的方块,检测这些高位数字是否已经形成某些角落区域结构。在搜索后续动作时,如果某一步会破坏已经保护起来的 formation,这个分支就可能被直接跳过。
这里很值得注意:剪枝不是魔法。
它并不是证明“这个动作数学上绝对错误”,而是在做工程取舍。
搜索预算有限。如果一种局面在经验和启发式上已经非常不值得继续,就把算力留给更有希望的分支。
Board.filterMoves 里还能看到一个很务实的兜底:它会优先保留不破坏 formation 的合法动作;但如果这样一个动作都没有,就退回到所有真正能改变棋盘的移动。
也就是说,保护阵型是偏好,不是让程序把自己锁死的铁律。
为什么不直接规定“永远搜索 8 层”?
这是这个项目里很有意思的一点。
很多初版搜索程序会固定深度:每一步统一看 6 层、8 层或者 10 层。
听起来很合理,但不同棋盘的复杂度根本不一样。
有的局面只剩两个合法方向,空格也不多,搜索树比较窄。
有的局面非常开阔,四个方向都能走,移动之后又有十几个空位可以生成新数字。即使搜索同样的“8 层”,需要计算的节点数量也可能差得非常远。
2048-ai 的 README 把它称为 dynamic depth allocation using memory-constrained BFS。
简单说,它不先死规定“我要搜几层”,而是先问:
“按照现在这个局面的分支规模,在给定内存/处理预算下,我大概承受得起多深?”
Bfs.zig 会从当前局面向外展开状态,并通过固定大小的缓冲区限制扩张规模。它还会对状态按哈希排序,以便近似去重,避免大量相同局面反复占空间。
代码里甚至会根据当前层与上一层的状态数量,估计下一层可能膨胀到多大;如果预测已经快要超过缓冲区能够承受的范围,就停止继续扩张。
于是搜索深度变成了一个“看菜吃饭”的结果。
局面简单,就多看几步;局面复杂,就控制深度。
真正固定的不是层数,而是预算。
算过的局面,为什么还要再算一次?
搜索树还有一个经典浪费:不同路径可能走到相同棋盘。
如果第一次遇到某个状态时已经向后搜索了 10 层,第二次又走到相同状态,再完整搜索一遍显然很亏。
所以项目用了 transposition table,可以理解成“局面答案缓存”。
search.zig 里的缓存项记录三类关键信息:
- 棋盘状态对应的 key;
- 当时搜索的深度;
- 算出来的评分。
再次遇到同一棋盘时,如果缓存里的结果至少和当前要求的搜索深度一样深,就可以直接拿评分,不必从头展开。
这个细节很重要:缓存不能只问“以前算没算过”,还要问“以前算得够不够深”。
如果上次只看了 3 层,现在需要看 8 层,那么旧答案显然不能直接冒充新答案。
项目还使用了非常轻量的乘法移位哈希,把 64 位棋盘快速映射到缓存表位置。这里的目标并不是做密码学级别哈希,而是在搜索热点路径上用尽量低的成本找到缓存槽位。
对于这种算法,少搜索一次完整子树,往往比省几个普通指令值钱得多。
浏览器凭什么扛得住这种搜索?
到这里,算法层面已经有 bitboard、查表、缓存、剪枝、动态深度。
但 2048-ai 还有另一个很吸引人的地方:这些东西可以直接跑在网页里。
核心引擎使用 Zig 编写,浏览器版本则把计算核心编译成 WebAssembly。
这里要分清两个角色。
JavaScript 很适合处理页面、按钮、动画和调度,但大量位运算、状态搜索、固定内存结构这些工作,交给编译后的 WebAssembly 更合适。
项目的构建配置会为 wasm32 目标启用 atomics、SIMD、bulk memory 等能力,并配置共享内存。也就是说,它不是把 WebAssembly 当成一个单线程小函数调用,而是认真按照并行搜索来构建。
ParallelSearch.zig 进一步把搜索树前沿拆成一批任务。
可以把过程理解成:
当前棋盘
↓
先展开出一批需要深入评分的子局面
↓
放进任务池
↓
多个 Worker 抢任务
↓
每个 Worker 用 Expectimax 深入搜索
↓
把分数写回来
↓
重新汇总,选出最终方向这里还用了原子操作和 WebAssembly 的 memory.atomic.wait32 / memory.atomic.notify 来协调 worker。
有意思的是,发起搜索的线程自己也不会闲着等结果。源码里会让调用方一起“帮忙干活”,先把任务池里还没被别人拿走的任务处理掉,再等待剩余 worker 完成。
这种设计背后的思路很朴素:
既然每一步都要等全部关键评分回来,那就尽量不要让任何一个可用执行单元闲着。
README 还特别说明,Web 版本使用共享、无锁的 transposition table。
所以你在浏览器里看到的,不是网页套壳调用某个服务器接口,而是一套真正跑在本地设备上的并行搜索程序。
Benchmark 最有意思的不是分数,而是“算力换棋力”
这个项目自带命令行版本,其中一个重要用途就是做可复现 benchmark。
README 给出的测试结果如下:
| Search Budget | 速度 | 平均分 | 达到 65536 | 达到 32768 | 达到 16384 | 达到 8192 |
|---|---|---|---|---|---|---|
2^15 | 1639.1 moves/s | 313838 | 0.0% | 9.1% | 72.1% | 95.8% |
2^17 | 419.0 moves/s | 389180 | 0.0% | 21.6% | 85.0% | 97.5% |
2^19 | 125.9 moves/s | 468109 | 0.1% | 39.1% | 91.1% | 98.9% |
2^21 | 25.5 moves/s | 530970 | 0.2% | 51.7% | 94.7% | 99.1% |
这张表其实很漂亮地展示了搜索程序最现实的一种交换关系:
想得越久,通常下得越好;但每秒能走的步数也会明显下降。
从 2^15 提高到 2^21 后,速度从每秒 1600 多步掉到 25.5 步左右,但平均分从约 31 万提高到了约 53 万,达到 32768 的比例也从 9.1% 上升到 51.7%。
这并不是“预算越大永远越划算”,而是让使用者自己选择:
- 想看 AI 飞快地跑很多局,可以降低 budget;
- 想让单局尽量下得更强,就给每一步更多搜索预算。
README 说明,速度数据是在 AMD Ryzen 5 5600G 上以单线程运行 10 局后取平均;平均分和到达各级大方块的比例,则来自使用 12 个 CPU 核心并行运行 1000 局。测试可以使用 benchmark 作为随机种子复现。
这比只写一句“性能很高”靠谱得多,因为任何 benchmark 离开测试条件都没什么意义。
如果你想读源码,从这几个地方下手最省时间
这个仓库并不大,但最好别从头按文件名逐个翻。
如果目标是理解算法,可以先看:
棋盘表示与移动逻辑(src/engine/Board.zig)
这里是棋盘表示和移动逻辑。
你会看到:
- 64 位 bitboard;
- 空格检测;
- 棋盘转置;
- 65536 项行移动查找表;
- 四个方向的快速移动生成;
- formation 过滤;
- 快速哈希。
这是理解后面所有性能优化的地基。
Expectimax 搜索核心(src/engine/search.zig)
Expectimax 主体在这里。
能看到:
- Max 节点;
- 随机生成节点;
2/4的概率权重;- transposition table;
- 搜索深度;
- formation 检查。
如果只允许读一个“AI 核心文件”,先读它。
启发式评分(src/engine/Heuristic.zig)
这里决定搜索到底喜欢什么样的棋盘。
空格、合并机会、单调性等最终都会变成评分。
它特别适合用来理解一个问题:
程序所谓的“感觉好”,最后到底是怎样被写成数字的?
动态深度与 BFS 预算(src/engine/Bfs.zig)
这里能看到动态搜索深度背后的预算思想,以及排序、近似去重、固定缓冲区等工程处理。
阵型保护与剪枝(src/engine/Formation.zig)
这里处理大数字的角落结构和剪枝。
如果你平时自己也玩 2048,会很容易把代码和“别把大数从角落里弄出来”的经验对应起来。
浏览器并行搜索(src/wasm/ParallelSearch.zig)
想看浏览器并行,就看这个。
搜索前沿怎么拆、worker 怎么抢任务、完成数量怎么同步、主调用线程怎么参与计算,都在这里。
命令行入口与统计(src/cli/)
命令行程序相关代码放在这里,包括参数解析、工作线程和统计。
它不只是为了方便启动程序,还是项目做批量测试和可复现 benchmark 的入口。
自己跑起来并不复杂
项目 README 当前要求 Zig 0.16.0。
编译优化版本:
zig build --release=fast编译完成后,命令行程序位于:
zig-out/bin/2048直接运行即可,也可以添加参数:
-i, --iter <u32> 运行多少局,默认 1
-b, --budget <u32> 每步处理预算,默认 524288
-t, --threads <u32> 线程数,默认自动
-s, --seed <bytes> 随机数种子,默认随机
-h, --help 查看帮助例如想固定随机种子、批量运行,可以围绕 --iter、--threads 和 --seed 组合。
seed 的意义尤其值得注意。很多“AI 玩游戏”的演示看起来很强,但如果每次随机过程都不同,就很难准确比较两个版本到底谁更好。
固定 seed 后,同一套随机序列可以再次出现,更适合做回归测试和 benchmark。
网页版本项目已经提供在线页面:
如果想本地运行网页,在完成构建后,用普通 HTTP Server 就可以,例如:
python3 -m http.server 8080然后浏览器打开:
http://localhost:8080一个小游戏,最后变成了一堂性能工程课
如果只看结果,2048-ai 就是一个很会玩 2048 的程序。
但顺着源码看下去,你会发现它真正有意思的部分几乎都发生在“AI”这两个字之外。
Expectimax 决定程序该如何思考未来。
启发式函数决定程序没法继续想时,怎样判断眼前局面。
bitboard 决定状态怎样被压缩和搬运。
lookup table 把重复操作变成一次数组访问。
transposition table 让算过的局面尽量别再算一遍。
formation pruning 把明显不值得展开的方向尽早砍掉。
受预算约束的 BFS 帮它决定这一个局面到底值得看多深。
Zig 和 WebAssembly 让这些计算可以高效落进浏览器,而 worker pool 又把一棵巨大的搜索树拆成可以同时处理的小块。
最后你会发现,这个项目并没有一个“突然让 AI 变聪明”的神奇技巧。
它更像很多高性能程序真实的样子:几十个并不神秘的决定,层层叠加,最后把原本算不动的东西推到了能实时运行的程度。
2048 只有上下左右四个方向。
真正复杂的,是在按下其中一个方向之前,把足够多的未来塞进那一瞬间。
项目链接
- GitHub:github.com/ziap/2048-ai
- License:MIT
