博弈论浅析

本文主要参考以下文章,非常感谢大佬的文章,大家可以去阅读下:
【洛谷日报#78】浅谈算法——博弈论(从零开始的博弈论) - 知乎
https://wenku.baidu.com/view/25540742a8956bec0975e3a8.html
此外,本文涉及的博弈均为公平博弈,至于不公平博弈的浅析以后再说吧,反正很少遇到相关的题目。咕咕咕

博弈论是acm中比较常见的题型,其难点在于,对于一个新的博弈游戏,不能简单地将已有的博弈模板套上去,而是要进行分析,拆解成熟悉的模板。或者打表找规律

本文会将一些博弈模型进行分析,但对于一些过于复杂的博弈模型也只会给出结果,详细的数学分析还请读者自行百度。或大佬可以选择自己证明

此外,下文的博弈游戏如果没有特别说明,都默认为无法行动的一方输。

巴什博弈:

先谈谈一个最简单的博弈模型——巴什博弈。

有两个人取石子,每次可以取 1,2,3,4,5 颗,问石子的数量为多少时先手必胜。

可以发现,当石子的数量为 nn\bmod6=0 时,无论先手取多少颗石子,后手一定能将石子的数量取到 6 的倍数。这样下去,最后一定是后手将石子取完,先手输。

而在其他情况,先手可以先把石子的数量取成 6 的倍数,然后后手就陷入了上一种情况中先手的处境,最后是先手胜。

巴什博弈就是这种情况的推广,当每次能取 [1,m] 颗石子,先手必败当且仅当石子数量 n\bmod(m+1)=0 ,否则先手必胜。

状态转移:

那上面的问题再改一改,变成:

有两个人取石子,每次可以取集合 S 内的个数,问石子的数量为多少时先手必胜。
S=\{1,3,7\}

这时候又该怎么做呢?

考虑将游戏终止的状态称为终止态,或者说必输态,其余的状态称之为必胜态。那么显然,一个状态是必输态当且仅当它没有后继状态或者说它的后继状态全是必胜态,而一个状态是必胜态当且仅当它的后继状态中存在必输态

我们可以考虑将状态看成点,状态的转移看成有向图的边。通过上述的说明我们就可以通过状态转移来求得每个状态是必输还是必赢。然后根据问题的规模,再考虑是打表找规律还是直接用状态转移来模拟。

在这个问题中,我们试下用刚刚学到的方法来求下各个状态的值。首先 0 没有后继状态是必输态, 1、3、7 是必胜态。继续推,发现奇数全是必胜态,偶数全是必输态,这就是这道题的规律了。

SG函数:

让我们把问题继续扩展,如果问题不只一堆石子呢?

有两个人取石子,有 n 堆石子,每堆石子的数目是 x_1,x_2,…,x_n ,每个人每次可以选择一堆石子从中拿任意数目的石子,但不能不取,问什么时候先手必胜?

顺便一提,这种游戏被称为Nim游戏

这里有一个非常有用的函数来解决这个问题——SG函数。为每一个状态设一个SG值,SG值 f(v)=mex\{f(u)|u \in child[v]\} 。其中 mex 的意思是输入一个集合,输出不属于该集合的最小自然数。 child[v] 的意思是 v 的后继状态。

例如,假设状态 4 的后继状态是状态 1、2、3 ,它们的SG值分别是 f(1)=0,f(2)=1,f(3)=3 ,那么状态 4 的SG值就是 f(4)=mex\{0,1,3\}=2.

可以发现,不能行动就输的博弈游戏的终止状态的SG值总是为 0 。那么对于这种博弈游戏,可以发现,先手必败当且仅当此时状态的SG值为 0 。证明过程可以类似于巴什博弈的证明:先手将游戏转变为下一个状态时,下一个状态的SG值必不为 0 ,之后后手一定有办法将SG值不为 0 的状态转变为SG值为 0 的状态。所以先手必败当且仅当博弈游戏状态的SG值为 0 ,反之先手必胜。

