拈游戏
11 Comments
Post a comment
细推物理须行乐 何用浮名绊此身
所谓拈游戏的规则是这样的：（在看了沙发的评论之后我才知道其标准名字应该是Nim游戏…）
桌面上有三行硬币，每一行中分别有a1、a2、a3个硬币，其中a1、a2、a3是可以任意指定的正整数。两个人轮流拿走硬币，每一次只能从某一行中拿走任意多个硬币，谁拿走最后一枚硬币谁就赢了。
比如说a1=1,a2=2,a3=3的情况吧，这时如果轮到我拿了，我可以从第三行拿走2枚硬币，或者可以把第三行的三枚硬币全都拿走，等等；但是我不能同时从第一行和第三行里各拿走1枚硬币。这个简单的情况，可以枚举所有可能性得出结论：先拿的必输。
当a1、a2、a3是任意给定的，在什么情况下先拿的必输呢？必胜策略是怎样的呢？这是一个相当有意思的问题，答案可绝不是显而易见一目了然的。而当我当年看到这个策略长什么模样之后，完全的叹服了。今天我就先不写必胜策略了，大家可以先自己想想，如果下周或者什么时候有时间了再来写。前一阵子我为了熟悉C++自己写了一个拈游戏的人机对弈程序，大家可以点击下面的链接下载。其中包含了必胜策略，所以只要你一步走错就一定会输。
其实拈游戏不仅仅局限于三行硬币，其实最初的问题是N行的，而且神奇的是其必胜策略对于任何N都是一样的。其实这个拈游戏是我上小学的时候奥数老师跟我玩的游戏，最近才发现这个经典的有意思的游戏还有好多人没有玩过，故写此文…
physixfan
eaglefantasy
Eagle_Fantasy
宇宙的心弦
Traction Theme by The Theme Foundry
Copyright © 2024 physixfan. All rights reserved. 
宇宙的心弦 by physixfan is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Necessary cookies are absolutely essential for the website to function properly. This category only includes cookies that ensures basic functionalities and security features of the website. These cookies do not store any personal information.
Any cookies that may not be particularly necessary for the website to function and is used specifically to collect user personal data via analytics, ads, other embedded contents are termed as non-necessary cookies. It is mandatory to procure user consent prior to running these cookies on your website.
Nim取子游戏，把每个堆写成2进制。
回复的这么迅速…
原来这个东西的标准名称叫Nim游戏啊…怪不得我搜索拈游戏搜不出来什么东西呢…
组合游戏论么，是有一整套系统的理论的哦。
像这个只要全部异或起来就好了……
……刚接触这个游戏的形式就是
任意在纸上画出几行圆圈然后分别删去……
记得总是输给数学课代表
这东西跟博弈论有关吧？
看看我下一篇日志就知道了
3行的时候只有（1，2，3）才是后取者胜
原来这游戏名叫Nim
把“每一次只能从某一行中拿走任意多个硬币，”改成“每一次只能从某一行中拿走 1到n 个硬币”后会有什么策略？我只想出来了n=2的情况