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