我们把能用SG函数解决的游戏称为SG组合游戏,这种游戏具有以下特征:

  1. 游戏由两人轮流行动,每次都采取对自己最有利的策略。
  2. 无法行动的人输,且无论双方如何行动,游戏总能在有限步结束
  3. 游戏中一个状态不能多次抵达。且游戏没有平局。
  4. 每个游戏者能采取的行动仅与游戏此时的状态有关,与游戏者无关,即游戏者没有独特的、仅由该游戏者能采取的行动。

当然,到这个时候读者可能有点奇怪,SG函数不是和上文必胜态和必输态的转化差不多吗?那为什么还要搞个SG值呢?

别忘了我们当前所要解决的Nim游戏问题。实际上其中的每堆石子都可以看成一个SG组合游戏,且每个SG组合游戏的SG值可以算得为这堆石子的颗数。那么我们就可以得出一个神奇的结论:Nim游戏的SG值可以看成其中每堆石子SG值的异或和,即每堆石子颗数的异或和,且Nim游戏先手必败当且仅当其SG值为 0

接下来就Nim游戏先手必败当且仅当其SG值为0给出证明:即为什么SG值是异或和我就不知道怎么证明了欸嘿

如果先手在一次行动前,游戏的异或和为 0 ,然后假设先手在进行一次行动后,游戏的异或和仍然为 0 。设先手是将一堆石子中的 x_k 个石子变成 x_t 个石子,那么由异或的运算法则得出 x_k 要等于 x_t ,而这是矛盾的。所以先手在异或和为 0 的游戏中进行一次行动后,游戏的异或和一定不为 0

然后后手一定面临的是异或和不为 0 的状态。此时后手只需找到一堆石子,异或和二进制最左端的 1 的位置对于这堆石子的SG值来说,其二进制对应位置的数也是 1 。这是一定能找得到的,因为只有存在符合这个条件的一堆石子,二进制异或和的那个位置才可能为 1 。然后从这堆石子中取走石子,使得二进制这一位的异或和为 0 ,这也是一定做得到的。之后,如果右端有异或和不为0的一位,再继续取石子,使得石子堆这一位的二进制 01 , 10 ,这样这一位的异或和就变为0了。重复上述操作,这样整个游戏又变为异或和为 0 的状态了

由此可证,在这种情况后手行动后总是能使得异或和为 0 ,又因为终结态的异或和也为 0 ,所以当异或和为 0 时后手必胜,反之先手必胜。(因为先手可以用上文提到的方式使得后手面临异或和为 0 的情况,使得先后手的地位反转了)

实际上,不止Nim游戏,我们可以把上述结论推广到所有SG组合游戏,即当双方每次都只能选择SG组合游戏中的其中一个SG游戏行动时,先手必胜当且仅当各个SG游戏的异或和不为 0

其中的证明和对于Nim游戏的证明类似,只不过要补充一点。当通过改变其中一个游戏的SG值将异或和变成不为 0 时,这个游戏的SG值也有可能增加。由于SG值为 m 的状态,其后继状态的SG值至少有 0m-1 ,所以这个时候可以重新把这个游戏的SG值变成和原来一样,这样结论仍然和原来没有差别了。

这个结论非常重要。很多博弈论的题目都可以通过将题目提炼为SG组合游戏从而得出答案。

Multi-SG游戏

如果在Nim游戏的基础上添加一个操作,即可以采取行动将一堆石子分成多堆石子,还可以用SG函数来解决问题吗?答案是是的,且此时这堆石子的这种情况的SG值为其分成的多堆石子的异或和。

例如在Nim游戏的基础上规定可以将一堆石子变成两堆石子,那么数量为 3 的一堆石子的SG值是 mex\{0,1,2,(1 xor 2)\}=4 ,其中的 1xor2 代表将数量为 3 的石子分成数量为 1 和数量为 2 这两堆石子的后继状态的SG值。

这个结论可以推广到SG组合游戏中,即在其他规则和SG游戏一样的情况下,增加一条规则:一个单一SG游戏的后继可分为多个SG游戏。这就是Multi-SG游戏:且可以用上文的方法求SG值。

