&&国之画&&&& &&&&&&
&& &&&&&&&&&&&&&&&&&&&&
鲁ICP备号-4
打开技术之扣，分享程序人生！ACM学习（10）
Nim游戏定义
Nim游戏是组合游戏(Combinatorial Games)的一种，准确来说，属于“Impartial Combinatorial Games”（以下简称ICG）。满足以下条件的游戏是ICG（可能不太严谨）：1、有两名选手；2、两名选手交替对游戏进行移动(move)，每次一步，选手可以在（一般而言）有限的合法移动集合中任选一种进行移动；3、对于游戏的任何一种可能的局面，合法的移动集合只取决于这个局面本身，不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它什么因素； 4、如果轮到某名选手移动，且这个局面的合法的移动集合为空（也就是说此时无法进行移动），则这名选手负。根据这个定义，很多日常的游戏并非ICG。例如象棋就不满足条件3，因为红方只能移动红子，黑方只能移动黑子，合法的移动集合取决于轮到哪名选手操作。
通常的Nim游戏的定义是这样的：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。
N-position,P-position
定义P-position和N-position，其中P代表Previous，N代表Next。直观的说，上一次move的人有必胜策略的局面是P-position，也就是“后手可保证必胜”或者“先手必败”，现在轮到move的人有必胜策略的局面是N-position，也就是“先手可保证必胜”。更严谨的定义是：1.无法进行任何移动的局面（也就是terminal position）是P-position；2.可以移动到P-position的局面是N-position；3.所有移动都导致N-position的局面是P-position。
所以对于当前的局面，递归计算它的所有子局面的性质，如果存在某个子局面是P-position，那么向这个子局面的移动就是必胜策略。
对于某个Nim游戏的局面(a1,a2,…,an)来说，要想判断它的性质以及找出必胜策略，需要计算O(a1*a2*…*an)个局面的性质。
Bouton’s Theorem
对于一个Nim游戏的局面(a1,a2,…,an)，它是P-position当且仅当a1^a2^…^an=0，其中^表示异或(xor)运算。
根据定义，证明一种判断position的性质的方法的正确性，只需证明三个命题:
1、这个判断将所有terminal position判为P-position；
2、根据这个判断被判为N-position的局面一定可以移动到某个P-position；
3、根据这个判断被判为P-position的局面无法移动到某个P-position。
第一个命题显然，terminal position只有一个，就是全0，异或仍然是0。
第二个命题，对于某个局面(a1,a2,…,an)，若a1^a2^…^an!=0，一定存在某个合法的移动，将ai改变成ai’后满足a1^a2^…^ai’^…^an=0。不妨设a1^a2^…^an=k，则一定存在某个ai，它的二进制表示在k的最高位上是1（否则k的最高位那个1是怎么得到的）。这时ai^k& ai一定成立。则我们可以将ai改变成ai’=ai^k，此时a1^a2^…^ai’^…^an=a1^a2^…^an^k=0。
第三个命题，对于某个局面(a1,a2,…,an)，若a1^a2^…^an=0，一定不存在某个合法的移动，将ai改变成ai’后满足a1^a2^…^ai’^…^an=0。因为异或运算满足消去率，由a1^a2^…^an=a1^a2^…^ai’^…^an可以得到ai=ai’。所以将ai改变成ai’不是一个合法的移动。证毕。
根据这个定理，我们可以在O(n)的时间内判断一个Nim的局面的性质，且如果它是N-position，也可以在O(n)的时间内找到所有的必胜策略。Nim问题就这样基本上完美的解决了。
Sprague-Grundy 函数
给定一个有向无环图和一个起始顶点上的一枚棋子，两名选手交替的将这枚棋子沿有向边进行移动，无法移动者判负。事实上，这个游戏可以认为是所有Impartial Combinatorial Games的抽象模型。也就是说，任何一个ICG都可以通过把每个局面看成一个顶点，对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。下面我们就在有向无环图的顶点上定义Sprague-Garundy函数。
SG函数性质
首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。对于一个给定的有向无环图，定义关于图的每个顶点的Sprague-Garundy函数g如下：g(x)=mex{ g(y) | y是x的后继 }。
来看一下SG函数的性质。首先，所有的terminal position所对应的顶点，也就是没有出边的顶点，其SG值为0，因为它的后继集合是空集。然后对于一个g(x)=0的顶点x，它的所有后继y都满足g(y)!=0。对于一个g(x)!=0的顶点，必定存在一个后继y满足g(y)=0。
SG函数用途
以上这三句话表明，顶点x所代表的postion是P-position当且仅当g(x)=0（跟P-positioin/N-position的定义的那三句话是完全对应的）。我们通过计算有向无环图的每个顶点的SG值，就可以对每种局面找到必胜策略了。但SG函数的用途远没有这样简单。如果将有向图游戏变复杂一点，比如说，有向图上并不是只有一枚棋子，而是有n枚棋子，每次可以任选一颗进行移动，这时，怎样找到必胜策略呢？
让我们再来考虑一下顶点的SG值的意义。当g(x)=k时，表明对于任意一个0&=i& k，都存在x的一个后继y满足g(y)=i。也就是说，当某枚棋子的SG值是k时，我们可以把它变成0、变成1、……、变成k-1，但绝对不能保持k不变。不知道你能不能根据这个联想到Nim游戏，Nim游戏的规则就是：每次选择一堆数量为k的石子，可以把它变成0、变成1、,,,,、变成k-1，但绝对不能保持k不变。这表明，如果将n枚棋子所在的顶点的SG值看作n堆相应数量的石子，那么这个Nim游戏的每个必胜策略都对应于原来这n枚棋子的必胜策略！
刚才，我们为了使问题看上去更容易一些，认为n枚棋子是在一个有向图上移动。但如果不是在一个有向图上，而是每个棋子在一个有向图上，每次可以任选一个棋子（也就是任选一个有向图）进行移动，这样也不会给结论带来任何变化。
所以我们可以定义有向图游戏的和(Sum of Graph Games)：设G1、G2、,,,,、Gn是n个有向图游戏，定义游戏G是G1、G2、……、Gn的和(Sum)，游戏G的移动规则是：任选一个子游戏Gi并移动上面的棋子。
Sprague-Grundy Theorem就是：g(G)=g(G1)^g(G2)^,,^g(Gn)。也就是说，游戏的和的SG函数值是它的所有子游戏的SG函数值的异或。
再考虑在本文一开头的一句话：任何一个ICG都可以抽象成一个有向图游戏。所以“SG函数”和“游戏的和”的概念就不是局限于有向图游戏。我们给每个ICG的每个position定义SG值，也可以定义n个ICG的和。所以说当我们面对由n个游戏组合成的一个游戏时，只需对于每个游戏找出求它的每个局面的SG值的方法，就可以把这些SG值全部看成Nim的石子堆，然后依照找Nim的必胜策略的方法来找这个游戏的必胜策略了！
SG函数代码模板
int sg[N];
bool vis[N];
void sg_solve(int *s,int t,int N)
memset(sg,0,sizeof(sg));
for(i=1;i&=N;i++)
memset(vis,0,sizeof(vis));
for(j=0;j&t;j++)
if(i - s[j] &= 0)
vis[sg[i-s[j]]] = 1;
for(j=0;j&=N;j++)
if(!vis[j])
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1507次
排名：千里之外
原创：24篇
(2)(6)(1)(2)(1)(1)(3)(16)推荐这篇日记的豆列结合游戏 - SG函数和SG定理 - 编程当前位置:& &&&结合游戏 - SG函数和SG定理结合游戏 - SG函数和SG定理&&网友分享于：&&浏览：0次组合游戏 - SG函数和SG定理&&&&&&& 在介绍SG函数和SG定理之前我们先介绍介绍必胜点与必败点吧.
必胜点和必败点的概念：
&&&&&& P点：必败点，换而言之，就是谁处于此位置，则在双方操作正确的情况下必败。
&&&&&& N点：必胜点，处于此情况下，双方操作均正确的情况下必胜。
必胜点和必败点的性质：
&&&&&&&&1、所有终结点是 必败点 P 。（我们以此为基本前提进行推理，换句话说，我们以此为假设）
&&&&&&& 2、从任何必胜点N 操作，至少有一种方式可以进入必败点 P。
&&&&&&& 3、无论如何操作，必败点P 都只能进入 必胜点 N。
我们研究必胜点和必败点的目的时间为题进行简化，有助于我们的分析。通常我们分析必胜点和必败点都是以终结点进行逆序分析。我们以hdu 1847 Good Luck in CET-4 Everybody!为例：
当 n = 0 时，显然为必败点，因为此时你已经无法进行操作了
当 n = 1 时，因为你一次就可以拿完所有牌，故此时为必胜点
当 n = 2 时，也是一次就可以拿完，故此时为必胜点
当 n = 3 时，要么就是剩一张要么剩两张，无论怎么取对方都将面对必胜点，故这一点为必败点。
以此类推，最后你就可以得到；
&&&&& n&&&&：&& 0&&& 1&&&&2&&& 3&&& 4&& 5&&& 6 ...
position：&&P&&&&N&& N&&& P&& N&& N&& P ...
你发现了什么没有，对，他们就是成有规律，使用了 P/N来分析，有没有觉得问题变简单了。
现在给你一个稍微复杂一点点的：
hdu 2147 kiki's game
&&&&&&& 现在我们就来介绍今天的主角吧。组合游戏的和通常是很复杂的，但是有一种新工具，可以使组合问题变得简单--------SG函数和SG定理。
Sprague-Grundy定理（SG定理）：
&&&&&& &游戏和的SG函数等于各个游戏SG函数的Nim和。这样就可以将每一个子游戏分而治之，从而简化了问题。而Bouton定理就是Sprague-Grundy定理在Nim游戏中的直接应用，因为单堆的Nim游戏 SG函数满足 SG(x) = x。不知道Nim游戏的请移步：这里
&&&&&&& 首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
&&&&&&& 对于任意状态 x ， 定义 SG(x) = mex(S),其中 S 是 x 后继状态的SG函数值的集合。如 x 有三个后继状态分别为&SG(a),SG(b),SG(c)，那么SG(x) = mex{SG(a),SG(b),SG(c)}。&这样 集合S 的终态必然是空集，所以SG函数的终态为 SG(x) = 0,当且仅当 x 为必败点P时。
【实例】取石子问题
有1堆n个的石子，每次只能取{ 1, 3, 4 }个石子，先取完石子者胜利，那么各个数的SG值为多少？
SG[0]=0，f[]={1,3,4},
x=1 时，可以取走1 - f{1}个石子，剩余{0}个，所以 SG[1] = mex{ SG[0] }= mex{0} = 1;
x=2 时，可以取走2 - f{1}个石子，剩余{1}个，所以 SG[2] = mex{ SG[1] }= mex{1} = 0;
x=3 时，可以取走3 - f{1,3}个石子，剩余{2,0}个，所以 SG[3] = mex{SG[2],SG[0]} = mex{0,0} =1;
x=4 时，可以取走4- &f{1,3,4}个石子，剩余{3,1,0}个，所以 SG[4] = mex{SG[3],SG[1],SG[0]} = mex{1,1,0} = 2;
x=5 时，可以取走5 - f{1,3,4}个石子，剩余{4,2,1}个，所以SG[5] = mex{SG[4],SG[2],SG[1]} =mex{2,0,1} = 3;
以此类推.....
&& x&&&&&&&&0& 1& 2& 3& 4& 5& 6& 7& 8....
SG[x]&&&&0& 1& 0& 1& 2& 3& 2& 0& 1....
由上述实例我们就可以得到SG函数值求解步骤，那么计算1~n的SG函数值步骤如下：
1、使用 数组f 将 可改变当前状态 的方式记录下来。
2、然后我们使用 另一个数组 将当前状态x 的后继状态标记。
3、最后模拟mex运算，也就是我们在标记值中 搜索 未被标记值 的最小值，将其赋值给SG(x)。
4、我们不断的重复 2 - 3 的步骤，就完成了 计算1~n 的函数值。
代码实现如下：
//f[N]:可改变当前状态的方式，N为方式的种类，f[N]要在getSG之前先预处理
//SG[]:0~n的SG函数值
//S[]:为x后继状态的集合
int f[N],SG[MAXN],S[MAXN];
getSG(int n){
memset(SG,0,sizeof(SG));
//因为SG[0]始终等于0，所以i从1开始
for(i = 1; i &= i++){
//每一次都要将上一状态 的 后继集合 重置
memset(S,0,sizeof(S));
for(j = 0; f[j] &= i && j &= N; j++)
S[SG[i-f[j]]] = 1;
//将后继状态的SG函数值进行标记
for(j = 0;; j++) if(!S[j]){
//查询当前后继状态SG值中最小的非零值
现在我们来一个实战演练（题目链接）：
&&&&&& 只要按照上面的思路，解决这个就是分分钟的问题。
代码如下：
#include &stdio.h&
#include &string.h&
#define MAXN 1000 + 10
#define N 20
int f[N],SG[MAXN],S[MAXN];
void getSG(int n){
memset(SG,0,sizeof(SG));
for(i = 1; i &= i++){
memset(S,0,sizeof(S));
for(j = 0; f[j] &= i && j &= N; j++)
S[SG[i-f[j]]] = 1;
for(j = 0;;j++) if(!S[j]){
int main(){
int n,m,k;
f[0] = f[1] = 1;
for(int i = 2; i &= 16; i++)
f[i] = f[i-1] + f[i-2];
getSG(1000);
while(scanf(&%d%d%d&,&m,&n,&k),m||n||k){
if(SG[n]^SG[m]^SG[k]) printf(&Fibo\n&);
else printf(&Nacci\n&);
大家是不是还没有过瘾，那我就在给大家附上一些组合博弈的题目：
POJ 2234 Matches Game
HOJ 2533 Stone II
POJ 2975 Nim
HOJ 1367 A Stone Game
POJ 2505 A multiplication game
ZJU 3057 beans game
POJ 1067 取石子游戏
POJ 2484 A Funny Game
POJ 2425 A Chess Game
POJ 2960 S-Nim
POJ 1704 Georgia and Bob
POJ 1740 A New Stone Game
POJ 2068 Nim
POJ 3480 John
POJ 2348 Euclid's Game
HOJ 2645 WNim
POJ 3710 Christmas Game
POJ 3533 Light Switching Game
（如有错误，欢迎指正，转载注明出处）
12345678910
12345678910
12345678910 上一篇：下一篇：文章评论相关解决方案 1234567891011 Copyright & &&版权所有
