Game theory - BuringStraw

Game Theory#

N: Winning position

P: Losing position

Bash Game#

There are n items in a pile, and two players take turns to take them. Each player can take at least 1 and at most k items each time.

If n%(k+1)==0, the first player will lose; otherwise, the first player will win.

Nim Game#

There are n piles of items, and the number of items in the i-th pile is a[i]. Two players take turns to remove any number of items from one pile.

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

If k is equal to 0, the first player will lose; otherwise, the first player will win.

SG Function#

The following content is taken from the PPT

Fair Combinatorial Games#

If a game satisfies the following conditions:

The two opposing sides take turns to move.

At any point in the game, the available legal moves are independent of which player's turn it is.

The player who cannot move loses.

Then the game is called a fair combinatorial game.

Obviously, Bash Game and Nim Game are both fair combinatorial games, while common board games are not fair combinatorial games, especially Gomoku (Do you know that the first player has a winning strategy?)

~~The above is taken from the PPT~~

Directed Graph Games#

Given a directed acyclic graph (DAG), there is a unique starting point in the graph, and a chess piece is placed at the starting point. Two players take turns to move the chess piece along the direction of the edges. Each time, they can only move one step, and if they cannot move, they lose. This kind of game is called a "directed graph game".
Obviously, any fair combinatorial game can be transformed into a directed graph game: we consider each position as a node, and when one position becomes another position through a legal move, we connect these two positions with a directed edge. Just like drawing a state transition diagram.

~~Taken from the PPT~~

Mex Operation#

Let S represent a non-negative integer set, and define Mex(S) as the operation of finding the smallest non-negative integer that does not belong to S, that is:

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

~~Taken from the PPT~~

SG Function#

In a directed graph game, for each node x,

$if its children are y_1,y_2…y_k, the function SG(x) is defined as follows,$

its value is the set of SG function values of all its children, and then the result of executing the mex operation on this set, that is:

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

In particular, the SG function value of the entire directed graph G is defined as the SG function value of the starting point s,
that is: SG(G)=SG(s). Let SG(e)=0 for the end point e.

For a state, if its SG value is 0, it is definitely a P position; otherwise, it is an N position.

Characteristics#

According to the characteristics of the mex function, if one of Si's successors is Sj and SG(Sj)=0, then SG(Si) must not be 0, indicating that when there is a losing position among the successor positions of a position, the position itself must be a winning position.

If all the successors Sj of Si have SG(Sj)!=0, then SG(Si) must be 0, indicating that all the successors of a position are winning positions, so the position itself is a losing position.

The solution of SG seems to require backward reasoning, because SG(terminal state)=0

Directed Graph Game Sum#

Define a directed graph game G, where each move can be chosen from G1, G2...Gm, which are m subgames. G is called the sum of directed graphs G1, G2...Gm. Then:

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

Example (Template)

Moving Chess Game  
Problem Description: Given a DAG graph with N nodes, some nodes have chess pieces on them, and two players take turns moving the chess pieces. Each player can move any chess piece along the directed edges to the next node, and if they cannot move, they lose the game.  
Assume that both players are smart enough. Determine whether the first player will win or the second player will win!  
Input: The first line contains three integers N, M, K, representing N nodes, M edges, and K chess pieces. The next M lines each contain two integers x and y, representing a directed edge from node x to node y. The next K lines represent the node numbers where the K chess pieces are located.  
Output: If the first player wins, output "win"; otherwise, output "lose".  
Hint: N<=2000, M<=6000, 1<=K<=N;

It's still a bit like topological sorting
Need a positive graph and a negative graph

#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";
}