Every-SG游戏:

如果在普通SG游戏的基础上,新增一条规则:每次行动,每个可以移动的SG游戏都要移动,这就是Every-SG游戏。

例如棋盘上有n个棋子在不同的位置,双方每次行动都要将每一个可以移动的棋子按规则移动,这就是典型的Every-SG游戏。

对于SG中每个游戏,我们设一个 step 函数,然后令 uv 的后继状态,那么:
step(v)= \begin{cases} 0,&v为终止状态\\ max(step(u))+1,&SG(v)>0且SG(u)=0\\ min(step(u))+1,&SG(v)=0 \end{cases}

然后就有一个定理:Every-SG游戏先手必胜当且仅当单一游戏中最大的step为奇数

奇异局势:

现在又有一个新的问题:

有两堆石子,个数为 x_1,x_2 。A,B轮流取石子,规定要么只取一堆的任意多个,要么在两堆里取同样任意多个,问A先手是否有必胜策略。

这个博弈叫做威佐夫博弈。这个游戏乍一看可能很简单,实际上比较复杂,不能用普通的SG函数来表示。在这里我们用 (a,b) 来表示两堆石子的数量并称之为局势。 (0,0) 局势时,先手必输,这种先手必输的局势称之为奇异局势。

我们用先前必胜态和必败态的转化分析,发现如下奇异局势 (0,0),(1,2),(3,5),(4,7),(6,10)

通过找规律,猜测奇异局势 (a_k,b_k) 满足两个条件:
\begin{cases} a_k是前面没出现过的最小自然数\\ b_k=a_k+k \end{cases}
可以通过分情况分析,可以发现如果先手将奇异局势破坏,后手总能将游戏恢复为奇异局势。

此外,奇异局势符合Beatty数列,我们可以通过Beatty数列来快速求出奇异局势:

取正无理数 \iota,\kappa ,使得 \frac{1}{\iota}+\frac{1}{\kappa}=1
再构造两个数列 a_n,b_n ,它们通项是 a_n=\lfloor n*\iota\rfloor,b_n=\lfloor n*\kappa\rfloor
那这两个数列就是Beatty数列,且满足两个数列都是严格递增的,并且每个正整数在两个数列中只出现一次这两个条件。

然后再选择满足 b_n=a_n+n 这一条件的Beatty数列,就能从Beatty数列得出奇异局势了。
由这一条件推出 \frac{1}{\iota}+\frac{1}{\iota+1}=1 ,从而求出 \iota=\frac{\sqrt{5}+1}{2}
所以求出通项式 a_k=\lfloor k*\frac{\sqrt{5}+1}{2} \rfloor,b_k=a_k+k

所以,我们只需要用通项式就能判断是否为奇异局势,从而判断是否先手必胜。

斐波那契博弈:

有一堆个数为 n 的石子,A,B轮流取石子,满足:
1.先手不能在第一次把所有的石子取完;
2.之后每次可以取的石子数介于 1 到对手刚取的石子数的 2 倍之间(包含 1 和对手刚取的石子数的 2 倍)。
约定取走最后一个石子的人为赢家,问A先手是否有必胜策略。

可以发现先手必胜当且仅当n不是斐波那契数列的数

Anti-SG游戏

之前提到的博弈都是不能行动时就输,但如果我们改变规则,变成不能行动时就赢呢?这就是Anti-SG游戏。

Anti-SG游戏规定决策集合为空的一方胜,其他规则和SG游戏相同。

我们对于求Anti-SG游戏何时先手必胜有这样一条定理,SJ定理:

对于任意一个Anti-SG游戏,如果规定局面中所有单一游戏SG值为 0 时,游戏结束,那么先手必胜当且仅当符合以下任一条件:

  • 游戏的SG值不为 0 且游戏中存在单一游戏SG值大于 1
  • 游戏的SG值为 0 且游戏中任何单一游戏SG值小于等于 1

Nim-k游戏

这是Nim游戏的一种扩展,题意为:

