Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

NIM游戏、博弈论与SG函数

写在前面

Part 1

由于这真的是一个比较大的专题 所以MB决定分开几次进行学习
更新当然是不定时更新了

Part 2

学习参考资料:来自zyf2000的博客 学姐讲的真的超好的 好多证明都特别巧妙
学姐的博客

0.引子

在《博弈圣经》中博弈论的定义:我们把动物利用大自然移动的瘾魂,在决策人期待的空间里,形成三维均衡的语文学理论,称为博弈论。
博弈论又被称为对策论(Game Theory)既是现代数学的一个新分支,也是运筹学的一个重要学科。
博弈论主要研究公式化了的激励结构间的相互作用。是研究具有斗争或竞争性质现象的数学理论和方法。 博弈论考虑游戏中的个体的预测行为和实际行为,并研究它们的优化策略。生物学家使用博弈理论来理解和预测进化论的某些结果。
本文只是讨论了信息学竞赛中博弈方面最基本最简单的几个方法和结论。
由于这一类博弈问题都有一个共同的要求就是博弈双方都是“绝对聪明”的,所以据说只有“绝对聪明”的人才能学好博弈论哦。
下面就跟随MB来体验这个问题的奇妙吧

1.NIM游戏

1.1 取石子游戏

今天我们认识一对好朋友 Alice和Bob 两个人喜欢玩各种各样的游戏
游戏大意:两个人游戏 给你n堆石子 每堆石子个 每次可以从一堆中取至少一个至多个 给你游戏开始的时候每堆石子多少 问你先手必胜还是后手必胜
这道题保证双方都知道最优策略

1.2 一点名词

N-position——先手必胜局面

P-position——先手必败局面

它们的性质如下:
- 对于一个N-position满足经过一次操作后能够变成一个P-position
- 对于一个P-position满足经过一次操作后无论如何都能变成一个N-position
- 易知对于集合如果满足 这是一个P-position

1.3 取石子游戏的结论

这样的一个游戏当然是让人哭笑不得 这就几堆自己分析分析还行 石子一多了马上就没用了
所以当然是有一个显而易见的结论的

我们说这是一个先手必败局面

1.4 结论的证明

我们分为三个角度来证明这个问题

1.4.1.特殊情况

当我们面对的集合满足上面提到的性质3 我们认为这是一个P-position
此时满足给出的结论

1.4.2.

这个是我们仅有的需要证明的东西
首先我可以先告诉大家这是一个N-position
怎么证明呢
我们从这个集合里面提取中一个 然后呢我们设所有元素的异或和是S 这个时候如果S不是0 那么一定存在S的二进制的某一位为1
不妨设这个1就来自我们提取出来的元素 那么经过一次Xor操作 我们把变成 根据二进制的性质 我们知道 一定变小了 而且这个时候S最高位的0也没了 接下来就是最令人惊奇的时刻
我们显然知道除掉 之后所有元素的异或和就是 (把异或两遍它就没了)
然后这个时候我们所有元素的异或和就变成了
这个时候变成了一个P-position 满足上面提到的N-position的性质

1.4.3.

这个显然知道不管你怎么动都会变成一个异或和不等于0的情况 此时变成了N-position
并且你只能把它变成N-position 满足上面提到的P-position的性质

1.5 结论的用处

知道了如上 你就可以在的复杂度下知道当前是一个N-position还是一个P-position
如果是N-position的话你就可以求出必胜策略 是不是很奇妙呢

1.6 一道例题

bzoj 1299
题解在这里

2.SG函数

2.1 一个问题

给定一个有向无环图和一个起始顶点上的一枚棋子,Alice和Bob交替的将这枚棋子沿有向边进行移动,无法移动者判负。问是否有必胜策略。

2.2 有关这个问题的一个讨论

事实上,这个游戏可以认为是所有ICG游戏的抽象模型。也就是说,任何一个ICG游戏都可以通过把每个局面看成一个顶点,对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。下面我们就在有向无环图的顶点上定义SG(Sprague-Garundy)函数。

2.3 SG函数

2.3.1 定义适用范围

有向无环图

2.3.2 这个有向无环图的组成

  • 顶点:每个局面我们看做一个顶点
  • 边:当前局面向它的后继局面连边(这里的后继局面指的是由当前局面进行一次移动得到的局面)

2.3.3 mex函数

