博弈论

N:必胜局面

P:必败局面

巴什博奕

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

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

尼姆博奕

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

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

若k==0则先手必败

否则先手必胜

SG函数

以下内容全摘自PPT

公平组合游戏

若一个游戏满足条件:

  1. 由对阵双方交替行动
  2. 游戏进程的任意时刻,可以执行的合法行动与轮到哪个玩家无关
  3. 不能行动的玩家判负。
  4. 则称这样的游戏为公平组合游戏。

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

以上摘自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函数值,
即: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";
}