有两个人取石子,有 n 堆石子,每堆石子的数目是 x_1,x_2,…,x_n ,每个人每次可以选择不超过 k 堆石子从中拿任意数目的石子,但不能不取,问什么时候先手必胜?

直接抛出结论和必败态时的最优取法吧。

结论:把n堆石子数都用二进制表示,统计二进制上每一位 1 的个数,如果每一位上 1 的个数 mod(k+1) 全为 0 ,先手必败,否则先手必胜。

取法:

当二进制每一位上 1 的个数 mod(k+1) 都为 0 时,不管什么取法,之后二进制每一位上 1 的个数 mod(k+1) 不会都为 0

当二进制每一位上 1 的个数 mod(k+1) 不都为 0 时,先将 mod(k+1)!=0 的最高位多出的 1 变为 0 ,使这一位的数目 \equiv0 \pmod{(k+1)} 。然后下面的位数如果 !=0 \pmod{(k+1)} ,视情况使得这一位一定数量的 01 ,或 10 。最后总能使得所有位的 1 的数目 \equiv0 \pmod{(k+1)}

SG衍生游戏:

以下都是SG游戏的派生,大家可以看看SG游戏可以有什么外包装。

翻硬币游戏:

有不同的规则翻硬币,全部翻到反面就游戏结束。只要规定翻硬币时,最右边的翻硬币方法一定从正面到反面,那么这个游戏就可以化简为SG游戏,SG值为每个正面朝上的硬币单独存在时的SG值的异或和。

树的删边游戏:

N 个点的树和根结点,轮流删边,删边后不与根节点相连的部分消失,无边可删者输。可以得出叶子结点SG值为 0 ,中间结点SG值为所有子节点SG值 +1 后的异或和。

例题分析:

由于光看博弈论的相关理论可能也很难对实际的题目进行解答,所以接下来将会有对题目进行解答时的分析。

博弈论的试题分析一般是将题目的关键部分提炼出来,找到和模板相符的地方,从而找到规律,或者利用SG值进行打表。


那先看第一道题目:

2020 CCPC网络赛 Lunch

n 堆石子,每次可以选择一个数目 l>1 的堆,将其分割为 k>1 个数目为 l/k 的堆。无法行动时当前玩家输。给出 n 堆石子各自的数目,问是否先手必胜。

看到将石子堆进行分割,首先想到Muti-SG游戏。将数目为 l 的石子分成 kl/k 堆,且只有这么一种操作。那么对于这个石子堆,其一种后继状态的SG值就是 kl/k 堆的SG值的异或和了。由于每个子堆的值都是相同的,所以有偶数个子堆时,异或和一定为 0 ,有奇数个子堆时,异或和就是其中一个子堆的SG值。
所以在考虑一个石子堆的后继状态时只需要考虑这个后继状态分割的堆数是奇数还是偶数,如果是奇数,那就只用考虑其中一个子堆就行了,不用全部考虑。(因为这个后继状态的SG值就是一个子堆的SG值)如果是偶数,由于这个后继状态的SG值是零,这个后继状态就可以看作是将这堆石子全部移除的情况了。

所以原题意就等价为:有 n 堆石子,每次可以选择一个数目 l>1 的堆,将其变为数目为 l/k 的堆, k>1k 为奇数,或者将整堆石子移走。无法行动时当前玩家输。给出 n 堆石子各自的数目,问是否先手必胜。

这样就变成了典型的组合SG游戏。这时我们考虑一堆石子的数目和SG值的关系。由题意得数目为 01 时SG值为 0 ;数目的因数没有奇数时,就只有数目归为 0 的操作,SG值为 1 。数目的因数包含奇数时,可以发现,当数目最多分解出一个奇质因数时,后继状态有数目变为全偶数因子(如果存在偶数因子)或数目变为 1 。那么可以推出这时的SG值为 1 (不存在偶数因子)或 2 (存在偶数因子)。继续推,发现如果石子的数目最多分解出 n 个奇质因数,那么SG值为 n (不存在偶数因子)或 n+1 (存在偶数因子)。

