1. 项目概述从游戏到算法的挑战2048这个小游戏估计不少朋友都玩过甚至沉迷过。在一个4x4的格子里通过上下左右滑动让相同的数字合并目标是合成那个传说中的“2048”方块。规则简单上手极快但想玩到高分甚至想用程序自动玩到高分那就是另一回事了。今天我们不聊怎么用手指滑出高分我们来聊聊怎么让机器“思考”用算法找出最优的移动策略实现所谓的“最佳算法”。这听起来像是个纯粹的编程练习但背后涉及到的决策逻辑、状态评估和搜索策略其实是人工智能和博弈论里非常经典的课题。为什么一个简单的合并数字游戏会让算法设计变得棘手核心矛盾在于游戏的进程充满了不确定性。你每次滑动后系统会在空白处随机生成一个“2”或“4”。这意味着你无法完全预测未来几步的棋盘状态你的最优决策必须建立在对这种随机性的“期望”之上。这和我们下象棋、围棋这类完全信息、确定性博弈完全不同。所以当我们谈论“2048最佳算法”时我们本质上是在寻找一个策略能够在随机方块出现的干扰下最大化长期存活并达到高分的概率。这不是一个能找到绝对“必胜”解的问题而是一个优化期望收益的问题。网络上流行的算法从简单的贪心策略到复杂的Expectimax搜索都在尝试逼近这个“最佳”。接下来我们就一层层剥开这些策略的外壳看看它们是怎么“思考”的以及为什么有些方法就是比另一些更强大。2. 核心思路拆解从直觉到数学期望要实现一个强大的2048 AI我们不能只靠“感觉”来编程。我们需要把游戏的规则和我们的目标转化为计算机可以理解和计算的模型。这个过程就是算法设计的核心。2.1 问题建模把游戏变成搜索树首先我们要把2048游戏抽象成一个“博弈”问题。虽然我们是在和带有随机性的系统对弈但这个模型依然适用。状态State 当前4x4棋盘上所有数字的分布就是游戏的一个状态。这是算法进行所有计算的基础。玩家动作Player Action 我们的AI可以执行的操作即上、下、左、右四个方向的滑动。对手动作Opponent Action / Chance Node 这里的“对手”不是智能体而是游戏规则本身。在我们滑动之后“对手”的动作是在一个随机空白格子里放置一个“2”90%概率或“4”10%概率。这是一个“机会节点”代表环境的不确定性。终局状态Terminal State 当棋盘被填满且无法再进行任何有效合并时游戏结束。我们的目标就是尽可能推迟这个状态的到来并在此过程中获得高分。这样一来游戏过程就可以被看作是一棵交替进行的搜索树AI选择一个移动方向决策节点然后游戏随机放置一个新方块机会节点如此循环。我们的算法就是要在这棵庞大的、充满分支的树上找到从当前状态出发能导向最好“期望结局”的那条路径。2.2 评估函数算法的“价值观”搜索树可能非常庞大尤其是考虑多步以后我们不可能搜索到游戏结束。因此我们需要一个评估函数Evaluation Function来给某个中间状态“打分”判断这个局面是好是坏。这个函数是算法性能的关键它定义了AI的“偏好”。一个好的2048评估函数通常会综合考虑以下几个因素并通过加权求和得到一个总分空格子数量Empty Tiles 这是最重要的指标之一。更多的空格意味着更多的操作空间和容错率是维持游戏生命的基础。通常直接给予较高的正权重。单调性Monotonicity 鼓励数字按大小顺序排列。例如理想情况是每一行的数字从左到右递增或递减每一列从上到下递增或递减。这样在滑动时更容易合并。计算时可以检查相邻格子的差值差值越小趋势一致得分越高。平滑度Smoothness 衡量相邻格子数字的接近程度。数值相近的格子挨在一起意味着下一次滑动时它们有合并的潜力。这与单调性相关但不完全相同。最大数值的位置Max Tile Position 通常希望最大的数字待在角落比如左上角。因为角落位置最稳定不容易被其他数字“卡住”并且便于构建一个单调递减或递增的行/列将其他数字向这个角落驱动。合并潜力Merge Potential 评估当前局面有多少对相同的数字是相邻的可以直接合并。注意 评估函数的设计是一门艺术没有绝对的标准答案。不同的权重组合会导致AI表现出不同的风格有的激进追求高分冒险有的保守追求存活稳健。通常需要通过大量对局测试来调整和优化这些权重。2.3 算法选型从简单到复杂有了问题模型和评估函数我们就可以选择具体的搜索算法了。根据对“对手”随机性建模方式的不同主要有以下几种策略贪心算法Greedy思路 只看一步。对当前状态分别模拟上、下、左、右四个动作然后用评估函数给执行动作后得到的状态打分忽略之后随机生成新方块的影响选择立即能带来最高分的那个动作。优点 速度极快计算量小。缺点 非常短视。因为它不考虑随机方块落下后的局面很容易走入死胡同。例如一个动作可能立刻创造很多空格高分但形成的棋盘结构很差导致下一步无论怎么走都会崩盘。Minimax 算法思路 假设对手随机性是“恶意”的总是做出对你最不利的选择即在新空格中生成对你最不利的数字通常是“4”在最坏的位置。算法会在决策层我方选择最大化评估分在对手层随机性选择最小化评估分。在2048中的问题 Minimax 假设了一个智能的、恶意的对手但2048的随机生成是“中性”的它只是按概率分布并非有意害你。因此用Minimax会过度悲观导致AI过于保守性能反而不如一些考虑概率的算法。Expectimax 算法核心推荐思路 这正是为2048这类带有随机性的游戏量身定做的。它不假设对手恶意而是理性地对待随机性。在决策层我方我们选择最大化期望效用的动作。在机会节点随机放块我们计算所有可能随机结果在每个空白格放“2”或“4”的评估分的概率加权平均值。优势 它更准确地建模了2048的随机过程。AI会选择一个动作这个动作在平均意义上考虑所有可能的随机结果及其概率能带来最好的未来期望。这是目前公认的、不依赖深度学习的最优基础算法框架。蒙特卡洛树搜索MCTS思路 通过大量随机模拟Rollout来评估某个动作的长期价值。从当前状态开始随机选择动作包括AI的动作和随机放块直到游戏结束记录得分。反复模拟多次用每个动作带来的平均模拟得分作为其价值依据。在2048中的应用 MCTS可以很好地处理随机性和庞大的状态空间并且不需要精心设计评估函数因为以最终得分作为反馈。但其计算量很大需要优化如UCT公式才能在实际时间限制内达到好的效果。它常与Expectimax结合用于评估搜索树叶子节点的价值。对于实现一个强大的2048 AIExpectimax搜索配合一个精心调优的评估函数是经典且有效的方案。下面我们就深入Expectimax的实现细节。3. Expectimax算法实现详解Expectimax是算法的骨架评估函数是血肉。我们将分步构建这个AI大脑。3.1 算法框架与伪代码Expectimax搜索是一个递归过程。我们需要定义两个函数expectimax(state, depth)用于计算一个状态的期望值以及get_best_move(state)用于选择最优动作。首先我们看核心的递归函数function expectimax(state, depth): if depth 0 or state is terminal: return evaluation_function(state) // 到达搜索深度或终局返回当前状态评估值 if its AIs turn (max node): best_value -∞ for each possible move (up, down, left, right) in state: if move is valid: new_state apply_move(state, move) // 注意滑动后立刻进入机会节点随机放块 value expectimax(new_state, depth, chance_nodeTrue) best_value max(best_value, value) return best_value else if its chance node: expected_value 0 empty_cells get_empty_cells(state) for each cell in empty_cells: // 考虑放置‘2’的情况 (90%概率) new_state_2 place_tile(state, cell, 2) expected_value 0.9 * expectimax(new_state_2, depth-1, max_nodeTrue) / len(empty_cells) // 考虑放置‘4’的情况 (10%概率) new_state_4 place_tile(state, cell, 4) expected_value 0.1 * expectimax(new_state_4, depth-1, max_nodeTrue) / len(empty_cells) return expected_value参数说明state: 当前游戏状态棋盘。depth: 剩余搜索深度。深度为N意味着AI将向前看N步自己的动作中间穿插着随机事件。max node: AI决策层目标是最大化评估值。chance node: 随机事件层目标是计算所有可能结果的期望值。然后是选择动作的入口函数function get_best_move(state, search_depth3): best_move None best_value -∞ for each move in [UP, DOWN, LEFT, RIGHT]: if move is valid for state: new_state apply_move(state, move) // AI先走一步 // 评估这个动作后的期望值传入深度时注意AI已走一步接下来是随机事件 move_value expectimax(new_state, depthsearch_depth, node_typechance_node) if move_value best_value: best_value move_value best_move move return best_move深度理解 这里的search_depth参数需要仔细理解。假设search_depth3那么搜索树的结构将是AI动作 - 随机事件 - AI动作 - 随机事件 - AI动作 - 评估状态。也就是说AI实际上向前预测了三次自己的决策。深度越大AI看得越远但计算量呈指数级增长。3.2 评估函数的设计实例一个经典且效果不错的评估函数可以这样实现以Python风格伪代码表示def evaluation_function(board): 评估当前棋盘状态。 返回一个分数分数越高表示局面越好。 empty_weight 1000000 # 空格权重通常最大 smooth_weight 10 # 平滑度权重 mono_weight 1000 # 单调性权重 max_tile_weight 100 # 最大数位置权重鼓励在角落 empty_score len(get_empty_cells(board)) * empty_weight smooth_score 0 for i in range(4): for j in range(4): if board[i][j] ! 0: # 检查右邻居和下邻居 value math.log(board[i][j], 2) # 对数值更易处理 if j 3 and board[i][j1] ! 0: neighbor_value math.log(board[i][j1], 2) smooth_score - abs(value - neighbor_value) if i 3 and board[i1][j] ! 0: neighbor_value math.log(board[i1][j], 2) smooth_score - abs(value - neighbor_value) smooth_score * smooth_weight mono_score 0 # 检查行单调性例如希望从左到右递减 for i in range(4): row [math.log(x, 2) if x!0 else 0 for x in board[i]] # 计算从左到右的差值如果递减则为正贡献 for j in range(3): if row[j] row[j1]: mono_score 1 else: mono_score - 1 # 检查列单调性例如希望从上到下递减 for j in range(4): col [math.log(board[i][j], 2) if board[i][j]!0 else 0 for i in range(4)] for i in range(3): if col[i] col[i1]: mono_score 1 else: mono_score - 1 mono_score * mono_weight # 鼓励最大数在角落 max_tile_score 0 max_val max(max(row) for row in board) max_positions [(i,j) for i in range(4) for j in range(4) if board[i][j]max_val] for pos in max_positions: if pos in [(0,0), (0,3), (3,0), (3,3)]: # 四个角落 max_tile_score max_tile_weight total_score empty_score smooth_score mono_score max_tile_score return total_score实操心得 这个评估函数中empty_weight设置得非常高这是经过实践检验的。在游戏早期和中期保证足够的空格是生存的第一要务。math.log(x, 2)的使用是个技巧因为2048的数字都是2的幂取以2为底的对数后数字2变成14变成22048变成11……这样处理使得数值增长线性化计算平滑度和单调性时更合理。3.3 搜索优化剪枝与启发纯的Expectimax搜索深度每增加1计算量就会剧增。为了在有限时间内搜索得更深必须优化。Alpha-Beta 剪枝 传统的Alpha-Beta剪枝适用于Minimax因为它依赖于“对手最优”的假设可以剪掉那些对手绝不会让你走到的分支。但在Expectimax的机会节点我们需要计算所有分支的期望值无法确定哪个分支是“坏”的因为对手是随机的所以标准的Alpha-Beta剪枝不直接适用于Expectimax。不过存在一些变体如*Expectimax with Alpha-Beta Pruning under Assumption of*但实现复杂。深度限制与迭代加深 这是最直接的方法。设定一个最大搜索深度如3-5层。为了平衡速度和效果可以采用迭代加深先深度1搜索如果时间还有剩余再深度2搜索依此类推直到时间用完。这样能保证在时间限制内给出当前能算出的最好答案。动作排序Move Ordering 在max node尝试动作的顺序很重要。优先尝试评估函数看来更好的动作这样有可能更快地找到高分分支虽然不能像Minimax那样剪枝但能帮助算法更快地聚焦于有希望的区域。例如可以先对四个方向滑动后的状态做个快速评估只调用很浅的搜索或静态评估按分数从高到低排序再进入深度搜索循环。预计算与缓存Transposition Table 不同的动作顺序可能导致相同的棋盘状态。我们可以使用一个哈希表例如Zobrist Hashing来缓存已经计算过的棋盘状态及其对应的期望值。当再次遇到相同状态时直接返回缓存值避免重复计算。这对于2048非常有效因为状态空间虽大但在一次搜索中重复状态可能不少。机会节点采样Chance Node Sampling 在机会节点严格计算每一个空白格放置“2”和“4”的期望值计算量很大。一种优化是进行随机采样不遍历所有可能性而是随机生成若干个比如10-20个可能的后续状态根据概率分布计算这些样本的期望值平均值来近似整体的期望。这能显著减少分支因子但会引入噪声。4. 完整实现流程与代码结构让我们把上述所有部分组合起来勾勒出一个可运行的2048 AI核心结构。这里以Python为例因为它语法清晰适合表达算法逻辑。4.1 游戏状态表示与基础操作首先我们需要定义棋盘和基本操作。import numpy as np import random import math class Game2048: def __init__(self): self.grid np.zeros((4, 4), dtypeint) self.score 0 self.add_random_tile() self.add_random_tile() def add_random_tile(self): 在随机空白位置添加一个2(90%)或4(10%)。 empty_cells list(zip(*np.where(self.grid 0))) if empty_cells: i, j random.choice(empty_cells) self.grid[i][j] 2 if random.random() 0.9 else 4 def move(self, direction): 执行滑动操作。 direction: 0,1,2,3 代表 上、下、左、右。 返回移动是否改变了棋盘。 moved False # 为了简化这里以向左移动为例其他方向可通过旋转矩阵复用逻辑 # 实际实现需要处理四个方向 # 1. 去除每行的零使数字靠左 # 2. 从左到右合并相邻相同数字 # 3. 再次靠左对齐 # 记录本次移动是否合并了格子以更新分数 # ... # 如果棋盘有变化则 movedTrue return moved def get_valid_moves(self): 返回当前状态下所有合法移动的方向列表。 valid_moves [] for dir in range(4): # 模拟向dir方向移动检查棋盘是否变化 # ... if would_change: valid_moves.append(dir) return valid_moves def is_terminal(self): 判断游戏是否结束。 # 如果有空格游戏肯定没结束 if np.any(self.grid 0): return False # 检查是否还有可合并的相邻格子 for i in range(4): for j in range(4): val self.grid[i][j] if j 3 and val self.grid[i][j1]: return False if i 3 and val self.grid[i1][j]: return False return True4.2 Expectimax搜索主体实现接下来是实现带缓存的Expectimax搜索函数。class AI2048: def __init__(self, search_depth3): self.search_depth search_depth self.cache {} # 用于状态缓存的字典 def hash_grid(self, grid): 生成棋盘的哈希键用于缓存。简单实现可以用tuple。 return tuple(grid.flatten()) def expectimax(self, grid, depth, is_chanceFalse): 递归计算期望值。 # 1. 终止条件 if depth 0: return self.evaluate(grid) # 检查缓存 state_key (self.hash_grid(grid), depth, is_chance) if state_key in self.cache: return self.cache[state_key] # 2. 机会节点随机放块 if is_chance: expected_value 0.0 empty_cells list(zip(*np.where(grid 0))) if not empty_cells: # 没有空格直接评估 value self.evaluate(grid) self.cache[state_key] value return value for (i, j) in empty_cells: # 放2 new_grid_2 grid.copy() new_grid_2[i][j] 2 exp_2 self.expectimax(new_grid_2, depth-1, is_chanceFalse) # 放4 new_grid_4 grid.copy() new_grid_4[i][j] 4 exp_4 self.expectimax(new_grid_4, depth-1, is_chanceFalse) # 加权平均注意概率要除以空格总数 expected_value (0.9 * exp_2 0.1 * exp_4) / len(empty_cells) self.cache[state_key] expected_value return expected_value # 3. 最大节点AI决策 else: best_value -float(inf) # 获取所有合法移动 for move_dir in range(4): # 0:上, 1:下, 2:左, 3:右 # 模拟移动得到新网格 new_grid, moved self.simulate_move(grid, move_dir) if not moved: continue # 此方向移动无效跳过 # 移动后轮到机会节点随机放块 value self.expectimax(new_grid, depth, is_chanceTrue) if value best_value: best_value value # 如果没有任何有效移动理论上在非终局状态不应发生则评估当前状态 if best_value -float(inf): best_value self.evaluate(grid) self.cache[state_key] best_value return best_value def get_best_move(self, grid): 根据当前棋盘返回最佳移动方向。 best_move None best_value -float(inf) self.cache.clear() # 开始新一轮搜索前清空缓存可选也可全局缓存 for move_dir in range(4): new_grid, moved self.simulate_move(grid, move_dir) if not moved: continue # 注意AI移动后深度不减但节点类型变为机会节点 move_value self.expectimax(new_grid, self.search_depth, is_chanceTrue) if move_value best_value: best_value move_value best_move move_dir return best_move # 返回方向索引 def simulate_move(self, grid, direction): 模拟向某个方向移动返回新网格和是否移动的布尔值。 # 这里需要实现具体的移动和合并逻辑返回新的网格副本 # 实现略同Game2048.move的逻辑但不改变原grid返回新grid pass def evaluate(self, grid): 评估函数同前文设计实例。 # 实现略参考3.2节 pass4.3 主循环与性能调优最后将AI和游戏循环结合起来。def main(): game Game2048() ai AI2048(search_depth3) # 深度3通常能在合理时间内运行 while not game.is_terminal(): print(f当前分数: {game.score}) print(game.grid) # AI决策 best_dir ai.get_best_move(game.grid.copy()) # 传入副本避免污染 dir_map {0: 上, 1: 下, 2: 左, 3: 右} print(fAI选择: {dir_map.get(best_dir, 无)}) if best_dir is not None: game.move(best_dir) game.add_random_tile() else: print(无有效移动游戏结束) break print(f游戏结束最终分数: {game.score}) print(f最大方块: {np.max(game.grid)}) if __name__ __main__: main()性能调优要点深度选择 在普通电脑上深度3是实时操作的可行选择。深度4会导致明显的思考延迟几秒到几十秒深度5通常就太慢了。迭代加深策略可以动态调整深度。缓存策略 缓存(grid_hash, depth, is_chance)三元组。注意在get_best_move开始时清空缓存是安全的因为每次决策都是基于全新的棋盘。如果实现迭代加深缓存可以复用。评估函数优化evaluate函数会被调用数百万次必须高效。使用NumPy向量化操作、预先计算对数表log2_table {2:1, 4:2, 8:3, ...}可以大幅提升速度。剪枝启发 虽然不能严格剪枝但在max node如果某个动作后的状态空格数极少例如少于2个且评估分远低于当前最佳值可以提前跳过对该动作的深度搜索这是一种激进的启发式策略。5. 常见问题、调试与进阶策略即使实现了上述所有代码你的AI可能一开始表现并不理想。别急调试和优化是必经之路。5.1 算法不工作或表现差排查清单移动模拟错误 这是最常见的Bug来源。确保你的simulate_move函数100%正确还原了游戏规则先按方向挤压再合并相邻相同数字每对数字在一次滑动中只合并一次最后再挤压。用几个简单的手动案例测试如一行[2,2,4,4]向左滑动结果应为[4, 8, 0, 0]。评估函数权重失衡 如果AI总是很快死亡可能是empty_weight不够高或者单调性/平滑度的负惩罚太强。尝试极端设置只使用空格数量作为评估函数看AI是否能长期存活。然后逐步加入其他因素观察效果变化。搜索深度错觉 深度增加不一定带来更好表现。有时深度2比深度3好因为深度3的AI可能会为了一个“看起来”更好的未来期望而做出一步导致当前局面风险激增的决策。深度1贪心是一个重要的基准线你的Expectimax必须稳定地超越它。缓存污染 确保缓存键(grid_hash, depth, is_chance)是唯一的。grid_hash必须能唯一代表棋盘状态包括数字位置和值。is_chance布尔标志必须包含在键中因为同一个网格在“决策节点”和“机会节点”的价值是不同的。随机性处理错误 在机会节点必须为每一个空白格计算放置2和4的期望并按照概率0.9和0.1以及空白格数量进行平均。公式是期望值 Σ_{每个空白格} [ (0.9 * 价值(放2) 0.1 * 价值(放4)) / 空白格总数 ]。忘记除以空白格总数是一个常见错误。5.2 性能瓶颈与优化实测当你的AI运行缓慢时使用性能分析工具如Python的cProfile找出热点。通常瓶颈在递归调用次数 深度是主因。尝试降低深度或启用动作排序让算法优先搜索好分支。评估函数计算 优化evaluate函数避免在循环中进行对数运算使用查表法。网格复制与哈希计算simulate_move和哈希计算hash_grid会被频繁调用。确保网格复制grid.copy()和哈希计算是高效的。对于4x4小数组直接使用tuple(grid.flatten())作为哈希键通常是可行的。一个实测技巧记录并分析决策日志。让AI在运行时打印出它考虑的几个动作及其计算的期望值。观察它是否做出了反直觉的决策。例如一个明明能立即合并大数字的动作为什么期望值反而低这能帮你反向调试评估函数的缺陷。5.3 超越经典Expectimax混合策略与学习如果经典Expectimax评估函数的天花板已经触及例如稳定达到4096但难以突破8192可以考虑以下进阶方向Expectimax作为局部分支决策器 不全程使用深度搜索。在游戏早期空格多可以使用更简单的策略或浅层搜索以节省时间。在游戏中后期空格少决策关键切换到深度更大的Expectimax。蒙特卡洛树搜索MCTS作为评估器 在Expectimax搜索树的叶子节点当深度耗尽时不直接调用静态评估函数evaluate()而是启动一个快速的MCTS模拟例如进行50-100次随机模拟到游戏结束用平均模拟得分作为该叶子节点的价值评估。这结合了MCTS的长期规划能力和Expectimax的精确决策框架。机器学习优化评估函数 手动调参总是有限的。可以使用强化学习如TD-Learning或进化算法如遗传算法来优化评估函数中的权重。让AI自我对弈成千上万局以“平均达到的最大方块数”或“最终得分”作为适应度函数自动寻找最优的权重组合。你会发现机器找到的权重可能和你直觉设计的很不一样。神经网络作为价值函数 这是目前顶级AI采用的方法如著名的2048 AI “2048-AI”。使用深度神经网络直接学习一个函数V(grid) - value来预测当前局面的胜率或期望得分。训练数据可以通过自我对弈生成。在搜索时用神经网络代替手写的评估函数可以处理更抽象、更复杂的局面特征潜力更大。从贪心算法到Expectimax你已经构建了一个会“思考”的2048 AI。它能理解随机性能做多步规划其核心思想——在不确定环境中最大化期望收益——远不止于游戏。调参和优化的过程就像在打磨一个决策系统每一次对权重的调整都是你对这个游戏“策略本质”理解的一次深化。当看到AI稳稳地合成那个4096甚至8192方块时那种成就感或许就是算法最迷人的地方。