博弈論 - 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";
}