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

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz