各种博弈论详解

鹰击天空同 2023-04-23 发布于山西

展开全文

博弈论

博弈论

理论铺垫：

定义P-position和N-position：其中P代表Previous，N代表Next。直观的说，上一次move的人有必胜策略的局面是P-position，即P-position代表先手必输，N-position代表先手必赢。

1.公平组合博弈(ICG)#

定义：

1.两个人轮流参与； 2.游戏局面有限； 3.同一个局面两个人操作完全相同； 4.无法进行操作的人输； 5.在有限步内结束。

模型：给定一个有向无环图和一个起始顶点上的一枚棋子，两名选手交替的将这枚棋子沿有向边进行移动，无法移动者判负。

解题思路：SG函数（Sprague-Grudy）

SG定理：#

1：给定一个有限子集 S ⊂ N,令mex S为没有出现在S中的最小自然数。例：mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

2：对于一个给定的有向无环图，定义关于图的每个顶点的Sprague-Garundy函数g如下：sg(x)=mex{ sg(y) | y是x的后继 }。即y可以一步操作到x;

SG函数性质：#

1：SG值为0必败态，否则为必胜态

2：对于一个sg(x)=0的顶点x，它的所有后继y都满足g(y)!=0。同理，对于一个sg(x)!=0的顶点，必定存在一个后继y满足g(y)=0。

例：有三堆石子，第一堆石子的可以取1、2、3个石子，则:sg[x] = x % 4；第二堆可以取奇数个石子，则sg[x] = n % 2；第三堆有n个石子，其为Nim博弈，sg值为n，将三堆的sg值全部异或一下，判断是不是0，是0则先手必败（推广到n堆其结论一样适用）。

SG函数求法#

其sg函数可以通过下面的模板来求：

Copy
//f[]：可以取走的石子个数
//sg[]:0~n的SG函数值
//hash[]:mex{}
int f[N],sg[N],hash[N];     
void getSG(int n)
{
    int i,j;
    memset(sg,0,sizeof(sg));
    for(i=1;i<=n;i++)
    {
        memset(hash,0,sizeof(hash));
        for(j=1;f[j]<=i;j++)
            hash[sg[i-f[j]]]=1;
        for(j=0;j<=n;j++)    //求mes{}中未出现的最小的非负整数
        {
            if(hash[j]==0)
            {
                sg[i]=j;
                break;
            }
        }
    }
}

记忆化搜索求SG函数，判断该点的sg值是否为-1，如果是，则调用函数：

Copy
//注意 S数组要按从小到大排序 SG函数要初始化为-1 对于每个集合只需初始化1遍
//n是集合s的大小 f[i]是定义的特殊取法规则的数组
int s[110],sg[10010],n;
void SG_dfs(int x)
{
    int i;
    if(sg[x]!=-1)
        return;
    bool vis[maxn];
    memset(vis,0,sizeof(vis));
    for(i=1;i<=k;i++)
    {
        if(x>=f[i])
        {
            if(sg[x-f[i]]==-1)
                SG_dfs(x-f[i]);
            vis[sg[x-f[i]]]=1;
        }
    }
    int e;
    for(i=0;;i++)
        if(!vis[i])
        {
            sg[x]=i;
            break;
        }
}

AC代码：

Copy
#include<bits/stdc++.h>

using namespace std;
const int maxn=1e4+5;
int f[101],sg[maxn];
int k,T,tot=0,temp,inf;
void SG_dfs(int x)
{
    int i;
    if(sg[x]!=-1)
        return;
    bool vis[maxn];
    memset(vis,0,sizeof(vis));
    for(i=1;i<=k;i++)
    {
        if(x>=f[i])
        {
            if(sg[x-f[i]]==-1)
                SG_dfs(x-f[i]);
            vis[sg[x-f[i]]]=1;
        }
    }
    int e;
    for(i=0;;i++)
        if(!vis[i])
        {
            sg[x]=i;
            break;
        }
}

int main()
{
    //ios::sync_with_stdio(false);
    while(scanf('%d',&k)&&k)
    {
        //memset(f,0,sizeof(f));
        memset(sg,-1,sizeof(sg));
        sg[0]=0;
        for(int i=1;i<=k;++i){
            scanf('%d',&f[i]);
        }
        //sort(f+1,f+k+1);
        scanf('%d',&T);
        while(T--)
        {
            tot=0;
            scanf('%d',&temp);
            for(int i=1;i<=temp;++i){
                scanf('%d',&inf);
                if(sg[inf]==-1)
                    SG_dfs(inf);
                tot^=sg[inf];        
            }
            !tot?cout<<'L':cout<<'W';
        }
        cout<<endl;
    }
    system('pause');
    return 0;
}