Serpent AI 策略研究：从最短路到压力控制

0. 问题重定义：从小游戏到动力系统

我最开始以为 Serpent 是一个“贪吃蛇变体”：吃东西，避障碍，尽量活久一点。这个理解没有错，但它太浅。

当 Greedy、A*、Lookahead、NoGrow、TailGuard、Depth-2、MinLength 一层层跑出来之后，这个游戏真正暴露出来的不是“哪个 AI 分数高”，而是它的状态空间里有一套非常清楚的动力结构：分数在增长，长度在增长，size 在扰动几何压力，墙和危险物在提供修剪，timeout 在强迫系统周期性进食。

所以本文的核心不是“怎么打高分”，而是：Serpent 的长期最优控制对象到底是什么？

最终答案不是 length，也不是 size，而是：

1. 游戏规则的数学抽象

1.1 状态变量

设当前游戏状态为：

代码里的关键常量可以直接翻译成数学约束：MAX_SIZE = 3，无进食死亡时间是 NO_PROGRESS_TIMEOUT = 30000ms，普通食物 +10，大奖励 +50，危险物 -20，障碍物扣分为 -5/-10/-15，砍节为 1/1/2。

1.2 行为变量

每个 tick，AI 直接控制的是方向：

但从策略层面看，它选择的是行为类型：

2. 基础资源方程

2.1 长度方程

设某段时间内吃普通食物 F 次，吃大奖励 B 次，撞三类墙分别为 W1/W2/W3 次，吃危险物 H 次。名义长度变化是：

但游戏里有一个非常关键的下限：

所以更准确地说：

这就是为什么一节蛇撞墙不会继续被砍死。它不是一个小实现细节，而是长期小长度稳态能成立的重要原因之一。

2.2 分数方程

如果把障碍物类型看作随机变量，障碍生成概率为：

那么一次随机撞墙的期望扣分是：

一次随机撞墙的期望砍节是：

所以每修掉 1 节的期望成本约为：

于是：

2.3 timeout 约束

30 秒无进食死亡，所以必须满足：

长期策略里，食物不是单纯得分源，它也是续命时钟。如果平均进食周期是 T_food，必须有：

实际策略要留安全余量，所以一般要把目标压到：

危险物和撞墙不重置 τ，所以长期主循环必须包含普通食物或大奖励。墙和危险物只能修剪，不能续命。

3. 几何压力：真正该控制的是 pressure

早期我们只看 N = length。这是必要的，但不够。因为 Serpent 里每节蛇的实际占地会随 size 增长。

所以定义近似几何压力：

更准确的版本是：

因为粗蛇相邻节会重叠，Nq² 是一个上界或近似指标。但它非常有用，因为它揭示了：同样的 length，在不同 size 下完全不是同一个状态。

3.1 墙在不同 size 下的几何修剪效率

撞一次随机墙，期望砍节是 1.15。如果 size 为 q，期望清理几何占地约为：

期望成本仍约 8 分，所以每清理 1 个几何格的成本：

3.2 稳态条件

成熟的长期目标不是 N ≤ 常数，而是：

例如可以设：

控制器目标变成：

4. L1–L17：策略演进与算法实现

下面每个策略都不是孤立版本号，而是一次问题重定义。Serpent AI 的进步不是“代码越来越复杂”，而是目标函数越来越接近游戏真实结构。

open_set: priority queue ordered by f(n)
g(n): current path length
h(n): Manhattan distance to target
blocked: snake body + hard obstacles
neighbors: four directions, with wrap-around if game rules allow

def safe_to_eat(game, food):
    path = astar(game.head, food.position, game.blocked_cells)
    if not path:
        return False

    future = simulate(game, path)
    return bfs_reachable(future.head, future.tail, future.blocked_cells)

def cell_cost(cell):
    if cell.is_empty:
        return 1
    if cell.is_fragile_wall:
        return 1 + wall_weight * 5
    if cell.is_brick_wall:
        return 1 + wall_weight * 10
    if cell.is_iron_wall:
        return 1 + wall_weight * 15
    return INF

def food_score(food, game):
    if food.type == "big_reward":
        return -INF   # NoGrow-Strict: treat bonus as forbidden
    return 10 - distance_penalty(food)

def reachable_area(game, start):
    queue = [start]
    visited = {start}
    while queue:
        cell = queue.pop()
        for nxt in neighbors(cell):
            if nxt not in visited and not blocked(nxt):
                visited.add(nxt)
                queue.append(nxt)
    return len(visited)

for food in visible_foods(game):
    path = astar(game.head, food.position, game)
    future = simulate_path(game, path)
    if can_reach_tail(future):
        candidates.append(score(food, path, future))
return best(candidates)

if timeout_soon:
    seek_safe_food_or_bonus()
elif pressure_high:
    trim_by_wall_or_hazard()
elif pressure_low:
    take_profitable_food()
else:
    safe_wander_or_follow_tail()

5. Hazard 纳入后的修正

危险物的效果是：

所以每节成本是：

所以 hazard 不是优质修剪资源。但它有两个价值：一次砍 2 节，适合高压应急；如果附近没有墙，它是备用减压阀。

6. L18：PressureControl-Profit 的理论设计

现在 L18 不该叫 MinLength-Profit，更准确应该叫：

目标函数：

6.1 状态机

LOW_PRESSURE:
  可以吃普通食物
  如果大奖励收益很高且路径安全，也可以吃

MEDIUM_PRESSURE:
  优先吃普通食物
  避免大奖励，除非 timeout 压力很高

HIGH_PRESSURE:
  停止吃奖励
  优先找脆墙/铁墙修剪
  hazard 可作为应急修剪

TIMEOUT_PRESSURE:
  不管 pressure，先吃最近安全食物/大奖励续命

RECOVERY_AFTER_BONUS:
  如果 size 刚变大，立刻降低 pressure

6.2 每步评分函数

其中 λ 应该随 pressure 增大：

pressure 越高，越重视修剪；pressure 低时，允许多吃、多赚钱。

6.3 动作估值

hazard 只有在 λ 很大，也就是 pressure 很高时才值得吃。

7. 思路演进：九次问题重定义

这轮研究的真正价值在于：我没有停在“哪个 AI 分数高”，而是不断追问“这个游戏的长期动力系统是什么”。

8. 当前能说的结论，和不能说的强结论

8.1 弱命题：Serpent 存在长期正收益压力受控策略

在以下条件下：

1. AI 能在 τ<30s 内找到普通食物或大奖励；
2. AI 能以有限代价找到障碍物或 hazard 作为修剪资源；
3. AI 使用 pressure 控制，使 P=Nq² 保持在某个上界附近；
4. q≤3，即 size 有上限；
5. 障碍物/危险物不会形成永久不可达死局。

则有模拟证据和正期望资源账支持存在策略，使得：

更直观地说：只要能持续把几何压力修回安全区，分数就可以长期正增长。

8.2 现在不能声称的强定理

不能严格声称：

原因很硬：地图随机生成；食物/大奖励/危险物位置可能短期极差；AI 寻路不是完美动态规划；timeout 是硬约束；size=3 后可达性下降；真实 occupied cells 比 Nq² 更复杂；撞墙结算一次只处理一个障碍，规划估值仍需校准。

9. 录像引用校正

我重新整理了正文里的回放引用：不是把 22 个录像全部塞进正文，而是按证据功能筛选。

其余录像保留在回放库作为附录。像 L8/L9/L10/L13 这类长跑或截断录像，不适合在正文里当“最终分数证据”，更适合作为策略库补充。