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

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

SG闲扯  

2012-04-17 21:23:41|  分类: 知识点 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
SG函数我也不是很会,所以说不能叫什么《21天,SG函数从入门到精通》、《SG Primer》之类的牛名字,就叫闲扯吧……
没遇到实际问题扯出来的东西叫无聊……所以我们先看看问题,再引出今天要闲扯的东西。

尼姆游戏(为了适应广大中国群众,特意翻成中文叙述……):
现在地上有N个石子堆,分别有A1,A2,…,An个石子。
现在Alice和Bob两个人玩游戏,规则如下:
1.Alice和Bob轮流走,每次只能从某一堆中取走任意数目的石子。不可以不取。
2.无路可走的人输。
Alice第一步由走,Alice问你,对于当前局面,她是否有必胜下法?

显然,我们之前学的博弈论知识都太弱了,不足以解决此问题,怎么办?

定义——游戏图:我们可以将游戏中的每一个状态抽象成图中的一个点,将每一步决策抽象成图中的一条有向边。我们将这个图称为该组合游戏的游戏图。
显然这个尼姆游戏的游戏图是个DAG(有向无环图),因为石子数是递减的,不可能玩着玩着玩多了几个石子对不对……
那么称一个局面做出一个决策能到达的新局面为后继局面。

我刚才罗里吧嗦地堆定义有什么用呢?因为SG函数要闪亮登场……
若v是尼姆游戏中的一个局面那么:
              0 (如果v局面为空,即无路可走)
SG(v) =  
              mex{SG(u)} (u是v的后继局面,mex是一种定义在整数集合上的操作,表示不在这个集合中的最小自然数)
那么,得到SG函数的性质:
1.当局面v是必胜局面时,SG(v)不为0
2.当局面v是必败局面时,SG(v)为0
自己悟一下……爱好数学的同学可以用数学归纳法证一下……

那么有同学会说了,那只要求个SG,这题不就完了?
显然不是!!!你怎么求SG?DFS吗?MLE+TLE啊。

要让SG发挥最大作用,不能只靠上面那个定义。
首先考虑简单情况,即只有一堆石子,石子个数为a,那么SG值为多少?
显然这有必胜策略,就是把石子都拿光,让对手无路可走。(走别人的路,让别人无路可走!——但丁),所以SG值必不为0
=_=知道SG值不为0有什么用……囧……
换个思路。没有石子时,SG为0。而一个石子时,共一个后继局面——没有石子。根据SG函数的定义,那么a = 1时SG为1。
2个石子呢?共2个后继局面——没有石子,一个石子。所以SG值为mex{0, 1} = 2
以此类推,a个石子时,SG值为a!

很多堆的话应该怎么求呢?总不能又像刚才一样递推出来吧……被囧到了吧……

重新审视这个尼姆游戏,每一堆的决策都是相互独立的,A堆取了石子并不妨碍在B堆取石子。那么,其实尼姆游戏本质上是许多堆石子组成的游戏,也就是说这个游戏可以拆成许多小游戏,虽然某个小游戏胜利了并不代表尼姆游戏会胜利,但小游戏的胜利在一定程度上影响着尼姆游戏的胜利,小游戏之间是无互相影响的,小游戏的SG值我们是知道的。我们是否可以猜想,可以通过对小游戏的SG的某种运算,算出尼姆游戏的SG值呢?
答案是肯定的。
下面引入SG定理:
如果:大游戏 = 小游戏1 + 小游戏2 + …… + 小游戏n
那么:SG(大游戏) = SG(小游戏1) ^ SG(小游戏2) ^ …… ^ SG(小游戏n)
这里的^学C/C++的都懂的,是位运算异或。
不要问我为什么是这样!!因为我也不知道!!啦啦啦……我还没有看见哪一篇论文证了这家伙。

好,那么尼姆游戏判断是否必胜的方法就是——A1 ^ A2 ^ A3 ^ … ^ An = 0 即为必败,否则为必胜。
尼姆游戏完美解决。Alice和Bob可以在比赛之前决出胜负了。

不过我们要研究的SG函数还没有研究完。什么时候可以用SG函数?
首先游戏要是一个组合游戏,即:
1.游戏有两个人参与,二者轮流做出决策。且这两个人的决策都对自己最有利。
2.当有一人无法做出决策时游戏结束,无法做出决策的人输。无论二者如何做出决策,游戏可以在有限步内结束。
3.游戏中的同一个状态不可能多次抵达。且游戏不会有平局出现。
4.任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关,而与游戏者无关。
什么时候能把游戏拆成若干个小游戏呢?
1.一个小游戏中的决策不会干扰另一个小游戏。
2.所分成的小游戏合起来一定要能拼成原来的游戏。

于是对于SG函数的各种变种,只要我们使用好SG定理,解出小游戏的SG再异或即可了。

——闲扯结束——
(有关更神一点的题目请见贾志豪的论文《组合游戏略述——浅谈SG游戏的若干拓展及变形》)
  评论这张
 
阅读(1262)| 评论(7)
推荐 转载

历史上的今天

评论

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

页脚

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