博弈论---Nim游戏（公平组合游戏，概念，证明异或为0就是必败态，示例)

游戏使用一堆物品，例如棋子、石头或者硬币，这些物品被分成几堆，每堆可以有任意数量的物品。Nim游戏的关键在于掌握取物品的策略，因为有正确的方法可以确保你获胜，无论对手怎么移动。这个策略涉及到让每一堆物品的数量保持在特定的模式，这样你就可以控制游戏的走向，迫使对手进入必败局面。NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。给定 n 堆石子，两位玩家轮流操作，每次操作可以

姜九笙561

3328人浏览 · 2024-02-29 14:59:19

姜九笙561 · 2024-02-29 14:59:19 发布

如何确定先手是否必胜或者必败（都采用最优策略）

证明：全部异或为0则是必败状态

综上：

例子

概念：

公平组合游戏ICG

    若一个游戏满足:
        1.由两名玩家交替行动;
        2.在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关;
        3.不能行动的玩家判负;
     则称该游戏为一个公平组合游戏。
    NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。

有向图游戏

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负，该游戏被称为有向图游戏。

任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

Nim游戏

NIm就是一种公平组合游戏。

Nim游戏是一个古老的数学游戏，通常由两名玩家轮流进行。游戏使用一堆物品，例如棋子、石头或者硬币，这些物品被分成几堆，每堆可以有任意数量的物品。玩家在每一回合可以选择一堆物品，并且从中取走任意数量的物品，但是至少要取走一个。最后取走最后一个物品的玩家获胜。

Nim游戏的关键在于掌握取物品的策略，因为有正确的方法可以确保你获胜，无论对手怎么移动。这个策略涉及到让每一堆物品的数量保持在特定的模式，这样你就可以控制游戏的走向，迫使对手进入必败局面。

Nim游戏可以有很多变种和扩展，包括多堆物品、多个玩家或者其他规则的变化。

先手）必胜状态

先手进行某一个操作，留给后手是一个必败状态时，对于先手来说是一个必胜状态。即先手可以走到某一个必败状态。

先手）必败状态

先手不管使用什么策略，都只留给后手必胜的状态。

如何确定先手是否必胜或者必败（都采用最优策略）

我们使用异或（XOR）运算来确定每一堆物品的数量。

如果所有堆物品的数量进行异或结果为0，则这是一个必败状态。
否则，是一个必胜状态。

证明：全部异或为0则是必败状态

分情况讨论：

1.当所有堆的物品数目都为 $0$ ， $0\oplus0\oplus0....\oplus0 = 0$

2.当前存在 $a_1\oplus a_2...\oplus a_ n = x \neq 0$

证明，一定可以通过某种方式（减少某些物品的数量）使得情况2的异或值变为 $0$ 。

假如 $x$ 的二进制表示中最高的一位 $1$ 在第 $k$ 位。

那么意味着 $a_1,\ a_2,\ ...a_n$ 中必然至少存在一个数 $a_i$ ， $a_i$ 的第 $k$ 位的值是 $1$ 。

那么 $a_i > a_i \oplus x$ ， $a_i - (a_i \oplus x )$ 是合法的。

现在将拿走 $a_i$ 中 $a_i - (a_i \oplus x )$ 数量的东西，则 $a_i-(a_i - (a_i \oplus x )) = a_i\oplus x$ 。

拿走之后所有堆的物品数目再进行异或： $a_1\oplus a_2...\oplus a_i\oplus x\oplus a_ n = x\oplus x = 0$

证明完成。

3.当前 $a_1\oplus a_2...\oplus a_ n = 0$

证明，不管证明去拿多少数目 $(\neq 0)$ ，剩下的所有数异或值都不是0。

反证：假设拿出 $a_i$ 中 $k(k \neq 0)$ 个数目，剩余 $a_i^`$ ，剩下所有数的异或值为 $0$ 。

则有 $a_1\oplus a_2...\oplus a_i^`\oplus a_ n = 0$ ①

原有 $a_1\oplus a_2...\oplus a_i\oplus a_ n = 0$ ②

再将 ① 和 ② 者进行异或运行，相同的数就被抵消掉，剩余 $a_i^` \oplus a_i = 0$

$a_i^` \oplus a_i = 0$ 说明 $a_i^` = a_i$ ，与假设矛盾。证明完成

综上：

当全是0的时候，那么先手必输。

如果当前先手中数目异或不为 $0$ ，那么可以取出某个数的值使得轮到后手时，手中数目异或值为 $0$ 。后手不管怎么拿，再次轮到先手时，异或值都不会为 $0$ 。保证了先手始终异或不为 $0$ 的状态，而后手始终为 $0$ 的状态，最后后手会首先遇到全 $0$ 状态，先手始终处于必胜态。

如果先手一开始异或值就为 $0$ ，那么后手可以始终保持最优策略使得先手异或为 $0$ ，先手处于必败态。

K-Nim游戏：每次只能取k个

例子

给定 n 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

输入格式

第一行包含整数 n。

第二行包含 n 个数字，其中第 i 个数字表示第 i 堆石子的数量。

输出格式

如果先手方必胜，则输出 Yes。

否则，输出 No。

数据范围

1≤n≤10^5,
1≤每堆石子数≤10^9

输入样例：
2
2 3
输出样例：
Yes

import java.io.*;

class Main{
    static int n;
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(in.readLine());
        String[] s = in.readLine().split(" ");

        int res = 0;
        for(int i=0;i<n;i++)
            res ^= Integer.parseInt(s[i]);

        if(res==0) System.out.println("No");
        else System.out.println("Yes");
    }
}

后续会更新更多版本的Nim游戏。