[数据结构与算法]博弈论——公平组合游戏ICG

参考自算法进阶指南

公平组合游戏与有向无环图

一个博弈游戏被称为公平组合游戏(ICG)当且仅当其同时满足3个条件

1. 由两名玩家交替行动
2. 游戏任意时刻可进行的操作与轮到哪名玩家无关
3. 不能进行操作的玩家判负

任何一个公平组合游戏都可以用一个有向无环图游戏模型表示
这个有向无环图有唯一的起点，表示游戏初始局面
图中每个结点表示一个局面，有向边表示能从一个局面到达另一个局面
想象初始时起点有一颗棋子，两名玩家轮流沿有向边将棋子移动一步，若某名玩家操作时棋子所在结点已无出边则判负
即分别代表了ICG中玩家交替行动和不能进行操作的玩家判负

SG函数

在有向无环图游戏模型中，对于每个节点$x$，设其后继节点为$y_1,y_2,...,y_k$
定义$$SG(x)=mex(SG(y_1),SG(y_2),...,SG(y_n))$$
其中 m e x ( S ) = m i n x ∈ N , x ? S { x } mex(S)=min_{x \in N, x \notin S }\{x\} mex(S)=minx∈N,x∈/?S?{x}
即$mex(S)$等于不属于集合S的最小非负整数

规定起点为s的有向图游戏G有$SG(G)=SG(s)$

设$G_1,G_2,...,G_k$为k个有向图游戏
若有向图游戏$G$的操作规则为任选某个有向图游戏$G_i$并在$G_i$上行动一次
则$G$被称为$G_1,G_2,...,G_k$的和，有
$$SG(G)=SG(G_1)xorSG(G_2)xor...xorSG(G_n)$$

ICG与SG函数的关系

规定有向图游戏中没有出边的结点$x$有$SG(x)=0$，则有

有向图游戏某个局面$x$必胜，当且仅当$SG(x)>0$
有向图游戏某个局面$x$必负，当且仅当$SG(x)=0$

一个简单的证明如下：
若结点x的某后继节点y有SG(y)=0，则mex运算后一定有SG(x)>0
即处于局面x的玩家只要向局面y移动，则一定能必胜

若结点x的后继节点均有SG(y)>0，则mex运算后一定有SG(x)=0
即处于局面x的玩家无论如何操作都一定会到达必败局面

SG函数的应用

POJ2311 Cutting Game

题目大意：有一张wh的网格纸，每次操作可选择任意一张网格纸，沿格线水平或垂直将纸剪成两张，先剪出11的玩家获胜，在两名玩家均采取最优策略的情况下，先手是否必胜？

题目分析：
首先将该游戏转化为有向图游戏
显然可以让每个结点表示有一张$n?m$网格纸的游戏
那么每次剪切（水平为例）后会产生两个$i?m$ 网格纸和 $(n?i)?m$ 网格纸的新游戏
所以 S G ( n , m ) = m e x ( { S G ( i , m ) ? x o r ? S G ( n ? i , m ) ∣ 2 ≤ i ≤ n ? 2 } ? { S G ( n , i ) ? x o r ? S G ( n , m ? i ) ∣ 2 ≤ i ≤ m ? 2 } ) SG(n,m)=mex(\{SG(i,m)\ xor\ SG(n-i,m)|2\leq i \leq n-2\} \bigcup \{SG(n,i)\ xor\ SG(n,m-i)|2\leq i \leq m-2\}) SG(n,m)=mex({SG(i,m)?xor?SG(n?i,m)∣2≤i≤n?2}?{SG(n,i)?xor?SG(n,m?i)∣2≤i≤m?2})

边界条件$SG(2,2)=SG(2,3)=SG(3,2)=0$
因为2x2,2x3,3x2的网格纸无论怎么剪都会产生1*x的纸，使得对方一定可以剪出1 * 1

#include<iostream>
#include<cstdlib> 
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;

int read()
{
    int f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return x*f;
}

int SG[210][210];

int getSG(int n, int m)
{
	if(SG[n][m]!=-1) return SG[n][m];
	
	int check[250];
	memset(check, 0, sizeof(check));
	
	for(int i=2;i<=n-i;++i)
	{
		int sg=getSG(i,m)^getSG(n-i,m); 
		check[sg]=1;
	}
	
	for(int i=2;i<=m-i;++i)
	{
		int sg=getSG(n,i)^getSG(n,m-i); 
		check[sg]=1;
	}
	
	int mex=0;
	for(int i=0;i<250;++i)
	if(!check[i]){
		mex = i;
		break;
	}
	
	return SG[n][m]=mex;
}

int main()
{	
	memset(SG, -1, sizeof(SG));
	SG[2][2]=SG[2][3]=SG[3][2]=0;
	
	int w,h;
	while(scanf("%d%d",&w,&h)!=EOF)
	{
		if(getSG(w,h)==0) printf("LOSE\n");
		else printf("WIN\n");
	}
	return 0;
}