文档介绍：游戏策略
朱全民
Nim问题
取石子问题
有N堆石子,其中第i堆有Pi颗石子,每次从某一堆里选出若干石子去掉(但不能不去石子),两人轮流取石,谁不能继续取谁就输了。
什么情况下先手必胜,什么情况下后手必胜?
第一堆:a1=3
第二堆:a2=3
第三堆:a3=1
博弈树
分析
从上述博弈树可以看出3,3,1是必胜点,那么我们可以这么想,如果某个点是必胜点,则取完棋子后,必须使得对方落在必败点。
若只有一堆石子,先收走必胜
若有m堆石子,每堆只有一颗石子, m堆为奇数时,先手必胜。
若有m堆石子,每堆有k颗石子, m堆为奇数时,先手必胜。
第1次,先手取k棵,轮到对手走时,若对手取k棵,则先手也取k棵,若对手取x<k棵,则先手也取另外一堆的x棵,因为剩下的是偶数堆,总能将剩下的堆变成若干个两两相等的堆。只要始终保持这种取法,先手总能取到最后的石子。
一般情况?
假设某个初始局面为先手必胜,那么先手每走一步都必须使得对手落在必败节点。
因此,对于每一个局面,要么为胜局面,要么为负局面,如果我们将胜局面非0表示,那么负局面就可以用0表示。
因此,对于某一个局面,若为非0局面,它的任务就是要寻找某一种取法,使得局面变为0局面。那么他的对手无论怎么取,都会使得局面又变成0局面。
有什么规律呢?
结论
定理:
如果一个局面先手必胜,就称之为N局面,反之称之为P局面。对于一个局面,令S=P1 XOR P2 XOR P3 XOR … XOR Pn。若S=0则为P局面,否则为N局面。
证明:
当P1=P2=….=Pn=0时,S=0,满足终状态是P局面。
若S=0,即P1 XOR … XOR Pn=0,若取堆i中的石子,Pi>Pi’,S ->S’,Pi>Pi’,则Pi XOR Pi’<>0。所以S’ XOR Pi XOR Pi’=S=0,即S’=Pi XOR Pi’<>0。满足P局面的所有子局面都是N局面。
若S<>0,设S的二进制位是A1…An,考虑第一位是1的。在P中取出该位同是1的,不妨设为P1。可知P1 XOR S<P1,令P1’=P1 XOR S。可知P1’ XOR P2 XOR … XOR Pn=0。即N局面存在至少一个子局面是P局面。
示例
Nim问题的扩展
取石子问题
有N堆石子,其中第i堆有Pi颗石子,每次去掉某一堆里最多m棵石子(m>0),两人轮流取石,谁不能继续取谁就输了。
什么情况下先手必胜,什么情况下后手必胜?
示例m=2
a1=7
a2=3
a3=5
1 2 3 4 5 6 7
结论
将P1P2P3 … Pn 对m+1求余得到P1 ’ P2 ’ P3 ’… Pn ’,然后符合定理一的结果,记S=P1’ XOR P2 ’ XOR P3 ’ XOR … XOR Pn ’。若S=0则为P局面,否则为N局面。
证明:
将P1P2P3 … Pn分解成为两部分P1 ’ P2 ’ P3 ’… Pn ’和 R1R2R3 …Rn,其中R1R2R3 …Rn 都是m+1的倍数。
若对P1 ’ P2 ’ P3 ’… Pn ’部分取子,则按NIM方法走步,若对R1R2R3 …Rn部分取子,则后手取k颗,先手方取m-k+1颗,先手始终保持不对R1R2R3 …Rn部分先取子。
若初始局面为胜局面,P1 ’ P2 ’ P3 ’… Pn ’部分NIM方法取子必胜,由于R1R2R3 …Rn都为m+1的倍数,因此,按m+1互补的取法,先手一定能取到最后K<=m颗石子。
Nimk问题
取石子问题
有N堆石子,其中第i堆有Pi颗石子,每次可以从最多K堆中选出若干石子去掉(但不能不去石子),两人轮流取石,谁不能继续取谁就输了。
什么情况下先手必胜,什么情况下后手必胜?