Skip to content

October 21, 2009

11

拈游戏

作者: physixfan

所谓拈游戏的规则是这样的:(在看了沙发的评论之后我才知道其标准名字应该是Nim游戏...)

桌面上有三行硬币,每一行中分别有a1、a2、a3个硬币,其中a1、a2、a3是可以任意指定的正整数。两个人轮流拿走硬币,每一次只能从某一行中拿走任意多个硬币,谁拿走最后一枚硬币谁就赢了。

比如说a1=1,a2=2,a3=3的情况吧,这时如果轮到我拿了,我可以从第三行拿走2枚硬币,或者可以把第三行的三枚硬币全都拿走,等等;但是我不能同时从第一行和第三行里各拿走1枚硬币。这个简单的情况,可以枚举所有可能性得出结论:先拿的必输。

当a1、a2、a3是任意给定的,在什么情况下先拿的必输呢?必胜策略是怎样的呢?这是一个相当有意思的问题,答案可绝不是显而易见一目了然的。而当我当年看到这个策略长什么模样之后,完全的叹服了。今天我就先不写必胜策略了,大家可以先自己想想,如果下周或者什么时候有时间了再来写。前一阵子我为了熟悉C++自己写了一个拈游戏的人机对弈程序,大家可以点击下面的链接下载。其中包含了必胜策略,所以只要你一步走错就一定会输。

拈游戏.rar

其实拈游戏不仅仅局限于三行硬币,其实最初的问题是N行的,而且神奇的是其必胜策略对于任何N都是一样的。其实这个拈游戏是我上小学的时候奥数老师跟我玩的游戏,最近才发现这个经典的有意思的游戏还有好多人没有玩过,故写此文...

11 Comments Post a comment
  1. ljx
    Oct 21 2009

    Nim取子游戏,把每个堆写成2进制。

    Reply
    • Oct 21 2009

      回复的这么迅速...
      原来这个东西的标准名称叫Nim游戏啊...怪不得我搜索拈游戏搜不出来什么东西呢...

      Reply
  2. evalls
    Oct 22 2009

    组合游戏论么,是有一整套系统的理论的哦。
    像这个只要全部异或起来就好了......

    Reply
  3. FTS
    Oct 24 2009

    ……刚接触这个游戏的形式就是
    任意在纸上画出几行圆圈然后分别删去……
    记得总是输给数学课代表

    这东西跟博弈论有关吧?

    Reply
  4. gter
    Jun 8 2013

    3行的时候只有(1,2,3)才是后取者胜

    Reply
  5. Feb 26 2016

    原来这游戏名叫Nim

    Reply
  6. 小文
    May 1 2016

    把“每一次只能从某一行中拿走任意多个硬币,”改成“每一次只能从某一行中拿走 1到n 个硬币”后会有什么策略?我只想出来了n=2的情况

    Reply

Trackbacks & Pingbacks

  1. Nim游戏的必胜策略和Xor运算的神奇应用 | 宇宙的心弦
  2. Nim游戏的必胜策略和Xor运算的神奇应用 | 宇宙的心弦

Share your thoughts, post a comment.

(required)
(required)

Note: HTML is allowed. Your email address will never be published.

Subscribe to comments