奇偶博弈的位置确定性

位置策略不记“这是第几次来这里”，却可以利用不同区域的结构。一个区域按吸引秩强制回到关键优先级；另一区域交给规模更小的博弈。只要跨区方式受到闭包约束，就无需在运行时额外保存一个“当前阶段”变量。

吸引域公理库安全博弈与反应式综合Safety game · Reactive synthesis · 安全游戏 · 获胜区域 · Controllable predecessor从安全闭包进入有限Büchi博弈，用嵌套吸引域计算反复到达目标的获胜区域，并构造双方位置策略。Attrᵢ(U)是玩家i能强制有限步到U的区域：己方有一个后继能推进，对方的所有后继都必须推进。去掉它之后，每个剩余顶点仍有剩余后继，所以能形成总的诱导子博弈。这里复用吸引域工具，不把一般奇偶结论归结为一次Büchi求解。

两种递归情形的完整证明 ​

空图结论平凡。对非空G，取最小优先级m，令p=m mod2，o=1−p，U为所有优先级m的顶点，A=Attrₚ(U)。在H=G∖A上用归纳假设，得到闭合获胜区Xₚ、Xₒ及位置策略。

情形一：Xₒ为空。 玩家p在H上已有统一获胜策略；在A∖U上用吸引域下降策略，在自己拥有的U顶点任取一个合法后继。各区不相交，这定义一份位置策略。

若一条符合策略的play无限次到A，则每次到A∖U都被严格下降的秩送到U；所以U无限出现，最小全图优先级m决定玩家p获胜。若A只出现有限次，play最终永留H并服从归纳策略，也由p获胜。有限前缀不改变奇偶结果，因此p赢全部V。

情形二：Xₒ非空。 先观察Xₒ在原图中仍由o控制并获胜。H是p的吸引域补集：p拥有的H顶点没有边逃到A；o自己的归纳策略又留在Xₒ。因此原图新增的出界边不会破坏这份o策略。

令B=Attrₒ(Xₒ)。在B∖Xₒ用o的吸引策略，进入Xₒ后用上述归纳策略，o赢整个B且保持其中。再对C=G∖B作第二次归纳，得到Yₚ、Yₒ。

玩家p在Yₚ的子博弈策略可直接用于原图，因为C是o吸引域的补集：o拥有的C顶点无法跳到B，p按自己的策略留在Yₚ。因此p赢Yₚ。

玩家o在Yₒ先用第二次归纳策略。如果play一直留在C，它按该策略获胜；若p选一条原图边跳入B，就转用B上的闭合策略，此后不再出来。每个顶点只属于Yₒ或B中的一块，选边仍只看当前顶点，不需要记录“以前是否进过B”。因此o赢B∪Yₒ。

两种情况都覆盖V，并交付双方位置策略。一个顶点不可能同时由双方获胜，否则把两份策略放在一起会产生一条既偶胜又奇胜的play。每个归纳子图都严格少至少一个顶点，因而整个证明良基且不循环。

六顶点例的区域拼接 ​

使用奇偶博弈页的图：s→a,c；a→a,b；b→a；c→c,d；d→b,e；e→e。归属Even={s,b,d}，优先级(s,a,b,c,d,e)=(2,1,0,2,1,2)。

最小色0出现在b，p=Even。它的吸引域A={b,d}，因为d可以主动选b，而a有自环、c有自环，不会被强迫进A。剩余H={s,a,c,e}中，Odd从a赢，Even在s选c并在c/e的2环获胜，所以Xₒ={a}。

回到原图取Odd吸引域B={a,b}。不能把d也放入B，因为d可选e逃开；也不能把s放入B，因为s可选c。剩下C={s,c,d,e}由Even统一选择s→c、d→e获胜。于是W₀=C、W₁=B，与直接逐路径分析一致。

一般Muller目标为什么可能需要记忆 ​

考虑一个全部由Even行动的图：中心s可选a或b，a、b都只能回s。目标要求a和b都无限出现，即Inf集合恰为{s,a,b}。策略可以记一位，在s轮流选择a、b，所以存在获胜策略。

但位置策略在s只能固定选一个后继，另一个永远不再出现，因此所有位置策略失败。这个Muller目标不是同一原图上的某个奇偶着色：若两种单独循环都要输而交替循环要赢，仅靠原顶点优先级的最小值无法实现。增加记忆的自动机积可以变成奇偶博弈，位置策略的“当前位置”也随之包含了新增记忆。

定理给获胜策略一个线性规模的输出接口：在己方每个获胜顶点标一条边。它不说求出这些边一定多项式，也不说任意取一条仍在获胜区域内的边都安全；例如随便困在一个奇自环可能毁掉长期目标。

Zielonka递归公理库Zielonka 奇偶博弈算法Zielonka algorithm · Recursive parity game solver按最小优先级吸引域递归求解，在对手种子非空时回原图扩张并二次递归，保留双方位置策略。将上述两种情形落实成可执行的集合运算与策略合并，算法页负责第二次递归的账本和成本，不反过来为本定理提供前提。

有限性、完整观察与轮流选择都是本页范围。部分观察需要根据相同观测历史作一致选择，不能把原图位置策略直接交给看不到顶点的控制器；一般无限图或更广接受目标也须引用相应版本，不能只凭同名“博弈”沿用结论。