取石子游戏与初步博弈论

chengni · 2018-09-29 17:20:59 · 个人记录

取石子是一种很古老的游戏，它以玩法多样，简单易懂，道具容易获取等优势深受广大玩家喜爱。但这个看似简单的游戏，实际上蕴含着丰富的思想价值，也代表着一类问题——博弈论。

接下来结合几个小问题，简单的介绍一下博弈论

首先我们要明确两个概念

必胜点，当你操作时状态为必胜点，游戏一定会胜利

必败点，当你操作时状态为必败点，游戏一定会失败

必胜点能转移到某个必败点，使对方必败

必败点只能转移到必胜点，使对方必胜

问题0

有一堆石子共 n 个，两个人每次取一个石子，谁不能取谁就输了，求判断先手必胜还是后手必胜

不要打我 逃)

答案是 当 n 是奇数的时候先手必胜，反之先手必败

问题1

有一堆石子共 n 个，两个人每次可以取一个石子，也可以取两个石子，谁不能取谁就输了，求判断先手必胜还是后手必胜

答案是 当 n mod 3=0 时后手必胜，反之先手必胜。

当 n=0 时很明显先手必败，而 n=1 或者 n=2 时就是先手必胜了，因为我们可以直接拿走所有石子，让对方进入 n=0 的情况

然而当 n=3 的时候先手就是必败了，因为我们只能拿走一个或者两个石子，无论怎样都会让对方进入上面所说的必胜点，所以我们所处的就是必败点。

答案是 当 n mod (l+r)<l 时先手必败，否则先手必胜。

首先在 n 大于 (l+r) 的时候，无论对方怎么走，我们中有一种办法使双方各一次所取石子之和为 (l+r)

那么我们只需要考虑 n mod (l+r) 之后会发生什么

前面已经说过了，当 n<l 的时候是必败点，所以这种情况先手必败

当 l<=n<=r 的时候，我们可以一步拿走所有的石子，必胜

当 r<n<l+r 的时候，我们只要拿走 r 个石子，对手就只进入了 n<l 的情况，于是我们必胜

综上可以得出结论

问题1.3

有一堆石子共 n 个，两个人每次可以 a_1,a_2,...,a_k 个石子，谁不能取谁就输了，求判断先手必胜还是后手必胜

我们可以考虑 DP

用 f[i] 表示有 i 个石子时游戏的胜利情况，f[i]=1 为必胜，反之为必败。

很明显 f[0]=0

对于所有能一步到达必败点的点，那个点就是必胜点，因为我们可以将对手置入必败点

对于只能到达必胜点的点，那个点就是必败点，因为无论如何对手都会进入必胜点

我们可以按照这个规律进行 DP

对于 f[i] 如果满足 \forall_{j=1}^k f[i-a[j]]=0 ((i-a[j])>=0) f[i]=1

否则 f[i]=0

这就是一个复杂度为 n*k 的 DP 问题了

问题2

对于一个有向无环图，将一个石子放在某一个结点上，两个人轮流将石子移动一个结点，谁不能动谁就输了，询问谁会获胜

这个游戏大概是上面的变形

很明显，如果某一个点出度为 0 ，那么这个点就是先手必败的，因为无路可走了

那么对于一个点，如果它能够一步走到出度为 0 的点，那么它就是必胜点

于是就跟上面的问题差不多了，如果这个点可以一步走到必败点，这个点就是必胜点，否则就是必败点。

因为我们需要知道这个点能一步到达的所有点是必胜点还是必败点，所以需要按照拓扑序的倒序完成转移。

画个图看看？

大概就是这个意思吧。

注意，当图为有环时，不能这么做

问题3

有一堆石子共 n 个，第一个人每次可以取 a_1,a_2,...,a_k 个石子，第二个人每次可以取 b_1,b_2,...,b_k 个石子，谁不能取谁就输了，求判断先手必胜还是后手必胜

这道题与前面不同的是他不是对称的游戏模型，我们不能将两个人放在一起考虑

所以我们需要搞一个 f[1][i] 和 f[2][i] 分别表示第一个人和第二个人的情况

我们对于 f[1][i] 枚举 k 判断 f[2][i-a[k]]，对于 f[2][i] 枚举 k 判断 f[1][i-b[k]]

然后就跟上面差不多了

问题3.1

有一堆石子共 n 个，第一个人每次可以取 l_1 到 r_1 个石子，第二个人每次可以取 l_2 到 r_2 个石子，谁不能取谁就输了，求判断先手必胜还是后手必胜

这个游戏也是不对称的

做法仍然是用 f[1][i] 和 f[2][i] 分别表示两个人的情况

当 n 的范围比较大时，我们可以考虑使用前缀和优化转移

我们用 s[2][j] 记录第二个人在 (n<=j) 时有多少个必败点，就可以优化 f[1][i] 的转移，另一边同理

小结

根据上面的例题，我们似乎摸到了一点门路。

我们是不是跟据游戏规则直接 DP 就好了啊？

嗯 好像是的，但似乎还可以找规律不是吗

下面再结合一到例题更好的让大家理解这种问题如何 DP (找规律(瞎蒙))

