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

很爱看一些有脑力游戏设计的大逃杀作品，最近的一个新综艺《十天后回到现实》，其中有一个关卡“【脑力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\le m_i$，且至少有一个不取等号，则称$P_1$为$P_2$的子状态，即$P_1\le 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\ne 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\ne 0$，则计算$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$$

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

$$\begin{gathered} 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 \end{gathered}$$

只需要从第8堆中拿取$n_i-(NimSum\oplus n_i)=8-8\oplus 8=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$$

那么计算异或值：

$$\begin{array}{r}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\end{array}$$

需要从第8堆中拿取$n_i-(NimSum\oplus n_i)=8-13\oplus 8=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;
    }
}