阅读 155

博弈论 | 详解搞定组合博弈问题的SG函数

本文始发于个人公众号:TechFlow,原创不易,求个关注


今天这篇是算法与数据结构专题的第27篇文章,我们继续深入博弈论问题。今天我们要介绍博弈论当中非常重要的一个定理和函数,通过它我们可以解决许多看起来杂乱无章的博弈问题,使得我们可以轻松地解决一大类博弈问题。

有了SG函数和SG定理,我们不再是单纯地通过构思、分析和找规律去解决问题了。并且我们之前学过的巴什博奕、威佐夫博弈以及Nim博弈都可以使用SG函数来解决,相当于我们找到了这一大类问题的通解。下面,我们来看几个基本定理和基本概念。

基本定理

ICG游戏

前面我们说了,SG函数和SG定理可以解决一大类的博弈问题。这一大类的博弈问题称为ICG游戏,我们之前介绍过的三种博弈模型,本质上都属于ICG游戏。

关于ICG游戏,它的定义如下,需要满足三个条件:

  1. 游戏有两人参与,两人轮流做出决策,并且两人做出的决策都是对自己最优的
  2. 当有一人无法决策的时候,该人失败。无论两人如何决策,该游戏都必然会在有限时间内结束
  3. 游戏中同一个状态不能达到多次,且游戏没有平局。游戏者在某个确定状态做出的决策集合只与状态有关,与游戏者无关

必胜态与必败态

也就是奇异状态与非奇异状态,我们定义P状态是必败态,N状态是必胜态。我们可以简单理解成,在P状态的玩家一定会输,而在N状态的玩家一定会赢

这一点在之前的Nim取子的文章当中我们曾经深入地分析过,展开来说,其实也有三条:

  1. 无法移动的状态为P状态
  2. 可以移动到P状态的状态为N
  3. 所有移动都会进入N局面的局面为P

我们曾经在分析威佐夫博弈问题的时候,将游戏局面抽象成了二维平面坐标系当中的点。其实所有ICG游戏都可以想象成一张有向无环图(DAG),游戏开始时有一颗放在起点的棋子,两个玩家轮流移动棋子,直到不能移动的玩家落败。所有只能移动到终点的局面都是必胜的,所有只能连接必胜点的点是必败的。我们用递归的思路可以计算出所有点的状态。

当然我们用算法去搜索遍历所有状态这耗时太多了,我们可以通过一个函数来计算它,这就是我们今天文章讨论的重点——SG函数

Sprague-Grundy数的推导

SG是Sprague-Grundy的缩写,我没有记错,这应该是两个人名,它使用起来非常简单,但是推导过程有些复杂。如果我们忽略推导过程直接去研究它的使用的话,你会有一种在运用魔法的感觉。因为你完全猜测不到它其中的原理,所以我们需要详细解释一下它的推导过程,这样才能加深理解。

我们先明确几个概念,首先对于ICG游戏来说,失败的最终状态只有一个,就是无法移动的点,可以认为是DAG图中的终点。从这个终点倒推,所有能够直接连接终点的点是N点。这个很好理解,假如在当前的状态当中,可以移动到一个对手的必败状态,那么对于当前玩家当然是必胜的。

我们对这些状态做一个简单的分层,直接可以连接P点的点是一级胜态。比如nim游戏当中的(1, 0)状态就是一级胜态,它只能通往P点。我们把可以变成败态也可以进入一级胜态的点称为二级胜态,比如nim游戏当中的(0, 2)。比如它进入(1, 0)便是一级胜态,而也可以直接进入(0, 0)变成败态,我们把这样的状态称为二级胜态。类似的,如果一个胜态可以变成败态也可以变成1至n-1级的所有胜态,则称为n级胜态,败态可以认为是0级胜态。

接着我们来看胜态的组合,我们可以把Nim取子问题中的结论照搬过来。两个同级的胜态组合是败态两个不同级的胜态组合是胜态。原因也很简单,就和Nim取子问题中面临两堆同样多的石子必败一样。因为后手可以拷贝先手的操作,直到无法继续操作,游戏结束。而两个不同的胜态,先手可以将其中一个转化成和另一个一样,从而让后手面临两个一样的胜态,所以不同的胜态组合是胜态。

注意这个结论要成立,有两个前提条件,第一个是一个n级胜态可以转移到1 - n-1级任意胜态。第二个是胜态级数只能降低不能升高,其实能升高也没问题,后手可以将先手升高的级数再降低回去,并不会影响结论。

如果你理解了这一层,其实我们对级数的定义其实就是SG函数的值。SG函数能够用来将一个状态映射成一个非负整数的值。它的公式写成这样:

