尼姆博弈

来源:互联网 发布:墨索里尼 黑手党 知乎 编辑:IT博客网 时间:2018/12/10 03:40
尼姆博奕

什么是尼姆博弈:

  • 尼姆博奕(Nimm Game):有三堆各若干个物品,两个人轮流从某一堆取任意多的物品,规定每次至少取一个,多者不限,最后取光者得胜。

尼姆博弈分析:

  • 我们用(a,b,c)表示某种局势,其中a,b,c分别表示当你选择时每一堆剩余的物品件数。
  • 无论谁面对某种局势时,都必败的话,我们称这种局势为奇异局势
  • 首先(0,0,0)显然是奇异局势。
  • 第二种奇异局势是(0,n,n)。因为在这种情况下无论你拿走多少件物品,对方都可以拿走和你一样多的物品,这样你必败。
  • 其次(1,2,3)也是奇异局势。因为无论你怎么拿,对手都可以将它变为(0,n,n)格式。

尼姆博弈方法:

  • 在计算机中有一种按位运算叫做异或运算。符号是
  • 有两个二进制数,如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0。
  • 对于奇异局势(a,b,c)有:a⊕b⊕c=0
  • 1 =二进制01 ,2 =二进制10,3 =二进制11 
  • 所以01⊕10⊕11=00
  • 所以(1,2,3)是奇异局势。
  • 对于非奇异局势(a,b,c)我们可以可以将c改为a⊕b即可。因为(a,b,a⊕b)是奇异局势。

尼姆博弈练习:

  • hdu oj 1849 Rabbit and Grass 
  • hdu oj 2176 取(m堆)石子游戏 
  • hdu oj 1907 john 

0 0