在我 小时候 以前做题的时候，遇到博弈题往往都是漫无目的地打表找法则，或者找一些非凡状况然而没有很好的分析方法。
其实博弈题是有比拟套路的解题办法的，那就是利用 SG 函数，第一节不会讲到 SG 函数的具体用法，咱们先来博弈入个门，学习一下最根本的博弈类型：Nim 游戏。
🎈 作者：Eriktse
🎈 简介：19 岁，211 计算机在读，现役 ACM 银牌选手🏆力争以通俗易懂的形式解说算法！❤️欢送关注我，一起交换 C ++/Python 算法。（优质好文继续更新中……）🚀
🎈 浏览原文取得更好浏览体验：https://www.eriktse.com/algorithm/1110.html
巴什博奕
在进入 Nim 游戏 之前，咱们先看一个简略的博弈：巴什博奕。
看这道例题：http://acm.hdu.edu.cn/showproblem.php?pid=1846
因为 HDUOJ 常常打不开，我这里复制一下题意：
1、本游戏是一个二人游戏;
2、有一堆石子一共有 n 个；
3、两人轮流进行;
4、每走一步能够取走 1…m 个石子；
5、最先取光石子的一方为胜；
如果游戏的单方应用的都是最优策略，请输入哪个人能赢。
假如此时的n = 10, m = 3，咱们来剖析一下这个场面。
咱们设一个布尔函数 f(x)，示意当n = x 时的输赢。
- f(0) = 0，因为无奈持续操作了，显然是 0，也就是说这是一个必败态。
- f(1) = 1，能够取走一个石子，使对手陷入必败态，所以这是一个必胜态。
- f(2) = 1，能够取走两个。
- f(3) = 1，能够取走三个。
- f(4) = 0，无论取走一个、两个或三个都必然使得对手进入必胜态，所以这是一个必败态。
- f(5) = 1
- f(6) = 1
- f(7) = 1
- f(8) = 0，无论取走一个、两个或三个都必然使得对手进入必胜态，所以这是一个必败态。
- f(9) = 1
- f(10) = 1
至此，咱们失去了答案，f(n) = f(10) = 1所以先手必胜，不难发现下面这个函数 f(x) 的法则，仅当 x % 4 == 0 时为0，其余状况都为1。
于是咱们只须要判断 n % (m + 1) 是否为 0 就能判断先手是否获胜。
这就是巴什博奕模型，是不是很简略，咱们简略打个表就找到了法则。
Nim 游戏
仍然看这道例题：https://www.luogu.com.cn/problem/P2197
咱们这么剖析：
败局肯定是全为 0 的状况，此时所有数字的异或和为 0（不晓得怎么写异或和的 latex，大家凑合着看）：
$$\oplus_{i=1}^{n}a_i = 0$$
那么想一下那些状态能够到这个败局呢？咱们反向的思考，往任意一个地位加上一个数字，就能够作为前一个状态，也就是一个必胜态（因为那个状态必然能够达到败局的状态）。
往任意一个地位加上一个数字之后就必然有：
$$\oplus_{i=1}^{n}a_i \ne 0$$
再想一下，从一个 异或和不为 0 的状态，是否肯定有方法转移到一个 异或和为 0 的状态。
不难发现是 肯定能够 的。
举个栗子：
咱们有 4 堆石子，数量别离为：1 7 2 6。这是我轻易写的一个数据。
它们的异或和为：1 ^ 7 ^ 2 ^ 6 = (0 1 0)，那么我能够通过调整 2 -> 0 使得异或和为 0，当初有1 ^ 7 ^ 0 ^ 6 = 0，当然我还能够通过6 -> 4，异或和后果也是 0。
不难发现，只须要从数组中找一个 最高非零位 大于等于 异或的后果的最高非零位 的数字，而后缩小一部分就能够，这样的数是肯定存在的。
那么也就是说任意一个 异或和非零的状态 都能够通过一步转移到 异或和为 0 的状态 ，任意一个 异或和为 0 的状态 不管怎么走一步，都必然转移到 异或和非 0 的状态。
而石子的个数是始终减小的，最终肯定会走到 全 0，异或和为 0 的状态 且肯定是败局。
也就是说：
必胜态 W(win)：异或和非 0;
必败态 L(lose)：异或和为 0;
以上就是 Nim 游戏 模型，当然你也能够叫他Nim 博弈。
这一节先理解这些，下一节将会解说 SG 函数的转移和子游戏的合并。
🎈 本文由 eriktse 原创，创作不易，如果对您有帮忙，欢送小伙伴们点赞👍、珍藏⭐、留言💬