标签相关文章

这个标签暂时没有关联文章。

2048-ai_项目介绍

只有上下左右四个方向,为什么这个 2048 AI 背后塞进了这么多算法? 如果让你写一个会玩 2048 的程序,你会怎么做? 最直接的办法大概是写几条规则:大数字尽量放角落、不要轻易打乱顺序、空格越多越好。这样的程序确实能玩,甚至可能比不少随手乱划的人更稳定。但问题很快就会出现——当棋盘被挤得只剩几个空位时,到底该向左,还是向下?眼前两步都能合并,哪一步

只有上下左右四个方向,为什么这个 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。

如果两个位置等概率,那么这个动作的期望评分就是:

TEXT1 行
100 × 0.5 + 60 × 0.5 = 80

再对“向右”“向上”“向下”分别做同样的事情,AI 就能比较哪个动作拥有更好的长期期望。

当然,真实搜索远比这个例子复杂。它要继续向后推演很多层,而每多看几步,状态数量都会迅速膨胀。

所以接下来的问题比 Expectimax 本身还重要:

怎么让它算得足够快?


棋盘只有 16 格,但项目并没有老老实实用一个二维数组

很多人第一次实现 2048,会自然地写出一个 4 × 4 数组。

这当然没问题。

但如果一个棋盘状态需要被复制十次、比较一百次、移动一千次,那也没什么问题;如果搜索过程中这些操作要发生几百万、几千万次,表示方法本身就开始决定性能。

2048-ai 的 Board.zig 里,核心棋盘直接是一句:

ZIG1 行
data: u64,

也就是说,一整个 4×4 棋盘被压进了一个 64 位整数。

每个格子占 4 bit,也就是一个 nibble。16 个格子刚好:

TEXT1 行
16 × 4 bit = 64 bit

这里存的并不是方块表面的数字本身,而是它的“等级”。例如可以把 2 看成等级 1、4 看成等级 2、8 看成等级 3……这样一个 4 bit 小格就足以覆盖搜索所需的大量状态。

这类表示通常被叫作 bitboard。

它的好处不是“看起来很极客”,而是很多关键操作都变得特别便宜。

判断棋盘是否相同?比较一个 64 位整数。

复制棋盘?复制一个 64 位整数。

计算哈希?直接围绕这个整数做乘法和位移。

找空格?源码甚至通过连续的位运算,把“哪些 nibble 是 0”直接变成一个掩码。

再往下,行列转置也不是构建新数组逐格交换,而是通过掩码、异或和移位完成。

当这些操作位于搜索树最内层时,少创建几个对象、少跑几层循环,累积起来就是非常实际的性能差距。


连“滑动一行”都不想现场计算:65536 种情况提前算完

bitboard 之后,还有一个更典型的性能优化:lookup table,查找表。

想象一行 2048:

TEXT1 行
2  2  4  0

向右移动时,需要做压缩、判断相邻数字、合并、再次排列。

这些规则本身并不复杂,但搜索树会一次又一次处理各种行。如果每遇到一行都重新跑完整逻辑,时间就被大量重复的小计算吃掉了。

项目干脆把一行的所有可能状态提前算好。

一行有 4 个格子,每个格子 4 bit,因此一整行就是 16 bit。

16 bit 一共有:

TEXT1 行
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 进一步把搜索树前沿拆成一批任务。

可以把过程理解成:

TEXT13 行
当前棋盘
   ↓
先展开出一批需要深入评分的子局面
   ↓
放进任务池
   ↓
多个 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^151639.1 moves/s3138380.0%9.1%72.1%95.8%
2^17419.0 moves/s3891800.0%21.6%85.0%97.5%
2^19125.9 moves/s4681090.1%39.1%91.1%98.9%
2^2125.5 moves/s5309700.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。

编译优化版本:

Shell1 行
zig build --release=fast

编译完成后,命令行程序位于:

Shell1 行
zig-out/bin/2048

直接运行即可,也可以添加参数:

TEXT5 行
-i, --iter <u32>     运行多少局,默认 1
-b, --budget <u32>   每步处理预算,默认 524288
-t, --threads <u32>  线程数,默认自动
-s, --seed <bytes>   随机数种子,默认随机
-h, --help           查看帮助

例如想固定随机种子、批量运行,可以围绕 --iter、--threads 和 --seed 组合。

seed 的意义尤其值得注意。很多“AI 玩游戏”的演示看起来很强,但如果每次随机过程都不同,就很难准确比较两个版本到底谁更好。

固定 seed 后,同一套随机序列可以再次出现,更适合做回归测试和 benchmark。

网页版本项目已经提供在线页面:

ziap.github.io/2048-ai

如果想本地运行网页,在完成构建后,用普通 HTTP Server 就可以,例如:

Shell1 行
python3 -m http.server 8080

然后浏览器打开:

TEXT1 行
http://localhost:8080

一个小游戏,最后变成了一堂性能工程课

如果只看结果,2048-ai 就是一个很会玩 2048 的程序。

但顺着源码看下去,你会发现它真正有意思的部分几乎都发生在“AI”这两个字之外。

Expectimax 决定程序该如何思考未来。

启发式函数决定程序没法继续想时,怎样判断眼前局面。

bitboard 决定状态怎样被压缩和搬运。

lookup table 把重复操作变成一次数组访问。

transposition table 让算过的局面尽量别再算一遍。

formation pruning 把明显不值得展开的方向尽早砍掉。

受预算约束的 BFS 帮它决定这一个局面到底值得看多深。

Zig 和 WebAssembly 让这些计算可以高效落进浏览器,而 worker pool 又把一棵巨大的搜索树拆成可以同时处理的小块。

最后你会发现,这个项目并没有一个“突然让 AI 变聪明”的神奇技巧。

它更像很多高性能程序真实的样子:几十个并不神秘的决定,层层叠加,最后把原本算不动的东西推到了能实时运行的程度。

2048 只有上下左右四个方向。

真正复杂的,是在按下其中一个方向之前,把足够多的未来塞进那一瞬间。


项目链接

相关文章