nim遊戲的必勝策略(博弈論)

假设有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肯定能够得到这个局面,所以游戏必胜。