2048 的难点并不只是“尽量合并大数字”,而是在每次移动后还会随机出现新方块。一个只看眼前得分的贪心策略很容易把棋盘压死,因此更实用的 AI 需要同时考虑未来可移动空间、数字排列结构以及随机事件的期望结果。
本文给出一套适用于经典 4×4 规则的 Expectimax 搜索 + 启发式评估 实现。它不是对所有未来状态进行穷举得到的数学意义上的全局最优策略,而是一种在计算量与决策质量之间较均衡的近似最优方案。
“最优”具体指什么
如果把整局 2048 从当前状态一直搜索到游戏结束,理论上可以为每个状态求出最优动作。但实际状态空间和随机分支都很大,完整求解通常不适合作为实时决策算法。
因此,工程实现通常采用有限深度搜索:
- 玩家节点枚举上、下、左、右四个合法动作。
- 随机节点枚举新方块可能出现的位置。
- 对每个空位分别考虑生成
2和4的概率。 - 搜索达到深度限制后,用启发式函数估计棋盘质量。
- 选择期望价值最大的动作。
这里的“近似最优”是指:在给定搜索深度、概率模型和启发式函数的条件下,选择期望评价最高的动作,而不是声称已经求出整个 2048 游戏的全局最优策略。
为什么使用 Expectimax
2048 中的新方块不是一个会故意让玩家失败的对手,而是随机事件。因此,随机节点不应该像 Minimax 那样选择“最坏情况”,而应该计算所有随机结果的数学期望。
玩家节点可写为:
其中:
- 是当前棋盘;
- 是所有合法移动;
- 是执行动作后的棋盘;
- 是本次合并得到的即时分数;
- 是剩余搜索深度。
随机节点可写为:
本实现按经典概率模型处理新方块:
- 在所有空位中均匀选择一个位置;
- 生成
2的概率为0.9; - 生成
4的概率为0.1。
如果目标游戏的生成规则不同,应同步修改源码中的概率模型。
启发式评估
搜索不可能无限向后展开,所以必须在叶子节点估计棋盘质量。本实现组合多个指标,而不是只看当前最大数字。
| 指标 | 作用 |
|---|---|
| 空格数量 | 保留操作空间,降低棋盘被堵死的风险 |
| 单调性 | 鼓励较大的方块沿行或列形成稳定梯度 |
| 平滑度 | 鼓励相邻方块的数量级接近,便于后续合并 |
| 可合并对数 | 奖励当前仍存在直接合并机会的局面 |
| 最大方块 | 对整体进度提供基础奖励 |
| 最大方块在角落 | 鼓励大数字稳定在边角,减少结构被打乱 |
评估函数形式为:
这些权重属于可调参数,不存在对所有实现、所有搜索深度都唯一最优的一组固定值。增加搜索深度、改变概率模型或改变棋盘规则后,都可能需要重新调参。
搜索深度与缓存
Expectimax 的主要成本来自随机节点。假设当前有 个空位,那么一次随机生成最多产生约 个子状态,再与玩家节点的最多四种移动组合,分支数会迅速增长。
源码采用两个办法控制计算量:
- 自适应深度:空格较多时搜索 2 层,棋盘较拥挤时搜索 3 层。
- 状态缓存:使用
lru_cache复用相同棋盘与深度的计算结果。
拥挤局面通常更危险,也更值得增加搜索深度;而开局空位很多,随机分支更多,较浅搜索能显著降低开销。
完整 Python 源码
下面的代码仅使用 Python 标准库,包含:
- 4×4 棋盘表示;
- 四方向移动与合并;
- 合法动作判断;
- 随机生成方块;
- 启发式评估函数;
- Expectimax 玩家节点与随机节点;
- 自适应搜索深度;
- 自动对局循环。
from __future__ import annotations
from dataclasses import dataclass
from functools import lru_cache
import math
import random
SIZE = 4
DIRECTIONS = ("left", "right", "up", "down")
Board = tuple[int, ...]
def rows(board: Board) -> list[list[int]]:
return [list(board[r * SIZE:(r + 1) * SIZE]) for r in range(SIZE)]
def flatten(grid: list[list[int]]) -> Board:
return tuple(cell for row in grid for cell in row)
def transpose(grid: list[list[int]]) -> list[list[int]]:
return [list(col) for col in zip(*grid)]
def merge_line_left(line: list[int]) -> tuple[list[int], int]:
"""Compress and merge one row to the left."""
values = [x for x in line if x != 0]
out: list[int] = []
gained = 0
i = 0
while i < len(values):
if i + 1 < len(values) and values[i] == values[i + 1]:
merged = values[i] * 2
out.append(merged)
gained += merged
i += 2
else:
out.append(values[i])
i += 1
out.extend([0] * (SIZE - len(out)))
return out, gained
def move(board: Board, direction: str) -> tuple[Board, int]:
"""Apply one move without spawning a random tile."""
grid = rows(board)
if direction == "left":
moved = [merge_line_left(row) for row in grid]
new_grid = [line for line, _ in moved]
gained = sum(score for _, score in moved)
elif direction == "right":
moved = [merge_line_left(list(reversed(row))) for row in grid]
new_grid = [list(reversed(line)) for line, _ in moved]
gained = sum(score for _, score in moved)
elif direction == "up":
cols = transpose(grid)
moved = [merge_line_left(col) for col in cols]
new_grid = transpose([line for line, _ in moved])
gained = sum(score for _, score in moved)
elif direction == "down":
cols = transpose(grid)
moved = [merge_line_left(list(reversed(col))) for col in cols]
new_cols = [list(reversed(line)) for line, _ in moved]
new_grid = transpose(new_cols)
gained = sum(score for _, score in moved)
else:
raise ValueError(f"unknown direction: {direction}")
return flatten(new_grid), gained
def valid_moves(board: Board) -> list[str]:
return [d for d in DIRECTIONS if move(board, d)[0] != board]
def empty_indices(board: Board) -> list[int]:
return [i for i, value in enumerate(board) if value == 0]
def spawn_tile(board: Board, rng: random.Random) -> Board:
empties = empty_indices(board)
if not empties:
return board
index = rng.choice(empties)
value = 2 if rng.random() < 0.9 else 4
data = list(board)
data[index] = value
return tuple(data)
def log_value(value: int) -> float:
return 0.0 if value == 0 else math.log2(value)
def smoothness(board: Board) -> float:
"""Prefer neighboring non-zero tiles with similar exponents."""
grid = rows(board)
penalty = 0.0
for r in range(SIZE):
for c in range(SIZE):
if grid[r][c] == 0:
continue
current = log_value(grid[r][c])
if c + 1 < SIZE and grid[r][c + 1] != 0:
penalty -= abs(current - log_value(grid[r][c + 1]))
if r + 1 < SIZE and grid[r + 1][c] != 0:
penalty -= abs(current - log_value(grid[r + 1][c]))
return penalty
def monotonicity(board: Board) -> float:
"""Reward rows and columns that are mostly ordered in one direction."""
grid = [[log_value(x) for x in row] for row in rows(board)]
score = 0.0
for row in grid:
inc = sum(max(0.0, row[i + 1] - row[i]) for i in range(SIZE - 1))
dec = sum(max(0.0, row[i] - row[i + 1]) for i in range(SIZE - 1))
score -= min(inc, dec)
for col in transpose(grid):
inc = sum(max(0.0, col[i + 1] - col[i]) for i in range(SIZE - 1))
dec = sum(max(0.0, col[i] - col[i + 1]) for i in range(SIZE - 1))
score -= min(inc, dec)
return score
def merge_potential(board: Board) -> int:
grid = rows(board)
pairs = 0
for r in range(SIZE):
for c in range(SIZE - 1):
if grid[r][c] != 0 and grid[r][c] == grid[r][c + 1]:
pairs += 1
for c in range(SIZE):
for r in range(SIZE - 1):
if grid[r][c] != 0 and grid[r][c] == grid[r + 1][c]:
pairs += 1
return pairs
def max_tile_in_corner(board: Board) -> bool:
maximum = max(board)
corners = (board[0], board[SIZE - 1], board[-SIZE], board[-1])
return maximum in corners
@lru_cache(maxsize=200_000)
def evaluate(board: Board) -> float:
empties = len(empty_indices(board))
maximum = max(board)
max_log = log_value(maximum)
return (
empties * 270.0
+ monotonicity(board) * 47.0
+ smoothness(board) * 3.0
+ merge_potential(board) * 25.0
+ max_log * 100.0
+ (700.0 if max_tile_in_corner(board) else 0.0)
)
@lru_cache(maxsize=500_000)
def player_value(board: Board, depth: int) -> float:
moves = valid_moves(board)
if depth <= 0 or not moves:
return evaluate(board)
best = -math.inf
for direction in moves:
next_board, gained = move(board, direction)
value = gained + chance_value(next_board, depth)
best = max(best, value)
return best
@lru_cache(maxsize=500_000)
def chance_value(board: Board, depth: int) -> float:
empties = empty_indices(board)
if depth <= 0 or not empties:
return evaluate(board)
cell_probability = 1.0 / len(empties)
expected = 0.0
for index in empties:
for tile, tile_probability in ((2, 0.9), (4, 0.1)):
data = list(board)
data[index] = tile
child = tuple(data)
expected += (
cell_probability
* tile_probability
* player_value(child, depth - 1)
)
return expected
def choose_depth(board: Board) -> int:
"""
Adaptive search depth:
- many empty cells: depth 2;
- crowded board: depth 3.
"""
empties = len(empty_indices(board))
return 3 if empties <= 6 else 2
def best_move(board: Board) -> str | None:
moves = valid_moves(board)
if not moves:
return None
depth = choose_depth(board)
best_direction = None
best_score = -math.inf
for direction in moves:
next_board, gained = move(board, direction)
score = gained + chance_value(next_board, depth)
if score > best_score:
best_score = score
best_direction = direction
return best_direction
@dataclass
class Game:
board: Board
score: int = 0
@classmethod
def new(cls, rng: random.Random) -> "Game":
board = (0,) * (SIZE * SIZE)
board = spawn_tile(board, rng)
board = spawn_tile(board, rng)
return cls(board=board)
def step(self, direction: str, rng: random.Random) -> bool:
new_board, gained = move(self.board, direction)
if new_board == self.board:
return False
self.board = spawn_tile(new_board, rng)
self.score += gained
return True
def over(self) -> bool:
return not valid_moves(self.board)
def print_board(board: Board) -> None:
grid = rows(board)
width = max(4, len(str(max(board))))
for row in grid:
print(
" ".join(
f"{value:>{width}}" if value else ".".rjust(width)
for value in row
)
)
print()
def run(seed: int | None = None) -> Game:
rng = random.Random(seed)
game = Game.new(rng)
while not game.over():
direction = best_move(game.board)
if direction is None:
break
game.step(direction, rng)
return game
if __name__ == "__main__":
game = run()
print_board(game.board)
print("score:", game.score)
print("max tile:", max(game.board))运行方式
将上面的代码保存为 2048_expectimax.py,然后使用 Python 运行:
python 2048_expectimax.py程序会自动完成一局,并在结束时输出最终棋盘、游戏分数和最大方块。
如果希望复现实验,可以把:
game = run()改成固定随机种子,例如:
game = run(seed=42)固定种子只用于复现同一组随机事件,不会让搜索算法本身获得未来信息。
接入现有 2048 项目
如果已经有自己的游戏界面,不需要使用示例中的 Game 类。通常只需要保留以下接口:
direction = best_move(board)其中 board 是长度为 16 的元组,按从左到右、从上到下的顺序保存棋盘。例如:
board = (
2, 2, 4, 8,
0, 4, 8, 16,
0, 0, 16, 32,
0, 0, 0, 64,
)返回值可能是:
left
right
up
down如果已经没有合法移动,则返回 None。
参数调优方向
如果希望继续提升决策质量,可以从以下方向修改,而不必重写整个搜索框架:
- 增加搜索深度:能看到更远的未来,但随机节点会显著增加计算量。
- 调整空格权重:更高的权重通常会让算法更重视生存空间。
- 增强角落策略:可以加入蛇形权重矩阵,进一步鼓励大数沿边缘有序排列。
- 改进单调性指标:可对最大方块所在行列给予额外奖励。
- 随机节点剪枝:只保留代表性空位能够提速,但会牺牲精确的期望计算。
- 位棋盘优化:将 16 个格子压入整数并预计算行移动表,可显著减少 Python 层面的棋盘操作开销。
- 并行搜索:四个首层候选动作可以独立计算,但是否值得并行取决于运行环境和搜索深度。
实现限制
这份实现的目标是清晰、完整和便于修改,因此没有使用更复杂的位运算棋盘、查表评估或专门的并行优化。
需要注意:
- 启发式权重是经验参数,不应解释为数学证明得到的唯一最优值。
- 搜索深度越高,通常决策信息越充分,但计算成本也越高。
- 不同 2048 变体可能具有不同的棋盘大小、生成概率或计分方式,接入前应先确认规则。
- 如果追求严格意义上的最优策略,需要定义明确的目标函数,并对远大于本文有限深度搜索的状态空间进行求解;这与实时游戏 AI 的工程目标并不相同。
对于大多数需要“自动选择下一步”的 2048 项目,Expectimax 的价值在于:它把随机生成方块的概率直接纳入决策,同时又允许通过启发式函数把棋盘结构知识加入搜索,因此比只看当前得分或固定方向策略更适合作为通用 AI 基线。