mex函数面向一个集合定义 对于一个集合A mex{A}表示没有在A中出现的最小非负整数
下面举几个例子
- mex{0,1,2,4}=3
- mex{2,3,5}=0
- mex=0

2.3.4 SG函数的定义

我们记表示对于x这个局面的SG函数
那么我们有 其中y为x的后继的集合
通过这个定义我们可以知道 一个局面的SG函数是通过它的后继局面的SG函数的所有值得到的

2.4 SG函数的性质

1.在一个有向无环图中 对于一个没有出边的点x 满足SG(x)=0
这是很显然的 没有后继局面
2.对于一个局面x 如果满足SG(x)=0 那么对于它的后继局面y一定有

3.对于一个局面x 如果满足那么对于它的后继局面y一定有

2.5 SG函数与N-position,P-position的联系

我们发现这个关系是完全等价的
对于一个局面x x是一个P-position当且仅当SG(x)=0
写成数学语言就是

2.6 对于SG函数的拓展

上面我们说的是一个棋子 下面我们增大难度 变成n个棋子在一个有向图上面来回动
这个时候我们探究一下结论是什么
探究Nim游戏的结论最后还是得从SG函数来找
我们重新考虑一下对于一个顶点x来说代表了什么
回到SG函数的定义这代表的是对于y(y是x的后继局面)满足每个值都能取到(当然了大一点的值也能取到) 这样的话就是说当我们更改x这个局面的时候 我们只能使SG(x)->SG(y)时这个值一定变小 不知道看到这里你想到了什么 不过总觉得这个情况我们之前提到过
没错就是取石子游戏!
当我们对于一堆石子进行操作的时候 我们可以使这堆的数目从x变成[0,x)的任何一个整数
这两种变化简直一模一样
这样的话 场面上面有n个棋子移动的时候 就相当于你有n堆石子需要取
结论自然显然了
我们说一个局面为P-position当且仅当

2.7 对于SG函数的再拓展

上面说的是n个棋子在一个图上面动
现在我们把问题换成
你有三堆石子:
这三堆石子要求各不相同
- 第一堆:每次你只能取出1,2,3颗石子
- 第二堆:每次你可以取出奇数颗石子
- 第三堆:你可以取出任意颗石子

这里我们就需要一些新的定义

2.7.1 游戏的和

对于一个如上的Nim游戏 我们假设有n个无向图分别标号为 并且满足这n个Nim游戏每次移动一个无向图上面的棋子的时候其他的不受到影响 把这个Nim游戏我们记做 那么我们说这个就是这n个Nim游戏的和

2.7.2 游戏的和的SG函数

这是一个规定
如果我们记 这n个游戏的和
那么我们有结论

也就是说,游戏的和的SG函数值是它的所有子游戏的SG函数值的异或。

2.8 如上结论使用范围

其实,任何一个ICG都可以抽象成一个有向图游戏。所以“SG函数”和“游戏的和”的概念就不是局限于有向图游戏。我们给每个ICG的每个position定义SG值,也可以定义n个ICG的和。所以说当我们面对由n个游戏组合成的一个游戏时,只需对于每个游戏找出求它的每个局面的SG值的方法,就可以把这些SG值全部看成Nim的石子堆,然后依照找Nim的必胜策略的方法来找这个游戏的必胜策略了!

2.8.1 举个例子

我们回到上一节(2.7节)提出的那个问题
现在你是不是就有思路了呢
我们可以把这个游戏看成三个游戏的和
其中第一个游戏就是针对第一堆石子以此类推
然后我们可以分别研究这三个游戏的SG函数
我们可以把它看作3个子游戏,第1个子游戏只有一堆石子,每次可以取1、2、3颗,很容易看出x颗石子的局面的SG值是x%4。第2个子游戏也是只有一堆石子,每次可以取奇数颗,经过简单的画图可以知道这个游戏有x颗石子时的SG值是x%2。第3个游戏有n-2堆石子,就是一个Nim游戏。对于原游戏的每个局面,把三个子游戏的SG值异或一下就得到了整个游戏的SG值,然后就可以根据这个SG值判断是否有必胜策略以及做出决策了。其实看作3个子游戏还是保守了些,干脆看作n个子游戏,其中第1、2个子游戏如上所述,第3个及以后的子游戏都是“1堆石子,每次取几颗都可以”,称为“任取石子游戏”,这个超简单的游戏有x颗石子的SG值显然就是x。其实,n堆石子的Nim游戏本身不就是n个“任取石子游戏”的和吗?

