博弈论基础

╰+哭是因爲堅強的太久メ 2023-05-31 03:20 14阅读 0赞

博弈论总结

# **什么是博弈论：** #

多人进行博弈，假设每个人都采取最优策略，一定有一个人胜出，在知道初态及规则的情况下，求解出

何人胜出的一类问题的理论及方法。

# **博弈论的一些性质** #

P点：必败点，N点：必胜点

（1）无法进行任何移动的局面（也就是terminal position）是P-position；

（2）可以移动到P-position的局面是N-position；

（3）所有移动都导致N-position的局面是P-position。

# **巴什博奕：** #

介绍：只有一堆n个物品，两个人轮流从中取物，规定每次最少取一个，最多取m个，最后取光者为

胜。

必定可以写成该式子 n=k\*(m+1)+r；

结论：若r=0，则先手必败，否则先手必胜。

if(n % (m + 1) == 0)
    
        cout<<"后手必胜"<<endl;
    
    else
    
        cout<<"先手必胜"<<endl;

# **威佐夫博弈：** #

介绍：有两堆各若干的物品，两人轮流从其中一堆取至少一件物品，至多不限，或从两堆中同时取相同

件物品，规定最后取完者胜利。

结论：若两堆物品的初始值为（x，y），且x<y，则另z=y-x；

记w=（int）\[（（sqrt（5）\+1）/2）\*z \]；（中间为熟知的黄金分割比）

若w=x，则先手必败，否则先手必胜。

if(x > y)
    
        swap(x, y);
    
    int c = floor((y - x) * (sqrt(5) + 1) / 2);
    
    if(c == x)
    
        cout<<0<<endl;
    
    else
    
        cout<<1<<endl;

# **尼姆博奕：** #

介绍：有三堆各若干个物品,两个人轮流从某一堆取任意多的物品,规定每次至少取一个,多者不限,最后取

光者得胜.

结论：n堆石子全部做异或运算，结果为0则为必败结果

# **SG****函数：** #

首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非

负整数。例如mex\{0,1,2,4\}=3、mex\{2,3,5\}=0、mex\{\}=0。

对于任意状态 x ， 定义 SG(x) = mex(F)，其中F 是 x 后继状态的SG函数值的集合（就是上述mex中的数

值）。最后返回值（也就是SG(X)）为0为必败点，不为零必胜点。

进一步解释一下F，就是题意中给出的可以移动的次数。举个例子来说，一堆石子，每次只能拿1，3，

5，7个，那么S数组就是1，3，5，7。

假如说是在一个游戏中有多个石子堆该怎么办了。我们只需要把对每个石子堆进行sg函数的调用，将得

到的所有的值进行异或。得出来的结果为0则该情形为必败态。否则为必胜态。

int sg[MAXN];
    int f[MAXM]; //可以取走的石子个数
    bool Hash[MAXN];
    
    void getSG(int m)
    {
        memset(sg, 0, sizeof(sg));
        for (int i = 1; i < MAXN; i++) {//枚举石子的个数
            memset(Hash, false, sizeof(Hash));
            for (int j = 0; j < m && f[j] <= i; j++)
                Hash[sg[i-f[j]]] = true;//枚举每次拿走的个数并标记
            for (int j = 0; j < MAXN; j++) {
                if (!Hash[j]) {
                    sg[i] = j; //找到这个F[](该状态可以达到的状态)中不存在的最小的数
                    break;
                }
            }
        }
    } 
    
    //例题：hdu1847
    int main()
    {
        int n, num = 1;
        for (int i = 0; i < MAXM; num <<= 1, i++)
            f[i] = num;//这里的F数组就是可以移动的步数，每次都是2的幂次
        getSG(MAXM);
        while (cin >> n)
        {
            if (sg[n])
                cout << "Kiki" << endl;
            else
                cout << "Cici" << endl;
        } 
        return 0;
    }