问题4

有一堆石子共 n 个，两个人轮流拿石子，每次只能拿 1,2,4,8,...,2^k(2^k<=n) 个石子，谁不能拿谁就输了，问谁会赢

根据我们做前面题的经验，我们应该先搞一个 f[i] ，然后一顿转移，大概式子如下

    for(int i=1;i<=n;i++){
        for(int j=1;i-j>=0;j*=2){
            if(f[i-j]==0){
                f[i]=1;
                break;
            }
        }
    }

(贴代码是因为刚好打了)

如果 n 很大我们该怎么办呢？我们稍稍稍微打个数据看看，结果大概是这样？

也可以当做是不进位的加法

我们举个例子

对于 1,2,3 这三堆石子，先手无论怎么拿，后手都可以留下相同的两堆石子，先手必败

对于 1,2,4 这三堆石子，先手可以把第三堆拿成 3，于是先手必胜

那么为什么是这个结论呢？

首先结束位置很明显是异或和为 0。

其次我们一定会有一种合法的操作在异或和不为 0 的情况下使异或和为 0

然后我们不会有一种合法的操作在异或和为 0 的情况下仍然使异或和为 0

随着这个游戏的进程，只要使这堆石子的异或和为 0 ，就能赢得游戏

那既然我们说到了异或和，就一定要介绍 SG 函数了。

SG函数

定义 mex 运算表示最小的不属于这个集合的非负整数。

对于一个有向无环图，一个点的 sg 值为其所有后继节点中的 mex

如果一个点是必败点，那么它的 sg 值为 0。否则 sg 值大于 0

还记得前面的问题2吗，重新画一下图

如果这个点的 sg 函数为 0，那么说明它的后继节点均不为 0，于是必败。

如果这个点的 sg 函数不为 0，那么说明它的后继节点出现了 0，于是必胜。

让我们带着 SG函数 的眼光回头看一下前面的题

问题1

根据对问题的分析，我们可以得出 sg[0]=0,sg[i]=mex(sg[i-1],sg[i-2])

问题1.1

同理 sg[0]=0,sg[i]=mex(sg[i-1],sg[i-2],...,sg[i-k])

其余不再累述。

问题3

由于两个人的操作集合不同，即游戏不对称，所以不能用 sg 函数解决。关于解决不对称博弈的方法回头再讲。

问题5.1

如果有 n 个独立的游戏，每个人可以选其中一个游戏进行操作，先手必胜的条件是所有的游戏的 sg 值异或起来不为 0

那么为什么是这个结论呢？

首先结束位置很明显是异或和为 0。

其次我们一定会有一种合法的操作在异或和不为 0 的情况下使异或和为 0

然后我们不会有一种合法的操作在异或和为 0 的情况下仍然使异或和为 0

这句话是从前面粘贴过来的，自行理解吧

我们把每堆石子都看做是一个游戏，很明显每堆石子的 sg 值就等于它的石子个数，于是符合定理

下面再甩一道例题出来

问题5.2

一共有 n 堆石子，两个人轮流操作，一次可以选择从某一堆石子中拿出任意个石子，或者将某一堆石子分成两堆，谁不能操作谁就输了，问谁会赢

我们考虑每一堆石子的 sg 函数。

对于一堆的 sg[i] 他只能通过两种方式来转移，一种是拿走一部分 sg[i]=sg[j] 或者将一堆石子变成两堆石子 sg[i]=sg[j] ^ sg[i-j] 我们在这个集合里求 mex 就可以得出某一堆石子的 sg 值，然后把这几堆石子合到一起，就跟前面差不多了。

在面对多个游戏时，sg 函数能够比较方便的处理问题。

问题6

有 n 堆石子，两个人轮流操作，一次可以将第 i 堆石子的任意数量转移到第 i-1堆 (第一堆无法操作)，谁不能操作谁就输了，问谁会获胜

当 n=2 时，很显然先手必胜。

当 n=3 时，很显然先手必胜。

你等等，这怎么就显然了

我们和 n=2 一样，把第二堆的石子扔到第一堆，然后无论对方怎么操作第三堆，我们只把第二堆的石子扔到第一堆里，所以我们必胜。

似乎，第三堆没有什么用啊

事实上奇数堆都是这样的，只要石子进了奇数堆，那么就可以当做他已经进了第一堆。

所以我们只需要关注偶数堆就可以了，而这个问题就转换成了最基础的 Nim游戏，偶数堆石子的异或和不为 0 时先手必胜，否则后手必胜。

这种两两位置绑定在一起的情况，我们叫它为阶梯博弈。

到这里，取石子模型就基本告一段落了，最后挖一个小坑

问题.ex

有一堆石子共 n 个，由 m 个人轮流取，每个人有一个可以取的集合，谁不能取算谁输。每个人都有一个列表，表示这个人最想让谁输，问最后谁会输。

多人博弈是一个比较棘手的问题。在面对这种问题时可以尝试将其转化为双人博弈

仅给出提示，不做过多解析

用 f[i][j] 表示还剩下 i 个石头，第 j 个玩家在玩，这个状态下谁会输。然后选择最想让他输的那个玩家转移。