注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

SG函数闲扯  

2013-05-24 13:27:17|  分类: 总结 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
SG、NIM游戏是一个思维难度相当高的知识,所以为了对其进行一定的归纳,特地写这样一篇总结
博弈论第一次在国内的算法竞赛中被提到,是张一飞大神的论文,里面讲了三个游戏,并提到了POI的一道题。
第一个游戏是普通的NIM游戏,第二个游戏是NIM游戏的一个改编(即每次取的石子数目不得超过m)。而第三个游戏,才是论文的核心,并引出了如何求SG的式子:
SG(n)=mex(SG(T)),T是n的后继。mex函数为最小的不存在于SG(T)集合的自然数
如何证明,先从NIM游戏的证明开始
设f(n)表示n的二进制形式
假设现在的局面是(a1,a2,……an),我们称之为局面S,#S表示S的f(a1)^f(a2)^……f(an)
我们发现S有着两个性质:
性质1:若#S等于0,则S的所有后继状态T,均有#T不等于0
性质2:若#S不等于0,必存在一个后继状态T,使得#T等于0

性质1证明:
不妨设后继状态T是取走了在a1取走了x,#T=0。则T的局面是(a1-x,a2,a3……,an)。a1^a2^a3……^an=0,所以a1=a2^a3^……an,a1不等于a1-x。所以a1-x不等于a2^a3……^an,所以(a1-x)^a2^……an不等于0
性质2证明:
若a1^a2……^an=p,p不等于0,则必有k使得p^ak<ak(因为p的最高位为1,所以必存在ak使得ak这一位为1,异或之后就等于0就小于ak了)。
不妨设k=1
设a1^p=x,则a1^a1^a2^……an=x,即a2^a3^……an=x。由于x<a1,所以a1可以变成x,于是性质二成立

那么如何推广呢?
对于一个SG函数的题,我们希望“构造”出一个非常神奇的函数表达式,使得满足上面两个性质
即如果得到(a1,a2,a3……an)的集合,我们希望构造出一个“函数”叫做SG(n)或f(n),满足若SG(a1)^SG(a2)^SG(a3)……SG(an)是否等于0可以推出胜负性,我们就成功了。那么怎么样才能通过等于0推到正负性呢?就要满足那两个性质。
性质1:若#S等于0,则S的所有后继状态T,均有#T不等于0
性质2:若#S不等于0,必存在一个后继状态T,使得#T等于0
比如NIM游戏中,SG(n)=n

怎样才能满足?
我们回忆NIM游戏的证明,并用g(ai)表示ai的后继状态的SG的函数值的集合

性质一证明:
“不妨设后继状态T是取走了在a1取走了x,#T=0。则T的局面是(a1-x,a2,a3……,an)。a1^a2^a3……^an=0,所以a1=a2^a3^……an,a1不等于a1-x。所以a1-x不等于a2^a3……^an,所以(a1-x)^a2^……an不等于0”
哪一步是NIM游戏独有的呢?“a1-x不等于a2^a3^……an”。在NIM游戏中,你一次只能减少ai,所以这个条件显然。如果这个条件不成立,性质一就没了。
推广到SG函数的构造,用数学语言书写为:
SG(ai)不属于g(ai)

性质二证明:
“若a1^a2……^an=p,p不等于0,则必有k使得p^ak<ak(因为p的最高位为1,所以必存在ak使得ak这一位为1,异或之后就等于0就小于ak了)。
不妨设k=1,设a1^p=x,则a1^a1^a2^……an=x,即a2^a3^……an=x。由于x<a1,所以a1可以变成x,于是性质二成立”
哪一步是NIM游戏独有的呢?“由于x<a1,所以a1可以变成x"。这个条件在NIM游戏中显然,同样的推广到SG函数的构造上,是这样的:
对于任意自然数p<SG(ai),必有p属于g(ai)

这样的话,设G(ai)为g(ai)在N集下的补集,SG(n)=min(G(ai)),也就是mex函数的由来

