NIM游戏策略

NIM取子游戏是由两个人面对若干堆硬币（或石子，或。。）进行的游戏，游戏由两个人进行，设有k>=1堆硬币，各堆含有n1，n2，n3,n4.....,nk个硬币，游戏的目的就是选取最后剩下的硬币。游戏规则如下：

1）游戏人交替进行游戏；

2）当轮到每个游戏人取子时，选择这些硬币中的一堆，并从所选的堆中取走至少一枚硬币（可以将所选堆中所有硬币全部取走剩下一个空堆）。

当所有堆变成空堆时，游戏结束。最后取子的人（即能够取走最后一堆中的所有硬币的人）获胜。

这个问题中的变量是堆数k和各堆的硬币数n1，n2，n3，。。，nk，确定游戏人1还是游戏人2获胜以及游戏人应该如何取子才能获胜。

将每个堆的硬币数ni表示成基为2的数：

n1=as。。a1a0

n2=bs....b1b0

.......

nk=rs...r1r0

我们通过在前面补0的办法可以假设，所有各堆的大小都是具有相同位数的一2为基的数。我们称游戏是平衡的当且仅当

as+bs+...+rs是偶数

.......

ai+bi+...+ri是偶数

.......

a1+b1+...+r1是偶数

a0+b0+...+r0是偶数

如果游戏不是平衡的，那么就称游戏是非平衡的。如果ai+bi+...+ri是偶数，那么就称第i位是平衡的，否则就称为非平衡的。

结论是：

游戏人1能够在非平衡NIM取子游戏中取得胜利，而游戏人2能够在平衡NIM取子游戏中取胜。

设NIM游戏是非平衡的。令最大的非平衡位位第j位。那么，游戏人1用这样一种方法取子，使得留给游戏人2的游戏是平衡的取子游戏。令j是是最大非平衡位，游戏人1选择第j位是1的一个堆，然后从所选的堆中取走一些硬币使得游戏成为平衡的游戏。此后，无论游戏人2如何取子，游戏均是不平衡的，游戏人1取硬币总是使得游戏是平衡的，那么游戏人1就可以取得胜利。如果游戏从平衡状态开始，游戏人1取走一些硬币后，使得游戏变为非平衡，游戏人2取硬币使游戏变得平衡，从而可以取得胜利。

下面举一个简单的例子

硬币个数	2^3=8	2^2=4	2^1=2	2^0=1
11	1	0	1	1
6	0	1	1	0
10	1	0	0	0
8	1	0	0	0

从表中可以看出，，简单的看就是第一列，第二列，第四列1的个数是奇数，游戏是非平衡的，最大非平衡位是2^3=8,因此取一个这个位是1的进行取硬币，这里取11个硬币的堆，取5个，使得游戏变为平衡的，如下

硬币个数	2^3=8	2^2=4	2^1=2	2^0=1
4	0	1	1	0
6	0	1	1	0
10	1	0	0	0
8	1	0	0	0

如此进行下去，游戏人最终会取得胜利。

巴特西

NIM游戏策略

最新文章

热门文章