2.9 怎么求SG函数

2.9.1 当前可选的是一个1-m这样的区间:直接取模

SG(x)=x%(m+1);

2.9.2 当前可选为任意值

SG(x)=x;

2.9.3 当前可选没什么规律

1.打表

  1. dfs

2.10 一道例题

bzoj 1874 题解在这里传送门
至此,我们对于SG函数的讨论暂时结束。

3.很多博弈类问题的模型

3.1 阶梯问题

3.1.1 问题描述


像这个图 每个楼梯上面都有一定数量的硬币(0层没有)
每次一个人可以把任意一阶上面的任意枚硬币向下移动一层
没有硬币可以移动的人输

3.1.2 问题分析

经过一个变换这个问题就能够变成Nim游戏类问题是不是特别神奇
太神奇了我去 大家镇静
理性分析一下怎么转换成一个Nim
这个题跟取硬币问题最大的区别就是硬币没有被移除游戏而去了另外一堆
我们只需要考虑能不能把这样的影响去掉
现在考虑到你作为相邻两阶楼梯 它们的奇偶性一定不同
最开始的想法就是分奇偶讨论
可不可以把奇数的堆作为石子堆 一旦石子在偶数那么看作被移出了游戏
想到这里就对了 下面将给出这个问题的证明
假如你是先手 MB是后手
按照我们刚才的猜想你需要看一看有没有一个操作能够使得 也就是我们把奇数堆看成石子堆的时候Nim游戏的一个P-position 如果能的话你就这么做 接下来就到了MB的操作
MB无非两种做法:动奇数堆里面的石子或者偶数堆里面的石子
当MB动了奇数堆里面的石子的时候 你继续进行上一步的那种操作 这样的话就相当于石子持续在减少 满足对所有的奇数堆进行NIM游戏的这样的一种方式
当MB动了偶数堆里面的石子的时候 就相当于MB将一些石子加入了这个Nim游戏 这样的话你可以手动把这些移出去 仍然满足对于MB这样的一个P-position
综上所述 我上面提到的就是一个必胜策略
反之当你不能从这个局面中制作出上面的这种策略的时候 这个时候对你就是一个P-position 因为这个时候MB面对奇数个N-position 你是偶数个 最后一个一定是MB面对的
好了听到这里我想你只剩下一个疑问了:为什么是对奇数堆进行Nim游戏
因为如果是对偶数堆做Nim 对手移动奇数堆的石子到偶数堆 我们跟着移动这些石子到下一个奇数堆 那么最后是对手把这些石子移动到了0 我们不能继续跟着移动 就只能去破坏原有的Nim而导致胜负关系的不确定 所以只要对奇数堆做Nim判断即可知道胜负情况

3.1.3 一道例题

bzoj 1115 题解在这里传送门

3.2 翻硬币问题

3.2.1 问题描述

你和MB两个人面对桌面上好多好多硬币 这些硬币有的正面朝上有的反面朝上
每次翻硬币的时候会有一些限制(比如说你只能翻一枚,两枚,不多于三枚,连续4枚之类的)
但是不管怎么样的一个规则 有一个规则是不变的 就是你翻的最右侧的那枚硬币必须是从正面翻到反面
谁不能翻谁输

3.2.2 问题分析

这个游戏表面看起来跟Nim游戏没什么关系 但是仔细想想是有点联系的 你可以把一个标号为i的正面朝上的硬币看做一个有i个石子的石子堆
这样的话你就有了一个Nim游戏的模型
然后假如说你在Nim游戏的某一步想要从一个10个石子的堆取出5个 在这个游戏里面如果允许的话 你可以把编号为10的从正面翻到反面 编号为5的从反面翻到正面 这样的话这个操作就模拟出来了

3.2.3 结论

这玩意有个结论
- 局面的SG值为局面中每个正面朝上的棋子单一存在时的SG值的异或和。

3.2.4 结论证明

MB咨询了很多人现在还没有弄明白 大概等学姐高考结束之后有时间看QQ了我就可以问她了

3.2.5 例题

没有23333

4. Anti-Nim游戏

4.0 解释

字面意思 跟Nim游戏相反

4.1 取石子游戏(II)

我们就从这个最简单的Anti-Nim游戏来说
这次取石子的不是Alice和Bob了 是你和MB
由于MB知道了你已经学过了Nim游戏 所以他不准备按照Nim的规则来玩
他指定的规则是
- 一次只能从一堆中取石子 在第k堆你可以随意地取
- 取到最后一个的输

