尼姆博弈游戏

《十天后回到现实》：黑色大楼

很爱看一些有脑力游戏设计的大逃杀作品，最近的一个新综艺《十天后回到现实》，其中有一个关卡“【脑力7】黑色大楼”很有意思，本质上是改编小时候玩过的“谁先数到20”的游戏，这个游戏的来源是“尼姆博弈游戏”，来分析一下。

游戏描述

大楼从7层开始到14层，每层分别有8、7、6、……、1个房间亮灯，共36盏灯。闯关者和关主轮流关灯，每次只能关一层的灯，最少1盏，最多全部。游戏获胜条件是：关掉14楼的最后1盏灯获胜（通往14楼的楼梯在其余楼层灯关闭完成之前不开放）。本质上这是一个尼姆博弈游戏。

尼姆博弈游戏

2名玩家轮流从数堆物品中拿取一定数量的物品，每次拿取时先选择某一堆，再从中拿取任意数量个物品，至少拿1个，至多将这一堆物品全部拿走，不能不拿。拿到最后一个物品的玩家获胜。

尼姆博弈游戏存在必胜策略

游戏有以下特点：

• 物品总量严格减小，博弈是有限的
• 拿取信息对双方公开，双方具有完全信息
• 不含任何运气成分

根据策梅洛定理，游戏存在必胜策略。

策梅洛定理：在二人的有限游戏中，如果双方皆拥有完全的资讯，并且运气因素并不牵涉在游戏中，那先行或后行者当中必有一方有必胜/必不败的策略。

存在必胜策略的严格证明

定义：

1. 假设有k个物品堆，每个堆中分别有\(n_1\)、\(n_2\)、……、\(n_k\)个物品，我们将这种局面用一个向量表示：\(<n_1,…,n_k>\)，向量位置顺序无关，比如\(<1, 2> = <2, 1>\)。

2. 如果先手方获胜，则总抓取次数为奇数，我们称这种局面为“奇状态”；如果后手方获胜，则总抓取次数为偶数，我们称这种局面为”偶状态“

3. 设状态\(P_1=<n_1,…,n_k>\)，\(P_2=<m_1,…,m_k>\)，二者元素按从小到大排列，物品堆数较少的补充0。如果对任意的\(i\in[1, k]\)，都有\({n_i}\leq{m_i}\)，且至少有一个不取等号，则称\(P_1\)为\(P_2\)的子状态，即\({P_1}\leq{P_2}\)。如果\(P_1\)和\(P_2\)中只有一个不同的元素，则称\(P_1\)和\(P_2\)为相邻子状态。

定理：对于任意给定的一种状态，必为“奇状态”或”偶状态“其中之一。

证明：

1. 由于游戏规则限制最后抓取者获胜，必然不存在双方同时获胜的状态。

2. 假设存在双方都无法获胜的状态\(P\)，处于非奇非偶状态：

• 一个状态是奇状态等价于相邻子状态是偶状态。所以，一个状态不是奇状态等价于相邻子状态不是偶状态。
• 一个状态是偶状态等价于相邻子状态是奇状态。所以，一个状态不是偶状态等价于相邻子状态不是奇状态。
• P是非奇非偶状态，相邻子状态必然是非奇非偶状态。但最终局面必然是奇状态或偶状态其中之一，因此P存在无穷个子状态。由于物品总量严格减小，P只能是有限个子状态，矛盾。故不存在非奇非偶状态，即不存在“双方都无法获胜的局面”。

寻找必胜策略

两堆物品的跟随策略

假设只有两堆物品，\(<1, 1>\)显然是偶状态，先手只能拿1，后手拿1就获胜了，后手必胜。推广到任意数量，\(<n, n>\)一定是偶状态，\(<n, m>, m \neq n\)一定是奇状态。也就是说，只需要跟随对方拿取，将局面控制在“两堆物品数量相等”的状态，则一定可以拿到最后一堆获胜。

任意堆物品和二进制

我们想寻求的局面是：拿取完成后，使得局面变为偶状态，自己作为后手方获胜。

