随便搞搞 ICG (公平组合游戏) 和其余的博弈

写在阅读之前:

本文是我在 10 月份期间开始的对一些见过或者想要学习的博弈模型的一个总结计划。本文篇幅较长,覆盖多种模型,以下是一份可以帮助阅读、理清主干的主题清单:

(待填充)

请注意本文分多页,可以在文末翻页

文章中数学证明、公式较多,请做好阅读理解的准备。这篇文不是闹着玩的,读就请认真读它。先说一句比较自以为是的话:

读这篇文学习博弈论的过程,并不是去背公式或者记性质,而是去熟悉并掌握处理博弈问题的一般思维方式。

快速索引:

Wythoff Game –  第 1 页

Nim Game – 第 2 页

从 Nim Game 到其他组合游戏 ||  归纳与推广、泛化模型 – 第 3 页

SG 函数的构造 || 更进一步的推广 – 第 4 页

Anti-Nim 与 Anti-SG – 第 5 页

Multi-SG || Every-SG – 第 6 页

翻硬币游戏 || NimK || 扩展 NimK第 7 页

树上删边游戏 || 无向图的删边游戏 – 第 8 页

扩展阅读列表  – 第   页

记号约定清单:

对于集合,用 \mathbb{A} 的字体表示。

对于局面,用 \mathbf{a} 的字体或 \mathrm{S},\mathrm{T} 来表示。

\text{s.t.}  → “ 使得 ”  , such that subject to 的缩写。

\forall \exists 分别为 “ 任意 ” 和 “ 存在 ” 的意思(数学量词)。

\oplus  → 代表 xor ( 按位异或 ) 运算。

DAG → 有向无环图。

ICG → 公平组合游戏。

SG → Sprague-Grundy 函数


Wythoff Game

经典的 Wythoff 博弈模型。

这个模型的描述是这样的:地上有两堆石子,其中一堆有 m 个石子,另外一堆有 n 个石子。两名玩家轮流取走石子,规定每次要么从其中一堆石子中取走任意多个石子,要么从两堆石子中取走相同数量的石子。等到谁没有石子可取了,谁就输了。也就是说,取到最后一个石子的玩家获胜。

这玩意其实还可以描述为:

把国际象棋棋子皇后放在棋盘上,两人遵循棋子的走法,轮流移动棋子,但只能将棋子往左方、下方或者左下方移动。谁先将棋子移动到棋盘的最左下角,谁就获胜。

描述局面、获得结论

我们知道博弈的关键就是局面,那么我们考虑用一个数学模型去描述局面好了。我们把局面记作一个无序二元组 (n,m)

  • 首先我们知道 (0,0) 是一个必败态
  • 其次, (n,0) \,(n \in \mathbb{N}_{+}) (n,n) \,(n \in \mathbb{N}_{+}) 是必胜态,因为先手拿走 n 就好了。
  • 再然后,我们考虑一个更加一般的状态 A=(n,m) \,( n,m \in \mathbb{N}_{+} \,\, , n \ne m)

我们先给出结论:所有先手必败的数对(我们称为奇异局面)分别是:

(1, 2), (3, 5), (4, 7), (6, 10), (8, 13)

更严格地来说,其实是:

\mathbb{S} = \{(\lfloor 1 \cdot \varphi \rfloor , \lfloor 1 \cdot \varphi^2 \rfloor ) \,,\, ( \lfloor 2 \cdot \varphi \rfloor , \lfloor 2 \cdot \varphi^2 \rfloor ) \,,\, ( \lfloor 3 \cdot \varphi \rfloor , \lfloor 3 \cdot \varphi^2 \rfloor ) \,,\, ( \lfloor 4 \cdot \varphi \rfloor , \lfloor 4 \cdot \varphi^2 \rfloor ) \}

其中的 \varphi \frac{ \sqrt{5}+1 }{2}

关于这个结论最科学的推法(而不是什么打表找规律),这里有我整理的一份文档,可以读一读 : Wythoff Game

证明结论

这里我们尝试证明这些状态的三个性质,从而证明这个构造是先手必败的(设状态为 \forall A \in \mathbb{S} )  :

  • 状态 A 无法一步转移到状态 (0,0)
  • 状态 A 无法一步转移到 \mathbb{S} 的另一个状态。
  • 状态集合 \mathbb{S} 之外的任何非零状态都可以一步转移到一个零状态\mathbb{S} 中的某一状态。

这样我们的博弈策略是后手始终把当前状态转移到 \mathbb{S} 中的状态,从而可以胜利。

对于上面三条性质的证明,可以在这里找到。我有空再仔细补坑