文档介绍：游戏策略朱全民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局面。证明:=P2=….=Pn=0时,S=0,满足终状态是P局面。=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局面。<>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=2a1=7a2=3a3=51 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堆中选出若干石子去掉(但不能不去石子),两人轮流取石,谁不能继续取谁就输了。?什么情况下先手必胜,什么情况下后手必胜?