所以得出一堆石子的SG值为石子数目所含的奇质因数数目,且如果存在因数 2 ,那么SG值再加 1

再根据组合SG游戏的定理,先手必胜当且仅当各个石子堆SG值的异或和不等于 0 ,从而得出答案。


再看第二道题目:

2020 ccpc绵阳站 G-Game of Cards

两个人玩游戏,现在有四种卡牌分别标号 0,1,2 ,3 。双方轮流游戏,每次选择两个标号和小于等于 3 的卡牌合并,把它们变成一张对应他们的和的标号的卡牌。最后无法进行合并操作的人输掉了游戏。给出各种卡牌的数目,问是否先手必胜。

先分析游戏的终结态,有“ *3*2 ”或者“ *3 加一个 1 ”或者“ *0 ”。

让我们对几种卡牌进行分别进行讨论:

先看 33 只能和 0 合并,合并后为 3 。所以我们不如将这个操作看成 3 不变,就 0 消失了。所以 3 只是提供消 0 的一种方法, 3 本身是不变的,所以我们可以将 3 忽略掉,或者说,在排除特殊情况后,由于 3 不起到任何作用,我们就认为 3 这种卡牌是不存在的了。

再看 0 。只要有其他卡牌, 0 都能于其合并,且合并后的数为被合并的数。所以和 0 有关的操作不妨看成将 0 消掉。那么对 0 的相关操作就是每次消去一个 0

最后只剩下 12 了,那 12 之间的互动就只有 11 合并、 12 合并。分别导致的结果是消去两个 1 、增加一个 2 和消去一个 1 、消去一个 2 .(别忘了上文为了简化游戏,我们认为 3 就是不存在了)发现对于 1 的数量,我们可以有减少 1 个和减少 2 个这两种选择。再看游戏的终结态要多少个 1 ,发现除了“ *3 加一个 1 ”这种情况,其他所需 1 的数目为 0 ,且“ *3 加一个 1 ”这种情况如果有前继状态的话(现在考虑 12 ,所以暂且不考虑 0 ),一定是“ *3 加两个 1 加一个 2 ”,而这个状态的后继状态也可以选择“ *3 加两个 2 ”这个终结态。所以对于 1 来说,终结态需要 1 的数目为 0

那么对于 1 的数目的操作就可以看成巴什博弈了。且如果采取巴什博弈来达成必胜策略,一次 1 的数目 -2 ,一次 1 的数目 -1 ,那对于 2 的数目分别是一次 +1 ,一次 -1 。所以对 2 的数目没有要求,可以忽略 2 了。

这样题意就粗略化简为两堆石子A和B,每次操作可以选择将A的数目 -1 或者将B的数目 -1-2

这就变成了组合SG游戏。容易得出 0 卡片数目为奇数时SG值为 1 ,偶数时为 01 卡片数目 mod 3=0,1,2 时的SG值分别为 0,1,2 。所以先手必胜当且仅当 01 卡片SG值异或和不等于 0 。所以对应SG值组合对应的先手胜负情况是:

0^0=0 负

0^1=1 胜

0^2=2 胜

1^0=1 胜

1^1=0 负

1^2=3 胜

但是,对于 1 卡片的数目,是不能任意减少的,如当没有 2 卡时, 1 卡不能-1。如果要先手必胜,要考虑是否能按照组合SG游戏的必胜策略来行动,即:异或和为 0 ->异或和不为 0 ->异或和为 0 ->异或和不为 0 ->…。

这样考虑后发现有些情况需要考虑特殊情况

0^1 ,当 2 的数目小于 1 时先手必败

1^1 ,当 2 的数目小于 1 时先手必胜

1^2 ,当 2 的数目小于 2 时先手必败

然后再考虑全为 0 或全为 2、3 之类的特殊情况,就能求出正解。


最后还有一些练习题希望大家能做一下,大概一周后给出简要题解。

练习题:
NC15826(牛客网)
POJ2311
CEOI2008 Knights
CF305E
Luogu3235(洛谷)

5赞
粤 ICP 备 2020080455 号