SG函数的计算方法：
一个局面的SG为mex{后继局面的SG}
mex运算为集合中没出现的最小的自然数
几个局面的和的SG为单个的SG亦或
SG不为0时先手必胜，SG为0时后手必胜
1.Nim Game
n堆石子，每次可以从一堆里面取任意个石子
对于一堆石子，SG函数就是石子数
整个游戏的SG函数是每一堆石子的SG函数的亦或和
必胜：SG不为0
必败：SG为0
2.Bash Game
每次最多取m个石子，其他同Nim
一堆石子的SG函数为石子数mod(m+1)
整个游戏的SG函数是每一堆石子的SG函数的亦或和
必胜：SG不为0
必败：SG为0
3.Nimk Game
每次最多可以同时从k堆石子进行操作，这k堆可以取不同数量的石子
一堆石子的SG函数为石子数
对每一个二进制位单独算，求SG函数每一个二进制位1的个数mod(k+1)，如果都为0，则必败，否则必胜
对于必败态不管怎么走都只能走到必胜态
对于变化的SG的最高位，你至少变化为1，最多变化为k，所以这一位1的个数不可能mod(k+1)还是为0
对于必胜态我们肯定可以找到一种方法走到必败态
我们从高位往低位做，记s为这一位可以随意填值的数字个数（如果把某一位从1变成0，那么更低位就能随便取值了）
假设我们现在做到第k位，记n为除了能随便取值的s位以外这一位1的个数mod(k+1)
如果n+s&=k，那么很简单，我们取出n个第k位为1的让这些数字的第k位变成0，那s个数字这一位也变成0，然后s+=n
如果n+s&k，即n+s&=k+1，那么s&=k+1-n，我们在s中间取k+1-n个变为1，其他变为0就可以满足条件了
4.Anti-Nim Game
不能取石子的一方获胜
必胜：SG不为0且至少有一堆石子数大于0，SG为0且每一堆石子数都为1
必败：其余为必败
5.Staircase Nim
每次可以从一个阶梯上拿掉任意数量石子放到下一层阶梯，不能操作的为输
SG函数为奇数阶梯上的石子的亦或和
如果移动偶数层的石子到奇数层，对手一定可以继续移动这些石子到偶数层，使得其SG不变
6.Wythoff Game
有两堆石子，每次可以从一堆或者两堆里拿走一样数目的石子，不能取的为输
必败态为(1,2)(3,5)(4,7)(6,10)...
差为1，2，3，4.....每一对数的第一个数为前面没出现的最小的正整数
7.Take & Break
每次可以把一堆石子分成两堆甚至多堆不为0的石子，不能操作的为输
暴力计算SG
8.树上删边游戏
给定根节点，每次可以删掉一条边，不与根节点相连的部分删除
叶子节点SG为0，其他节点的SG函数为子树SG+1的亦或和
将子树SG+1看做石子数（我们可以定义没有节点的图的SG为-1），然后就变成了取石子游戏
9.无向图删边
规则同树上删边游戏
结论：把奇环缩成一个点加一条新边，把偶环缩成一个点，不影响SG，然后套用树上删边游戏
10.翻硬币游戏
n枚硬币排成一排，有的正面朝上，有的反面朝上。 游戏者根据某些约束翻硬币（如：每次只能翻一或两枚，或者每次只能翻连续的几枚），但他所翻动的硬币中，最右边的必须是从正面翻到反面。 谁不能翻谁输。
需要先开动脑筋把游戏转化为其他的取石子游戏之类的,然后用如下定理解决: 局面的 SG 值等于局面中每个正面朝上的棋子单一存在时的 SG 值的异或和。
证明的基本套路：
必胜局面存在一个操作到达必败局面，必败局面无论怎么操作都会到必胜局面
阅读(...) 评论()博弈游戏_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
阅读已结束，下载文档到电脑
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，方便使用
还剩1页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢博弈论的哪些知识可以用在生活里？ - 简书
博弈论的哪些知识可以用在生活里？
博弈论的哪些知识可以用在生活里？假期凭借兴趣学习刚结束《博弈论基础》的课程。归纳总结一下哪些技巧妙招可以用在生活之中让我们拥有更好的生活呢？博弈的核心在于整体思维上的理性换位思考。用他人利得推测行为，选择最有利于自己行为的策略。不玩儿负和游戏，少玩儿零和游戏，多玩儿正和游戏。提问技巧：多做选择题，少做判断题。让对方在2-3个选项里面选。给对方的选项要有明显的区别。（比如你要约人吃饭。你不是问她：中午一起吃饭可以吗？而是说：我们中午吃西餐还是火锅？要愿意吃亏，与那些比你更愿意吃亏的人做朋友。在信息不对称的情况下，博弈的结果不取决于大家怎么想，取决于大家认为大家怎么想。领导更喜欢下属间有点小矛盾，否则自己将会有危险。陷阱的三大特征：1有明显的诱饵。2通往诱饵之路是单向的，可进不可出。3越想挣脱就越陷愈深。抢占成本的最低点就是抢占竞争的制高点。搭便车 别忘了给对方回报。竞技体育很多时候就是万元陷阱。除非你本身很享受这个过程。困扰我们的不是能够过上幸福的生活。而是能过上比别人更幸福的生活。没有信仰的人很难理解一个有信仰人的思维和习惯。人生是永远不会停息的博弈过程，博弈意味着通过选择合适策略达到合意结果。作为博弈者。最佳策略是极大限度利用游戏规则。博弈的精髓不是通过暴力或阴谋诡计去战胜对方。而是大家共用去建设更好的游戏规则最终实现共赢。=====ACM=====（482）
HihoCoder（11）
【博弈】（2）
【题目链接】：
【题目大意】：
#1163 : 博弈游戏·Nim游戏
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
今天我们要认识一对新朋友，Alice与Bob。
Alice与Bob总是在进行各种各样的比试，今天他们在玩一个取石子的游戏。
在这个游戏中，Alice和Bob放置了N堆不同的石子，编号1..N，第i堆中有A[i]个石子。
每一次行动，Alice和Bob可以选择从一堆石子中取出任意数量的石子。至少取1颗，至多取出这一堆剩下的所有石子。
Alice和Bob轮流行动，取走最后一个石子的人获得胜利。
假设每一轮游戏都是Alice先行动，请你判断在给定的情况下，如果双方都足够聪明，谁会获得胜利？
第1行：1个整数N。表示石子堆数。1≤N≤100
第2行：N个整数，第i个整数表示第i堆石子的个数A[i]，1≤A[i]≤10000
第1行：1个字符串，若Alice能够获胜输出&Alice&，否则输出&Bob&
【思路】：
古老而又经典的博弈问题：Nim游戏。
Nim游戏是经典的公平组合游戏(ICG)，对于ICG游戏我们有如下定义：
1、两名选手；
2、两名选手轮流行动，每一次行动可以在有限合法操作集合中选择一个；
3、游戏的任何一种可能的局面(position)，合法操作集合只取决于这个局面本身；局面的改变称为“移动”(move)。
4、若轮到某位选手时，该选手的合法操作集合为空，则这名选手判负。
对于第三条，我们有更进一步的定义Position，我们将Position分为两类：
P-position：在当前的局面下，先手必败。
N-position：在当前的局面下，先手必胜。
他们有如下性质：
1.合法操作集合为空的局面是P-position；
2.可以移动到P-position的局面是N-position；
3.所有移动都只能到N-position的局面是P-position。
在这个游戏中，我们已经知道A[] = {0,0,...,0}的局面是P局面，那么我们可以通过反向枚举来推导出所有的可能局面，总共的状态数量为A[1]*A[2]*...*A[N]。并且每一次的状态转移很多。
虽然耗时巨大，但确实是一个可行方法。
当然，我们这里会讲这个题目就说明肯定没那么复杂。没错，对于这个游戏有一个非常神奇的结论：
对于一个局面，当且仅当A[1] xor A[2] xor ... xor A[N] = 0时，该局面为P局面。
对于这个结论的证明如下：
1. 全0状态为P局面，即A[i]=0，则A[1] xor A[2] xor ... xor A[N] = 0。
2. 从任意一个A[1] xor A[2] xor ... xor A[N] = k != 0的状态可以移动到A[1] xor A[2] xor ... xor A[N] = 0的状态。由于xor计算的特殊性，我们知道一定有一个A[i]最高位与k最高位的1是相同的，那么必然有A[i]
xor k & A[i]的，所以我们可以通过改变A[i]的值为A[i]'，使得A[1] xor A[2] xor ... xor A[i]' xor ... xor A[N] = 0。
3. 对于任意一个局面，若A[1] xor A[2] xor ... xor A[N] = 0，则不存在任何一个移动可以使得新的局面A[1] xor A[2] xor ... xor A[N] = 0。由于xor计算的特殊性，我们可以知道，一定是存在偶数个1时该位置的1才会被消除。若只改变一个A[i]，无论如何都会使得1的数量发生变化，从而导致A[1]
xor A[2] xor ... xor A[N] != 0。
以上三条满足ICG游戏中N,P局面的转移性质，所以该结论的正确性也得到了证明。
#include&bits/stdc++.h&
int main()
int n,m,k;
scanf(&%d&, &n);
for(int i=0; i&n; i++)
scanf(&%d&,&m);
if(i==0) k=m;
else k^=m;
if(!k) puts(&Bob&);
else puts(&Alice&);
#1173 : 博弈游戏·Nim游戏·三
在这一次游戏中Alice和Bob决定在原来的Nim游戏上增加一条规则：每一次行动时，不仅可以选择一堆取走任意数量的石子(至少取1颗，至多取出这一堆剩下的所有石子)，还可以选择将一堆石子分成两堆石子，但并不取走石子。比如说有一堆石子为k个，当Alice或者Bob行动时，可以将这一堆石子分成两堆，分别为x,y。满足x+y=k,x,y&0。那么增加了这一条规则后，在Alice总先手的情况下，请你根据石子堆的情况判断是Alice会获胜还是Bob会获胜？
第1行：1个整数N。表示石子堆数。1≤N≤100
第2行：N个整数，第i个整数表示第i堆石子的个数A[i]，1≤A[i]≤20000
第1行：1个字符串，若Alice能够获胜输出&Alice&，否则输出&Bob&
【思路】：
居然最佳代码都是找规律的。。没有想出来怎么推导的，于是也只能找规律了~~
规律见代码！
对于ICG游戏，我们可以将游戏中每一个可能发生的局面表示为一个点。并且若存在局面i和局面j，且j是i的后继局面(即局面i可以转化为局面j)，我们用一条有向边，从i出发到j，连接表示局面i和局面j的点。则整个游戏可以表示成为一个有向无环图：
根据ICG游戏的定义我们知道，任意一个无法继续进行下去的局面为终结局面，即P局面(先手必败)。在上图中我们可以标记所有出度为0的点为P点。接着根据ICG游戏的两条性质，我们可以逆推出所有点为P局面还是N局面：
因此，对于任意一个ICG游戏，我们可以采取逆推的方法，标记出所有局面是N局面还是P局面。
但仅仅只是标记N、P，所能得到的信息太少，于是我们定义了Sg(Sprague-Grundy)函数：
对于一个游戏可能发生的局面x，我们如下定义它的sg值：
(1)若当前局面x为终结局面，则sg值为0。
(2)若当前局面x非终结局面，其sg值为：sg(x) = mex{sg(y) | y是x的后继局面}。
mex{a[i]}表示a中未出现的最小非负整数。举个例子来说：
mex{0, 1, 2} = 3, mex{1, 2}=0, mex{0,1,3}=2
我们将上图用sg函数表示后，得到：
可以发现，若一个局面x为P局面，则有sg(x)=0；否则sg(x)&0。同样sg值也满足N、P之间的转换关系：
若一个局面x，其sg(x)&0，则一定存在一个后续局面y，sg(y)=0。
若一个局面x，其sg(x)=0，则x的所有后续局面y，sg(y)&0。
由上面的推论，我们可以知道用N、P-Position可以描述的游戏用sg同样可以描述。并且在sg函数中还有一个非常好用的定理，叫做sg定理：
对于多个单一游戏，X=x[1..n]，每一次我们只能改变其中一个单一游戏的局面。则其总局面的sg值等于这些单一游戏的sg值异或和。
sg(X) = sg(x[1]) xor sg(x[2]) xor … xor sg(x[n])
要证明这一点我们只要证明：
(1) 假设sg(x[1]) xor sg(x[2]) xor … xor sg(x[n]) = A，对于任意一个0 &= B & A，总存在一个X的后续局面Y，使得sg(Y) = B。
(2) 假设sg(x[1]) xor sg(x[2]) xor … xor sg(x[n]) = A，不存在一个X的后续局面Y，使得sg(Y) = A。
下先证明(1)：
假设M = A xor&
B，设M表示为二进制之后最高位的1为第k位。所以A的第k位为1，B的第k位为0。又因为A的第k位为1，至少存在一个i，sg(x[i])的第k位也为1。那么一定有sg(x[i]) xor M & sg(x[i])，即一定通过某个操作使x[i]变为x[i’]，且sg(x[i’]) = sg(x[i]) xor M。那么：
sg(x[i’]) xor Other = sg(x[i]) xor M xor Other = M xor A = B
下证明(2)：
若sg(X) = A，sg(Y) = A。不妨设我们改变的游戏为x[i]，则X=x[1..n], Y=x[1…i’…n]。有sg(x[i]) = sg(x[i’])，产生矛盾，所以sg(Y)不可能等于A。
现在让我们回到我们的题目上：
局面上一共有N堆石子，每一次我们只能改变一堆石子。那么我们可以将每一堆石子看作一个单一游戏。
对于一堆石子，若该堆石子数量为0，就达到了终止状态，所以sg(0) = 0。
若其石子数量为k，接下来我们从k=1开始枚举递推每一个sg(k)。对于k，其可能的后继状态有：
(1)不分堆：石子数量为k’=0..k-1，则sg(k’)
(2)分堆：石子变为2堆，数量为(1,k-1),(2,k-2),…,(k-1,1)。设第一堆的石子数量为i，则sg值为sg(i) xor sg(k-i)。(这里用到了sg定理)
那么可以推算出sg(k) = mex{sg(0), sg(i), sg(i) xor sg(k - i) | i = 1..k-1}。
0 1 2 3 4 5 6 7 8 9 10 11 12 …
sg(k) 0 1 2 4 3 5 6 8 7 9 10 12 11 …
对于N堆石子，其sg值则为这N堆各自的sg值异或和。
#include&bits/stdc++.h&
int get_sg(int n)
if(n==0)return 0;
int re=n%4;
if(re==0) return n-1;
else if(re==3) return n+1;
int main()
int n, yihuo=0;
scanf(&%d&, &n);
for(int i=0; i&n; i++){
scanf(&%d&,&m);
yihuo^=get_sg(m);;
if(!yihuo) puts(&Bob&);
else puts(&Alice&);
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：440124次
积分：10495
积分：10495
排名：第1555名
原创：532篇
转载：25篇
译文：75篇
评论：90条
nyist计科13级本科，bjtu17级在读硕士，喜爱算法，热爱编程，欢迎一起学习交流。
加贝木苇的理想国
文章：10篇
阅读：7259
文章：14篇
阅读：4193
阅读：2739
文章：77篇
阅读：72295
(4)(4)(18)(5)(18)(1)(15)(5)(2)(2)(12)(5)(4)(4)(6)(36)(42)(36)(33)(40)(19)(60)(27)(39)(43)(12)(37)(29)(12)(11)(31)(13)(2)(2)(3)