ReMind

Recent Writing

See 247 more →

博弈论

7 min read

NIM游戏

我的回合！

概念

先手必胜状态 我的回合下，我可以走到让局面进入必败状态 先手必败状态 我的回合下，走不到任何一个必败状态

[!原型题] 两个人，聪明绝顶，每次操作都是最优的操作 对多堆石子操作，任取其中一堆的任意数量，判断先手是否必胜

石子数量 a 满足 先手必败 否则先手必胜

证明： 假设上述式子等于x x的二进制最高位为第k位，则一定存在某个a，a的第k位为1（只有至少一个k位为1才有可能x最高位是k）

在这种情况下，异或的结果a1一直到an为x，x异或x为0，必败

若为0 则拿走任意数量石子后，假设还是0 拿走前后做异或，结果还得是0，而每个数都成对，则异或后每对相消，除了有更改的那一堆石子消不去，则结果不为0

得证 ——证明中用了递归定义，可能不够严谨

int ans = 0; //0开始才可以计算全部异或结果
    int x;
    for(int i = 0; i < n; i ++)
    {
        cin >> x;
        ans ^= x;
    }

SG函数

定义SG函数是 其中，y是从当前状态能走到的状态，x是当前状态，mex函数是集合中不存在的最小非负整数，同时定义终点为

发现，当SG(X) = 0 时，意味着x能走到的状态里没有一个状态是0，而SG(x) != 0时，则一定有一个状态SG(y)为0，而终点SG为0 则SG(x) = 0，先手必败，因为只能走到一个SG(x) != 0 的状态，后手必可以走到一个SG(x) = 0的状态，反复循环，则走到终点的必定是后手，先手败，反之则先手胜

多堆同时操作 多个SG图，可以用Nim游戏的证明逻辑证明

必败，否则必胜 因为可以找到一个，则必可以走到，使得最后异或结果为0 结果为0时，可以反证 任意操作之后还是0不成立

#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <cstring>
 
using namespace std;
 
const int N = 110, M = 100010;
 
int s[N], f[M];
int n, k;
 
//记忆化搜索
int sg(int x)
{
    if(f[x] != -1)  return f[x];  // 找过不再找,语句避免对同样数量的石堆多次查找，memset
    
    unordered_set<int> S;  // 起点下一步的状态集合
    
    for(int i = 0; i < k; i ++)
    {
        if(x >= s[i])  S.insert(sg(x - s[i])); 
    }
    
    for(int i = 0; ; i ++) //找非负最小数
    {
        if(!S.count(i))  return f[x] = i;  //状态里没有，则说明找到最小的数了
    }
}

台阶Nim游戏

基本概念与Nim游戏一样

[!题意] 从任意台阶取任意石子放在下一级上，如果没得操作就输

证明：先手时奇数台阶异或为0，则先手必败，否则必胜

  1. 全是0时为败，此时奇数异或为0
  2. 若先手不为0（奇数），则按照Nim游戏，可以将0的局面创造给对手
  3. 后手操作奇数，先手可以操作奇数台阶，找到一种方案将奇数台阶的异或值变为0，一直把0的局面给对手
  4. 后手操作偶数，先手操作其操作的石子再下放到另一个偶数台阶或地面，奇数异或值还是0
  5. 由于总是对手遇到异或为0的局面，意味着后手一定输

为什么看奇数？ 因为偶数台阶放到地面总是需要偶数次移动，这样需要偶数次参与，而奇数全是0的局面是留给后手的，那么意味着后手总是没有办法参与到把石头放在地上这一步，则其必输

因此做题只需要判断奇数台阶的情况就可以了

int main()
{
    int n;
    cin >> n;
    
    
    int res = 0;
    // 注意这里是代表台阶，要从1开始
    for(int i = 1; i <= n; i ++)
    {
        int x;
        cin >> x;
        if(i % 2)   res ^= x;  //奇数台阶就异或
    }
    
    if(res)  puts("Yes");
    else puts("No");
    
    return 0;
}

参考AcWing 892. 台阶-Nim游戏 - AcWing

拆分Nim游戏

SG函数的应用

[!题意] 有多堆石子，每次可以拆其中一堆石子为两堆，拆出来的总数可以大于原来的石子数，也可以少于，但是拆出来的单独一堆不可以大于等于原来的石堆

依旧是定义终点SG为0 由 要计算开局的SG异或值就可以断定每次的输赢

有性质 ——SG定理 然后应用记忆化搜索来计算SG的值

int sg(int x)
{
    if(f[x] != -1) return f[x];  //找过不找
    
    unordered_set<int> S;
    
    for(int i = 0; i < x; i ++)
        for(int j = 0; j <= i; j ++)  //避免重复（i,j)(j,i)
            S.insert(sg(i) ^ sg(j));  //当前状态的下个状态
    
    for(int i = 0; ; i ++)
    {
        if(!S.count(i)) return f[x] = i;
    }
}

Graph View

Backlinks