4.2 这个游戏的结论以及证明

4.2.1 结论

我们说当前局面是一个N-position 当且仅当当前局面满足下述条件之一
- 所有堆的石子数都为1并且游戏的SG值为0
- 有的石子堆有两个以上的石子并且游戏的SG值不是0

这里面我们说这个游戏的SG值其实就是每堆石子的数量

4.2.2 证明

我们分成三种情况来证明

Case 1:当前场上所有的石子堆中只有一个石子

那么这个结论很简单了
时就相当于说现在有偶数堆石子 这样的话先手必胜 记这种情况为A情况
反之这个时候先手必败 记这种情况为B情况

Case 2:当前场上存在石子数大于1的石子堆并且只有一个

我们把这种情况记做C情况
这个时候的情况也是非常简单的 说白了你作为先手 目标就是给MB留下一个B情况
我们假设这是一堆多于一个石子的石子堆
这个时候你针对n的奇偶性进行分析
当n是奇数的时候 证明这个时候有偶数个石子为1的石子堆 这个时候你把第i堆取剩一个 这个时候就有了奇数个石子数量为1的石子堆 成功给MB造成了B情况
偶数的时候聪明的你一定想到了 没错全取走就好了

Case 3:当前场上存在石子数大于1的石子堆并且有多个

先给结论再证明:
当异或值=0时,先手必败 我们把这个情况记做D情况
当异或值≠0时,先手必胜 我们把这个情况记做E情况
怎么证明呢
首先,参考Nim游戏的证明,当异或值=0时,无论进行怎样的操作都会使异或值≠0;而当异或值≠0时,一定存在一种移动方案,使得异或值=0,这个性质符合N,P状态的转换。
当你这么动啊动啊的时候 考虑一个特殊的状态 当前局面可不可能变成C局面呢 答案是当然可以
看一看C局面的状态 喔异或值不可能是0 这样的话根据我们刚才的N,P局面转换结论 C局面一定是由D局面转化到的 这样的话D局面一定只能转化成为C局面 这样的话D局面满足只能转化成为N-position 它就是P-position了
第二种情况正好相反

这样的话我们对于这个Anti-Nim游戏的结论证明完毕

4.2.3 一道例题

bzoj 1022 题解在这 传送门
那么至此,我们对于Anti-Nim游戏的研究暂时结束

5.Anti-SG游戏和SJ定理

从上面的Anti-Nim游戏我们来类比Anti-SG游戏

5.1 定义

我们在Anti-SG游戏中有如下规定
- 决策集合为空的游戏者赢
- 其他的规则跟SG游戏相同

说白了就是把SG游戏的获胜条件换一下

5.2 SJ定理

据说来源有点不要脸哈哈哈哈
来源是一篇国家队的论文 传送门
这个SJ定理就是针对Anti-SG游戏来提出的
在这个定理给出之前 你需要明白一个问题:
当SG函数为0的时候 可能游戏并没有到终点
知道了这个之后事情就有点好办了
说明:在本节中,G表示游戏的和,G数组代表子游戏

5.2.1 定理内容

一个Anti-Nim先手必胜的条件是当前局面满足下列两个条件之一

5.2.2 定理证明

证明这个定理 我们对所有可能的情况进行讨论
这个证明不算严格 但是理解一下大概可以懂
首先从上面的Anti-Nim游戏中 我们可以暂时理解一下定理的两个内容没有什么问题
然后接下来我们考虑没有提及的两种情况
(当然了我们自动忽略全场所有的SG(i)=0这种情况 证明这种情况没有什么意义)

5.2.2.1 讨论1:

这样的一种情况 首先我们注意到SG函数有个性质 如果当前的SG(G)=0 那么对于G的所有后继局面G' 都满足SG(G')!=0 然后又因为异或和为0 证明此时场上一定至少有两个SG(i)>1 然后根据我们对于一次操作的定义 我们只能把一个SG值改掉 所以这个时候场上还有至少一个>1的SG值 并且异或和!=0 满足上面提及的第二个N-position 根据这两个互相转化的规律 只能变成N-position的我们说是一个P-position
讨论1证明结束

5.2.2.2 讨论2:

