在我小时候以前做题的时候，遇到博弈题往往都是漫无目的地打表找法则，或者找一些非凡状况然而没有很好的分析方法。

其实博弈题是有比拟套路的解题办法的，那就是利用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原创，创作不易，如果对您有帮忙，欢送小伙伴们点赞、珍藏⭐、留言