(转载)-关于sg函数的理解

最近学习了nim博弈,但是始终无法理解sg函数为什么sg[S]=mex(sg[S'] | S->S'),看到一篇博文解释的不错,截取了需要的几章节。

四、Sprague-Grundy数的提出

  我们以Flip Game为例,研究一下胜态还有什么更深入的性质。

  状态“++”是最简单的胜态,它只有一种走法,结果是败态。状态“+++”跟“++”在这一点上是一样的,因此它们其实是等价状态。状态“++++”就有两种不同的走法(对称的走法算同一种):一是把中间两个加号变成减号,这样得到的次态“+--+”是个败态;二是把某一端的两个加号变成减号,这样得到的次态“--++”或“++--”(等价于“++”)是个胜态。

  于是我们发现了两种不同的胜态。像“++”、“+++”这样,只能变成败态的胜态,我们称之为“一级胜态”。像“++++”这样,可以变成败态,也可以变成一级胜态的胜态,我们称之为“二级胜态”。类似地,如果一个胜态可以变成败态,也可以变成1至n-1级的所有胜态,则我们称之为“n级胜态”。而败态可以称为“零级”。

  我们看一下胜态的组合是否与级数有关。两个一级胜态的组合是败态,因为先手玩家的任意一步行动都会将其中一个胜态变为败态,留给后手玩家的就是胜态与败态组合成的胜态。一个一级胜态与一个二级胜态的组合是胜态,因为先手玩家可以将二级胜态变为一级胜态,留给后手玩家的就是两个一级胜态组合成的败态。两个二级胜态组合成的胜态也是败态,因为先手玩家无论将其中一个二级胜态变成败态还是一级胜态,留给对方的组合都是胜态。

  我们似乎发现了一个规律:两个同级胜态的组合是败态,两个不同级胜态的组合是胜态。没错!考察两个同级胜态的组合,无论先手玩家如何降低其中一个胜态的级数(甚至将其变成零级的败态),后手玩家总可以将另一个胜态降到同一级,最终先手玩家将面对两个败态组合成的败态。而若先手玩家面对的是两个不同级的胜态,他就总可以将其中较高级的胜态降至与较低级的胜态同级,这样留给后手玩家的就是败态。

  上面对于胜态等级的定义有一个漏洞:如果一个胜态A可以变成败态或二级胜态,但不能变成一级胜态,那么它应该算一级还是三级呢?规律的证明过程同样也有一个漏洞:我们默认了一步行动只能让胜态的级数降低,那么能不能让胜态的级数升高呢?注意到规律证明过程的关键,在于如果要降低一个胜态的级数,则可以降低到任一级。于是我们就知道,上面的状态A应当定义为一级胜态。这导致胜态的级数可以升高,不过没关系,可以这样弥补规律证明的漏洞:在两个同级胜态的组合下,若先手玩家升高了其中一个胜态的级数,则后手玩家可以将它降回原级,这样两个同级胜态的组合仍是败态。

  通过定义胜态的级数,我们解决了两个胜态组合而成的母状态的胜负判定问题。事实上,我们定义的“级数”,就是传说中的Sprague-Grundy数(简称SG数)。SG数是一个从状态映射到非负整数的函数,它的形式化定义如下:

  ★ (转载)-关于sg函数的理解

式中A、B代表状态,(转载)-关于sg函数的理解代表B是A的一个次态。mex是一个定义在集合上的函数,表示不属于集合的最小非负整数,它是minimum excludant的缩写。这个定义用通俗的语言表达,就是说一个状态的SG数,等于它的次态取不到的最小SG数。

五、状态组合时Sprague-Grundy数的运算规则

5.1 规则的发现

  有了SG数,我们就可以判断任意两个子状态组合成的母状态的胜负了。但是,如果一个母状态是由三个子状态组成的,怎么办?我们发现,仅仅判断两个子状态组合成的母状态的胜负是不够的,我们还需要求出母状态的SG数。在下文中,我们用(转载)-关于sg函数的理解表示SG数分别为a、b的两个子状态组合成的母状态的SG数为c,我们的目标,就是弄清(转载)-关于sg函数的理解运算的法则。当然,我们这么写默认了由子状态的SG数可以唯一确定母状态的SG数,这一点其实未经证明。

  依然从最简单的情况开始。两个败态的组合还是败态,也就是说(转载)-关于sg函数的理解。两个一级胜态的组合也是败态,即(转载)-关于sg函数的理解。一个败态和一个一级胜态的组合,我们可以考虑最简单的情况:败态是终局态,不能再改变;而一级胜态只能变成败态。显然,这个组合的次态只能是两个败态组成的败态,故它本身是一级胜态,即(转载)-关于sg函数的理解

  ——(转载)-关于sg函数的理解(转载)-关于sg函数的理解(转载)-关于sg函数的理解,聪明的读者,你看出规律了吗?

  如果你没看出规律,或者不相信你看出的规律,我们可以再算几个SG数稍微大一点儿的情况。考虑最简单的败态和二级胜态的组合:败态不能变化,二级胜态只能变成一级胜态或败态,于是组合的次态的SG数只能是(转载)-关于sg函数的理解(转载)-关于sg函数的理解。这说明败态和二级胜态的组合是二级胜态,即(转载)-关于sg函数的理解。同理可得(转载)-关于sg函数的理解。再看胜态和胜态的组合。前面已经得到,两个同级胜态的组合为败态,故(转载)-关于sg函数的理解。那么两个不同级胜态的组合呢?

    • (转载)-关于sg函数的理解的次态可能是(转载)-关于sg函数的理解(转载)-关于sg函数的理解(转载)-关于sg函数的理解,次态的SG数中0、1、2俱全,故(转载)-关于sg函数的理解
    • (转载)-关于sg函数的理解的次态可能是(转载)-关于sg函数的理解(转载)-关于sg函数的理解(转载)-关于sg函数的理解(转载)-关于sg函数的理解,次态的SG数缺少2,故(转载)-关于sg函数的理解
    • (转载)-关于sg函数的理解的次态可能是(转载)-关于sg函数的理解(转载)-关于sg函数的理解(转载)-关于sg函数的理解(转载)-关于sg函数的理解(转载)-关于sg函数的理解,次态的SG数缺少1,故(转载)-关于sg函数的理解

  现在看出规律了吗?相信了吗?

  我们再换个角度,看看我们已经得到了(转载)-关于sg函数的理解运算的哪些性质:

    1. 交换律(转载)-关于sg函数的理解:显然;
    2. 结合律(转载)-关于sg函数的理解:显然;
    3. 归零律(转载)-关于sg函数的理解:因为两个同级胜态的组合为败态;
    4. 恒等律(转载)-关于sg函数的理解:本节已用最简单的情况说明。

具有这四个性质的二元运算是什么呢?是异或

  到此为止,我们通过举例的方法,发现了状态的组合对应着SG数的异或。不过,我们并没有证明通过子状态的SG数能够唯一确定母状态的SG数(即(转载)-关于sg函数的理解运算结果的唯一性),也没有证明异或是能够达到这个目的的唯一一种运算。下面,我们就通过SG数和状态组合的定义,证明状态的组合对应着SG数的异或,即(转载)-关于sg函数的理解,其中加号表示状态的组合,(转载)-关于sg函数的理解号表示异或。

5.2 规则的证明

  由SG数的定义,有(转载)-关于sg函数的理解。由状态组合中子状态的独立性,可知状态(转载)-关于sg函数的理解必能拆成(转载)-关于sg函数的理解(转载)-关于sg函数的理解的形式,其中(转载)-关于sg函数的理解(转载)-关于sg函数的理解。于是有:

  ★ (转载)-关于sg函数的理解

下面,我们想要把右边的(转载)-关于sg函数的理解(转载)-关于sg函数的理解换成(转载)-关于sg函数的理解(转载)-关于sg函数的理解。但这正是我们要证明的结论呀!怎么办呢?可以用数学归纳法。不过,由于SG数在游戏过程中可能会增加,不能按SG数本身的顺序来归纳。但是,由于游戏是有限的,游戏的所有状态可以进行拓扑排序,这个顺序的逆序可以用作归纳的顺序。这样,我们就可以放心地进行代换了:

  ★ (转载)-关于sg函数的理解

下面要证明的,就是(转载)-关于sg函数的理解不属于右边两个集合中的任意一个,但比它小的正整数都属于两个集合中的某一个。为书写简便,用(转载)-关于sg函数的理解代替(转载)-关于sg函数的理解

  先看(转载)-关于sg函数的理解本身。由SG数的定义,既然(转载)-关于sg函数的理解(转载)-关于sg函数的理解,故(转载)-关于sg函数的理解(转载)-关于sg函数的理解,故两个集合均不包含(转载)-关于sg函数的理解。再看比(转载)-关于sg函数的理解小的任意非负整数(转载)-关于sg函数的理解。定义(转载)-关于sg函数的理解,则用(转载)-关于sg函数的理解(转载)-关于sg函数的理解三者异或,至少使得其中一者减小(因为(转载)-关于sg函数的理解非零,(转载)-关于sg函数的理解的二进制表示中最高位的1必来自(转载)-关于sg函数的理解三者之一,(转载)-关于sg函数的理解与这一者异或会使它减小)。但这一者不会是(转载)-关于sg函数的理解,因为(转载)-关于sg函数的理解。不妨设这一者是(转载)-关于sg函数的理解,即(转载)-关于sg函数的理解。此时,可取(转载)-关于sg函数的理解的一个次态(转载)-关于sg函数的理解使得(转载)-关于sg函数的理解,由SG数的定义,这是一定能做到的。这就证明了(转载)-关于sg函数的理解(转载)-关于sg函数的理解都属于右边两个集合之一,故(转载)-关于sg函数的理解

  (最后一段的证明思路来自*Nimber词条)

六、Sprague-Grundy定理的完整表述

  下面给出Sprague-Grundy定理的完整表述:

  若一个游戏满足以下条件:
  1. 双人、回合制;
  2. 信息完全公开(perfect information);
  3. 无随机因素(deterministic);
  4. 必然在有限步内结束,且每步的走法数有限(finite);
  5. 没有平局;
  6. 双方可采取的行动及胜利目标都相同(impartial);
  7. 这个胜利目标是自己亲手达成终局状态,或者说走最后一步者为胜(normal play);
则游戏中的每个状态可以按如下规则赋予一个非负整数,称为Sprague-Grundy数:
  ★ (转载)-关于sg函数的理解 
(式中A、B代表状态,(转载)-关于sg函数的理解代表A状态经一步行动可以到达B状态,mex表示一个集合所不包含的最小非负整数)。SG数有如下性质:
  1. SG数为0的状态,后手必胜;SG数为正的状态,先手必胜;
  2. 若一个母状态可以拆分成多个相互独立的子状态,则母状态的SG数等于各个子状态的SG数的异或。

  利用Sprague-Grundy定理,可以将记忆化搜索的程序优化成如下形式:

mem = {}
def SG(A): # 求状态A的SG数
if A not in mem:
S = sub_states(A) # sub_states(A)将A尽可能细致地拆分成子状态
if len(S) > 1: # A可以拆分,用子状态的异或求其SG数
mem[A] = reduce(operator.xor, [SG(B) for B in S])
else: # A不可拆分,根据定义求其SG数
mem[A] = mex(set(SG(B) for B in next_states(A)))
# next_states(A)返回A的所有次态
# 注意这条语句蕴含了“终局态的SG数为0”
return mem[A]

这段程序中的状态只包含棋盘信息,不包含“下面轮到谁”。其中mex函数的实现十分平凡,从略。


10833 更新:

  受这个问题启发,我加强了Sprague-Grundy定理中的两个条件:

  • 一是“有限”:原先我只要求“游戏在有限步内结束”,这次添加了“每步的走法数也有限”;
  • 二是“impartial”:原先我只要求“双方可采取的行动相同”,这次添加了“双方的胜利目标也相同”。

  另外,我补充了第二部分结尾处代码遗漏的递归终止条件。

上一篇:Android 动态加载 (一) 态加载机制 案例一


下一篇:IOS开发 APP提交程序上传流程