这样的一种情况我们显然知道此时场上有奇数个SG值=1的子游戏
接下来你有两种移动方式
1.把一个SG(i)变成>1的一个值
转移后的局面 显然异或和不为0 并且有一个SG(i)>1 这个时候我们说这是定理提到的N-position
只能变为N-position的局面我们说是一个P-position、
这种转移证明完毕
2.把一个SG(i)^1
这个时候你发现场面上面SG值=1变成了偶数个 异或和变成了0
我们说这是定理提到的另外一个N-position
只能变为N-position的局面是一个P-position
这种转移证明完毕
综上 讨论2证明完毕
在上面两个讨论的前提下 我们看一看这个定理

5.2.2.3 讨论3:我们证明这个定理

这个定理证明的时候分两种情况
1.局面中只有一个SG(i)>1
证明与Anti-Nim类似 我们分奇偶性讨论决定把这个值变为1还是0
留给后手的一定是一个P-position
能够进行一步操作变成P-position的局面是一个N-position
证明完毕
2.局面中有多个
我们可以显然知道有一种操作可以使SG(G)=0 并且修改之后场上仍然有SG(i)>1
此时变成了讨论1中的P-position
能够进行一步操作变成P-position的局面是一个N-position
综上 这个讨论证明完毕

5.2.2.4 我们证明最后那个定理

显然此时场面上面有偶数个SG(i)=1
经过一次变换你使这个数量变成了奇数
这个时候场面满足如下条件:
异或和不为0 场上只有0,1的SG值
讨论2中已经证明 这是一个P-position
能够进行一步操作变成P-position的局面是一个N-position
证明完毕
这样的话我们算是证明了这个SJ定理
至此有关Anti-SG告一段落

6.Multi-SG游戏

6.1 不妨从最简单的例子开始

这次取石子的仍然是你和MB MB发现上边的问题聪明的你还是可以轻松虐他 他表示不服
这一次他带来了新的规则
有n堆石子 每次操作可以选择从一堆石子中取出任意个 也可以把这堆石子分成非空的两堆
先拿完的人获胜

6.2 问题分析

这个题其实是这么多变形中最像Nim的
此话怎讲?
首先你第一个操作就是Nim 第二个操作无非把一个游戏拆成了两个子游戏
然后你还有一个概念叫做游戏的和
这个时候你两个子游戏的SG值异或和就是你原来游戏的SG值
而求某一个点的SG函数要利用它的后继 它的后继就应该为当前局面能产生的所有单一游戏 以及当前局面所有能分成的多个单一游戏的游戏的和
例如说对于3的后继局面就有(0),(1),(2),(1,2)
这四个游戏的SG值分别为0,1,2,3
所以SG(3)=4
在更多个石子的时候 你就不能这么硬算了
在这里我给出上面引入问题的SG值
至于更多规则比如说可以分成三堆之类的你可以用我上面提及的公式来求

这个结论来自打表
这样的话变成了一道结论题

6.3 Multi-SG 游戏

在上面的基础上 我们来定义Multi-SG游戏

6.3.1 Multi-SG游戏的定义

1.游戏规定,在符合拓扑原则的前提下,一个单一游戏
的后继可以为多个单一游戏。
2.Multi-SG其他规则与SG游戏相同。

6.3.2 Multi-SG游戏的普遍解决方法

通过上面那个简单的例子我们知道一定还是跟每个子游戏的SG值有关
对于一个单一游戏,不同的方法可能会将其分成不同的多个单一游戏。而这个单一游戏的SG函数即为未在所有方法的SG函数值中出现过的最小值。
大概理解到这样就可以了

6.4 一道例题

bzoj 2940 题解在这里传送门
至此,我们对于Multi-SG这种情况的讨论基本结束

7.Every-SG游戏

7.1 还是最简单的例子

MB还是不服输 这次他找来了n个棋子和一个有向无环图 找你再次一决高下
这次他也带来了全新的规则:
你没玩过的全新版本
某些顶点上面有棋子 你和MB轮流移动棋子 每一次移动必须移动所有的可以移动的棋子
无法移动者输

7.2 问题分析

当然了最先想到的一定是看成n个游戏的和 每个棋子作为一个游戏都有它自己的必胜策略
你当然是不希望自己没有棋子可以移动的
所以说你的策略是在场上找到几个自己有必胜策略的游戏 让它一直玩下去 然后把没有必胜策略的游戏尽量玩成必胜 这样的话你就胜券在握
当然最重要的就是你要利用当前的必胜游戏为你当前没有必胜策略的游戏争取时间
MB则当然不希望自己必败的游戏玩的太久 这样的话他就一定会陷入被动 必败的游戏结束的早点也行 或者玩成必胜的也行(当然了我们在本文认为两个人绝顶聪明 所以后面的情况不存在)
这就是Every-SG的特点 不但有胜负之间的博弈 还有长短之间的博弈