式子中的A和B表示状态表示A状态可以达到B状态。mex是一个定义在集合上的函数,返回的是不属于这个集合的最小非负整数。比如mex(0, 1)= 2,mex(0, 2) = 1, mex(0,1, 2, 3)=4。也就是说我们可以通过A能达到的状态的SG函数值推算出A的SG值

比如在Nim取子问题当中,没有石子是必败,它没有后继状态,所以SG(0) = 0。1颗石子的时候可以移动到0,所以SG(1) = mex{SG(0)} = 1。这样我们就把Nim取子问题和ICG问题当中胜态的级数对应起来了。一个SG数对应Nim当中的一个石子堆,如果我们有多个石子堆,我们怎么计算开始时候的胜负状态?通过Nim取子问题的推导,我们知道是计算各个石子堆石子数量的亦或值,如果亦或之后的结果为0,那么先手必败,否则先手必胜。同样我们计算所有状态的SG值,如果最后得到的SG值亦或的结果为0,说明先手必败,否则先手必胜

关于SG(A + B) = SG(A) xor SG(B)我们可以用数学归纳法来证明,但这个证明没什么必要,我们更重要的是理解SG函数的思想和推导过程。最后,我们利用SG函数来看一道例题。

例题实战

我们来看一道改进版的Nim取子问题,假设有n堆石子,每堆当中有若干个石子。现在两个人轮流从其中取石子,一个人可以选择从任意一堆石子当中取走若干个石子,或者是选择一堆大于1颗石子的石堆将它拆分成两堆。最后无法取走石子的人落败,请问给定每堆石子的数量,谁会获胜。

这题如果去除掉石堆可以拆分的限制,那么它就是一道裸的Nim取子问题。但是加上了限制之后,我们就无法直接使用Nim取子的规则来求解了。但是我们分析一下会发现,这个虽然加上了限制条件,但是仍然满足ICG游戏的限制,所以我们可以使用SG函数来求解。

对于状态N来说,它可以转移到0-N-1任意状态,并且可以拆分成i和N-i两个状态。根据上文的公式:SG(A+B) = SG xor SG(B),所以我们SG(N)而言,它可以转移到0-N-1状态,**以及(i, N-i)**状态。

根据状态之间的关系,我们可以很容易写出求解SG函数的代码:

sg_arr = [0 for _ in range(50)]

def mex(nums):
    # 返回第一个不在nums当中的自然数
    if len(nums) == 0:
        return 0
    for i in range(1, len(nums)+1):
        if i not in nums:
            return i
    return len(nums) + 1
        
        
def sg(n):
    sgs = []
    # 记录下0-N-1状态
    for i in range(n):
        sgs.append(sg_arr[i])
    # N也可以达到(i, N-i)状态,SG(i, N-i) = SG(i) ^ SG(N-i)
    for i in range(1, n):
        ret = sg_arr[i] ^ sg_arr[n-i]
        if ret not in sgs:
            sgs.append(ret)
    # 通过mex函数求解出sg[n]
    sg_arr[n] = mex(sorted(sgs))
    print(sg_arr[n])
复制代码

由于我们计算后面的SG值也需要用到前面的SG值,所以我们需要将之前的答案存储在数组当中。否则的话,如果用递归执行的话会非常耗时。实际上我们计算每一个数的SG值本身也非常耗时,尤其是N很大的时候。所以这个时候可以采取取巧的办法,就是打出一些状态的SG值来进行观察,寻找其中的规律

打表找规律这种方法不甚高明,但是在比赛当中经常使用。

我们打印出一些SG值之后,可以发现对于n而言,如果n % 4 == 0,那么SG(n) = n-1, n % 4 == 3, SG(n) = n+1,否则SG(n) = n。

利用这个规律,我们可以直接得到SG值,把每堆石子的SG值亦或在一起就是最终的答案了。

总结

到这里,我们关于博弈论当中SG函数值的使用就介绍完了。虽然我们用了很多笔墨去说明其中的原理,但是对于初学者而言,估计还是蒙圈的。这是非常正常的,博弈论问题本身就比较考验思维,加上SG函数的推导过程也不是很直观,初学会觉得烧脑和想不明白也是肯定的。

有一个技巧是抓住SG值和Nim取子游戏这个模型的对应关系,从Nim游戏入手,会简单一些。实际上SG值最初也的确是从Nim取子游戏当中推导出来的。

理解了SG函数之后,就足够我们解决绝大多数博弈论算法问题了。这也是博弈论领域非常重要的概念和方法,希望大家都能理解。

今天的文章就到这里,如果喜欢本文,可以的话,请点个关注,给我一点鼓励,也方便获取更多文章。

本文使用 mdnice 排版