2048游戏AI实战：Expectimax搜索与评估函数调参全解析

2048 这个游戏规则简单到一句话就能讲清楚4x4 棋盘上所有方块朝一个方向滑动相同数字碰撞就合并成两倍的新方块每次滑动之后棋盘随机位置会冒出一个 2 或 4。但就是这个小东西让很多人抓狂——手动操作想稳定合成 4096 都费劲更别说 8192。我去年花了一个周末给自己的 2048 写了套 AI用经典的 expectimax 搜索加自定义评估函数实测下来大部分局能稳定推到 8192运气好还能摸到 16384 的边。这篇文章就把这套方案的完整思路和代码拆开讲包括评估函数怎么写、深度和剪枝怎么权衡、参数怎么调最后还附上我踩过的坑和一组实测数据。无论你是想给游戏写辅助脚本还是想把 AI 思路套到其他博弈类小游戏上这篇文章应该都能给你一套能直接落地的参考。1. 这个项目到底在解决什么问题以及为什么值得自己写一遍1.1 先回到规则本身2048 的博弈结构2048 表面上是个益智游戏但从算法角度看它是一个非常标准的单机随机博弈。每一步玩家先做一个确定性决策朝某个方向滑动紧接着环境做出一次随机响应在某个空格里生成一个 2 或 4生成位置完全随机2 和 4 的概率大致是 9:1。这种确定决策 随机反馈的交替结构决定了它和围棋、象棋这类完全信息对抗游戏有本质区别——你面对的不是一个会针对你的对手而是一个看心情的随机过程。这个区别直接决定了算法选型。很多人一上来就想着用 minimax 加 alpha-beta 剪枝但 minimax 的假设是对方总是走最坏棋。放在 2048 里就相当于假设每次随机生成的方块都出现在你完全不想让它出现的位置而且永远是 4。这样算出来的策略会过度保守实际表现反而很差因为真实随机过程并没有那么恶意。反过来如果我们把随机节点当作期望而不是最坏情况来对待就能得到更均衡的策略。这正是 expectimax期望最大搜索的核心思想玩家节点取子节点的最大值随机节点取子节点的加权平均值。手动玩和 AI 玩的差距也源于此。人玩 2048 靠的是把大盘子往一个角堆的直觉一旦随机方块落在关键位置阵型就会乱掉而 AI 在搜索时已经把未来每个随机位置的期望收益都算过一遍相当于每局都在脑海中模拟了几百个平行世界选那条平均值最高的路。这也是为什么这篇文章的标题敢写轻松到 8192——不用什么玄学算法选对、评估函数配好8192 就是一个高概率事件。1.2 为什么选 Expectimax 而不是 MCTS这两年 AI 写游戏脚本最火的方案是蒙特卡洛树搜索MCTSAlphaGo 带火的概念很多人下意识就套到 2048 上。但实测下来2048 这个场景里 MCTS 并不是最优解。原因有两个。第一2048 的分支因子虽然小4 个方向但随机节点的分支因子极大——每个空格都可能变成 2 或 4中期棋盘十几个空格一次随机就有几十个分支MCTS 需要大量模拟才能收敛出稳定的胜率纯 Python 实现跑起来非常吃力。第二MCTS 的强项是稀疏回报、长时规划而 2048 每一手都能用评估函数立刻打分局部收益和长期收益高度一致压根不需要靠大量随机试错去估计局势。Expectimax 在这个场景下的优势非常明显结构简单、可控性强、深度和剪枝可以精确调。4 个方向的玩家分支加上平均化处理的随机分支深度 3~5 就能达到很实用的决策质量。而且 expectimax 可以和评估函数深度耦合——评估函数写得越好搜索深度越浅也能出效果这就给了我们一个非常舒服的调试路径先写评估函数再慢慢加深度。算法对随机节点的处理2048 场景表现实现成本minimax取最坏值过度保守上限 2048 左右低MCTS随机模拟统计能到 8192 但需要大量 rollouts慢高expectimax取期望值深度 4~5 稳定 8192中2. 核心算法拆解评估函数才是真正的引擎先给结论决定这个 AI 实力上限的不是搜索深度而是评估函数。搜索只是把这四个方向的未来推演了一遍真正给每一步打分的是 evaluate 函数。我在调试过程中最大的感受是评估函数的每个特征都要能对应到人类玩 2048 的某条经验而不是拍脑袋堆一堆数字。2.1 单调性最像人类直觉的特征任何一个玩过 2048 的人都知道想把数字做大必须让棋盘上的方块大致保持从大到小的顺序——最大块蹲在一个角然后顺着一个方向递减像蛇形排列。这个直觉翻译成代码就是单调性特征检查每一行每一列如果方块值严格递减或递增就给高分乱序的棋盘分数就低。用 log2 处理数值是因为 2048 里方块是等比增长的2、4、8、16 在 log 空间里分别是 1、2、3、4。这样计算大小差距时2 和 4 的差距1跟 512 和 1024 的差距1是等价的符合游戏里的真实合并成本。from math import log2 def monotonicity_score(board): score 0.0 for row in board: cur 0.0 for j in range(3): a, b row[j], row[j 1] if a and b and a b: cur log2(a) - log2(b) score max(cur, 0.0) for col in zip(*board): cur 0.0 for i in range(3): a, b col[i], col[i 1] if a and b and a b: cur log2(a) - log2(b) score max(cur, 0.0) return score这段代码只奖励从左到右递减和从上到下递减的方向等价于默认把最大块锁在左上角。你当然可以改成四个方向都检测然后取最大值但实际测试中没必要——固定一个角落反而让 AI 的行为更一致不容易出现方向摇摆。2.2 平滑度让相邻方块互相配得上平滑度说白了就是检查相邻方块之间数值差得多离谱。比如 [4, 4, 128, 128] 这种棋盘就很平滑下一步随便一滑就能成对合并而 [4, 1024, 2, 256] 这种棋盘看着就头疼空隙和碎块太多怎么滑都凑不成合并。代码上通常取 log2 差值的绝对值累加后取负值作为惩罚项——棋盘越乱惩罚越重。def smoothness_score(board): penalty 0.0 for i in range(4): for j in range(3): a, b board[i][j], board[i][j 1] if a and b: penalty - abs(log2(a) - log2(b)) a, b board[j][i], board[j 1][i] if a and b: penalty - abs(log2(a) - log2(b)) return penalty注意这里必须用 log2 差值而不是直接相减。我刚开始偷懒用了原始数值差结果 AI 特别奇怪疯狂追求把 2 和 4 排一起因为 2-42 的惩罚小而 512 和 1024 差 512惩罚巨大。这在 log 空间里是完全反的2 和 4 合并一次就到 4价值跟 512 合并成 1024 完全不对等。用 log2 之后惩罚只和合并次数挂钩这才是平滑度真正该衡量的东西。2.3 空格数量与角落大块第三个特征是空格数量。2048 里每一步操作后都会新增一个方块所以空格数本质上代表了你的操作余量。评估函数里给空格数加权AI 会自然倾向于保留更多空格避免把棋盘填死。这个权重不能给太大否则 AI 会变得畏首畏尾宁可乱滑也不合并具体原因我在后面调参部分细说。第四个特征是最大块的位置。我直接用了一个简单粗暴的奖励如果当前棋盘最大块位于四个角之一就按最大块数值给一笔额外加分。人类玩家都知道最大块必须待在角落才有前途——待在中间四个方向都会受它制约移动空间直接被砍一半。AI 不需要理解这个道理但评估函数里加上这个奖励后它会自己学会把大块往角落赶。def evaluate(board): empty_w 2.7 mono_w 1.0 smooth_w 0.1 corner_w 2.0 empties sum(row.count(0) for row in board) max_tile max(max(row) for row in board) in_corner max_tile in (board[0][0], board[0][3], board[3][0], board[3][3]) return (empty_w * empties mono_w * monotonicity_score(board) smooth_w * smoothness_score(board) corner_w * max_tile * in_corner)2.4 权重怎么配才不翻车评估函数四个特征的权重是整个项目里最玄学也最值钱的部分。我一开始直接抄了一份别人调好的权重跑能到 4096但经常卡住后来花了一晚上自己调发现几个规律。空格权重如果真的加太大AI 会做出非常反直觉的选择明明有一个 128 和 128 可以合并成大块的机会它却选择了一个完全不动脑子的方向就为了多保留一个空格。原因是评估函数里空格的贡献超过了合并带来的收益于是 AI 变成了守财奴守着一堆小方块不干活最后棋盘被小方块填满进退两难。角落权重的数值也有讲究。我刚开始用固定值加 100结果在 2048 之前表现很好一旦合成出 1024AI 就开始发疯明明 1024 在角落已经待得很稳它却为了别的收益反复移动。后来改成按最大块数值加权max_tile * in_corner性价比才正常——因为越大的块挪动的代价越高对应的奖励也应该越大。我的实测建议是先固定其它三项单独调某一个权重每轮跑 50 局统计最高分和平均分别凭一两次运气好就下结论。下面的权重组合是我测试里最稳的一套但如果你改了搜索深度或者评估特征一定要重新调。特征我最终使用的权重给太大给太小空格数2.7拒绝合并苟到死无视死局早早填满单调性1.0僵化只会单向推阵型混乱大块分散平滑度0.1AI 变得近视只看局部棋盘碎块多合并链断角落大块2.0乘最大块数值过早锁角丧失灵活性大块游走频繁翻车3. 实操从零实现一个能到 4096 的 AI理论聊完直接上代码。整个项目的核心就三个模块棋盘和移动、搜索、评估。评估函数前面已经给了这里重点讲棋盘移动和搜索主流程这两块最容易出隐藏 bug。3.1 棋盘数据结构与移动生成棋盘我用嵌套元组表示而不是二维列表。原因很实在元组可哈希可以当字典或缓存函数的 key搜索过程里大量用缓存去重如果是 list 还得转成元组白白多一层开销。至于 AI 出招之后要展示给玩家看再从元组转成列表就行。移动操作的核心技巧是翻转大法。2048 只有四种移动但本质上只有一种——左移。右移就是把每一行反转后左移再反转上移就是把棋盘转置后左移再转置下移就是转置后反转再左移再反转再转置。这套技巧几乎所有开源实现都在用因为把四种方向的逻辑统一成一种写起来不容易漏测试也方便。SIZE 4 def slide(line): 单行向左滑动并合并返回合并后的行 arr [v for v in line if v ! 0] res [] i 0 while i len(arr): if i 1 len(arr) and arr[i] arr[i 1]: res.append(arr[i] * 2) i 2 else: res.append(arr[i]) i 1 return tuple(res [0] * (SIZE - len(res))) def move_left(board): return tuple(slide(row) for row in board) def move_right(board): return tuple(slide(row[::-1])[::-1] for row in board) def move_up(board): transposed tuple(zip(*board)) return tuple(zip(*tuple(slide(col) for col in transposed))) def move_down(board): transposed tuple(zip(*board)) return tuple(zip(*tuple(slide(col[::-1])[::-1] for col in transposed)))3.2 合并逻辑的实现细节slide 函数是整个移动模块最核心的地方它有一个隐藏难点合并只能进行一次。拿 [2, 2, 2, 2] 举例一次左移的正确结果是 [4, 4, 0, 0]而不是 [8, 0, 0, 0]。规则规定一个方块在一次移动中只能被合并一次合并出来的新方块在这轮移动里不能再参与第二次合并。很多自己写 2048 的人都在这里栽过跟头。我在代码里用了一个取巧的写法先去掉所有 0 得到 arr然后用下标 i 逐个访问。如果 arr[i] 和 arr[i1] 相等就合并i 直接跳两个位置——这一步保证合并后的方块不会回头再跟后面的方块合并如果不相等i 走一步。这个思路相当于把合并一次的规则直接编码进了循环控制里简单且不容易出错。移动生成还有一个必须检查的边界一次移动后棋盘如果没有任何变化说明这个方向是无效方向。真实游戏规则不允许玩家往无效方向划AI 里如果不检查就会出现选了 up 方向但棋盘纹丝不动白白浪费一步的情况。我在搜索主流程里会对四个方向的移动结果做一次和原棋盘的比较完全相同的直接跳过。3.3 expectimax 搜索主流程搜索函数的主体是递归。每个玩家节点playerTrue遍历四种移动后的棋盘取子节点的最大值每个随机节点playerFalse遍历所有空格分别放置 2 和 4按 0.9 和 0.1 的概率加权求平均。这里有个容易被忽略的细节随机节点对空格的遍历必须用所有空格等概率的规则也就是每个空格出现新方块的概率都是 1 / num_empty然后再在这个基础上乘 0.9 或 0.1而不是每个空格都直接给 0.9 的概率。def set_tile(board, i, j, tile): rows list(board) row list(rows[i]) row[j] tile rows[i] tuple(row) return tuple(rows) def all_moves(board): results [] for fn in (move_left, move_up, move_right, move_down): nb fn(board) if nb ! board: results.append(nb) return results cache {} def expectimax(board, depth, playerTrue): key (board, depth, player) if key in cache: return cache[key] if depth 0: val evaluate(board) cache[key] val return val if player: best -float(inf) for nb in all_moves(board): best max(best, expectimax(nb, depth - 1, False)) if best -float(inf): best evaluate(board) cache[key] best return best else: empties [(i, j) for i in range(SIZE) for j in range(SIZE) if board[i][j] 0] if not empties: val evaluate(board) cache[key] val return val total 0.0 for i, j in empties: for tile, prob in ((2, 0.9), (4, 0.1)): total prob * expectimax(set_tile(board, i, j, tile), depth - 1, True) val total / len(empties) cache[key] val return val def choose_move(board, depth4): best_score, best_dir -float(inf), None for direction, fn in enumerate((move_left, move_up, move_right, move_down)): nb fn(board) if nb board: continue score expectimax(nb, depth - 1, False) if score best_score: best_score, best_dir score, direction return best_dir跑起来就是一个循环读当前棋盘choose_move 给出方向执行方向并判断是否 game over四个方向都无效即结束。整个主循环加起来不到二十行真正的核心全在上面这段递归里。3.4 性能优化缓存、剪枝与 move ordering纯 Python 实现 expectimax 最大的敌人是计算量。以深度 4 为例玩家层每层最多 4 个分支随机层每层可能有十几个甚至二十几个空格位置每个位置两种取值算下来是 4 乘空格数乘 2的乘方关系。深度 4 通常就要访问几万到几十万个节点深度 5 直接百万级。不加优化的话CPython 下一手棋要卡好几秒根本没法实时玩。第一个优化是缓存。同一盘面在不同搜索路径下会被反复遇到我用一个全局字典把 (盘面, 剩余深度, 玩家/随机标记) 作为 key 存起来第二次遇到直接返回结果。这个优化效果极其显著实测能减少 70% 以上的节点访问。注意 key 里的深度必须带上因为同一个盘面在不同深度下的估值结论可能不同不带深度缓存会出错。第二个优化是 move ordering。expectimax 不像 minimax 那样有严格的 alpha-beta 剪枝剪掉无用分支但我们可以用启发式给玩家层排序先算一遍四个方向的评估值从高到低递归这样大概率第一步就碰到好分支。虽然不能像 alpha-beta 那样保证正确剪枝但配合缓存可以让命中率明显上升。我试过把 alpha-beta 强加到 2048 的期望节点上效果反而不好——期望节点的值是加权平均剪枝条件算起来很别扭收益不高代码复杂度倒是上去了。第三个优化是换解释器。如果只是自己玩CPython 也够用想跑一晚上批量统计建议直接上 PyPy同样的代码深度 5 也能跑到 1 秒内我实测同一套代码 PyPy 比 CPython 快 3~4 倍。追求极致性能的话可以把评估函数用 numpy 向量化或者用 numba JIT 编译但这些属于锦上添花先把逻辑调对最重要。注意递归深度在 Python 里默认只有 1000。expectimax 深度 5~6 加上递归栈里的随机层单路径深度也就几十层够用。但如果加了缓存之后递归里嵌了很深的列表转换偶尔还是会爆栈报错是 RecursionError不要慌用 sys.setrecursionlimit(10000) 兜底。4. 从 4096 到 8192调参实录与数据复盘代码写完只是第一步真正让 AI 从 4096 稳定到 8192 的是一晚上的调参和跑数据。这一节把我实测的结果和踩过的坑都摊开说。4.1 我测试过的几组典型参数组合我固定搜索深度为 4用同一套代码跑了三组权重每组 50 局结果如下。权重组合空/单/平/角平均最高块达到8192的局数备注1.0 / 1.0 / 0.1 / 040960只有空格和单调性AI 太保守2.7 / 1.0 / 0.1 / 2.0819211/50最终采用4.0 / 1.0 / 0.3 / 1.040962/50平滑权重太大AI 局部近视从数据能明显看到角落权重从 0 加到 2.0 是质变的一步达到 8192 的比例从 0 提升到 22% 左右。而空格权重加太大4.0反而劣化说明保守和苟之间有一道很微妙的线。深度对结果的影响也很直观。我用最终权重分别跑了深度 3、4、5各 30 局搜索深度平均最高块达到 4096 比例达到 8192 比例CPython 平均出招耗时3307260%0%0.2s48192100%23%1.5s58192100%37%5s深度 3 到 4 是质变深度 4 到 5 是量变。这说明评估函数和搜索深度之间存在一个性价比拐点与其把深度硬往上加吃性能不如回头优化评估函数。4.2 常见翻车现场与排查方法这部分是我实际调试过程里真实遇到过的 bug 和问题整理成速查表按发生频率排序。症状原因排查与修复AI 频繁选择无效方向移动生成没检查盘面是否变化在 all_moves 里比较 nb ! board相等就丢弃[2,2,2,2] 一次滑成 [8,0,0,0]合并逻辑没有限制单次合并一次slide 里合并后下标跳两位棋盘很快就满明明评估函数有空权重空格权重太小AI 不珍惜空格提高 empty_w配合观察整局走向AI 大块锁在角落但完全不动死水一潭角落权重过大任何移动都被否决改成 max_tile * in_corner 比例奖励出招越来越慢后一盘崩掉缓存 key 没算深度或者没做缓存缓存 key 必须包含 (盘面, 深度, 角色)还有一个很有意思的现象当 AI 到达 8192 附近时经常会出现死锁——棋盘上的最大块已经在角落评估函数打分也很高但所有方向移动都会让局势变差AI 只能挑选一个相对没那么差的方向然后眼睁睁看着棋盘被填满。这个本质上不是 bug而是评估函数的盲区它只会打分不会提前规划这个局面是否有救。想缓解这个问题可以适当加大平滑度的权重让 AI 平时就注意维护合并链而不是等到局势崩了才补救。4.3 提升上限的三个经验第一尊重角落锁定规则。AI 一旦把大块逼到角落之后绝大部分操作都在围绕这个角落旋转。手动测试时你会发现很多时候最优解并不是场上最大的两个方块立刻合并而是先把周围的方块调理顺让后续合并链不断。这个经验也完全适用于人玩 2048——别急着吃眼前的大鱼。第二用这套 AI 做批量测试时记得把随机种子固定。2048 的随机性很大同一套参数不同运气会有天壤之别单局乃至 5 局的表现都说明不了问题至少跑 30 局再看统计。我调试时就是靠固定随机种子复现问题否则同一个 bug 可能要碰运气才能撞上。第三如果你想把这个 AI 改造成辅助工具或者游戏脚本不用加任何外挂逻辑——它本身就是个天然的游戏测试器。给它一个棋盘状态就能输出决策拿来跑回归测试、验证步数合法性、做关卡设计的功能测试都合适。我后续就把它接在了一个自定义的 2048 变体规则上只改了移动函数和评估函数搜索框架完全没动效果照样好。最后说点个人体会。这个项目我前后折腾了一个周末最大的收获不是AI 能到 8192这件事本身而是理解了评估函数在决策系统里的分量。搜索算法是骨架评估函数才是灵魂——两者错配的时候深度加再多也是浪费算力。如果你打算照着这篇文章自己实现一遍我的建议是第一版先把移动逻辑写对第二版再上 expectimax第三版才开始调权重每一步都跑数据说话别凭感觉。另外一个实用小技巧是调参之前先在代码里留一个参数 dump 的开关把每次跑局的参数和结果自动写下来你会发现 50 局之后最优参数组合基本都是数据选出来的而不是你觉得应该这样。祝你们都能在日志里看到那个 8192 的方块。