title: Game Theory (II)
date : 2021-11-6
Tags: ACM, mathematics, game theory
author : Linno

Pre cheese - SG function

You can see my last blog: https://blog.csdn.net/SC_Linno/article/details/121181361

Firstly, an ICG game model is given. Given a directed acyclic graph and a piece on a starting vertex, two players alternately move the piece along the directed edge, and those who cannot move are judged negative.

Transform the ICG problem: any ICG can be abstracted into this "directed graph game" by treating each situation as a vertex and connecting a directed edge to each situation and its sub situation.

So we can convert the ICG problem into the above game, and then solve the ICG problem by looking for the solution of the game.

First, we define the mex (minimal exclusive) operation, which is applied to a set and represents the smallest nonnegative integer that does not belong to the set. For example, mex{0,1,2,4}=3,mex{2,3,5}=0,mex{}=0;

For a given directed acyclic graph, the SG function for each vertex of the graph is defined as follows:

sg(x)=mex{sg(y)|y is the successor of X}

step

1, Find out the failure state (SG value is 0)

2, Find the precursor nodes in all current states

3, Calculate node SG value according to definition

Repeat the above steps until the whole tree is established

SG theorem

The SG function value of the sum of the game is the XOR of the SG function values of all its sub games.

Therefore, when we face a game composed of n different games, we only need to find the SG function value of each game, regard all these SG values as Nim's stone pile, and then find the winning strategy of the game according to the method of finding Nim's winning strategy.

Coin flipping problem

Problem description

N coins in a row, some face up, some reverse up. Players turn over coins according to certain constraints (only one or two coins can be turned at a time, or only several consecutive coins can be turned). Who can't turn over will lose.

conclusion

The SG value of the situation is the exclusive or sum of the SG value when each face up chess piece in the situation exists alone. The SG value for any coin is 2 k 2^k 2k (k is the coin number)

Delete edge from tree

Green Hachenbush

Both sides delete edges in a tree in turn, and the parts that are no longer connected to the root node will be removed. There are many trees in the game. Finally, the player who cannot delete the edge fails.

If all the trees in this game are "bamboo" without branches, it will become an ordinary Nim game. At this time, SG[x]=x. when we know the Krone principle, we can turn all branches into a bamboo into an ordinary Nim game.

Colon Principle

For a certain point in the tree, the branch of ta can be transformed into a bamboo rooted at this point. The length of the bamboo is the XOR sum of the number of edges of each branch of ta.

Edge deletion on graph

Feisen principle

(the points on the ring can be fused without changing the SG value of the graph.)

Generally speaking, a ring with odd edges can be equivalent to an endpoint and an edge, while a ring with even edges is equivalent to a point.

Christmas Game

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N=1007;
const int mod=1e9+7;

vector<int>G[N];
inline void addedge(int u,int v){
	G[u].push_back(v);
	G[v].push_back(u);
}

int n,m,u,v,k,vis[N],SG[N];
int stk[N],top;

void dfs(int x,int fa){
	stk[++top]=x;
	vis[x]=1;
	SG[x]=0;
	bool flag=0;
	for(int i=0;i<G[x].size();i++){
		int to=G[x][i];
		if(to==fa&&!flag){flag=1;continue;} //Connect to parent node for the first time
		if(vis[to]==1){
			int cnt=1,y=x;
			while(y!=to) cnt++,vis[y]=-1,y=stk[--top];
			if(cnt&1) SG[y]^=1; //Odd ring 
		}else if(!vis[to]){
			dfs(to,x);
			if(~vis[to]) SG[x]^=(SG[to]+1); //Only those not on the ring can be updated 
		}
	}
	if(~vis[x]) --top;
} 

signed main(){
	while(cin>>n){
		int ans=0;
		for(int p=1;p<=n;p++){
			cin>>m>>k;
			for(int i=1;i<=m;i++) G[i].clear(),vis[i]=0;
			for(int i=1;i<=k;i++){
				cin>>u>>v;
				addedge(u,v);
			}
			dfs(1,0);
			ans^=SG[1];
		}
		if(ans) puts("Sally");
		else puts("Harry");
		
	}
	return 0;
}

reference material

https://blog.csdn.net/wu_tongtong/article/details/79311284

https://www.cnblogs.com/maoyiting/p/14169209.html#/cnblog/works/article/14169209

Brief introduction to combinatorial Games -- on some expansion and deformation of SG games