博弈:关于SG函数的一些心得(知识总结+叙述证明+例题)
思路来源
IOI2009集训队论文 贾志豪《组合游戏略述——浅谈SG游戏的若干拓展及变形》
翻硬币游戏部分:
https://www.cnblogs.com/kuangbin/p/3218060.html
树的删边与图的删边部分:
https://blog.****.net/wu_tongtong/article/details/79311284
http://blog.sina.com.cn/s/blog_8f06da990101252l.html
《Game Theory》(其实没有直接用到 但上述几篇都有该博弈书的影子)
Anti-Nim游戏
先手必胜当且仅当:
(1)所有堆石子数均为1,且游戏的SG值为0
(2)存在堆石子数大于1,且游戏的SG值不为0
口胡证明:
(1)第一种情况,一定是偶数堆1,无论先手怎么取后手只能模仿,故后手必败
(2)第二种情况,分两种子情况,
①有一堆大于1,先手可以把这堆变1或者变0,使剩下的1为奇数堆,
这样后手再取一个1,先手就面临(1)的局面必胜
②有至少2堆(不妨记为第i堆和第j堆)大于1,先手把SG变为0,
这样在i、j堆一直大于等于2的时候,后手把SG变为非0,先手把SG变为0即可
考虑后手的某次操作使得i、j有一堆少于2了(可以为0,也可以为1),
若后手没有增加一堆1,则先手可以增加一堆1,也可以不增加;
若后手若增加一堆1,则先手可以增加一堆1,也可以不增加。
先手总可以保证在游戏未结束的情况下,
使这两堆总共产生的1与场上剩下的1构成奇数堆1
而奇数堆1是必败局面,故先手必胜
人家的证明真是简洁啊我理解了好久
Anti-SG游戏&&SJ定理
与SG游戏的概念基本一致,
只是最后一步者负,而SG游戏中最后一步者胜
注意到SG游戏的子游戏都可等价为nim游戏
即sg[i]=k的游戏,可以转化为nim游戏里的一堆有k个的石子
规则:
①先手无法操作的为必胜态,即所有单一游戏SG值均为0时停止游戏
②其余与SG函数适用范围均相同
SJ定理
其实由Anti-Nim可以立刻得出,
先手胜当且仅当:
①所有单一游戏SG值均为1,且游戏的SG值为0
②存在单一游戏SG值大于1,且游戏SG值不为0
简记为:①全1,为0 ②不全1,不为0
只需讨论以下四种情况,
①所有单一游戏SG值均为1,且游戏的SG值为0
②所有单一游戏SG值均为1,且游戏的SG值不为0
③存在单一游戏SG值大于1,且游戏SG值不为0
④存在单一游戏SG值大于1,且游戏SG值为0
其中①③是必胜态,②④是必败态,
只需证明,①③只能转移到②④,②④只能转移到①③,
且最后的必败态只有一个子游戏SG值为1其余均为0,是可以由①③转移过来的
口胡证明:
类似数学归纳,①③是奇数,②④是偶数,
然后奇数只能转移到偶数,偶数只能转移到奇数,
又因为1是必胜态,所以奇数是必胜态,偶数是必败态
大致证明就是这个思路
具体证明:
见《组合游戏略述——浅谈SG游戏的若干拓展及变形》P11-P13
一点小说明:
只要有一个局面出现全0,即认为游戏结束,
若在该局面下先手还能将其变为仅一堆1的情况,
后手只能取这堆1从而使后手败,这与原局面是等价的
Multi-SG游戏
即一个局面的后继可以为多个子游戏,
即一个sg值的后继可以为多个子游戏sg值的异或
比如可以把一堆石子分成若干堆非空石子
如hdu5795,算sg值的时候,考虑这些后继情况即可
Every-SG游戏
即多个没结束的游戏一起玩,每个没结束的游戏都必须决策,
且必胜的局面希望玩久一点,必败的局面希望玩快一点
若v的后继为u,则
①step[v]=0,v为终止状态
②step[v]=max(step[u])+1,v为必胜态,u为v的后继,会挑步数最多的后继转移
③step[v]=min(step[u])+1,v为必败态,u为v的后继,会挑步数最少的后继转移
这其实很像alpha-beta的剪枝算法
Every-SG定理
我们认为,最后一个结束的游戏中胜者是最终的获胜者,
那么,先手必胜,当且仅当该单一游戏的最大step为奇数
口胡证明以下三条:
①先手必胜step为奇数,后手必胜step为偶数,
数学归纳法显然,一步是先手必胜,两步是后手必胜,剩下的都是先后手轮流走
②设最大的step为max,既然max存在,说明后手只能一次令max最多减一步,
而先手一次也不得不令max减一步,说明先手可以达到这个max
③设最大的step为max,则其它必败游戏中最大step2<=max,
而这在后手必胜的情况下,先手只能一次令step2最多减一步,后手不得不令step2减一步,
同理说明后手也可达(step2-1),又因为step2<=max,故先手最多在max步结束其必败游戏
翻硬币游戏
规则:
从左到右1-n标号的硬币,有正有反
每次可以翻若干枚连续的硬币,
但要求翻的这些硬币里,最右边那枚一定是从正翻到反
即在翻的过程中,正的硬币的最右位置不断向左移动
翻硬币定理
总局面的SG值,为每个正面硬币朝上单独存在的局面的SG值的异或和
如令1为正面朝上,0为反面朝上,则sg[011001]=sg[01]^sg[001]^sg[000001],
故讨论问题时,单独讨论形如00001这样的一串0后缀一个1的sg值即可
这里有一些奇奇怪怪的翻硬币游戏及其sg值的规律:https://www.cnblogs.com/kuangbin/p/3218060.html
如:翻一个硬币、翻一个硬币或非连续两个硬币、翻连续k个硬币
Subtraction Games、Twins游戏、MockTurtles游戏、Ruler游戏、Grunt游戏
不过看了这么多博弈好像也没见出过这样的翻硬币题目,出了就打表找规律呗……
翻硬币其实就是对某个右端点为1的区间异或1
证明可采用数学归纳法,和nim游戏的证明非常类似
如果我们对左起第i位赋权值(1<<i),则这样的异或方式,满足按位模2加法(不进位)
而局面的总权值,是这些二进制位权值的和,
由于正的硬币的最右位置不断向左移动,某个局面的权值是不断减小的
这也对应了nim游戏中,某堆石子只能减少不能增多,这个图逆时针转90度是不是好点
如果我们只能连续翻一枚硬币,这与nim游戏一次只能取完一堆石子是等价的
如果我们能连续翻两枚硬币,这与nim游戏一次只能取完一堆石子的一半是等价的
即001(左起低位二进制)只能变成010(左起低位二进制),再变成100(左起低位二进制)
然后就终止了,恰对应4->2->1的取石子过程
对于连续若干枚的硬币,也是存在只能向某个特定石子数转化的情形,
毕竟全反面朝上的也可认为是全0即终止局面嘛,所以是可以认为nim游戏的一种,
故符合nim游戏的性质,局面的sg值等于这些正面朝上sg值的异或,
口胡的证明,严格证明不大会证
这沙雕游戏为啥不规定一下最左边那枚从正到反,这样就和二进制高低位完美对应了
树的删边游戏
规则:
有一棵树,两人可轮流选一条边,
把这条边和它连的子树一起删掉,无边可删者输
树的删边定理
①叶子结点leaf的SG值sg[leaf]=0
②某棵树的根节点的SG值sg[root]=(sg[i]+1)^(sg[j]+1)^...^(sg[k]+1),其中i、j、k是其子节点,^是异或
口胡证明:
①一个节点无边可删,sg[root]=0;两个节点一条边,sg[root]=mex{sg[leaf]}=1=sg[leaf]+1,均成立
②设小于等于K个节点均成立,数归证(K+1)个节点也成立,
以下设根为点A,分A有一棵子树和A有多棵子树讨论
第一种情况:A只有一棵子树,且这棵树的根为点B,
计以A为根节点的全树为G,不包含A点和AB边的以B为根节点的树为GG
显然G的点数为(K+1),GG的点数为K
①删去边AB则必胜,故该局面存在sg=0的后继局面
②删去B这棵子树里的一条边E,E至少带走一个叶子结点,
使得G-E的点数<=K,且G-E和GG-E都具有完整树形
由归纳假设G-E的点数<=K和小于等于K个节点均成立,
设sg[树(GG-E)中的根B]=P,则sg[树(G-E)中的根A]=sg[树(GG-E)中的根B]+1=P+1,成立
③设sg[树GG中的根B]=Q,则由sg函数定义,
该树可以通过删一条边E,转移到sg值为[0,Q-1]的局面,
即sg[树(GG-E)中的根B]的值域为[0,Q-1],
由②知,sg[树(G-E)中的根A]的值域为[1,Q]
由①知,sg[树(G-E)中的根A]也可取到值0,
故sg[树(G-E)中的根A]的值域为[0,Q],
由sg函数定义,sg[树G中的根A]=Q+1=sg[树GG中的根B]+1,成立
第二种情况:A有若干棵子树,子树的根分别为B、C、D……
即证sg[A]=sg[B]^sg[C]^...^sg[D],
显然根节点对答案是没有影响的,那我们就把A拆点
有k棵子树就把A拆成k个点,每个点挂一棵子树
这样我们发现,在原树上断边的时候,一次最多断掉一棵A的子树,
这和在拆点之后的只挂一棵子树的A上进行操作是一样的,
于是,一棵树的操作就等价于多棵树的操作,
满足sg函数性质的游戏与nim游戏是一样的
第一种情况中已证一棵树的sg[root]=sg[子节点]+1
该情况下只需将多棵树的sg值异或起来,
即拆点之后的k个A点的sg值异或起来,等于拆点之前的A点的异或值
只有简单环的图的删边游戏
例题:poj3710 Christmas Game
规则:
有N个图,每个图是在上题中的树中加了一些边和点后,有了简单环,
即原树上的一个节点,最多只能被加进一个以该点为起点该点为终点的简单环,
且简单环之间没有公共边,
两人轮流删边,删边之后与根节点不连通的部分被一并删掉,
无边可删者输,给定图,问谁必胜
简单环的性质
注意到上题中,树上的链的性质,
有根之后每个非叶结点只有一个子节点
对于一条链,若定一端为根A,另一端为叶子E,
不妨这条链ABCDE五个点,则sg[E]=0,sg[D]=1,sg[C]=2,
即sg[root]与这条链的边数相同,自然与链长同奇偶
①长度为奇数的环,
去掉任意一条边后,剩下的两条链同奇偶,共用一个节点root2
故sg[链1]与sg[链2]同奇偶,二者异或不可能为奇数,
又因为去掉中间那条边后,两条链是完全相同的,
存在后继状态使得sg[链]^sg[链]=0,故sg[root2]=1
sg相同的有根节点的子图对其父节点的贡献是等价的,
因此,可以把奇环等效成长度为1的链
②长度为偶数的环,
去掉任意一条边后,剩下的两条链异奇偶,共用一个节点root3
故sg[链1]与sg[链2]异奇偶,二者异或不可能为0,故sg[root3]=0
同理,可以把偶环消成只有root3一个点
消去环之后的图就变成了一棵树,solution同上例,
各树求根节点sg值后,异或即可
此外还有一个Colon Principle(冒号原则)
即:一个节点的若干条链的长度值异或在一起,
得到新的长度,用该长度去构造该节点的一条新链
实际应用意义感觉不大,当做了解吧
无向图的删边游戏
规则:
一个无向连通图,有一个根节点,
二人轮流删边,删边之后与根节点不连通的部分被一并删掉,
无边可删者输,给定图,问谁必胜
即环没有了简单环的性质,变得更为一般化
不加证明的给出定理:
其实和Tarjan缩点有点像,又结合了上例sg值不会变的性质
Fusion Principle(融合原则)
即:
任意一个奇环缩成一个点加一条新边
任意一个偶环缩成一个点
实际代码不会敲……就当理解叭……
心得
博弈真的是深坑啊……去年寒假学了一部分现在发现啥也没学……
学完树的删边这些,发现这只是Green Hachenbush(树上公平删边游戏)
还有一种不公平删边,一方只能删除蓝边,另一方只能删除红边,而双方都可以删除绿边
很迷很迷……估计以后还会有各种各样的迷之变种……
先把论文提到的课后题做了叭……
例题
基本除了sg打表题,都是这篇论文讲的吧……