首页 > 其他分享 >博弈论二次回顾

博弈论二次回顾

时间:2024-10-04 21:01:54浏览次数:1  
标签:石子 游戏 回顾 二次 sg 博弈论 后继 硬币 SG

主要是一些模型。

ICG的定义

  • 双方轮流移动
  • 不能行动者判负
  • 所能进行的操作仅与当前局面有关,与操作者无关

一般而言发现 ICG 就可以考虑 SG 了。

SG

分清楚 后继状态子游戏

子游戏的和是 \(\oplus\),后继状态的和是 \(mex\)。

后继状态 指进行一次操作所能够达到的状态。

子游戏 是指将原本游戏拆分为若干个同时进行的游戏,也就是当前的决策者可以随意挑出一个单一子游戏进行决策。

一个例子是Nim游戏里子游戏指每一堆石子的变化,而后继状态对于整体游戏相当于是操作一次后的局面,对于子游戏相当于是当前这一堆石子取走后的局面(只看这堆)

运用SG函数时,找到合适的视角划分子游戏后继状态

我们可以将组合游戏中的每一个状态抽象成图中的一个点,将每一 步决策抽象成图中的一条边。我们将这个图称为该组合游戏的游戏图。 这样,对于组合游戏中的每一次对弈,我们都可以将其抽象成游戏 图中的一条从某一顶点到出度为 0 的点的路径。 组合游戏向图的转化,并不单单只是为了寻找一种对应关系,它可以帮助我们淡化游戏的实际背景,强化游戏的数学模型,更加突出游戏 的数学本质!

-by JZH2009年集训队论文。

对于任意的组合游戏,我们仅关心它的 \(sg\) 函数值,而不关心具体细节,所以可以将其直接变为一堆石子,石子个数是 \(sg\) 函数值


一些模型

Anti-SG

将ICG变为不能行动者胜利。

当且仅当:

  • 所有石子堆都只有一颗且有偶数堆。
  • 至少有一堆石子大于一颗且游戏和不为零。

可以给出 SJ 定理

当所有游戏条件不变,仅将最后行动者判负,则先手必胜当且仅当:

  • 任意子游戏 \(sg\) 值 \(\le 1\),且最终游戏和为零。
  • 存在子游戏 \(sg\) 值 \(\ge 2\),且最终游戏和不为零。

Multi SG

事实上更多问题是这玩意。

其实就是:我们需要进行多次子游戏的拆分

原本游戏视作若干单一游戏的和,而某个单一游戏的后继是多个单一游戏

只要 后继关系满足拓扑原则(不成环) 即可以使用 \(sg\) 函数求解,后继使用 \(mex\),游戏和使用 \(xor\)。

可以在P3197看到这个应用。

阶梯Nim

  • 有若干级阶梯,每级阶梯上有一个单个游戏
  • 每次可以对一个阶梯操作并将操作中失去的东西丢到下一级阶梯上。

结论是奇数阶梯上的 \(sg\) 游戏和。

翻硬币

  • N 枚硬币排成一排,有的正面朝上,有的反面朝上。我们从左开始对硬币按 \(1\) 到 \(N\) 编号。
  • 游戏者根据某些约束翻硬币(如:每次只能翻一或两枚,或者每 次只能翻连续的几枚),但他所翻动的硬币中,最右边的必须是从正面翻到反面。
  • 谁不能翻谁输。

局面的 SG 值为局面中每个正面朝上的棋子单一存在时的 SG 值的异或和

Proof:

由于游戏是正面到反面,所以将反面看作 \(0\),正面看作 \(1\),这样一个左边是最高位的二进制数。

则在翻动过程中二进制数的值始终减小,那么满足拓扑原则。

那么可以考虑归纳证明,按照二进制数的大小,首先正面硬币不超过 \(1\) 个的局面显然成立。

利用 \(sg\) 值相同的两个游戏可以互相抵消,可以看作给影响到的硬币全部叠上一个正面朝上的硬币。这样的一个新游戏的 \(sg\) 值与原本只去掉操作的硬币后的局面 \(sg\) 值的异或可以得到后继局面的 \(sg\) 值,那就完了。

K-nim

每次可以取不超过 \(k\) 堆石子。

设 \(r_i\) 为每一堆石子二进制第 \(i\) 位数字之和,若 \(\forall i,r_i\equiv 0(\bmod k+1)\) 则先手必败。

树的删边游戏

考虑解决子树 \(u\) 的 \(sg\) 值。

可以看作 \(u\) 与其每个儿子 \(v_i\) 构成一个单一的子游戏(其他儿子树内操作不会影响到它们)。

并且这个子游戏的 \(sg\) 值是 \(sg_v+1\)。这可以归纳证明,我们考虑用一棵树的节点个数作为拓扑序进行归纳(满足拓扑原则)。

对于叶子显然成立,否则对于非叶子,我们知道删掉其子树 \(v\) 里的边构成的 \(sg\) 值集合是 \(\lbrace 1,2,…sg_v\rbrace\) 同时存在 \(0\),也就是断掉 \(u\to v\)。

那么就得到 \(sg_v+1\) 这个结论。

所以 \(sg_u=\oplus_i (sg_{v_i}+1)\)

无向图删边游戏

一个特殊情况是每条边至多属于一个环的情况,则对于一个奇环而言,断掉一条边后剩下两条不同奇偶的链,其 \(sg\) \(xor\) 和不可能为 \(0\),此时 \(sg\) 是 \(0\)

对于一个偶环而言,断掉后奇偶性相同,且是可以取到 \(0\) 的,则 \(sg\) 值是 \(1\)。

那么扩展后有 Fusion Principle 定理。

对无向图做如下改动:将图中的任意一个偶环缩成一个新点,任意一个奇环缩成一个新点加一条新边;所有连到原先环上的边全部改为与新点相连。这样的改动不会影响图的 SG 值。

虽然我并没有懂这什么意思

标签:石子,游戏,回顾,二次,sg,博弈论,后继,硬币,SG
From: https://www.cnblogs.com/spdarkle/p/18447262

相关文章