阅读了《由感性认识到理性认识——透析一类搏弈游戏的解答过程》、《解析一类组合游戏》、《组合游戏略述——浅谈SG游戏的若干拓展及变形》这三篇论文,对组合游戏以及SG函数有了更深的理解。这篇文章摘下了这三篇论文的部分重要内容,以及部分我对组合游戏的理解。


一些名词与约定:

  • 游戏:这里的游戏指的并不是平时玩的那些游戏(Dota2啥的),而是只一些如Nim取石子之类的“益智”组合游戏。并且,我们关注的不是游戏好不好玩,而是游戏有没有必胜策略。下文详细介绍。
  • 状态:用一些数字来表示的游戏进行中的一个局面。
  • 必胜状态:存在一种走法走到一个必败状态。
  • 必败状态:后继状态都为必胜状态。
  • 特别的在组合游戏中一个状态不是必胜状态就是必败状态。

组合游戏是满足以下一些性质的游戏:

  1. 游戏只有两名参与者。
  2. 游戏过程中任意时刻有确定的状态。
  3. 规则规定了任意状态参与者可以到达的状态集合。
  4. 参与者轮流进行操作。
  5. 在游戏处于某状态,当前参与者不能进行操作时,游戏结束。此时按照规则决定胜负。
  6. 无论参与者做出怎样的操作游戏都可以在有限步数内结束(没有平局)。
  7. 信息对于两位参与者都是公平的透明的。
  • 我们还假设参与者都足够聪明,在有必胜策略时一定会走必胜策略。

几个游戏

游戏0:

有一堆石子,甲乙两人轮流取,不能不取,最多取完,当轮到一个人取不了时这个人输。
  这个游戏很显然,只要现在有石子,就可以都取完,然后第二次另一个人就没法取。 所以在这个游戏里{0}是必败状态,其他都是必胜状态。

游戏1:

有两堆石子,甲乙两人轮流取,每次只能从其中一堆取,不能不取,最多取完一堆,当轮到一个人取不了时这个人输。
  这个游戏相当于两个第一个游戏的“和”。我们可以很轻松的发现,如果两堆的石子个数一样的时候是先手必败的,因为不论先手怎样取石子,后手可以在另一堆中用相同的策略取,知道先手没有可以取的石子。而两堆石子个数不一样的时候是先手必胜的,先手可以拿较多的一堆使得两堆石子一样多。

游戏2:

甲乙两人面对若干堆石子,其中每一堆石子的数目可以任意确定,每一步应取走至少一枚石子,每一步只能从某一堆中取走部分或全部石子,如果谁无法按规则取子,谁就是输家。
  这个游戏看起来更复杂了,现在我们要引入一个有力的工具,叫做SG函数SG定理

SG函数

  • 一个游戏的终态x的SG(x)=0。
  • 其余状态x的SG(x)=min( n|n∈N且n!=SG(F(x)) )

其中F(x)为状态x能转移到的任意一个状态。

  • 第二个式子也写作 SG(x)=mex{SG(F(x))}
    SG函数的性质:所有SG(x)==0的状态都是必败状态,所有SG(x)!=0的状态都是必胜状态。

SG定理:几个单个的组合游戏组成的游戏状态的SG值为每个单个游戏状态SG值的Xor和。

  • 证明见论文。
      然后对于游戏0有x个石子时SG(x)=x,所以求以下这些状态的Xor和就可以得到整个状态的SG值。

游戏3:

甲乙双方事先约定一个数m,并且每次取石子的数目不能超过m个,其余规则同游戏2。
  设只有一堆且m=3:
  SG(0)=0,SG(1)=1,SG(2)=2,SG(3)=3,SG(4)=0,SG(5)=1…
  所以SG(x)=x mod (m+1)。
  求一下整个状态的SG值就可以判断了。

游戏4:

甲乙两人面对若干排石子,其中每一排石子的数目可以任意确定。两人轮流取走一些石子,每一步必须从某一排中取走两枚石子,并且这两枚石子必须是紧紧挨着的,拿走后这一排就会断裂成两排。如果谁无法按规则取子,谁就是输家。(发挥想象力)
  这个题看起来不像前几道题那么裸了。但是与前几道题还是很像,也可以用SG解决。
  只是没有那么明显的规律了。需要从SG(0)=0,SG(1)=0,开始枚举可能转移的状态递推计算SG函数,程序实现可以记忆化搜索。


  组合游戏还有许多的问题,定理,这里只是最基础的入门,还需要深入学习啊。


  人们认识事物的过程中,开始只是看到了各个事物的现象。这就是认识的感性阶段。在这个阶段中,还不能作出合乎逻辑的结论。 随着研究的深入,这些感觉和印象的东西反复了多次,于是在人们的脑子里生起了一个认识过程中的突变,最后产生出合乎逻辑的结论。这就是认识的理性阶段。
  “由此及彼、由表及里、去粗取精、去伪存真” ,这才是由感性认识上升到理性认识的关键。(摘)

  • 本文缺少一些证明,若需了解详细,请参考原论文。