nim遊戲的必勝策略（博弈論）

tags:

• codeforces
• acm
• ACM

假设有n堆石子，每堆石子的个数分别如下

a1, a2, a3, … an

定义nim-sum为a1^a2^a3…an

可以证明

1. 若a1^a2^a3…an != 0

则经过一次合法的移动之后必定可变成

a1^a2….an = 0

此时留下的局面为必胜。

2. 若a1^a2^a3…an = 0

则经过一次合法的移动，局面必定成为

a1^a2^a3…an != 0

3. 只要在某回合中留下a1,a2…an

使a1^a2^a3…an = 0，此时局面必胜

证明1：假设a1^a2^a3…an != 0 = k

则查看k的最高位，假设是在第x位上，则此位上有a1x^a2x^a3x….anx = 1 (a1x表示a1写成二进制，取a1的第x位)

必然可以寻找到一个ai（至少一个），其aix = 1

此时有ai^k < ai

改变ai这堆石子使其成为ai^k

列出式子

a1^a2^a3..^ai^…an = k

则有

a1^a2^a3..^(ai^k)^…an = a1^a2^a3..^ai^…an^k = (a1^a2^a3..^ai^…an)^k = k^k = 0 即得证

证明2：使用反证法，

假设移动了ai堆石头使其成为ai'

有a1^a2^a3..ai..an = 0

即(a1^a2…a(i-1)^a(i+1)…an)^ai = 0 可得

等式 a1^a2…a(i-1)^a(i+1)…an = ai

假设a1^a2^a3…ai’….an = 0

根据前面得出的等式a1^a2…a(i-1)^a(i+1)…an = ai

即得 ai^ai’ = 0

可推出ai = ai'

此等式必然不成立，原式得证

证明3：假设游戏开始，P1 P2两名玩家，初始nim-sum != 0，使用必胜策略，P1始终能得到nim-sum != 0 的局面，而游戏过程石头始终在减少，查看最终局面：只有一行，此行可能有若干个石头，而游戏进行到最后必然会得出这个局面，这个局面是一个nim-sum != 0的局面，P1肯定能够得到这个局面，所以游戏必胜。