您的位置: 首页  >  IT文章  >  【博弈论·入门篇】$SG$函数基础入门

【博弈论·入门篇】$SG$函数基础入门

分类: IT文章 • 2023-11-06 19:04:51

(Preface)

博弈论是个好东西，它的核心便是(SG)函数。

博弈论的应用应该算是非常广泛的，只不过余做过的不多罢了。

“由此及彼、由表及里、去粗取精、去伪存真” ，这就是由感性认识上升到理性认识的关键。

(SG)函数的概念

(A)

经典的取石子游戏，即(nim)游戏。

有若干堆石子，每堆石子个数不一定相同。

对弈双方轮流进行决策，每次可以从一堆石子中取走部分或全部石子，但不能不取。

当某一个人无法决策时，他就输了。

询问先手和后手谁有必胜策略。

局面表示的两种暴力

考虑应该用怎样的方式来表示当前局面。

可重集

最简单的方法就是可重集了，即直接记录下当前每堆石子的个数。

显然这种方法复杂度过高，一点都不美丽，不值得余去喜爱。

集合

考虑如果有两堆数量相同的石子，那么当一个人操作其中一堆时，另一个人必然可以在另一堆中进行镜像操作。

唔姆，也就是说，这两堆石子完全无法对最终结果造成影响。

因此，若同种数量的石子堆存在多个，只需考虑堆数的奇偶性，一种数量最多只有一个贡献。

那么就可以用一个集合来记录下每堆石子的个数啦！

可惜这样还是远远不够的，还需要进一步优化。

局面的加法

暂且不管如何表示局面，先考虑把两种局面(X,Y)拼在一起会发生什么事。

假设已知(X,Y)先手的最终结果，那么所得局面(S)先手的最终结果对应为：

  • (X)负，(Y)负：先手在其中一个游戏会输，则在另一个游戏中依旧是先手，仍然会输。因此，(S)负。
  • (X)胜，(Y)负：先手在(X)中会胜，则后手在(Y)中就变成了先手，而先手变成后手有必胜策略。因此，(S)胜。
  • (X)负，(Y)胜：同上，(S)胜。
  • (X)胜，(Y)胜：要视情况而论，(S)的胜负并不一定。

用二进制数来表示一个局面

考虑能否用一个二进制数来表示一个局面，并用二进制下的异或运算表示局面的加法，规定二进制数为(0)时先手必败。

看看它是否满足先前的一些规律和性质：

  • 两堆相同数量的石子会抵消，扩展一下也就是两个相同的局面会抵消：两个相同的数异或值为(0)，完美满足这个性质。
  • (X)负，(Y)负(Leftrightarrow S)负：(0oplus0=0)。
  • (X)胜，(Y)负(Leftrightarrow S)胜：(Xoplus0=X ot=0)。
  • (X)胜，(Y)胜(Leftrightarrow S)胜负未知：(Xoplus Y)不知道是不是(0)。

综上，用二进制数来表示一个局面是可行的！

然后问题就在于，如何用一个合适的二进制数，能准确描述当前局面。

(SG)函数

唔姆，之前做了那么多的铺垫，现在终于可以请出黄金剧场今日的荣耀嘉宾——(SG)函数啦！

对于这个游戏，每一堆石子的(SG)函数就等于石子数。

关于如何求出一个游戏的(SG)函数在后文会有介绍，这里仅仅考虑证明它的正确性：

  • 每一个必胜态(S)可以到达必败态(T)：
    • 设(S=s_1oplus s_2oplus...oplus s_n)。
    • 因为(S ot=0)，必然存在(s_k)，满足(Soplus s_k<s_k)。（比较显然，例如当(S)和(s_k)最高位相同，异或之后就会消去，值必然减小）
    • 不妨令(k=1)，且设(x=Soplus s_1=s_2oplus s_3oplus...oplus s_n)。
    • 由于(x<s_1)，因此可以从这堆石子中拿走(s_1-x)个石子，使得(s_1'=x)。
    • 则新状态(T=s_1'oplus s_2oplus s_3oplus...oplus s_n=xoplus x=0)，为必败态。
  • 每一个必败态(S)只能到达必胜态(T)：
    • 同样设(S=s_1oplus s_2oplus...oplus s_n=0)。
    • 由于一次取石头必然导致某个(s_i)发生改变，改动之后总异或和不可能再为(0)，也就是说(T ot=0)。

(SG)函数的一般求法

(SG)函数需要满足的条件

其实可以结合先前对(nim)游戏(SG)函数正确性的证明分析。

  • 每一个必胜态(S)可以到达必败态(T)：
    • 设(SG(S)=SG(s_1)oplus SG(s_2)oplus...oplus SG(s_n))。
    • 因为(SG(S) ot=0)，必然存在(s_k)，满足(SG(S)oplus SG(s_k)<SG(s_k))。
    • 不妨令(k=1)，且设(x=SG(S)oplus SG(s_1)=SG(s_2)oplus SG(s_3)oplus...oplus SG(s_n))。
    • 若能通过操作使得(SG(s_1')=x)，则新状态(SG(T)=SG(s_1')oplus SG(s_2)oplus SG(s_3)oplus...oplus SG(s_n)=xoplus x=0)，为必败态。
    • 为了保证(SG(s_1'))必然可以等于(x)，我们可以强制所有(SG)值小于(SG(s_i))的后继状态都存在。（充分）
  • 每一个必败态(S)只能到达必胜态(T)：
    • 同样设(SG(S)=SG(s_1)oplus SG(s_2)oplus...oplus SG(s_n)=0)。
    • 如果一次操作能让某个(SG(s_i))不变，则改动之后总异或和仍旧为(0)，也就是说(SG(T))可能会是(0)，显然不合法。
    • 即，(SG(s_i))不能与某个后继状态的(SG)值相等。（充要）

(SG)函数的求法

既要满足(SG)值小于(SG(s_i))的后继状态都存在，又要满足(SG(s_i))不能与某个后继状态的(SG)值相等。

结合在一起就会发现，(SG(S)=mex{SG(s_1),SG(s_2),...,SG(s_n)})。

顺便简单解释一下之前的游戏(A)（(nim)游戏），(S)可以转移到(0sim S-1)，容易发现当(SG(x)=x)时刚好满足条件。

参考文献

2002 - 张一飞：《由感性认识到理性认识——透析一类搏弈游戏的解答过程》

(Postscript)

(SG)函数的入门结束了，但真正的博弈论才刚刚开始吶。。。

相关推荐