张一飞大神的论文所讲的也到此为止了

接下来的发展就是07年王晓柯大神的论文,里面讲了不少例题
比如第一道题就是hnoi2007的分裂游戏,这道题目把simga(si)个石子的一个游戏变成1个石子的simga(si)个游戏,而每个游戏是独立的
第二题是阶梯NIM游戏,结论是对奇数阶梯做NIM游戏。在此感谢vfleaking的证明:
我们相当于在NIM取子游戏中添加了一些偶数阶梯,可以通过这种方法使得他与NIM等价:

首先我们按照NIM游戏的取子规则取奇数层,“拿走”操作看作是把奇数阶梯放到偶数阶梯
如果对手从偶数阶梯取x个到奇数阶梯,我们可以再取x个到偶数阶梯。这样一来相当于奇数层的状态不变

这样一来,就相当于等价了。由于边界条件是1->0,0是最底层,所以如果只看奇数阶梯的NIM和某人胜,那么此人就必胜。

然后vfleaking神犇丢了一道POI神题给我,即bzoj 1115(POI 2009)的石子游戏
感觉是道挺好的阶梯NIM游戏题目
阶梯NIM游戏还有一道题:bzoj 2066(POI2004) 游戏
这两题都比较有思维难度(当然在vfleaking看来都是水题)

当然阶梯NIM也有大水题
bzoj 1777(usaco 2010)石头木头
水的无法直视,裸的无法直视

再来看一道例题:
翻转硬币:
在一条直线上排列着一行硬币,有的正面朝上、有的背面朝上。2名游戏者轮流对硬币进行翻转。翻转时,先选一枚正面朝上的硬币翻转,然后,如果愿意,可以从这枚硬币的左边选取一枚硬币翻转。最后翻转使所有硬币反面朝上的玩家胜利。

看上去和NIM游戏没有半毛钱关系?
其实是有关系的
我们对于第i个硬币,正面朝上,看成是一堆规模为i的石子。然后做NIM游戏即可
为什么呢?
一、NIM游戏中,从规模为i的石子堆取走x个,此时不存在i-x规模的石子堆。转化到此游戏,这对应第i个棋子正面朝上,i-x石子反面朝上。我们可以理解为把i和i-x翻转。
二、NIM游戏中,从规模为i的石子堆取走x个,此时还存在i-x规模的石子堆。转化到此游戏,这对应第i个棋子正面朝上,i-x石子正面朝上。我们在此游戏中把i和i-x翻转,对应NIM游戏中去掉i和i-x。事实上NIM游戏中从规模为i的石子堆里取就相当于去掉i,取完后有两个i-x,异或和为0,这与两个都消掉是等价的(张一飞论文)

然后王晓柯还留了个大BOSS:无向图删边游戏

成长体:链删边游戏
Solution:
叶节点的SG=0
叶节点爸爸的SG=1
叶节点爷爷的SG=2
………………

成熟期:树删边游戏
Solution:
叶节点SG=0
一个点的SG等于他的所有儿子的SG+1的异或和(很显然相互独立,可以拆成一坨链,看成NIM)

完全体:局部联通图删边游戏
局部联通图是指的什么?
图是一个基础树加边得到的
所有形成的环不共用边,且与基础树只有一个公共点
Solution:
这个图的环很特别,我们可以把环单独考虑一下
事实上所有的环都是从一个点出发走了一圈回到起点的环
这么来看:
    如果环长度为奇数,我们删去一条边,得到的两条链同奇偶,异或和不可能等于1,同时必然存在一对异或和为0。所以他们的mex值等于1
    如果环长度为偶数,我们删去一条边,得到的两条链一奇一偶,根据《米小渊语录》:“奇数等于偶数?真是滑天下之大稽。”。所以异或和不可能等于0,所以其mex值等于0

究极体:无向图删边游戏
Solution:
暂时还不明
可以去看http://blog.sina.com.cn/s/blog_51cea4040100h5j4.html与07年王晓柯论文后面的英文证明