7.3 Every-SG游戏的定义

从上面这个基本的游戏 我们来对Every-SG游戏进行一个定义
1.Every-SG游戏定义:对于每个还没有结束的单一游戏,游戏者必须在移动的时候对该游戏进行一次移动
2.Every-SG游戏其他规则与普通SG游戏相同

7.4 考虑方式

根据Every-SG游戏的定义方式 我们显然看出还是要从SG函数这个角度来考虑
对于当前的游戏 有三种情况
1.当前游戏已经结束
不过多赘述这种情况
2.当前游戏对于当前决策者先手必败
这样的话根据上面的分析 当前决策者需要尽快让这个游戏结束
3.当前游戏对于决策者先手必胜
这样的话为了不让自己没有棋子可以移动 他需要考虑当前游戏最晚结束
给出这个游戏的一个结论
我们用step(x)表示当前决策者希望这个游戏终止的步数
那么有下面的式子(v代表x的后继集合)

7.5 Every-SG游戏定理

对于Every-SG游戏先手必胜当且仅当单一游戏中最大的step为奇数。

7.5.1 定理理解

最大的单一游戏步数如果是奇数的话那么肯定是先手取得进行最后一步,否则一定是对手取走最后一个棋子。
这个理解是很简单的
接下来我要进行一波高难度操作

7.5.2 解法证明

我们想理解这个解法的正确性 需要利用定理理解如下三个结论
1.设最大的step是S,那么先手需要保证他所有的必胜游戏至少在S步结束
2.设最大的step是S,那么先手需要保证他所有的必败游戏最多在S步结束
3.对于每个单一游戏,先手必胜的step值是奇数,先手必败的step是偶数

7.5.2.1 证明结论1

我们找到任意一个step值最大的游戏A,最后的胜者是W(根据定理可知这个游戏一定是先手必胜)
那么对于W:他总是在先手必胜的状态移动游戏A,并且他能够保证这次移动最多将step减少1
对于它的对手:他总是在先手必败的状态下移动游戏A,并且他这次移动最多将step减少1
综上两个分析:W一定可以在先手必胜局面下至少用step步结束这个游戏

7.5.2.2 证明结论2

我们找到任意一个step值最大的游戏A,最后的胜者是W(根据定理可知这个游戏一定是先手必胜)
那么这个时候我们再找到一个游戏B(这是一个W的先手必败游戏)
每次移动:
W将这个游戏的step最多减少1 将B变成先手必胜态
这个时候对于他的对手 他最少将这个游戏的step减少1
所以最差策略就是step步结束

7.5.2.3 证明结论3(数学归纳法)

1.特殊情况:所有的step等于0 先手必败
2.假设状态树中有符合要求的
我们找一个后继状态已经全部证明的点
(1)这个点先手必败:那么后继状态一定是全都为先手必胜 step全都为奇数
这个点的step是偶数
(2)这个点先手必胜:大概同理

7.6 一道例题

HDU 3595 传送门
至此我们对于Every-SG这个问题的讨论告一段落

8.树的删边游戏

8.1 游戏内容

今天MB又找到了你 他决定再跟你玩玩游戏
你比他强 但是还想和他谈笑风生
你答应了他
他今天带来的游戏规则是这样的:
给出一个有 N个点的树,有一个点作为树的根节点。你和MB轮流从树中删去边,删去一条边后,不与根节点相连的部分将被移走。谁无法移动谁输。

8.2 问题分析

这个题作为博弈专题的倒数第二个问题 当然是要超级大的思维量的
分析无非就是我们可以人为地把树上面的节点分成好多类 然后找到一类或者两类非常特殊的点分析SG值 其他的点可以考虑游戏状态的转移
当然了 首先映入你脑海的无非就是根节点还有叶子节点

8.3 游戏结论

这个游戏有个好玩的结论

叶子节点的SG值为0;中间节点的SG值为它的所有子节点的SG值加1后的异或和。

8.4 游戏结论证明(数学归纳法)

这个东西我们可以从最基本的最终状态开始考虑

8.4.1 简单的最终状态

