DarkForest 简化对局的经典随机游走模型

@YuZhuZhi · 2026-10-05

本文抽去装备、信息和策略差异，把角色行动近似为固定权重的网格随机游走。模型用于分离地图边界、遭遇和淘汰对时间分布的影响；下面的概率与回合数属于这一简化规则，不能直接视为完整 DarkForest 对局的预测。

题目 1.

设若干角色在一张可通行范围有限的二维方格地图上游走。每回合按固定顺序让各角色行动一次；轮到某角色时，它选择向上、下、左、右移动一格，或留在原地。五种行动的概率可以不同，但对同一角色保持不变；不同角色独立选择行动。若某方向通向不可通行方格，就删去该动作，并在其余动作上重新归一化概率。

一名角色移动到另一名存活角色所在的方格时，立即发生遭遇。回合暂停，双方以相同概率淘汰其中一人，然后继续本回合尚未完成的行动。场上只剩一名角色时，游戏结束。需要计算：

指定角色在指定回合到达指定方格的概率，以及首次到达该方格的期望回合数和标准差；
指定角色在指定回合遭遇的概率，以及首次遭遇的期望回合数和标准差；
游戏在指定回合结束的概率，以及结束时间的期望和标准差。

本文以一张 $15 \times 15$ 方格地图为算例：中央 $5 \times 5$ 的方格不可通行，七名角色从不同位置出发，五种行动的权重均为 $1$ 。

计算方法取决于所问事件。若暂时忽略淘汰，单名角色的位置只依赖自身的上一步位置，可以用有限状态 Markov 链精确计算到达概率和首达时间。实际游戏内的占用概率则还受淘汰影响。遭遇及游戏结束更依赖多名角色在回合内部的行动路径；七人局的联合位置状态约有 $200^{7} \approx 1.3 \times 10^{16}$ 个，无法直接递推。本文对这部分采用蒙特卡洛模拟，并用同一地图上可精确求解的两人局校核。

一、地图、行动权重与边界转移

定义 1.（地图）

用有限连通图

𝐺 = (𝑉, 𝐸)

表示地图。

𝑉 \subset ℤ^{2}

是可通行方格的集合，

𝑁 = | 𝑉 |

；当两个方格的行列坐标只在一个方向相差

1

时，它们由一条边连接。角色不能进入

𝑉

之外的方格。算例共有

225 - 25 = 200

个可通行方格。

地图给出了角色能到达哪些位置。接下来为每名角色指定出发点，以及它选择五种行动的相对权重。

定义 2.（角色与权重）

角色 $𝑖$ 由出发点 $𝑐_{𝑖}^{(0)} \in 𝑉$ 与一个五元非负权重

𝑤_{𝑖} = (𝑤_{𝑖}^{up}, 𝑤_{𝑖}^{down}, 𝑤_{𝑖}^{left}, 𝑤_{𝑖}^{right}, 𝑤_{𝑖}^{stay})

给出，其中原地不动的权重 $𝑤_{𝑖}^{stay} > 0$ 。权重只表示各动作的相对倾向：在不考虑地图边界时，选择动作 $𝑘$ 的概率为

𝑃_{𝑖}^{(𝑘)} = \frac{𝑤_{𝑖}^{(𝑘)}}{\sum_{𝑘^{'} \in {up, down, left, right, stay}} 𝑤_{𝑖}^{(𝑘^{'})}} .

七名角色的出发点两两不同；算例中五种动作的权重均为

1

。以下涉及“从任意格到任意格都能到达”的结论，还要求四个移动方向的权重严格为正。若允许方向权重为

0

，需要另行检查可达性。

地图边界会使某些动作失效，因此不能直接把上述五个概率用于每个方格。需要按当前位置重新计算可执行动作的概率。

定义 3.（合法动作与转移矩阵）

记五种动作的位移分别为 $𝛿_{up} = (- 1, 0)$ 、 $𝛿_{down} = (1, 0)$ 、 $𝛿_{left} = (0, - 1)$ 、 $𝛿_{right} = (0, 1)$ 、 $𝛿_{stay} = (0, 0)$ 。角色 $𝑖$ 位于方格 $𝑐$ 时，只有落点仍在 $𝑉$ 中且权重大于 $0$ 的动作才可执行。将这些动作组成集合

𝐾_{𝑖} (𝑐) = {𝑘 : 𝑐 + 𝛿_{𝑘} \in 𝑉, 𝑤_{𝑖}^{(𝑘)} > 0} .

记

𝑊_{𝑖} (𝑐) = \sum_{𝑘 \in 𝐾_{𝑖} (𝑐)} 𝑤_{𝑖}^{(𝑘)} .

$𝑊_{𝑖} (𝑐)$ 是角色 $𝑖$ 从 $𝑐$ 出发时所有可执行动作的权重之和，用于对这些动作重新归一化。由于原地不动始终可执行且权重为正， $𝑊_{𝑖} (𝑐) > 0$ 。

以 $𝑉$ 中的方格为行、列索引，定义角色 $𝑖$ 的一步位置转移矩阵 $𝑄_{𝑖}$ 。矩阵元 $𝑄_{𝑖} [𝑐, 𝑐^{'}]$ 表示角色当前位于 $𝑐$ 时，下一次行动后位于 $𝑐^{'}$ 的条件概率：

𝑄_{𝑖} [𝑐, 𝑐^{'}] = \frac{\sum_{𝑘 \in 𝐾_{𝑖} (𝑐), 𝑐 + 𝛿_{𝑘} = 𝑐^{'}} 𝑤_{𝑖}^{(𝑘)}}{𝑊_{𝑖} (𝑐)} .

