博弈问题分析 ——取石子游戏实例解答小红是个游戏迷，他和小蓝一起玩拿石子游戏游戏规则为 2 个人轮流拿石子一次可以拿 1 颗或 3 颗，规定谁取到最后一颗石子谁就胜出最后决定由小红先取两人都是游戏高手，该赢的绝不会输(表示不会失误） 问在知道石子总数的情况下，怎样快速预测谁将会胜出分析：小红和小蓝各取一次共有三种情况：② 共取走 2 颗石子(1,1)② 共取走 4 颗石子(1,3)③ 共取走 6 颗石子(3,3)设方案①取了 N1 次，方案②取了 N2 次，方案③取了 N3 次后，还剩下 K（k有一种很有意思的游戏，就是有物体若干堆，可以是火柴棍或是围棋子等等均可两个人轮流从堆中取物体若干，规定最后取光物体者取胜这是我国民间很古老的一个游戏，别看这游戏极其简单，却蕴含着深刻的数学原理下面我们来分析一下要如何才能够取胜一）巴什博奕（Bash Game）：只有一堆 n 个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取 m 个最后取光者得胜显然，如果 n=m+1，那么由于一次最多只能取 m 个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜因此我们发现了如何取胜的法则：如果n=（ m+1）* r+s， （r 为任意自然数，s≤m） ，那么先取者要拿走 s 个物品，如果后取者拿走 k（k≤m ）个，那么先取者再拿走 m+1-k 个，结果剩下（m+1） （r-1）个，以后保持这样的取法，那么先取者肯定获胜。
总之，要保持给对手留下（m+1）的倍数，就能最后获胜这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十个，谁能报到 100 者胜总结：通过分析可知，设 n=(m+1)*r+s(s 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 ak ，b= ak + k，则从第一堆中拿走多余的数量 a - ak 即可；如果 a 0;把 c 表示成二进制，记它的二进制数的最高位为第 p 位，则必然存在一个 A(t),它二进制的第 p 位也是 1。
（否则，若所有的 A(i)的第 p 位都是 0，这与 c 的第 p 位就也为 0 矛盾） 那么我们把 x = A(t) xor c,则得到 x =2 的 T 用 T2 表示,全是单根堆的 T 用 T0 表示(没有 T1 这种状态，分析可知)同样的充裕堆>=2 的 S 态用 S2 表示,全为孤单堆的 S（可知堆数必为奇数）态用 S0 表示,只有一堆充裕堆的用 S1 表示孤单堆的根数异或只会影响二进制的最后一位，但充裕堆会影响高位（非最后一位） 一个充裕堆，高位必有一位不为 0，则所有根数异或不为 0故不会是 T 态[定理 5]：S0 态，即仅有奇数个孤单堆（没有充裕堆） ，必败T0 态必胜 证明：S0 态，其实就是每次只能取一根每次第奇数根都由己取，第偶数根都由对 方取，所以最后一根必己取同理, T0 态必胜#[定理 6]：S1 态，只要方法正确，必胜 证明：若此时孤单堆堆数为奇数，把充裕堆取完；否则，取成只剩下一根（此时变成 S0 态，但是自己是后手） 这样，就变成奇数个孤单堆，由对方取由定理 5，对方必输 [定理 7]：S2 态不可转一次变为 T0 态 证明：充裕堆数不可能一次由 2 变为 0。
得证 # [定理 8]：S2 态可一次转变为 T2 态 证明：由定理 1，S 态可转变为 T 态，又由定理 7，S2 态不可转一次变为 T0 态，所以转变的 T态为 T2 态 # [定理 9]：T2 态，只能转变为 S2 态或 S1 态 证明：由定理 2，T 态必然变为 S 态由于充裕堆数不可能一次由 2 变为 0，所以此时的 S 态不可能为 S0 态命题得证 [定理 10]：S2 态，只要方法正确，必胜. 证明：方法如下： 1） S2 态，就把它变为 T2 态 （由定理 8） 2） 对方只能 T2 转变成 S2 态或 S1 态（定理 9） 若转变为 S2, 转向 1） 若转变为 S1, 这己必胜 （定理 5） [定理 11]：T2 态必输 证明：同 10 总结， 必输态有： T2,S0 必胜态： S2,S1,T0. 两题比较： 第一题的全过程其实如下： S2->T2->S2->T2-> …… ->T2->S1->T0->S0->T0->……->S0->T0(全 0) 第二题的全过程其实如下： S2->T2->S2->T2-> …… ->T2->S1->S0->T0->S0->……->S0->T0(全 0) 下划线表示胜利一方的取法。
是否发现了他们的惊人相似之处 我们不难发现(见加黑部分) ，S1 态可以转变为 S0 态（第二题做法） ，也可以转变为 T0（第一题做法） 哪一方控制了 S1 态，他即可以有办法使自己得到最后一根（转变为 T0）,也可以使对方得到最后一根（转变为 S0） 所以，抢夺 S1 是制胜的关键！ 为此，始终把 T2 态让给对方，将使对方处于被动状态，他早晚将把状态变为 S1.推荐 HDOJ 题目 2 道了 S-Nim 1536 1517 1907小子最近迷途于博弈之中感触颇深为了让大家能够在学习博弈的时候少走弯路，最重要的也是为了加深自己的影响，温故而知新，特发此贴与大家共勉学博弈先从概念开始：特别推荐 LCY 老师的课件：博弈入门下载地址： SG 值的问题:SG 值：一个点的 SG 值就是一个不等于它的后继点的 SG 的且大于等于零的最小整数后继点：也就是按照题目要求的走法（比如取石子可以取的数量，方法）能够走一步达到的那个点具体的有关 SG 值是怎么运用的希望大家自己多想想课件后面有一个 1536 的代码可以放在后面做做看到这里推荐大家做几道题：1846（最简单的博弈水题）1847（求 SG 值） 有了上面的知识接下来我们来看看组合博弈（n 堆石子）推荐大家看个资料：博弈-取石子游戏( 推荐等级五星级 ) SG 值的求解，但是知道这么一种思路无疑对思维的广度和深度扩展是很有帮助的。
ZZ 博弈 N 状态一种是最后取的是 P 状态，两个状态的解题方法能看懂很有帮助当然，能够把推导过程理解，吃透无疑是大牛级的做法~小子也佩服的紧~ 1536 题推荐做做这题，这题前面提醒大家是一个求 SG 值的题目，题目前面是对异或运算运用在组合博弈问题中的很好的解释当然题目本身是有所不同的因为在这里面对取法有所要求那么这样就回归到了解决博弈问题的王道算法——求 SG 值上有关运用求 SG 值的博弈题目有： 1850（也可基于奇异状态异或）1848（中和的大斐波那契数列的典型求 SG 值题）1517（个人认为有点猥琐的题目在此题上困扰很久当然搞出来很开心小子是用比较规矩的求 SG 值的方法求出来的，但是论坛有人对其推出来了规律，这里佩服一下，大家可以学习一下）1079（更猥琐的题目，对新手要求较高，因为按传统方法需要比较细致的模拟加对边角状态的考虑，同样有人推出来了公式）当你全部看完以上的东西做完以上的题目的话小子恭喜你~你博弈入门了~~~~这里小子告诉大家博弈很强大学习要耐心~ 谢谢Current System Time : 2008-12-11 19:16:03ACM 课作业：1001 Brave Game1002 Good Luck in CET-4 Everybody!1003 Fibonacci again and again1004 Rabbit and Grass1005 Being a Good Boy in Spring Festival1006 Public Sale 1007 悼念 512 汶川大地震遇难同胞——选拔志愿者 1008 kiki’s game 1009 Calendar Game 1010 A Multiplication Game 1011 Digital Deletions 1012 S-Nim 的参考代码本部分设定了隐藏,您已回复过了,以下是隐藏的内容Copy code//博弈-基于求 SG 值//Accepted 1536 578MS 416K 904 B#include”iostream”using namespace std;int f[101],sg[10001],k;int mex(int b){int a[101]={0},i;for(i=0;i> k,k){for(i=0;i> f;}memset(sg,-1,sizeof(sg));for(i=0;if[j]){ f+=f[j];f[j]=f-f[j];f-=f[j];}sg[0]=0;cin >> t;while(t–){cin >> n;s=0;while(n–){cin >> bead;//该堆的成员个数if(sg[bead]==-1)sg[bead]=mex(bead);s=s^sg[bead];}if(s==0)cout =5000000000)break;for(j=2;j=n)break;}for(j=i-1;a[j]*9>=nj–)sg[j]=1;while(j>=0){for(k=j+1;k=a[k];k++)if(a[k]%a[j]==0&&sg[k]==0) {sg[j]=1;break;}j。