1.只有一个点 这个时候是一个P-position
它的SG值是0 也没有什么子节点之类的 显然成立
2.只有两个点 这个时候是一个N-position
这两个点的SG值分别是1,0 你只需要删除一条边 你就赢了

8.4.2 一般的状态证明

要想让结论具有普遍性 我们就需要找到任意的一个k使得当树上面有k个节点的时候 我们的定理成立
这个时候我们随便找到一个k 假设小于等于k个节点的所有情况全部成立
这个时候我们来证明k+1个节点的时候成立
证明方向是什么样的呢?
1.证明根节点只有一个子节点的时候结论成立
2.证明根节点有多个子节点的时候结论成立
下面我们讨论这两种情况:

8.4.2.1 证明第一种情况

我们设这棵树的根节点是A节点 跟它直接相连的是B节点
当前游戏是G,后继游戏是G'
我们下面需要证明的就是SG(G)=SG(G')+1
然后通过这个树的性质我们可以显然看出我们有一种方案可以切掉所有的节点(就是切断A,B相连的那条边)这样的话后手必败 这样的话我们说我们可以有一种情况使得SG(G')=0
上面结论请大家记住 我们记作结论一
接下来我们讨论不删除那条边的情况
我们删除除了那条边外的任意一条边 这样的话你可以知道 剩下的边数最多是k
设以B为根的G’去掉E以后的后继局面的SG值为P
∵以A为根的G去掉E以后图中的总边数小于等于K
又∵中间节点的SG值为它的所有子节点的SG值加1后的异或和
∴A为根的G去掉E以后的后继局面的SG值为P+1
∵以B为根的G’可以通过去边操作使得后继局面的SG值变为0到SG(G’)-1
∴以A 为根的G可以通过删除 G’中有的边使得后继局面的SG值变为1到SG(G’)
这个结论记作结论二
通过结论一,二我们可以知道 SG(G')可以取到0-SG(G')
这样的话 SG(G)=SG(G')+1
结论证明完毕

8.4.2.2 证明第二种情况

我们假设现在与B相连的有T个节点分别为
经过一次去除边后 我们假设我们保留了这条边 根据我们删边的这些各种情况 我们得到了很多个子游戏 这个时候根据子游戏的定义不难得出

根据上文 每一种情况我们都已经证明完毕
综上所述 这个第二种情况我们证明完毕
所以结论我们证明完毕

8.5 一道例题

poj 3710 题解在这里传送门
至此我们对于树的删边问题的讨论基本结束

9.无向图的删边问题

我们来到了最后的一个专题 这个专题MB终于认输了 他不再跟你拿来新的游戏规则来玩 而是跟你对于上面的那道题展开延伸

9.1 延伸

无向图不就是大概一棵树多点边嘛
我们把上面那提对于环的所有限制删掉 就是我们的无向图删边游戏

9.1.1 无向图的删边游戏

一个无相联通图,有一个点作为图的根。
游戏者轮流从图中删去边,删去一条边后,不与根节点相连的部分将被移走。
谁无路可走谁输。

9.2 定理

我在上一道题中的题解已经提到
对于这个模型,有一个著名的定理——Fusion Principle。

9.2.1 定理内容

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

9.2.2 定理证明

这个原理的证明十分复杂,这里不给出证明(记个结论吧)
这样的话,我们可以将任意一个无向图改成树结构,“无向图的删边游戏”就变成了“树的删边游戏”。
至此我们对于无向图的删边游戏讨论基本结束

10,你的终极挑战

hdu 2509 这里是题解传送门

11.后记

讲到这里有关Nim,SG函数就真正告一段落了
说了这么多 主要还是在引导着大家了解这些基本的模型
大家以后见到复杂的问题 就尽量想着这些基本的模型去靠拢
SG函数永远是最有力的工具
Nim游戏虽然本质看起来简单 但是我们在上文的探索中仍然挖掘到了很多深层次的东西
但是同样有一些题目由于时间或空间的限制我们无法用最基本的方法求解 这时候也需要我们将问题特殊化来寻求更有用的性质。
和Michael_Bryant在不断地思考与质疑中继续体会博弈论的美妙吧

12.主要参考文献,资料

https://blog.csdn.net/clove_unique/article/details/53868567
Thomas S. Ferguson 《GAME THEORY》
IOI2009国家集训队论文 贾志豪《组合游戏略述——浅谈SG游戏的若干拓展及变形》
IOI2007国家集训队论文 王晓珂《解析一类组合游戏》

One Comment

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