天使与方格吞噬者问题的策略模拟
天使问题发生在一张无限大的整数网格棋盘上，天使初始在原点 $(0, 0)$ 处。每回合，先由魔鬼禁用掉任意一个格子，然后天使尝试移动到一个未被禁用的格子。天使的移动受力量值 $K$ 约束：若当前在 $(x, y)$ 则下一步位置需满足 $|x' - x|, |y' - y| \leq K$. 天使的胜利条件是总是有方法移动下去。
以下概述 $K = 2$ 下的必胜策略思路，参考的是知乎回答有哪些令人为之惊叹的数学题目？对应的在线项目见于天使与方格吞噬者。
我们称两个相邻格子之间的边界为线段，由无限个线段序列构成的连续有向路径是曲线（允许线段在曲线中多次出现）。
对曲线中一线段 $s$, 沿曲线的行进方向观察时，与该线段相邻且位于其右侧的格子称为 $s$ 的右格，另一侧相邻的格子称为左格。
曲线 $\kappa$ 称为边界曲线，如果存在某个满足以下条件的格子集合 $V_{\kappa}$:
- 棋盘上的任意一条线段在 $\kappa$ 中出现的次数不超过 $2$ 次
- 若某一线段在 $\kappa$ 中仅出现 $1$ 次，则该线段的左格属于 $V_{\kappa}$ 右格不属于 $V_{\kappa}$
- 若某一线段在 $\kappa$ 中仅出现 $2$ 次，则这两次出现的方向相反，且该线段的两个相邻格子均属于 $V_{\kappa}$
- 若某一线段未出现在 $\kappa$ 中，则该线段的两个相邻格子要么均属于 $V_{\kappa}$ 要么均不属于 $V_{\kappa}$
- $V_{\kappa}$ 及其补集均为无限集
- $V_{\kappa}$ 在 $\kappa$ 的分隔下连通
可以证明 $V_{\kappa}$ 若存在则唯一，称为 $\kappa$ 的左集，其补集称为 $\kappa$ 的右集。
我们定义两种变换边界曲线 $\kappa$ 的操作：
- “拓展”：若 $\kappa$ 中某一线段的右格 $q$ 不属于 $V_{\kappa}$, 将此线段替换为 $q$ 的另外三条边界，且替换后的线段方向使得 $q$ 成为其左格
- “收缩”：若 $\kappa$ 中某两条连续线段在棋盘上重叠但方向相反，将这两条线段从 $\kappa$ 中删除
在操作下左集只会增加元素。称有限次操作得到的为 $\kappa$ 的后代曲线。
天使的策略是维护一条边界曲线作为逃生路径（天使始终处在某个线段的右格；依此划分为过去段、当前段与未来段）。初始的边界曲线自南向北无限延申。每次魔鬼操作后，天使尝试更新边界曲线，然后沿着它移动两格（这使得天使甚至不需要用 $(\pm 2, \pm 2)$ 这样的移动）。
在任意时刻，将方格划分为三类：
- “规避格”：当前路径的左集中的方格
- “被禁格”：右集中被禁用的方格
- “自由格”：右集中未被禁用的方格
我们记天使第 $i$ 轮行动得到的路径为 $\lambda_i$, 则可定义 $\kappa$ 的长度 $L_{\kappa}$ 是 $\kappa$ 与 $\lambda_0$ 去除过去段与未来段足够远的完全一致部分后，两者线段的数量差。
对第 $j$ 轮行动与某条边界曲线 $\kappa$, 定义规避值 $n_{\kappa}(j)$ 为：第 $j$ 轮行动时 $\kappa$ 左集中曾经的“被禁格”的数量。也就是用来统计自游戏开始到第 $j$ 轮以来，天使更新路径时，主动把“被禁格”转换为“规避格”的数目。
天使的正式策略如下：
在第 $i$ 轮行动开始时，设 $\lambda_{i-1}$ 为当前路径，$p_{i-1}$ 为当前所在线段。
首先，定义 $P_i$ 为满足以下两个条件的所有边界曲线 $\mu$ 构成的集合：
- $\mu$ 是 $\lambda_{i-1}$ 的后代曲线
- $\mu$ 与 $\lambda_{i-1}$ 在过去段及当前段完全一致
随后，定义 $Q_i$ 为 $P_i$ 中 $L_{\mu}-2n_{\mu}(i)$ 最小的那些 $\mu$ 构成的集合。
最后，定义 $R_i$ 为 $Q_i$ 中 $n_{\mu}(i)$ 最大的那些 $\mu$ 构成的集合。逃生路径 $\lambda_i$ 可以在 $R_i$ 中任取。