当有三堆或多堆时，不能像两堆那样跟随策略地拿取。我们换个思路，“拿取物品”的操作，本质上就是在做减法，如果将物品数量转换为二进制，减法的操作实际上就是在改变二进制位的“0”、“1”值。由于规则限制“每次只能拿取1堆中的物品”，因此这种变化只能在1堆中的二进制位上产生。那么我们只要保证拿取完成后，对于所有堆相同位置的二进制位，“1”的个数是偶数，就能采用“二进制位上的跟随策略”，来进行跟随获胜。

我们以3堆\(<7, 1, 3>\)为例，我们看作二进制\(<111, 001, 011>\) ，把它横向地看就是：

二进制第2位：1 0 0 = 1个1
二进制第1位：1 0 1 = 2个1
二进制第0位：1 1 1 = 3个1
           -----
           7 1 3

只要我们能保证把奇数个“1”拿走，就能将局面控制在“偶状态”，通过跟随，让自己后手获胜。为了快速判断每一位上对应“1”的个数，可以将全部的数进行“异或”，如果异或结果为0，就是偶数个“1”处于奇状态，否则就是奇数个“1”处于偶状态：

1 0 0 = 1 xor 0 xor 0 = 1
1 0 1 = 1 xor 0 xor 1 = 0
1 1 1 = 1 xor 1 xor 1 = 1
-----                 ---
7 1 3                   5

同时，通过异或的结果，我们可以判断奇数个的”1“所在的二进制的位置，比如“5=101(2)”，说明“1”在第2个和第0个二进制位上。为了将其消除掉，我们可以拿取任意堆上的“1”让其变为偶数个，并且拿“1”的过程可以在1个堆上完成，只要这个二进制位上存在“1”，比如：

// 拿取7上的1
0 0 0 
1 0 1 
0 1 1 
----- 
2 1 3 

这时会有个疑惑，我们一定能在某个堆上找到全部的“1”吗？比如换成如下的局面：

1 0 0 = 1个1 = 1
1 0 1 = 2个1 = 0
0 1 0 = 3个1 = 1
-----        ---
6 1 2          5

一个“1”出现在第1堆，另外一个“1”出现在第“2”堆。我们知道，当做减法的时候，最高位的“0”是不能变为“1”的，只有最高位的“1”是可以变为“0”的，因此我们要找的就是“最高位是1”的堆，对于这个局面，只有“6=110(2)”满足条件。对于剩下的二进制位，对应0、1二进制位的全排列，必然能从中找到一个满足条件的数字使得“1”的个数为偶数的位不变，“1”的个数为奇数的数字变反。以6为例：

1 0 0 = 1个1 = 1
1 0 1 = 2个1 = 0
0 1 0 = 3个1 = 1
-----        ---
6 1 2          5

// “6”去掉高位“1”后，只能取0、1、2、3
// 对于第1位和第0位，显然是“0”、“1”的全排列：
0 0 0 0 
0 0 1 1
0 1 0 1 
-------
0 1 2 3

// 那么总能找到一个数满足需求，比如3：
0 0 0 = 0个1 = 0
1 0 1 = 2个1 = 0
1 1 0 = 2个1 = 0
-----        ---
3 1 2          0

从异或的角度来看，需要让异或值变为0，并且拿取完成后的剩余物品数不能是负数。假设异或值为\(S\)，要找的堆的物品数量为\(n_i\)。剩余物品数量目标是：

• 如果\(S\)位置上是“1”，则\(n_i\)对应位置变反
• 如果\(S\)位置上是“0”，则\(n_i\)对应位置不变

这又是一个异或运算，剩余物品数量就是\({S}\oplus{n_i}\)，并且\({S}\oplus{n_i}<{n_i}\)，要拿走的物品数量就是\(n_i-({S}\oplus{n_i})>0\)

尼姆和必胜策略

假设有k个物品堆，每个堆中分别有\(n_1\)、\(n_2\)、……、\(n_k\)个物品，那么物品堆的尼姆和为物品数量的异或：

$$ NimSum = {n_1}\oplus{n_2}\oplus...\oplus{n_k} $$

若物品堆的尼姆和为0，则后手方有必胜策略，否则先手方有必胜策略。因此，拿取物品的算法是：