2009年有多篇论文,贾志豪讲了许多例题
无向图删边游戏啊、硬币翻转游戏啊,都在王晓柯的论文里提到
不过Sprague Grundy——Jia Zhihao 定理倒是很有意思
让我们先从一道题开始
bzoj 1022(SHOI 2008)小约翰的游戏
题目描述:NIM游戏,取到最后一个的输,问先手能否必胜
Solution:
一、如果棋子全部为1,根据奇偶性判断
二、如果存在一堆棋子大于1,根据异或和判断

然后我们来讲讲Sprague Grundy-Jia Zhihao定理:
首先把SG游戏改成不能走的胜利的游戏成为Anti-SG游戏
对于任意一个 Anti-SG 游戏,如果我们规定当局面中所有的单一游戏的 SG 值为 0 时,游戏结束,则先手必胜当且仅当:
    (1)游戏的 SG 函数不为 0 且游戏中某个单一游戏的 SG 函数大于 1;
    (2)游戏的 SG 函数为 0 且游戏中没有单一游戏的 SG 函数大于 1。
否则是先手必败

证明思路:
一、称所有单一游戏SG为0时称之为终止状态,终止状态为先手必胜局(显然)
二、对于任意一个我们定义的“先手必胜”,存在一种方式让他走到我们定义的“先手必败”
三、对于任意一个我们定义的“先手必败”,无论怎么走都只能走到我们定义的“先手必胜”

证明:
    一、游戏的SG函数为0且游戏中没有单一游戏的SG函数大于1。(此为必胜态)
        证明:
            若每个单一游戏SG为0,此时是终止状态,于是先手必胜
            否则存在一个单一游戏SG为1,由于SG是mex得到的,所以他可以变成0,这样一来新游戏的SG=1,这是我们定义的“先手必败”
    二、游戏的SG函数不为0且游戏中某个单一游戏的SG大于1。(此为必胜态)
        证明:
            由于SG不为0且有单一游戏SG大于1,容易通过反证法证明至少两个单一游戏的SG大于1,这样一来操作之后必然存在至少一个单一游戏的SG大于1。
            根据张一飞论文中SG函数的公式由来(还记得那个SG的构造过程吧),存在一个方法让他的SG为0。
            综上所述,我们可以构造出我们定义的“先手必败”
    三、游戏的SG函数为0且游戏中有单一游戏的SG大于1(此为必败态)
        证明:
            由于SG为0且有单一游戏SG大于1,容易通过反证法证明至少有两个单一游戏的SG大于1,这样一来操作之后必然存在至少一个单一游戏的SG大于1。
            根据张一飞论文中SG函数的公式由来(还记得那个SG的构造过程吧),不存在一种方法让他的SG为0。
            综上所述,无论怎么走,新游戏的SG不可能为0,这是我们定义的“先手必胜”
    四、游戏的SG函数不为0且游戏中没有单一游戏的SG函数大于1。(此为必败态)
        证明:
            显然是若干个1和若干个0
            操作1:我们把某个SG小于1的单一游戏变成SG函数大于1的单一游戏,这时有SG值大于1的单一游戏有且只有一个,显然游戏SG值不可能等于0
            操作2:我们把某个单一游戏的SG值取反,这时游戏的SG值等于0且没有单一游戏的SG值大于1
            综上所述,无论操作1还是操作2,都是我们定义的“先手必胜”
于是Sprague Grundy-Jia Zhihao定理得证
回过头去看那道题……是不是觉得太水了?

SG函数的“闲扯”就到此为止了……感觉说白了就是例题集?
参考文献:
张一飞《由感性认识到理性认识——透析一类搏弈游戏的解答过程》
王晓柯《解析一类组合游戏》
贾志豪《组合游戏略述——浅谈SG游戏的若干拓展及变形》
vfleaking《SG函数闲扯》
特别感谢:
vfleaking大神……
  评论这张
 
阅读(1707)| 评论(4)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017