标签相关文章

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

2048 高胜率 AI:Expectimax 近似最优算法与完整源码

介绍适用于经典 4×4 2048 的 Expectimax 搜索方案,解释随机节点、启发式评估、自适应搜索深度与缓存策略,并给出一份不依赖第三方库的完整 Python 源码。

2048 的难点并不只是“尽量合并大数字”,而是在每次移动后还会随机出现新方块。一个只看眼前得分的贪心策略很容易把棋盘压死,因此更实用的 AI 需要同时考虑未来可移动空间、数字排列结构以及随机事件的期望结果。

本文给出一套适用于经典 4×4 规则的 Expectimax 搜索 + 启发式评估 实现。它不是对所有未来状态进行穷举得到的数学意义上的全局最优策略,而是一种在计算量与决策质量之间较均衡的近似最优方案。

“最优”具体指什么

如果把整局 2048 从当前状态一直搜索到游戏结束,理论上可以为每个状态求出最优动作。但实际状态空间和随机分支都很大,完整求解通常不适合作为实时决策算法。

因此,工程实现通常采用有限深度搜索:

  1. 玩家节点枚举上、下、左、右四个合法动作。
  2. 随机节点枚举新方块可能出现的位置。
  3. 对每个空位分别考虑生成 2 和 4 的概率。
  4. 搜索达到深度限制后,用启发式函数估计棋盘质量。
  5. 选择期望价值最大的动作。

这里的“近似最优”是指:在给定搜索深度、概率模型和启发式函数的条件下,选择期望评价最高的动作,而不是声称已经求出整个 2048 游戏的全局最优策略。

为什么使用 Expectimax

2048 中的新方块不是一个会故意让玩家失败的对手,而是随机事件。因此,随机节点不应该像 Minimax 那样选择“最坏情况”,而应该计算所有随机结果的数学期望。

玩家节点可写为:

Vplayer(s,d)=max⁡a∈A(s)(R(s,a)+Vchance(T(s,a),d))V_{player}(s, d) = \max_{a \in A(s)} \left( R(s,a)+V_{chance}(T(s,a),d) \right)

其中:

  • ss 是当前棋盘;
  • A(s)A(s) 是所有合法移动;
  • T(s,a)T(s,a) 是执行动作后的棋盘;
  • R(s,a)R(s,a) 是本次合并得到的即时分数;
  • dd 是剩余搜索深度。

随机节点可写为:

Vchance(s,d)=∑iP(i)Vplayer(si,d−1)V_{chance}(s,d) = \sum_i P(i)V_{player}(s_i,d-1)

本实现按经典概率模型处理新方块:

  • 在所有空位中均匀选择一个位置;
  • 生成 2 的概率为 0.9;
  • 生成 4 的概率为 0.1。

如果目标游戏的生成规则不同,应同步修改源码中的概率模型。

启发式评估

搜索不可能无限向后展开,所以必须在叶子节点估计棋盘质量。本实现组合多个指标,而不是只看当前最大数字。

指标作用
空格数量保留操作空间,降低棋盘被堵死的风险
单调性鼓励较大的方块沿行或列形成稳定梯度
平滑度鼓励相邻方块的数量级接近,便于后续合并
可合并对数奖励当前仍存在直接合并机会的局面
最大方块对整体进度提供基础奖励
最大方块在角落鼓励大数字稳定在边角,减少结构被打乱

评估函数形式为:

E(s)=270Eempty+47Emono+3Esmooth+25Emerge+100Emax+EcornerE(s) = 270E_{empty} + 47E_{mono} + 3E_{smooth} + 25E_{merge} + 100E_{max} + E_{corner}

这些权重属于可调参数,不存在对所有实现、所有搜索深度都唯一最优的一组固定值。增加搜索深度、改变概率模型或改变棋盘规则后,都可能需要重新调参。

搜索深度与缓存

Expectimax 的主要成本来自随机节点。假设当前有 ee 个空位,那么一次随机生成最多产生约 2e2e 个子状态,再与玩家节点的最多四种移动组合,分支数会迅速增长。

源码采用两个办法控制计算量:

  • 自适应深度:空格较多时搜索 2 层,棋盘较拥挤时搜索 3 层。
  • 状态缓存:使用 lru_cache 复用相同棋盘与深度的计算结果。

拥挤局面通常更危险,也更值得增加搜索深度;而开局空位很多,随机分支更多,较浅搜索能显著降低开销。

完整 Python 源码

下面的代码仅使用 Python 标准库,包含:

  • 4×4 棋盘表示;
  • 四方向移动与合并;
  • 合法动作判断;
  • 随机生成方块;
  • 启发式评估函数;
  • Expectimax 玩家节点与随机节点;
  • 自适应搜索深度;
  • 自动对局循环。
PYTHON304 行
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 运行:

Shell1 行
python 2048_expectimax.py

程序会自动完成一局,并在结束时输出最终棋盘、游戏分数和最大方块。

如果希望复现实验,可以把:

PYTHON1 行
game = run()

改成固定随机种子,例如:

PYTHON1 行
game = run(seed=42)

固定种子只用于复现同一组随机事件,不会让搜索算法本身获得未来信息。

接入现有 2048 项目

如果已经有自己的游戏界面,不需要使用示例中的 Game 类。通常只需要保留以下接口:

PYTHON1 行
direction = best_move(board)

其中 board 是长度为 16 的元组,按从左到右、从上到下的顺序保存棋盘。例如:

PYTHON6 行
board = (
    2, 2, 4, 8,
    0, 4, 8, 16,
    0, 0, 16, 32,
    0, 0, 0, 64,
)

返回值可能是:

TEXT4 行
left
right
up
down

如果已经没有合法移动,则返回 None。

参数调优方向

如果希望继续提升决策质量,可以从以下方向修改,而不必重写整个搜索框架:

  1. 增加搜索深度:能看到更远的未来,但随机节点会显著增加计算量。
  2. 调整空格权重:更高的权重通常会让算法更重视生存空间。
  3. 增强角落策略:可以加入蛇形权重矩阵,进一步鼓励大数沿边缘有序排列。
  4. 改进单调性指标:可对最大方块所在行列给予额外奖励。
  5. 随机节点剪枝:只保留代表性空位能够提速,但会牺牲精确的期望计算。
  6. 位棋盘优化:将 16 个格子压入整数并预计算行移动表,可显著减少 Python 层面的棋盘操作开销。
  7. 并行搜索:四个首层候选动作可以独立计算,但是否值得并行取决于运行环境和搜索深度。

实现限制

这份实现的目标是清晰、完整和便于修改,因此没有使用更复杂的位运算棋盘、查表评估或专门的并行优化。

需要注意:

  • 启发式权重是经验参数,不应解释为数学证明得到的唯一最优值。
  • 搜索深度越高,通常决策信息越充分,但计算成本也越高。
  • 不同 2048 变体可能具有不同的棋盘大小、生成概率或计分方式,接入前应先确认规则。
  • 如果追求严格意义上的最优策略,需要定义明确的目标函数,并对远大于本文有限深度搜索的状态空间进行求解;这与实时游戏 AI 的工程目标并不相同。

对于大多数需要“自动选择下一步”的 2048 项目,Expectimax 的价值在于:它把随机生成方块的概率直接纳入决策,同时又允许通过启发式函数把棋盘结构知识加入搜索,因此比只看当前得分或固定方向策略更适合作为通用 AI 基线。

相关文章