分子汇总所有以 $𝑐^{'}$ 为落点的合法动作的权重，分母则是该位置全部合法动作的权重之和。因此边界处先排除不可通行的方向，再对其余动作重新归一化；动作的原始权重本身不随位置改变。

这个定义需要满足两个基本要求：从任一方格出发，各落点的概率之和应为 $1$ ；而“原地不动”应使留在原格的概率为正。

命题 1.（

𝑄_{𝑖}

行随机，且对角元为正）

𝑄_{𝑖}

的每一行恰好求和为

1

，并且

𝑄_{𝑖} [𝑐, 𝑐] \geq 𝑤_{𝑖}^{stay} / 𝑊_{𝑖} (𝑐) > 0

。

证明. 固定出发格

𝑐

。每个合法动作都有且只有一个落点，因此对所有

𝑐^{'}

求和时，转移概率的分子恰好把

𝐾_{𝑖} (𝑐)

中的动作权重各计入一次，总和为

𝑊_{𝑖} (𝑐)

；除以同一个

𝑊_{𝑖} (𝑐)

后，行和为

1

。原地不动的落点仍是

𝑐

，所以它对对角元

𝑄_{𝑖} [𝑐, 𝑐]

至少贡献

\frac{𝑤_{𝑖}^{stay}}{𝑊_{𝑖}} (𝑐) > 0

。

□

有了转移矩阵，还可以问角色持续游走后是否偏向某些方格。对称的方向权重使相邻方格之间的概率流量相互平衡，从而给出平稳分布。

命题 2.（平稳分布正比于合法权重之和）

若权重满足对称性 $𝑤_{𝑖}^{up} = 𝑤_{𝑖}^{down}$ 且 $𝑤_{𝑖}^{left} = 𝑤_{𝑖}^{right}$ ，定义

𝜋_{𝑖} (𝑐) = 𝑊_{𝑖} (𝑐) / \sum_{𝑐^{'} \in 𝑉} 𝑊_{𝑖} (𝑐^{'}) .

则

𝑄_{𝑖}

关于

𝜋_{𝑖}

可逆，因而

𝜋_{𝑖}

是平稳分布。若四个移动方向的权重还严格为正，则该分布唯一，且

𝑝_{𝑖}^{(𝑡)} \to 𝜋_{𝑖}

（几何收敛）。

证明. 验证任意两个方格之间的细致平衡，即 $𝜋_{𝑖} (𝑐) 𝑄_{𝑖} [𝑐, 𝑐^{'}] = 𝜋_{𝑖} (𝑐^{'}) 𝑄_{𝑖} [𝑐^{'}, 𝑐]$ 。按方格之间的关系分三种情形：

若 $𝑐^{'} = 𝑐$ ，两边都是 $𝜋_{𝑖} (𝑐) 𝑄_{𝑖} [𝑐, 𝑐]$ ，自动成立。
若 $𝑐^{'}$ 与 $𝑐$ 相邻，则从 $𝑐$ 到 $𝑐^{'}$ 只有唯一一个方向 $𝑘$ ，从 $𝑐^{'}$ 到 $𝑐$ 只有它的反向 $𝑘^{'}$ ；把 $𝜋_{𝑖} = 𝑊_{𝑖} / \sum 𝑊_{𝑖}$ 代入，两边分别是 $𝑤_{𝑖}^{(𝑘)} / \sum 𝑊_{𝑖}$ 与 $𝑤_{𝑖}^{(𝑘^{'})} / \sum 𝑊_{𝑖}$ ，由对称性假设相等。
其它情形两边都是 $0$ 。

因此 $𝜋_{𝑖}$ 是平稳分布。若四个移动方向的权重均为正，地图连通性保证链不可约；再由对角元为正知其非周期，故平稳分布唯一，并且分布几何收敛。

□

对算例的单位权重， $𝑊_{𝑖} (𝑐)$ 有更直观的含义：它等于原地不动这一种动作，加上从 $𝑐$ 可以走到的相邻方格数。按位置分类，可得：

$𝑊_{𝑖} (𝑐)$	含义	格数	平稳概率
$3$	地图四角（只有 $2$ 个可通行邻居）	$4$	$3 / 920 = 0.003261$
$4$	四条边或紧贴障碍块	$72$	$4 / 920 = 0.004348$
$5$	内部（四面可通）	$124$	$5 / 920 = 0.005435$

这三类方格的权重总和为 $4 \cdot 3 + 72 \cdot 4 + 124 \cdot 5 = 920$ 。因此，四角的平稳概率为 $\frac{3}{920}$ ，内部方格为 $\frac{5}{920}$ ，前者是后者的 $\frac{3}{5}$ 。用幂法计算得到的平稳分布与解析式的最大绝对偏差为 $2.265 \times 10^{- 15}$ 。

注 1.（边界方格的平稳概率）

四角各有三个合法动作，其中一个是原地不动。因此角色位于角上时，下一步离开的概率为

\frac{2}{3}

；位于四邻均可通行的内部方格时，离开的概率为

\frac{4}{5}

。虽然角上单个出边的概率较大，但可进入角上的相邻方格也较少。细致平衡表明，角上的长期占用概率仍低于内部方格。

以上只定义了单次移动。为了确定遭遇发生在回合内的哪个时刻，还需明确行动、决斗和终止的顺序：

注 2.（假设清单）

A1（地图） $𝑉$ 是有限连通方格集。
A2（顺序行动）每回合按固定顺序 $1, 2, \dots, 𝑛$ 让每名存活角色各行动一次（已淘汰者跳过）。“行动顺序固定”因此是有内容的：它决定了谁先移动、谁被撞到时还未行动。
A3（边界与可达性）非法方向从合法动作集中删除，其余按权重重新归一化（定义 3）。所有首达时间的有限性与几乎必然遭遇的结论还要求四个移动方向的权重严格为正；算例满足此条件。
A4（遭遇）角色 $𝑖$ 移动后若落点上有另一名当前存活角色 $𝑗$ ，立即发生遭遇；同格超过两人不会出现（见命题 4）。
A5（决斗）决斗在此刻完成、不消耗额外回合；两人各以 $1 / 2$ 被淘汰，幸存者留在相遇格。
A6（回合继续）决斗结束后，本回合从 $𝑖$ 之后的角色继续；若被撞者 $𝑗$ 尚未行动且幸存，它仍保有本回合自己的行动。
A7（终止）只剩一名角色时游戏结束。

注 3.（为什么把“行动顺序固定”读成顺序行动）

题目同时规定“所有角色均移动完成，该回合才视为结束”和“回合锁定……方可继续回合”，并强调行动顺序固定。本文据此采用顺序行动模型：角色依次移动，遭遇发生后立即决斗，再继续处理本回合尚未行动的角色。这一解释与 Code/gridGameOptimized.py 的实现一致；若采用同时行动模型，遭遇事件及其分布需要重新定义（见 “四、讨论”）。

1. 单角色：到达概率与首次到达

先研究不受淘汰影响的移动过程。为此，给每名角色定义一条延续轨迹 $𝑋_{𝑖} (𝑡)$ ：即使它已在游戏中出局，也设想它继续按同一个转移矩阵独立移动。这样得到的是单角色位置分布。若要问实际游戏中角色在第 $𝑡$ 回合末占据格 $𝑐$ 的概率，还必须同时要求它没有被淘汰；两种概率的含义不同。

定理 1.（占用分布）

设 $𝑝_{𝑖}^{(0)}$ 是在出发点取 $1$ 的行向量，则延续轨迹在第 $𝑡$ 步的位置分布为

𝑝_{𝑖}^{(𝑡)} = 𝑝_{𝑖}^{(0)} 𝑄_{𝑖}^{𝑡}, 即 𝑝_{𝑖}^{(𝑡)} (𝑐) = Pr (𝑋_{𝑖} (𝑡) = 𝑐) .

证明.对

𝑡

归纳。

𝑡 = 0

是初值；由全概率公式与 Markov 性，

𝑝_{𝑖}^{(𝑡 + 1)} (𝑐^{'}) = \sum_{𝑐} 𝑝_{𝑖}^{(𝑡)} (𝑐) 𝑄_{𝑖} [𝑐, 𝑐^{'}]

。

□

位置分布回答“第 $𝑡$ 步在哪里”；若要回答“最早何时到达目标格”，需改看整条轨迹，并定义首达时间。

定义 4.（首次到达时间）

𝑇_{𝑖, 𝑐} = inf {𝑡 \geq 0 : 𝑋_{𝑖} (𝑡) = 𝑐} .

这是延续轨迹首次到达目标格

𝑐

的时间；若角色从

𝑐

出发，则

𝑇_{𝑖, 𝑐} = 0

。它不要求角色在到达时仍存活。

注 4.（游戏内首次到达与延续轨迹的区别）

若把“首次到达”限定为淘汰之前，应另记

𝑇_{𝑖, 𝑐}^{game} = inf {𝑡 \geq 0 : 角色 𝑖 在第 𝑡 回合末存活且位于 𝑐}

。它可能取

\infty

，因此无条件期望未必有限。此时应报告到达概率

Pr (𝑇_{𝑖, 𝑐}^{game} < \infty)

，并在该事件上计算条件期望与标准差；本文后续的首达热图与数表均对应延续轨迹。

以下固定目标格 $𝑐$ ，把角色 $𝑖$ 的出发格记为 $𝑠 = 𝑐_{𝑖}^{(0)}$ 。从 $𝑄_{𝑖}$ 中删除 $𝑐$ 对应的行和列，得到 $(𝑁 - 1) \times (𝑁 - 1)$ 矩阵 $𝑄_{- 𝑐}$ 。它只记录游走尚未进入 $𝑐$ 时，在其余方格之间的转移；以下矩阵下标均表示方格。

引理 1.（首达尾概率由缩减矩阵给出）

对 $𝑠 \neq 𝑐$ ，

Pr (𝑇_{𝑖, 𝑐} > 𝑡) = \sum_{𝑣 \neq 𝑐} {(𝑄_{- 𝑐}^{𝑡})}_{𝑠 𝑣} .

证明.

{𝑇_{𝑖, 𝑐} > 𝑡}

就是“前

𝑡

步都没踩到

𝑐

”。把

𝑐

从链里抹掉（既不允许进入也不允许离开），剩下的过程正是以

𝑄_{- 𝑐}

为转移矩阵的链，其

𝑡

步转移概率之和就是“始终留在

𝑉 - {𝑐}

内游走

𝑡

步”的概率。对步数归纳即得。

□

上式给出每一步仍未到达目标格的概率。要由这些尾概率计算期望和标准差，还需要下列适用于非负整数随机变量的恒等式。

定理 2.（尾和公式）

对取值于 ${0, 1, 2, \dots}$ 的 $𝑇$ ，

𝔼 [𝑇] = \sum_{𝑡 \geq 0} Pr (𝑇 > 𝑡), 𝔼 [𝑇^{2}] = \sum_{𝑡 \geq 0} (2 𝑡 + 1) Pr (𝑇 > 𝑡), Var [𝑇] = 𝔼 [𝑇^{2}] - 𝔼 {[𝑇]}^{2} .

证明. 第一个等式来自

𝑇 = \sum_{𝑡 \geq 0} 𝟙 [𝑇 > 𝑡]

：右端沿轨道从

𝑡 = 0

加到

𝑇 - 1

，恰好加了

𝑇

个

1

。第二个来自恒等式

\sum_{𝑡 = 0}^{𝑇 - 1} (2 𝑡 + 1) = 𝑇^{2}

（奇数之和），把

𝑇^{2}

写成

\sum_{𝑡 \geq 0} (2 𝑡 + 1) 𝟙 [𝑇 > 𝑡]

后取期望即可。

□

尾和公式可能包含无限多项。为保证它们对本文的首达时间收敛，需要利用地图连通性和正方向权重建立一个统一的尾概率上界。

定理 3.（尾概率几何衰减、各阶矩有限）

若四个移动方向的权重严格为正，则存在

𝐶 > 0

、

𝜌 \in (0, 1)

，使

Pr (𝑇_{𝑖, 𝑐} > 𝑡) \leq 𝐶 𝜌^{𝑡}

；因此

𝑇_{𝑖, 𝑐}

的各阶矩都有限。

证明. 设

𝑁 \geq 2

。由于地图连通且四个移动方向的权重为正，任意

𝑥 \neq 𝑐

都有一条长度不超过

𝑁 - 1

的正概率路径通向

𝑐

。令

𝜀

为全部正转移概率的最小值，

𝛿 = 𝜀^{𝑁 - 1}

。沿该路径移动，并在需要时用原地不动补足

𝑁 - 1

步，概率至少为

𝛿

。逐段使用 Markov 性，得到

Pr (𝑇_{𝑖, 𝑐} > 𝑘 (𝑁 - 1)) \leq {(1 - 𝛿)}^{𝑘}

。令

𝜌 = {(1 - 𝛿)}^{1 / (𝑁 - 1)}

、

𝐶 = 𝜌^{- (𝑁 - 2)}

，便有对所有

𝑡 \geq 0

成立的上界

Pr (𝑇_{𝑖, 𝑐} > 𝑡) \leq 𝐶 𝜌^{𝑡}

。因此各阶矩有限。

𝑁 = 1

时结论直接成立。

□

尾和适合逐步计算首达时间分布；若只需要期望和标准差，可以把尚未到达目标格的转移写成线性方程组，直接求出所有起点的结果。

命题 3.（基本矩阵公式与二阶矩公式）

记 $𝑁_{𝑐} = {(𝐼 - 𝑄_{- 𝑐})}^{- 1}$ 。对任意起点格 $𝑥 \neq 𝑐$ ，令 $𝑚_{𝑥} = 𝔼_{𝑥} [𝑇_{𝑐}]$ 、 $𝑠_{𝑥} = 𝔼_{𝑥} [𝑇_{𝑐}^{2}]$ ，其中下标 $𝑥$ 表示从 $𝑥$ 出发，则

𝑚_{𝑥} = \sum_{𝑣 \neq 𝑐} {(𝑁_{𝑐})}_{𝑥 𝑣}, 𝑠_{𝑥} = \sum_{𝑣 \neq 𝑐} (2 {(𝑁_{𝑐})}_{𝑥 𝑣} - 𝛿_{𝑥 𝑣}) 𝑚_{𝑣} .

因而角色

𝑖

的首达期望与二阶矩分别为

𝑚_{𝑐_{𝑖}^{(0)}}

与

𝑠_{𝑐_{𝑖}^{(0)}}

。

证明. 由定理 3，矩阵级数 $𝑁_{𝑐} = \sum_{𝑡 \geq 0} 𝑄_{- 𝑐}^{𝑡}$ 收敛。 ${(𝑁_{𝑐})}_{𝑥 𝑣}$ 是从 $𝑥$ 出发、首次到达 $𝑐$ 之前访问 $𝑣$ 的期望次数。每个 $0 \leq 𝑡 < 𝑇_{𝑐}$ 的时刻链恰好位于一个格子，所以对 $𝑣$ 求和得到 $𝑚_{𝑥}$ 。

再按第一步条件化。对 $𝑥 \neq 𝑐$ ，有 $𝑠_{𝑥} = \sum_{𝑣 \neq 𝑐} 𝑄_{𝑖} [𝑥, 𝑣] (1 + 2 𝑚_{𝑣} + 𝑠_{𝑣}) + 𝑄_{𝑖} [𝑥, 𝑐]$ ；整理得 $(𝐼 - 𝑄_{- 𝑐}) 𝑠 = 𝟏 + 2 𝑄_{- 𝑐} 𝑚$ 。由于 $𝑁_{𝑐} 𝑄_{- 𝑐} = 𝑁_{𝑐} - 𝐼$ 且 $𝑚 = 𝑁_{𝑐} 𝟏$ ，故 $𝑠 = (2 𝑁_{𝑐} - 𝐼) 𝑚$ 。

□

得到尾概率后，首达时间恰好等于 $𝑡$ 的概率就是相邻两项尾概率之差。

推论 1.（首达分布）

𝑓_{𝑖, 𝑐} (𝑡) = Pr (𝑇_{𝑖, 𝑐} = 𝑡)

满足

𝑓_{𝑖, 𝑐} (0) = 𝟙 [𝑠 = 𝑐]

与

𝑓_{𝑖, 𝑐} (𝑡) = Pr (𝑇_{𝑖, 𝑐} > 𝑡 - 1) - Pr (𝑇_{𝑖, 𝑐} > 𝑡)

（

𝑡 \geq 1

）。

注 5.（为什么要有两套算法）

命题 3 对每个目标格求解一个

(𝑁 - 1)

阶线性方程组，得到所有起点的首达期望与标准差；定理 2 则迭代缩减矩阵求尾概率。两种计算路径可相互校核。程序抽查了

6

个目标格，首达期望最大偏差为

7.0 \times 10^{- 11}

；其中最长的一次尾和迭代用了

45171

步。该偏差反映有限精度计算，不能单凭它归因于某一步骤。

2. 多角色：顺序行动下的遭遇与结束

单角色转移矩阵只记录一名角色在行动后的落点。遭遇可能发生在回合中途，并随即改变存活人数；因此完整计算需记录存活集合及其位置，递推一回合时还需跟踪已经处理到哪名角色。

定义 5.（局面与一回合核）

在每个回合结束时，用 $(𝑆; {(𝑐_{𝑖})}_{𝑖 \in 𝑆})$ 表示局面。其中 $𝑆 \subseteq {1, \dots, 𝑛}$ 是存活角色的集合， $𝑐_{𝑖} \in 𝑉$ 是角色 $𝑖$ 的位置；不同的存活角色占据不同方格，即 $𝑖 \neq 𝑗$ 时 $𝑐_{𝑖} \neq 𝑐_{𝑗}$ 。

一回合转移核 $𝒦︀$ 给出从当前局面到下一回合结束时各局面的概率。它按固定顺序处理角色；轮到存活角色 $𝑖$ 时，先按 $𝑄_{𝑖}$ 抽取落点 $𝑐_{{(𝑖)}^{'}}$ ，再根据落点是否被占据执行下列规则：

若 $𝑐_{{(𝑖)}^{'}}$ 上没有别的存活角色，局面更新为 $𝑐_{𝑖} \leftarrow 𝑐_{{(𝑖)}^{'}}$ ，继续下一个；
若 $𝑐_{{(𝑖)}^{'}}$ 上停着存活角色 $𝑗$ （ $𝑗$ 可能在 $𝑖$ 之前或之后行动），则 $𝑖$ 、 $𝑗$ 立即决斗：以 $1 / 2$ 淘汰 $𝑖$ 、以 $1 / 2$ 淘汰 $𝑗$ ；幸存者停在 $𝑐_{{(𝑖)}^{'}}$ ；然后从 $𝑖$ 的下一个角色继续本回合。

这套规则只在每次行动后、决斗完成后保存局面。下一命题说明这样做始终不会留下两个存活角色同格的状态。

命题 4.（不变量始终成立）

在每次动作开始及决斗结束之后，全部存活角色都两两不同格。因此每名角色每回合至多主动移动一次并触发一次决斗，“同格超过两人”不可能出现；若角色在自身行动前后始终存活，它仍可能在同一回合被其他移动角色多次撞上。

证明. 初始局面满足两两不同格。假设角色

𝑖

行动前仍满足这一性质。若落点无人占据，移动后性质不变；若落点由角色

𝑗

占据，则该格至多只有

𝑗

。决斗立即淘汰两人之一，留下的角色占据该格，其余角色的位置未变，因此决斗后的局面仍满足两两不同格。对每次行动归纳即可。

□

还需确认上述流程没有遗漏或重复计入任何概率质量。只要每名角色的移动分支、决斗分支都保持总概率，整回合流程就定义了合法的转移核。

命题 5.（

𝒦︀

是 Markov 核）

对任意局面，

𝒦︀

给出的下一回合局面的概率之和为

1

。

证明. 沿角色

𝑖

的位置坐标应用

𝑄_{𝑖}

时，由命题 1 可知概率总质量不变。随后按落点是否与其他存活角色重合，把结果分成互斥情形；这只是划分事件。若发生决斗，两个淘汰结果各取得该分支一半的质量；消去淘汰者的位置坐标也不改变剩余质量。逐名角色处理后，全部下一回合局面的概率之和仍为

1

。

□

由于每一步的分支和概率均已确定，可以用张量保存各存活集合下的位置分布，并逐回合推进。下面给出这一递推及其可提取的时间分布。

定理 4.（精确张量递推）

对每个存活集合 $𝑆$ ，用形状为 ${(𝑁,)}^{| 𝑆 |}$ 的次概率张量 $𝜈^{𝑆}$ 保存其各位置组合的概率；所有张量的总质量为 $1$ 。初始时，只有包含全部角色的张量在初始位置组合上取值 $1$ 。每回合依定义 5 的顺序，对轮到的角色沿其坐标轴应用 $𝑄_{𝑖}$ ，再按是否遭遇拆分，并对决斗结果分别更新存活集合。这样得到每回合结束时局面的精确分布。记录每次决斗发生的回合与参与者，还可同时得到

Pr (𝜏_{𝑒} = 𝑡), Pr (𝑇_{end} = 𝑡), Pr (𝑇_{𝑖}^{enc} = 𝑡), Pr (第 𝑡 回合遭遇发生在格 𝑐) .

证明. 对回合数归纳。初始局面的分布已知；若第

𝑡 - 1

回合末的分布已知，则按定义 5 的行动顺序逐步应用全概率公式，所得正是第

𝑡

回合末的分布。对首次遭遇时间

𝜏_{𝑒}

，相邻两项生存概率之差给出

Pr (𝜏_{𝑒} = 𝑡)

。程序还单独传播“至第

𝑡

回合均未决斗”的概率质量，并与这一差分结果对照。

□

注 6.（底层移动是乘积链，但“遭遇”不是终点位置的函数）

如果无视遭遇机制，各角色的位置在任意固定时刻是相互独立的（每人的移动只依赖自己），联合分布就是乘积测度 $\prod_{𝑖} 𝑝_{𝑖}^{(𝑡)}$ 。可是遭遇并不由“回合结束时的位置”决定：A2 的顺序模型里，两人交换位置也会触发遭遇——先动的那个人正好走进了对方当时所在的格子。所以

Pr (𝜏_{𝑒} > 𝑡) \leq Pr (𝑋 (𝑡) \in 𝒟︀), 𝒟︀ = {各角色位置两两不同},

且一般严格不等。右端只用到

7

条单角色边缘分布，可以用积和式精确算出（命题 6），但它是上界，不是答案。

这个上界虽然不能代替真实的“尚未遭遇”概率，却能直接由各角色的单人位置分布计算。其计算形式是矩形概率矩阵的积和式。

命题 6.（同一时刻全体互异的概率 = 积和式）

记 $𝐴_{𝑡}$ 为 $𝑛 \times 𝑁$ 矩阵 ${(𝐴_{𝑡})}_{𝑖 𝑐} = 𝑝_{𝑖}^{(𝑡)} (𝑐)$ ，则

Pr (𝑋 (𝑡) \in 𝒟︀) = per (𝐴_{𝑡}),

且

per (𝐴_{𝑡})

可以由“逐格子集 DP”在

𝑂 (𝑁 \cdot 2^{𝑛} \cdot 𝑛)

次乘加内精确算出（本文

𝑛 = 7

、

𝑁 = 200

，每步约

1.8 \times 10^{5}

次）。

证明.

per (𝐴_{𝑡}) = \sum_{单射 𝜑} \prod_{𝑖} 𝐴_{𝑡} [𝑖, 𝜑 (𝑖)]

，每一项正是“角色

𝑖

落在

𝜑 (𝑖)

且七格互异”的概率，求和即得。DP 的递推：按格子从左到右扫描，

𝑓 [𝑀]

表示“已经把

𝑀

中这些角色安置好”的总权重；每扫到一格，要么不分配给人（

𝑓

不变），要么分配给一个尚未安置的角色

𝑖

（

𝑓 [𝑀 \cup {𝑖}] + = 𝑓 [𝑀] \cdot 𝐴_{𝑡} [𝑖, 𝑐]

）。每个单射只对应一条这样的路径，故最终

𝑓 [{1, \dots, 𝑛}] = per (𝐴_{𝑡})

。

□

注 7.（为什么采用逐格子集递推）

矩形矩阵的积和式也可由容斥展开计算，但交错求和可能放大浮点误差。这里的逐格子集递推只累加非负项，既保留

𝑂 (𝑁 2^{𝑛} 𝑛)

的可计算复杂度，也更便于检查每一项对应的单射。

上界可能长期接近 $1$ ，并不能说明游戏会持续多久。另一方面，只要每个方向都具有正权重，就能证明角色最终必然相遇；这个结论只保证终止，不给出实用的等待时间估计。

定理 5.（遭遇几乎必然发生，游戏几乎必然结束）

在 A1、A3 以及各角色四个移动方向的权重严格为正的条件下，若初始至少有两名角色，则

Pr (𝜏_{𝑒} < \infty) = 1

；此后每次决斗使存活人数严格减少

1

，故游戏在恰好

𝑛 - 1

次决斗之后结束。特别地每名角色必然至少遭遇一次（

Pr (𝑇_{𝑖}^{enc} < \infty) = 1

），因为最后一场决斗的胜者正是那名唯一幸存者。

证明. 固定两名角色

𝑎

、

𝑏

。从任意局面出发，考虑如下事件：其余所有角色在接下来每一步都选择“原地不动”（合法且概率为正），而

𝑎

沿一条长度不超过

𝑁 - 1

的路径逐回合朝

𝑏

的格子走去。若

𝑎

中途撞上任何角色，遭遇已经发生（正是我们要的）；否则在至多

𝑁 - 1

回合后

𝑎

与

𝑏

相邻，下一回合

𝑎

走进

𝑏

的格子，必然遭遇。这条“剧本”的概率有一个只依赖

𝑁

与最小正权重的正下界

𝛿

，因此

Pr (𝜏_{𝑒} > 𝑘 𝑁) \leq {(1 - 𝛿)}^{𝑘} \to 0

。遭遇之后剩下

| 𝑆 | - 1

人的子局合同理，逐次归纳即得游戏几乎必然结束，决斗次数恰为

𝑛 - 1

。最后，每名角色要么在某场决斗中被淘汰（那就是遭遇过），要么是唯一幸存者（它参加了最后一场决斗），故

𝑇_{𝑖}^{enc} < \infty

几乎必然。

□

注 8.（几何尾界与实际等待时间）

证明中的

𝛿

是统一下界，通常远小于实际相遇概率，因此不能据此估算等待时间。算例中游戏结束的平均时间约为

731

回合（见 “三、数值结果”）；“几乎必然结束”只说明结束事件的概率为

1

，并不限制其期望必须很小。

理论上可递推，不等于在给定规模下能够存储全部状态。下一步估计状态数，以决定哪些情形采用精确计算、哪些情形采用模拟。

定理 6.（精确递推的可解性边界）

定理 4 的状态数是

，数量级为

𝑁^{𝑛}

。本文算例中，

𝑁 = 200

、

𝑛 = 7

对应约

1.3 \times 10^{16}

个七人位置状态，无法直接存储；若只保留两名角色，则有

𝑁 (𝑁 - 1) = 39800

个未遭遇的位置状态，可以在同一张地图上做精确递推。因此七人局采用蒙特卡洛，并用两人局的精确解检验实现。

七人局采用独立重复的模拟。对每个回合的遭遇、结束等事件，记录出现次数便得到概率估计；误差的量级由模拟局数决定。

命题 7.（蒙特卡洛估计量与误差）

设独立重复 $𝑀$ 局。对任意事件 $𝐴$ ， $^𝑝 = 𝐾 / 𝑀$ 无偏，标准误为 $\sqrt{𝑝 (1 - 𝑝) / 𝑀}$ ，95% 的 Wilson 区间为

(^𝑝 + 𝑧^{2} / (2 𝑀) \pm 𝑧 \sqrt{^𝑝 (1 -^𝑝) / 𝑀 + 𝑧^{2} / (4 𝑀^{2})}) / (1 + 𝑧^{2} / 𝑀), 𝑧 = 1.96 .

对均值，用样本均值与样本标准误。本文取

𝑀 = 8 \times 10^{5}

，此时

𝑝 \approx 1 / 2

的标准误约

5.6 \times 10^{- 4}

；对整局结束时间的均值，标准误是

0.51

个回合。

二、面向对象的实现

完整代码把上述数学对象分为地图、单角色、精确游戏递推、蒙特卡洛模拟和可视化五部分。地图文本、行动顺序与默认权重分别由 MAP_TEXT、TURN_ORDER 和 DEFAULT_MOVE_WEIGHTS 给出，与 Code/gridGameOptimized.py 中的算例配置一致。下表列出各类与模型的对应关系。

类	表示的数学对象	关键成员
`GridMap`	地图 $𝐺 = (𝑉, 𝐸)$ 与角色标签	`cells` / `index` / `step_table`（ $𝛿_{𝑘}$ 查表，非法记 $- 1$ ） / 连通性自检
`Walker`	角色权重与链 $𝑄_{𝑖}$	`legal` / `total_weight`( $= 𝑊_{𝑖}$ ) / `Q` / `occupancy` / `first_passage_maps` / `stationary_analytic`
`Game`	定义 5 的一回合核与张量递推	`_advance`（逐角色推进） / `_split_at` / `first_duel` / `self_check`
`MonteCarlo`	同一核的采样版本	向量化整局推进 + 已结束试验即时剔除
`Visualizer`	可视化	逐帧概率 GIF / 分布曲线 / 首达热图

定义 3 的“先筛合法方向、再归一化”直接落成一张逐格的合法动作表；均匀权重时可以走一条更快的采样捷径，但这里有一个真实的坑：

# 均匀权重时动作在合法集合上均匀分布，可以把合法目标压缩到前几列
order = np.argsort(~self.legal, axis=1, kind="stable")   # 合法排在前
self.legal_targets = np.take_along_axis(grid.step_safe, order, axis=1)
# 反例：某格"向上"是障碍而其余方向合法时，合法掩码是 [F,T,T,T,T]，
# 若直接按方向顺序取前 d=4 列，就会把"向上"（原地）算进来、"原地不动"挤出去，
# 采样分布立刻偏离 Q_i。必须先把合法项压到前 d 列。

定理 4 的核心是“逐角色推进 + 即时决斗”，实现上就是一个带分支的递归：

def _advance(self, turn, alive, arr, k, dueled, turn_dueled, nxt):
    if k == len(self.order):                      # 本回合队列走完
        nxt[alive] = self._add(nxt.get(alive), arr); return
    who = self.order[k]
    if who not in alive:                          # 已淘汰 -> 跳过
        self._advance(turn, alive, arr, k + 1, dueled, turn_dueled, nxt); return
    axis = alive.index(who)
    arr = _contract(self.walkers[who].Q, arr, axis)          # who 移动一格
    free, pieces = self._split_at(arr, alive, axis)          # 拆分：互异 / 第一对重合
    if free.any():
        self._advance(turn, alive, free, k + 1, dueled, turn_dueled, nxt)
    for partner, sel in pieces:                   # who 撞上了 partner
        ...
        for dead in (who, partner):               # 各以 1/2 被淘汰
            alive2 = tuple(x for x in alive if x != dead)
            new = 0.5 * sel.sum(axis=alive.index(dead))      # 求边缘，消去死者坐标
            if len(alive2) == 1:                              # 只剩一人 -> 结束
                self.end_pmf[turn] += float(new.sum())
            else:
                self._advance(turn, alive2, new, k + 1, new_dueled, True, nxt)  # 本回合继续

单角色那一侧， $𝔼 [𝑇]$ 与 $𝜎 [𝑇]$ 走命题 3（ $200$ 次 $199 \times 199$ 求逆），定理 2 只用来抽查校核，避免把四万步迭代套在 $200 \times 200$ 个格对上。

复杂度：精确递推单回合 $𝑂 (\sum_{𝑆} | 𝑆 | 𝑁^{| 𝑆 | + 1})$ 、存储 $𝑂 (𝑁^{𝑛})$ ；本文只对 $𝑛 = 2$ 与一个 $6 \times 6$ 的测试地图用精确递推， $7$ 人局用蒙特卡洛， $8 \times 10^{5}$ 局、上限 $10^{4}$ 回合、已结束的试验即时从数组里剔除，几分钟跑完。

三、数值结果

以下结果使用同一地图与初始配置。七人局模拟 $8 \times 10^{5}$ 次，每局最多运行 $10^{4}$ 回合，所有试验都在上限内结束；两人局另模拟 $4 \times 10^{5}$ 次，与精确递推对照。单角色首达量由转移矩阵计算。阅读图表时应区分：占用动画对应实际游戏，首达热图对应忽略淘汰的延续轨迹。

1. 单角色的到达概率与首次到达

先看实际游戏内的短时占用概率，再看不考虑淘汰时的首达时间。两类图使用同一移动规则，但对应的随机事件不同，数值不能直接互换。

占用动画展示的是概率质量随回合扩散的过程。若要比较“从某个出发点到不同目标格需要多久”，则应转向延续轨迹的首达时间；下面两幅热图分别给出其期望和标准差。

热图汇总了全部目标格。为看清首达时间分布的形状，再从角色 1 的出发点选取四个距离和位置不同的目标格，绘制各自的概率质量函数与累积分布。

角色 1 的目标格	$(0, 0)$	$(7, 4)$	$(0, 14)$	$(14, 14)$
首达期望 $𝔼 [𝑇]$	458.50	709.13	1623.23	1801.48
首达标准差 $𝜎 [𝑇]$	1085.07	852.28	1563.64	1571.01

全部 $200 \times 200$ 个（起点, 目标）组合的期望落在 $[0, 1802.98]$ 内，标准差最大 $1571.01$ 。在这张有限地图上，部分较远目标格的首达标准差与期望同量级，说明单次等待时间分散。定理 3 保证尾概率最终几何衰减，因此不宜把这一有限状态模型的分布直接称为重尾分布。

2. 遭遇

遭遇记录的是回合内部是否出现角色同格，不能仅凭回合结束时的位置判断。以下先看整局第一次遭遇发生在哪里，再比较首次遭遇、任意遭遇及“尚未遭遇”的时间分布。

图中的全局首次遭遇与各角色首次遭遇不是同一随机变量。前者在一局中只出现一次；后者分别记录每名角色第一次参与决斗的回合。相应的期望与离散程度列于下表。

量	期望	标准差	中位数	众数	90% 分位
整局首次遭遇 $𝜏_{𝑒}$	20.594	13.606	17	11	40
角色 1 首次遭遇	99.867	170.225	50	—	212
角色 2 首次遭遇	94.711	161.971	48	—	199
角色 3 首次遭遇	95.438	172.833	43	—	212
角色 4 首次遭遇	77.828	150.410	34	—	170
角色 5 首次遭遇	102.465	177.879	48	—	226
角色 6 首次遭遇	82.169	151.855	39	—	175
角色 7 首次遭遇	166.614	236.532	91	—	370

积和式上界与模拟得到的“尚未遭遇”概率差别明显： $Pr (全体互异)$ 在第 $1$ 、 $5$ 、 $10$ 、 $20$ 、 $50$ 回合分别是 $1.0000$ 、 $0.9806$ 、 $0.9528$ 、 $0.9309$ 、 $0.9123$ ，而真正的“尚未遭遇”概率同一批时刻只有 $1.0000$ 、 $0.9501$ 、 $0.7591$ 、 $0.4040$ 、 $0.0476$ 。到第 $20$ 回合，真实生存概率已降至约 $0.40$ ，仅由终点位置计算的上界仍为约 $0.93$ 。这个差距表明，终点位置没有记录回合中途发生的遭遇；要估计遭遇时间和结束时间，必须保留路径信息（定理 4）。

整局第一次遭遇的期望为 $20.59$ 回合，各角色首次参与决斗的期望则介于 $78$ 与 $167$ 回合之间。原因是整局第一次决斗只涉及两名角色，其余角色仍须等待各自的首次遭遇。角色 7（ $(8, 14)$ ，地图最右侧）最晚被卷入（ $166.6$ ），角色 4（ $(10, 5)$ ，紧贴障碍块下方、离角色 3 只有 $4$ 步）最早（ $77.8$ ）。

3. 游戏结束

每场决斗淘汰一人，因此七人局在第六场决斗后结束。结束时间不仅取决于第一场遭遇，还取决于其后各次相遇的等待时间。下图和表给出完整分布及其主要统计量。

量	期望	标准差	中位数	众数	95% 分位
游戏结束 $𝑇_{end}$	731.082	459.417	614	404	1631

结束时间的 25%、75%、90%、99% 分位分别为 $408$ 、 $927$ 、 $1328$ 、 $2332$ 回合。中位数为 $614$ 回合，说明约一半的试验需要至少这么久；约百分之一的试验超过 $2332$ 回合。定理 5 给出的是几乎必然终止，并不要求终止时间集中在较短的范围内。

4. 谁会赢：这一配置中的位置与行动顺序

决斗双方的淘汰概率相同，并不意味着七名角色的最终获胜概率相同。出发位置和行动顺序会改变它们参与决斗的时机。先比较原配置下的首次遭遇时间与获胜概率：

角色	1	2	3	4	5	6	7
首次遭遇期望	99.9	94.7	95.4	77.8	102.5	82.2	166.6
获胜概率	0.13813	0.13478	0.14075	0.12791	0.14315	0.12894	0.18634

这些获胜概率并不相等。若七名角色在地图和规则下完全对称，它们才都应为 $1 / 7 = 0.14286$ ；当前配置并不满足这种对称性。角色 7 是 $0.186$ ，角色 4 只有 $0.128$ ，相差近 $1.5$ 倍。在这七名角色中，首次遭遇期望较大的角色通常也有较高的获胜概率。两者的 Spearman 秩相关系数是 $0.96$ （ $7$ 个点里只有第 1、3 名的次序互换了）。

这一相关性可以这样理解：每参加一次决斗，角色都有 $\frac{1}{2}$ 的概率被淘汰；较晚遭遇的角色可能少经历若干场决斗。不过，首次遭遇时间本身并不能单独决定胜率。角色 7 从地图右侧出发，在本次模拟中首次遭遇最晚，获胜概率也最高。

角色 7 同时具有靠右的出发位置和最后行动的顺序，单凭原配置不能区分两者的作用。保持地图、出发点和行动权重不变，仅将行动顺序整体倒过来（ $7, 6, \dots, 1$ ）重跑了一遍 $2 \times 10^{5}$ 局：

角色	正序 $1 \to 7$ （ $8 \times 10^{5}$ 局）	逆序 $7 \to 1$ （ $2 \times 10^{5}$ 局）
1	0.13813	0.14113
2	0.13478	0.13486
3	0.14075	0.13941
4	0.12791	0.12698
5	0.14315	0.14277
6	0.12894	0.12871
7	0.18634	0.18615

正序与逆序估计的标准误分别约为 $4 \times 10^{- 4}$ 和 $8 \times 10^{- 4}$ 。角色 7 的两项估计为 $0.18634$ 与 $0.18615$ ，差值小于合并标准误；其余角色的变化绝对值均不超过 $0.003$ 。这组对照支持如下有限结论：在本文配置与这两种行动顺序下，角色间约 $0.058$ 的获胜概率差异主要与出发位置相关，倒转顺序的影响较小。角色 1 的两项估计相差约 $3.4$ 个合并标准误，提示顺序也可能产生可测影响；仅凭这两组模拟，不能断言任意顺序下都如此。

四、讨论

单角色移动。 延续轨迹的到达概率和首达时间只依赖 $𝑄_{𝑖}$ ，可以精确计算。游戏内占用还取决于角色是否存活，本文用蒙特卡洛估计。若要计算“淘汰前首次到达”，还需在完整游戏模型中另行统计到达概率及条件首达时间；本文的首达热图不表示这一事件。对称权重下，平稳概率与方格的合法动作权重之和成正比。
遭遇时间。 命题 6 只根据同一时刻的位置分布给出“尚未遭遇”概率的上界。它不记录回合中途的碰撞，因此不能代替遭遇时间分布。完整局面链在七人局中无法直接存储，故采用蒙特卡洛。
游戏结束时间。 七人局需经历六次决斗才会只剩一人。因此结束时间的期望约为 $731$ 回合，显著大于整局首次遭遇时间的期望 $20.6$ 回合。两者之间的差额来自首次遭遇之后的继续游走与后续决斗；不能仅由第一次遭遇的分布推得结束时间。
行动顺序决定谁先移动以及遭遇发生时谁尚未行动。“三、数值结果” 的逆序对照中，获胜概率的变化绝对值不超过 $0.003$ ；这一结果只适用于所比较的两种顺序和当前配置。

以上数值结果依赖 “一、地图、行动权重与边界转移” 中的规则。尤其是顺序行动和决斗耗时的约定，改变它们会改变相应的时间分布：

A2（顺序行动）。若改读为“所有角色同时提交动作、回合结束时检查是否有同格”，那么“回合锁定—继续”就失去了对象，交换位置也不再触发遭遇；三问都会变。本文采用顺序读法的理由已经写在 “一、地图、行动权重与边界转移” 的注记里，也与 Code/gridGameOptimized.py 的实现一致。
A5（决斗同回合完成）。若决斗占用额外回合，首次遭遇之前的分布仍由相同移动规则决定；之后的遭遇时间、游戏内占用与结束时间都要计入锁定时长。只有在额外时长的分布及其与局面的依赖关系明确后，才能进一步修正结果。