Nim游戏的介绍
Nim游戏是博弈论中最经典的模型(之一),它又有着十分简单的规则和无比优美的结论 Nim游戏是组合游戏(Combinatorial Games)的一种,准确来说,属于“Impartial Combinatorial Games”(以下简称ICG).
Nim游戏的定义
通常的Nim游戏的定义是这样的：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。
这游戏看上去有点复杂，先从简单情况开始研究吧。如果轮到你的时候，只剩下一堆石子，那么此时的必胜策略肯定是把这堆石子全部拿完一颗也不给对手剩，然后对手就输了。如果剩下两堆不相等的石子，必胜策略是通过取多的一堆的石子将两堆石子变得相等，以后如果对手在某一堆里拿若干颗，你就可以在另一堆中拿同样多的颗数，直至胜利。如果你面对的是两堆相等的石子，那么此时你是没有任何必胜策略的，反而对手可以遵循上面的策略保证必胜。如果是三堆石子……好像已经很难分析了，看来我们必须要借助一些其它好用的（最好是程式化的）分析方法了，或者说，我们最好能够设计出一种在有必胜策略时就能找到必胜策略的算法。
定义P-position和N-position，其中P代表Previous，N代表Next。直观的说，上一次move的人有必胜策略的局面是P-position，也就是“后手可保证必胜”或者“先手必败”，现在轮到move的人有必胜策略的局面是N-position，也就是“先手可保证必胜”。更严谨的定义是：1.无法进行任何移动的局面（也就是terminal position）是P-position；2.可以移动到P-position的局面是N-position；3.所有移动都导致N-position的局面是P-position。
按照这个定义，如果局面不可能重现，或者说positions的集合可以进行拓扑排序，那么每个position或者是P-position或者是N-position，而且可以通过定义计算出来。
nim游戏与SG函数
如果轮到你的时候，只剩下一堆石子，那么此时的必胜策略肯定是把这堆石子全部拿完一颗也不给对手剩，然后对手就输了。如果剩下两堆不相等的石子，必胜策略是通过取多的一堆的石子将两堆石子变得相等，以后如果对手在某一堆里拿若干颗，你就可以在另一堆中拿同样多的颗数，直至胜利。如果你面对的是两堆相等的石子，那么此时你是没有任何必胜策略的，反而对手可以遵循上面的策略保证必胜。如果是三堆石子……好像已经很难分析了，看来我们必须要借助一些其它好用的（最好是程式化的）分析方法了，或者说，我们最好能够设计出一种在有必胜策略时就能找到必胜策略的算法。NIM游戏的获胜策略已由美国数学家C.L.Bouton 分析完成，用到的是二进制和平衡状态概念。其结论是：
（1）如果一开始火柴的总根数转化成二进制后各位数上的 数字和都是偶数时，则是平衡状态，后取者必胜。最 简单的平衡态是（1，1），即2 堆火柴，每堆各1 根。
（2）如果开始时火柴的状态处于不平衡状态，先取者必胜， 其策略是取完后使火柴根数保持为平衡状态。
求用C++编程的：强化学习算法应用于NIM游戏中。
#include
#include
int main()
{
srand(time(NULL))
int n = 10;
int input;
int computer;
int flag = 1;
int flag_cmputer = 0;
while(flag)
{
computer = (double)rand()/(1+MAX_RAND)*2+1;
printf(“Input one number \n”);
scanf(“%d”,&input);
n-= input;
if(n <= 3)
{
flag = 0;
break;
}
n-=computer;
if(n<=3)
{
flag = 0;
flag_computer = 1;
break;
}
}
if(!flag_computer)
{
printf(“computer’s win!”);
}
else
{
printf(“Yours win!!”);
}
}
java nim游戏 两个玩家轮流取石头 每次剩下的石头怎么算
public static void main(String[] args) { try { System.out.println(“石头:1,剪子:2,布：3,请输入1或2或3。输入0游戏结束”); char userInput; while((userInput=(char) System.in.read())!=’0′){ String result=””; if(userInput==’1′){ result=”布”; }else if(userInput==’2′){ result=”石头”; }else if(userInput==’3′){ result=”剪子”; } if(userInput!=’\r’userInput!=’\n’){ System.out.println(“你输了！电脑出的是:”+result+”，再来一次吧^_^”); } } } catch (IOException e) { e.printStackTrace(); } }
有趣味性的现实生活中的小游戏
尼姆游戏 击鼓传花
Nim游戏的证明
根据定义，证明一种判断position的性质的方法的正确性，只需证明三个命题： 1、这个判断将所有terminal position判为P-position；2、根据这个判断被判为N-position的局面一定可以移动到某个P-position；3、根据这个判断被判为P-position的局面无法移动到某个P-position。
第一个命题显然，terminal position只有一个，就是全0，异或仍然是0。
第二个命题，对于某个局面(a1,a2,…,an)，若a1^a2^…^an<>0，一定存在某个合法的移动，将ai改变成ai’后满足a1^a2^…^ai’^…^an=0。不妨设a1^a2^…^an=k，则一定存在某个ai，它的二进制表示在k的最高位上是1（否则k的最高位那个1是怎么得到的）。这时ai^k第三个命题，对于某个局面(a1,a2,…,an)，若a1^a2^…^an=0，一定不存在某个合法的移动，将ai改变成ai’后满足a1^a2^…^ai’^…^an=0。因为异或运算满足消去率，由a1^a2^…^an=a1^a2^…^ai’^…^an可以得到ai=ai’。所以将ai改变成ai’不是一个合法的移动。证毕。 根据这个定理，我们可以在O(n)的时间内判断一个Nim的局面的性质，且如果它是N-position，也可以在O(n)的时间内找到所有的必胜策略。Nim问题就这样基本上完美的解决了。
关于斐波那契数列
它的性质是:前面相邻两项之和,构成了后一项.如:1,1,2,3,5,8… 应用有: 例如有一种两个游戏,名叫“尼姆”.游戏方法是由两个人轮流取一堆粒数不限的砂子.先取的一方可以取任意粒,但不能把这堆砂子全部取走.后取的一方,取数也多少不拘,但最多不能超过对方所取砂子数的一倍.然后又轮到先取的一方来取,但也不能超过对方最后一次所取砂子的一倍.这样交替地进行下去,直到全部砂子被取光为止,谁能拿到最后一粒砂子,谁就算胜利者. 在这个游戏中,若所有砂子的粒数是个斐波那契数的话,那么后取的一方稳操胜券,而录所有的砂子不是一个斐波那契数的话,那么先取的一方稳胜.
如何用java写一个完整的Nim游戏程序?
如果是攻击电脑的话,客户端之间需要衔接的桥梁,才能Nim–
考虑堆的大小分别为10,20,30,40,50的5堆nim游戏.这局游戏是平衡的吗
A老师:30、36 B老师:32、38、62 剩余:40 解题过程:一共有六堆本子30.32.36.38.40.62他们之和是238,用238减去每一堆后的得数分别为208.206.202.200.198.176这六组数表示的分别是任意可能组成五堆本子的本子数.由于已知一个老师领的本子正好是另一个老师领的2倍,所以这些数应该被3整除,因此只有198可以整除3.所以这五堆数字应该是30.32.36.38.62,剩下的一堆是40,由于已知一个老师领的本子正好是另一个老师领的2倍,所以198/3=66=30+36,所以有结论, A老师:30、36 B老师:32、38、62 剩余:40 !