1. 计算尼姆和\(NimSum=S\)
2. 如果\(S\neq0\)，则计算\(S\)与每一个物品堆数量\(n_i\)的异或值\({S}\oplus{n_i}\)，直到找到一个\({S}\oplus{n_i}<{n_i}\)的物品堆，拿取\(n_i-({S}\oplus{n_i})\)个物品，让尼姆和归0
3. 如果\(S=0\)，随机拿取，等待对方犯错

黑色大楼尼姆和案例1

以黑色大楼谜题为例，有k=8个物品堆，\(n_1\)=1、\(n_2\)=2、……、\(n_8\)=8，此时尼姆和为：

$$ NimSum = {1}\oplus{2}\oplus...\oplus{8} = 8 $$

因此，先手方有必胜策略。计算异或值：

$$ NimSum \oplus n_1 = 8 \oplus 1 = 9 > 1 \\ NimSum \oplus n_2 = 8 \oplus 2 = 10 > 2 \\ NimSum \oplus n_3 = 8 \oplus 3 = 11 > 3 \\ NimSum \oplus n_4 = 8 \oplus 4 = 12 > 4 \\ NimSum \oplus n_5 = 8 \oplus 5 = 13 > 5 \\ NimSum \oplus n_6 = 8 \oplus 6 = 14 > 6 \\ NimSum \oplus n_7 = 8 \oplus 7 = 15 > 7 \\ NimSum \oplus n_8 = 8 \oplus 8 = 0 < 8 \\ $$

只需要从第8堆中拿取\(n_i-({NimSum}\oplus{n_i})=8-8\oplus8=8\)个物品，对应到游戏场景就是关闭第7层的全部8盏灯就能获胜。此时：

$$ NimSum = {1}\oplus{2}\oplus...\oplus{7} = 0 $$

黑色大楼尼姆和案例2

我们假设开始拿取的人不懂这个原理，随机从第6堆拿了3个物品破坏局面，此时：

$$ NimSum = {1}\oplus{2}\oplus{3}\oplus{4}\oplus{5}\oplus{3}\oplus{7}\oplus{8} = 13 $$

那么计算异或值：

$$ NimSum \oplus n_1 = 13 \oplus 1 = 12 > 1 \\ NimSum \oplus n_2 = 13 \oplus 2 = 15 > 2 \\ NimSum \oplus n_3 = 13 \oplus 3 = 14 > 3 \\ NimSum \oplus n_4 = 13 \oplus 4 = 9 > 4 \\ NimSum \oplus n_5 = 13 \oplus 5 = 8 > 5 \\ NimSum \oplus n_6 = 13 \oplus 3 = 14 > 3 \\ NimSum \oplus n_7 = 13 \oplus 7 = 10 > 7 \\ NimSum \oplus n_8 = 13 \oplus 8 = 5 < 8 \\ $$

需要从第8堆中拿取\({n_i}-({NimSum}\oplus{n_i})=8-13\oplus8=3\)个物品，对应到游戏场景就是关闭第7层的3盏灯就能获胜。此时：

$$ NimSum = {1}\oplus{2}\oplus{3}\oplus{4}\oplus{5}\oplus{3}\oplus{7}\oplus{5} = 0 $$

谁先数到20：LeetCode 292 Nim游戏

题目描述

https://leetcode.cn/problems/nim-game/description/

你和你的朋友，两个人一起玩 Nim 游戏：

• 桌子上有一堆石头。
• 你们轮流进行自己的回合， 你作为先手 。
• 每一回合，轮到的人拿掉 1 - 3 块石头。
• 拿掉最后一块石头的人就是获胜者。

假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false。

解决思路

虽然只有1堆石头，但由于每次拿取数量的限制，营造了奇偶状态：

• 奇状态是剩余1、2、3块石头，抓取次数为奇数次，先手使用跟随策略，拿走全部石头，将其转变为偶状态；
• 偶状态是剩余4块石头，抓取次数为偶数次

作为先手，如果当前局面为奇状态，赢；如果当前局面为偶状态，输。因此，只需要判定n是否是4的倍数：

class Solution {
    public boolean canWinNim(int n) {
        return n % 4 != 0;
    }
}