Nim Game 问题 。求教数学高手。【博弈论吧】_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0可签7级以上的吧50个
本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：49,389贴子：
Nim Game 问题 。求教数学高手。
上面是NIM GAME 的说明，感觉不难，但是有个问题。考虑三行硬币的NIM Game,第一行一枚硬币，第二行两枚硬币，第三行有一、二或三枚硬币。（1）第三行的硬币数量对游戏结果有影响吗？（请高手小小解释一下！） （2）在第三行硬币数量的每种可能情况下，谁将获胜？（请给出分析，谢谢！）
好像找到类似的游戏了
我看能不能复制上来~
超好玩硬币游戏，你都会玩吗？方弦发表于 18:55:04死理性派表示，硬币是世界上最好的游戏机，给我们几枚硬币，就能玩到天亮。不不不，硬币可不止抛正反面这么简单。好玩的硬币游戏，你们都会玩吗？出门在外，恰逢不巧，你和朋友被困住了，干点什么呢。来几局三国杀？是个不错的提议，但问题是你带牌了吗，没牌怎么打？死理性派想说的是，会玩的孩子怎么不能玩！凑几个硬币，随随便便就能玩一整天。不得不说，硬币是世界上最好的游戏机，哦，前提是你得懂点数学。尼姆游戏在所有二人游戏中，最古老最有魅力的就是这个尼姆游戏了（好吧，在所有二人数学游戏中）。据说它发源于中国，有时候孩子们用纸片玩，但通常人们出门可能很少带纸片，所以我们用硬币玩。这个游戏最流行的版本是用 12 枚硬币摆成三行。游戏规则很简单，游戏双方轮流取 1 枚或多枚硬币（只能在同一行），谁拿到最后一枚就算赢。留心的朋友玩几把就可以琢磨出，只要在自己的某一个回合里留下两行多于 1 枚且数量相同的硬币，就能确保获胜。一个优势策略是，先手的人一开始就拿掉最上面一行 2 枚硬币，这样的话，离胜利就不远了。有趣的是，有人发现，当扩展到任意多行，每行有任意枚硬币时，利用二进制，可以把这个游戏玩得风生水起。哈佛大学的数学教授布顿在 1901 年首次发表了论文详述了这个问题，也正是他，正式将这个游戏命名为尼姆游戏。把玩家每一步操作之后的游戏局面叫做“棋局”。在布顿的论文中，如果玩家每一步操作后的棋局能保证自己获胜，那就是“安全的”，否则就是“不安全的”。每个不安全棋局都可以一步正确的操作变成安全的，而如果没有正确地操作，一个安全的棋局就会变成不安全的。如何判定一个棋局是安全的还是不安全的呢？这就用到了前面提到的二进制。将每一行的硬币数都用二进制表示，按矩阵元素的排列方式对齐，这时候如果每一列的数（ 0 或 1 ）相加都为偶数（包括 0 ），那么这个棋局就是安全的，只要有一列元素相加不为偶数，那这个棋局就是不安全的。回到我们上面说的那个流行版本上，可以看到在初始状态，它的二进制表示如下图可以看到，第 2 列之和为奇数，所以这个本版的初始状态是不安全的。拿掉最上面一行的 2 枚硬币，第 1 行就变成了 1 ，从而留下了一个安全棋局。通过用其他方法试验，可以看到，拿掉第 1 行的 2 枚硬币是留下安全棋局的唯一操作。把棋局转化成上面这个二进制表格，根据表格决定怎么操作就不会出错了。但是在玩的时候，恐怕对手没那么宽容，让你不断画表格，在脑子中计算，一不小心就出错。那么记住下面这条就很有用了：在两行里留下同样多的硬币，总能赢。在此之后，让每行硬币数量保持相等就可以了。尼姆游戏深受数学家喜爱并被广泛研究，它因此产生了很多变体。1910 年美国数学家穆尔就提出了一个，它规则与尼姆游戏相同，只不过玩家可以从不超过指定数 k 的任意多行里拿掉硬币。有趣的是，它同样可以通过二进制来分析，只要把安全棋局定义为：二进制表里的每列之和都可以被 k + 1 整除就可以了。后选择一定赢的硬币游戏对于粗心大意和无知的人来说，这个游戏就是一个十足的陷阱。让我们来看看这个它是怎么玩的。
抛三次硬币看最后哪一面朝上，结果无非只有这 8 种：正正正 正正反 正反正 反正正 正反反 反正反 反反正 反反反这个游戏的规则是，对手有优先选择权。首先对手在这 8 种组合总选一种作为他的组合，然后你选一组作为自己的组合。双方选定后，随便选一个人来连续抛硬币，直到他的或你的组合出现为止，谁的组合先出现谁就算赢。这个游戏看上去没有什么问题，不管哪种组合，它们出现的概率都是一样的。但如果谁真这么想，那他可就输定了。事实上，先选的人一定会被针对。无论对手选择选择哪个组合，后选的人都可以选一个组合来针对他，是自己的获胜概率至少提高到 2／3 !如果你不相信的话，就让我们选一个简单的例子来分析看看。假设对手选择的是“正正正”的组合，这时候我们只要选择“反正正”，胜率就可以瞬间到达 7／8。这是为什么呢？如果前三次就抛出了“正正正”的结果，那对手就获胜了，这种情况发生的概率为 1／8 。但除此之外，只要最开始的三次对手没有获胜，那么我可以说，他已经没有获胜的机会了。因为前三次没有获胜，就说明在他获胜之前一定出现了反面，那第一次出现“正正正”的情况必然包含在如下的结果中：……反正正正……可以看到，当出现“反正正”的时候，他已经没有办法再玩下去了，因为那正是我们选择的组合，到这里我们已经获胜了。对于其他组合，这里不再专门讨论了，下面附出一张表格，给出了后选择的人采用正确策略的获胜概率，可以看到，后选择的人获胜的最低概率也是 2／3 。你是否觉得这个结果有些出乎意料？需要说明的是，在涉及到概率时，我们的直觉很多时候都是错误的。如果你不相信，来看看死理性派的 不要相信直觉！那些概率统计的奇妙结论 是如何颠覆你对世界的认识的吧。硬币正反不一样通常我们所说的硬币，都是理想硬币。但由于设计的原因，硬币正反面的花纹并不一样，这就导致了它的实际重心不在正中心上。由于重心有偏向，所以掷硬币时，正反面出现的概率也会有所偏差，想要知道这个偏差具体有多大，难度颇大。幸好花纹导致的概率偏差非常非常小，可以忽略不计。尽管如此，但万一就遇到了一个死较真的和你玩抛硬币，我们能不能找到一个方法，让真实的硬币达到理想硬币的效果呢？***是能。我们可以用下面这种玩法“化腐朽为神奇”：连续掷两次硬币，如果两次结果是相同的（都是正面朝上或都是反面朝上），那就重新再连续掷两次硬币，直到结果不同为止（一次反面朝上，一次正面朝上）。这时， [正,反] 的结果就可以对应掷理想硬币结果为正的情形， [反,正] 的结果就可以对应理想硬币为反的情形（反过来也可以）。这是为什么呢？假设硬币掷出正面的概率是 p ，那掷出 [正,反] 的概率为 p( 1 - p ) ； [反，正] 的概率为 （1 - p）p。二者相等，所以采取这种方法，即便是一枚非理想硬币，游戏结果也会变成完全公平的。
已经打印出来了
我好好研究一下~
麻烦各位啦~~
- -前面的我还是用我自己的方法就好了！你的方法还是理解点的至于那个正正正的 我还是不了解！其实我还想说，我身上很少有硬币
有❤就可以~~~
nim是最简单的博弈算法也是最高效的博弈算法，在百度文库中有大量的资料。人工智能编程吧就是主要搞人工智能机器博弈的，目标就是“深蓝”。
这个挺有意思的，可以考虑推广到多个硬币的情况。
已经在我们学校吧推广了
简单解法。。。
我说的不是简单的Nim游戏，这个已经研究得很成熟了。我考虑的是类似于连续抛三次硬币的正反情况的问题，先手说一个，后手再说一个，看双方的输赢比例。这个可以推广到四个硬币、五个硬币……，可以考虑一般的情况。
求详解~~~~
博弈论基础知识: 巴什博奕+威佐夫博奕+尼姆博弈(及Staircase);(一)巴什博奕(Bash Game):只有一堆n个物品,两个人轮流从这堆物品中取物,规定每次至少取一个,最多取m个.最后取光者得胜.若(m+1) | n，则先手必败，否则先手必胜。显然,如果n=m+1,那么由于一次最多只能取m个,所以,无论先取者拿走多少个,后取者都能够一次拿走剩余的物品,后者取胜.因此我们发现了如何取胜的法则：如果n=(m+1)r+s,(r为任意自然数,s≤m),那么先取者要拿走s个物品,如果后取者拿走k(≤m)个,那么先取者再拿走m+1-k个,结果剩下(m+1)(r-1)个,以后保持这样的取法,那么先取者肯定获胜.总之,要保持给对手留下(m+1)的倍数,就能最后获胜.(二)威佐夫博奕(Wythoff Game):有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜.奇异局势下先手必败，非奇异局势下先手必胜。这种情况下是颇为复杂的.我们用(ak,bk)(ak ≤bk ,k=0,1,2,...,n)表示两堆物品的数量并称其为局势,如果甲面对(0,0),那么甲已经输了,这种局势我们称为奇异局势.前几个奇异局势是：(0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20).可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而bk= ak + k,奇异局势有如下三条性质：1、任何自然数都包含在一个且仅有一个奇异局势中.由于ak是未在前面出现过的最小自然数,所以有ak & ak-1 ,而bk= ak + k & ak-1 + k-1 = bk-1 & ak-1 .所以性质1.成立.2、任意操作都可将奇异局势变为非奇异局势.事实上,若只改变奇异局势(ak,bk)的某一个分量,那么另一个分量不可能在其他奇异局势中,所以必然是非奇异局势.如果使(ak,bk)的两个分量同时减少,则由于其差不变,且不可能是其他奇异局势的差,因此也是非奇异局势.3、采用适当的方法,可以将非奇异局势变为奇异局势.假设面对的局势是(a,b),若b = a,则同时从两堆中取走a 个物体,就变为了奇异局势(0,0)；如果a = ak ,b & bk,那么,取走b - bk个物体,即变为奇异局势；如果a = ak , b & bk ,则同时从两堆中拿走ak - ab - ak个物体,变为奇异局势( ab - ak , ab - ak+ b - ak)；如果a & ak ,b= ak + k,则从第一堆中拿走多余的数量a - ak 即可；如果a & ak ,b= ak + k,分两种情况,第一种,a=aj (j & k),从第二堆里面拿走b - bj 即可；第二种,a=bj (j & k),从第二堆里面拿走b - aj 即可.从如上性质可知,两个人如果都采用正确操作,那么面对非奇异局势,先拿者必胜；反之,则后拿者取胜.那么任给一个局势(a,b),怎样判断它是不是奇异局势呢？我们有如下公式：ak =[k(1+√5)/2](下取整), bk= ak + k (k∈N)奇妙的是其中出现了有关黄金分割数的式子：(1+√5)/2 =1.618...,若两堆物品个数分别为x,y(x&y)，则k=y-x，再判断x是否等于[(y-x)*( √5+1)/2] 即可得知是否是奇异局势。参考例题：POJ1067取石子游戏参考代码：var a,b:begin repeat readln(a,b); if a&b then begin a:= b:= a:= if a=trunc((b-a)*(sqrt(5)+1)/2) then writeln(0) else writeln(1);end.(三)尼姆博奕(Nimm Game):有三堆各若干个物品,两个人轮流从某一堆取任意多的物品,规定每次至少取一个,多者不限,最后取光者得胜.这种情况最有意思,它与二进制有密切关系,我们用(a,b,c)表示某种局势,首先(0,0,0)显然是奇异局势,无论谁面对奇异局势,都必然失败.第二种奇异局势是(0,n,n),只要与对手拿走一样多的物品,最后都将导致(0,0,0).仔细分析一下,(1,2,3)也是奇异局势,无论对手如何拿,接下来都可以变为(0,n,n)的情形.计算机算法里面有一种叫做按位模2加,也叫做异或的运算,我们用符号xor表示这种运算.这种运算和一般加法不同的一点是1+1=0.先看(1,2,3)的按位模2加的结果：1 =二进制01Xor 2 =二进制10Xor 3 =二进制11 --------------0 =二进制00 对于奇异局势(0,n,n)也一样,结果也是0.任何奇异局势(a,b,c)都有a xor b xor c =0。该结论可以推广至若干堆，都是成立的。如果我们面对的是一个非奇异局势(a,b,c),要如何变为奇异局势呢？假设a & b& c,我们只要将c 变为a xor b,即可,因为有如下的运算结果: a xor b xor (a xor b)=(a xor a) xor (b xor b)=0 xor 0=0.要将c 变为a xor b,只要从c中减去c-(a xor b)即可.(四)Nim Staircase博奕:这个问题是尼姆博弈的拓展：游戏开始时有许多硬币任意分布在楼梯上，共n阶楼梯从地面由下向上编号为0到n。游戏者在每次操作时可以将楼梯j(1&=j&=n)上的任意多但至少一个硬币移动到楼梯j-1上。游戏者轮流操作，将最后一枚硬币移至地上（0号）的人获胜。算法：将奇数楼层的状态异或，和为0则先手必败，否则先手必胜。证明略。例题：Poj1704这道题可以把两个棋子中间间隔的空格子个数作为一堆石子，则原题转化为每次可以把左边的一堆石子移到相邻的右边的一堆中。也就是阶梯尼姆博弈，注意对输入数据先排序，然后倒着往前数（a[n]-a[n-1]-1为第一个），奇数个数到的就做一下xor，其中最前面的看做a[1]-0-1，参考程序：var t,n,b,i,j: a:array[0..1000]begin readln(t); repeat dec(t); readln(n); for i:=1 to n do read(a[i]); qsort(1,n);//快排略 j:=0; b:=0; for i:=n downto 1 do begin inc(j); if odd(j) then b:=b xor (a[i]-a[i-1]-1); if b=0 then writeln('Bob will win') else writeln('Georgia will win'); until t=0;end.
三堆，121，拿掉第二堆的2个，先手必胜三堆，122，拿掉第一堆的一个，先手必胜三堆，123，（1）不论先手那光那一堆，后手必胜（2）先手拿掉第二堆的一颗，则剩下113，后手只需那光第三堆三颗，后手必胜（3）先手拿掉第三堆的一颗，则剩下122，后手拿掉第一堆的一颗，后手必胜（4）先手拿掉第三堆的两颗，则剩下121，后手拿光第二堆，后手必胜以上，后手必胜
小Q滴滴滴 那个抛硬币游戏，我发到了人工智能编程吧和其它几个吧，反响热烈！
贴吧热议榜
使用签名档&&
保存至快速回贴