博弈论 - BuringStraw

博弈论#

N: 必胜局面

P: 必败局面

巴什博奕#

一堆物品有 n 个，两个人轮流拿，每次至少拿 1 个，至多拿 k 个。

则n%(k+1)==0时先手必败其他情况下先手必胜

尼姆博奕#

n 堆物品，第 i 堆数量为a[i]，两人轮流从某一堆里曲任意多的物品

记k=a[1]^a[2]^...^a[n]

若 k==0 则先手必败

否则先手必胜

SG 函数#

以下内容全摘自 PPT

公平组合游戏#

若一个游戏满足条件：

由对阵双方交替行动

游戏进程的任意时刻，可以执行的合法行动与轮到哪个玩家无关

不能行动的玩家判负。

则称这样的游戏为公平组合游戏。

显然，巴什博弈、尼姆博弈都是公平组合游戏，而常见的棋类游戏就不是公平组合游戏，尤其是五子棋（先手有必胜态，不知道吧？）

~~以上摘自 PPT~~

有向图游戏#

给定一个 DAG 图（有向无环），图中有唯一的起点，在起点处放一个棋子，两名玩家交替沿着边的方向移动棋子，每次只能移动一步，无法移动着判负。这样的游戏叫做 “有向图游戏”。
显然，任何的公平组合游戏都可以转化为有向图游戏：我们把每个局面看作节点，当一个局面通过合法行动变成另一个局面时，给这两个局面节点连一条有向边。就像我们画状态转移图一样。

~~摘自 PPT~~

Mex 运算#

设 S 表示一个非负整数集合，定义 Mex (S) 表示求一个不属于 S 的最小非负整数的运算，即：

$mex(S)=min(x),e \in N 且 x \notin S$

~~摘自 PPT~~

SG 函数#

在有向图游戏中，对于每个节点 x,

$若其儿子为y_1,y_2…y_k,定义函数SG(x)，$

其值为 x 的所有儿子的 SG 函数值构成的集合再执行 mex 运算的结果，即：

$SG(x)=mex({SG(y_i)})$

特别的，整个有向图 G 的 SG 函数值被定义为起点 s 的 SG 函数值，
即(G)=SG (s)。令，对于终点 e 有 SG (e)=0。

对于一个状态，若其 SG 值等于 0，则一定是 P 态，否则就是 N 态。

特点#

根据 mex 函数的特点，设 Si 的某个后继节点为 Sj，当 SG (Sj)=0 时，SG (Si) 必然不等于 0，表明当一个局面的后继局面中存在必败局，则该局面必胜。

若 Si 的所有后继节点 Sj, 都有 SG (Sj)!=0，则 SG (Si) 必然等于 0，说明一个局面的全部后继都是必胜局面，则该局面为必败局面。

SG 的求解似乎都需要逆推，因为 SG (终态)=0

有向图游戏和#

定义一个有向图游戏 G，它的每一次行动都可以在 G1,G2…Gm 共 m 个子游戏中选择，这里的 G 就叫做有向图 G1,G2…Gm 的和。则：

$SG(G)=SG(G_1) \; xor \; SG(G_2) \; xor \; ... \; xor \; SG(G_m)$

例题（板子）

移棋子游戏  
题目描述：给定一个有N个节点的DAG图，图中某些节点上有棋子，两名玩家交替移动棋子。玩家每一步可以将任意一颗棋子沿着有向边移动到下一个节点，无法移动者输掉游戏。  
假设双方都足够聪明。问先手必胜还是后手必胜！  
输入：第一行三个整数N,M,K,表示N个节点M条边K个棋子，接下来M行，每行两个整数x,y,代表x节点到y节点的有向边，再接下来K行，表示K个棋子所在的节点编号。  
输出：先手胜则输出“win”，否则输出“lose”  
Hint:N<=2000,M<=6000,1<=K<=N;

还是有点像拓扑
需要一个正图一个反图

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define clear(a) memset(a,0,sizeof(a))
#define max(a,b) (a)>(b)?(a):(b)
using namespace std;

const int MAXN=6005;

int n,m,k;

int chudu[MAXN],qizi[MAXN],v[MAXN],sg[MAXN];

struct tu{
	public:
		int newp;
		int head[MAXN];
		
		struct ed{
			int to,w,nex;
		} e[MAXN];
		
		tu(void){
			clear(head);
			clear(e);
		}
		
		void insert(int p1,int p2){
			++newp;
			e[newp].to=p2;
			e[newp].nex=head[p1];
			//e[newp].w=w;
			head[p1]=newp;
		}
};		

tu a,b;

string solve(void);

int main(void){
	cin>>n>>m>>k;
	for(int i=1;i<=m;++i){
		int x,y;
		cin>>x>>y;
		a.insert(x,y);
		b.insert(y,x);
		++chudu[x];
	}
	for(int i=1;i<=k;++i){
		cin>>qizi[i];
	}
	
	cout<<solve()<<endl;
	return 0;
}

string solve(void){
	queue<int> q;
	for(int i=1;i<=n;++i){
		if(!chudu[i]){
			q.push(i);
		}
	}
	while(!q.empty()){
		clear(v);
		int u=q.front();
		q.pop();
		int maxsg=0;
		for(int i=a.head[u];i;i=a.e[i].nex){
			int y=a.e[i].to;
			maxsg=max(maxsg,sg[y]);
			v[sg[y]]=1;
		}
		
		int i=0;
		while(i<=maxsg+1){
			if(!v[i])break;
			++i;
		}
		sg[u]=i;
		for(int i=b.head[u];i;i=b.e[i].nex){
			--chudu[b.e[i].to];
			if(!chudu[b.e[i].to])q.push(b.e[i].to);
		}
	}
	int ans=sg[qizi[1]];
	for(int i=2;i<=k;++i){
		ans^=sg[qizi[i]];
	}
	if(!ans)return "lose";
	else return "win";
}