博弈论总结

 

 1、N-P图

 定义 P 表示的是：走到当前位置时，我的上一个选手必赢的状态，即我在当前回合无论怎么走，都是必败的，故 P 表示的是必败点。

定义 N 表示的是：走到当前位置时，我的上一个选手必输的状态，即我在当前回合中有至少一种走法，能使自己获胜，在双方都聪明的情况下，即我必赢的状态，故 N 表示的是必胜点。

 

换句话就是说：

走到 P 点的人，是必败的；而走到 N 点的人，是必胜的。

对于 N-P 图有以下一些准则：

1、对于 “走不动的选手是输” 的时候，当走到 “无法移动的状态”，即终结态时，标记为 P 点。因为走到终结点的人就无法移动了，是必败态。

2、必败点 P 只能进入到必胜点 N 。

3、必胜点 N 既可以进入必败点 P，也可以进入必胜点 N 。

 

这里我们对上面做一个总结：

1、只能走到 N 点的，是 P 点。

2、同样，如果能走到 P 点，是 N 点。（它不可能是 P 点，因为只有 N 点才能进入 P 点）

2、既能走到 N 点又能走到 P 点的， 是 N 点。

 

这样我们可以通过这三个准则画出一个基本的 NP图了~

 

例题：HDU 2147

题目大意：给你一个 n*m 的棋盘，有一颗棋子在最右上角，两个人只能移动棋子到 左边、下面以及左下角。最后无法移动棋子的人输。在双方足够聪明的情况下，问你先手和后手谁赢。

 

首先， （n，1） 这个点是终结态，无论谁处于这个局势，都将无法移动棋子，则设为 P 。

其次，由于进入 P 点的只能是 N 点，故将 P 的上面一格和右边一格以及右上边一格都设为 N 。因为这三个点都可以一步进入 P 点，而只有 N 点才可以进入 P 点 。

N	N
P	N	A

 

 

再来看，对于下边界：

由于只能往左走（因为棋子能往 左、下、左下走，而对于下边界，其它两种情况不通）。故对于表格中： P N A  ，A 点只能进入 N 点，故 A 是 P 。

对于左边界同理，故我们可以接着画：

　　　　　　　　

P
N
P
N	N
P	N	P	N	P

 

同样，我们对其它格子进行处理可以得到：

P	N	P	N	P
N	N	N	N	N
P	N	P	N	P
N	N	N	N	N
P	N	P	N	P

 

故这就是该题在 5*5 棋盘下的 N-P图了。

对于每一个以 （1，m） 为起点的局势：我们看它是 P 还是 N ，由于在 （1，m） 时，是先手先走，若此时 （1，m） 是 P 态，说明先手此时是 必败态，故这个局势下，先手必败，同样，起点处于 N 态 ，则先手必胜。

我们很容易的发现，如果 n 为奇数且 m 为奇数，则 （1，m） 即起点是 P 态，先手必败，反则必胜。这题就可以解决了~

 

2、巴什博奕

 模型：有两个人，一堆有 n 个石子，每个人每次可以从这一堆拿走 1 ~ m 个石子（包括 1 和 m）。当刚好拿完石子的人获胜。当然两人足够聪明。

 

我们先来看看最基本的局势：若当前石子剩有 m + 1 个，则我无论拿多少个石子，都不会拿完（因为最多拿 m 个）。而无论拿多少个，我拿完后，石子肯定剩余 a 个， a 一定属于  [1，m] ，然后下一个人（即对手）就可以全部拿完了，就输了。

意思就是说，当一个人面对石子有 m + 1 的时候（或 m + 1 的倍数） ，我无论拿多少棋子，拿到最后，我的对手一定可以拿完，则我必输。

故这个博弈就转化成了，如果要赢，我要使对方永远面对石子数为 m + 1 的倍数。

对于一开始：如果 n%（m + 1）== 0 ，即先手处于 （m + 1） 态，则必输，反则必赢。

先手赢的原因是：若 n%（m + 1）！= 0 ，则设 n = k *（m + 1）+ b ，先手一定可以拿走 b 个石子，使得对方处于 （m + 1） 态，使对手必输。

 

变式：题目其它条件不变，若拿完石子的人输，求谁赢。

当： （n - 1）%（m + 1）== 0 时，则先手必输。

原因：我们这么考虑，首先将总石子数去掉 1 个，然后站在后手考虑必赢的情况。

由于取完的输，则在双方绝对聪明情况下，后手如果要赢，则到最后必须要给先手只留下 1 个石子，使先手必须拿完，则先手输。

这就相当于，先拿走 1 个石子，然后使得先手永远处于 （m + 1）态。因为当先手在 m + 1 个石子中取走石子后，后手一定可以取完全部石子。而由于我们当时减去了 1 个石子，故再轮到先手取的时候，就只给他剩下 1 个石子了~

综上，等式证毕。

 

模板题：HDU 2188   HDU  2149   HDU 1846

 

#include<iostream>   // HDU 2188
#include<algorithm>
#include<string.h>
using namespace std;
int t,n,m;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        if(n%(m+1)==0) printf("Rabbit\n");
        else printf("Grass\n");
    }
}


#include<iostream>   // HDU 2149
#include<algorithm>
#include<string.h>
using namespace std;
int n,m;
int main()
{
    while(~scanf("%d%d",&n,&m)){
    if(n%(m+1)==0) printf("none\n");
    else{
        if(n<=m) {
            for(int i=n;i<=m;i++) {
                printf("%d",i);
                if(i!=m) cout<<" ";
                else cout<<endl;
            }
        }
        else{
            printf("%d\n",n%(m+1) );
        }
}
    }
}


#include<iostream>   // HDU 1846
#include<algorithm>
#include<string.h>
using namespace std;
int t,n,m;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        if(n%(m+1)==0) printf("second\n");
        else printf("first\n");
    }
}
 

 

3、威佐夫博奕

 模型：有两个人，两堆石子各有 a b 个石子，每个人可以在一堆中取至少一个石子，或者在两堆中取同样个数的石子（也是每堆中至少一个），最后取完的人获胜。两人足够聪明。

 

这里需要引入一个概念：奇异局势与非奇异局势。

我们分析下最基本的情况：当某人面对的石子状态为（0 , 0）时，则他不可以再取石子了，意思是上一个人已经取完了，故当前的先手已经输了。

同样的，当面对（1 , 2）的选手也已经输了，因为我无论怎么取，下一个选手都可以取完。

上面这种 （0，0）  （1， 2）局势称为奇异局势。可知，当某人面对奇异局势时，则必输。反则必赢，因为任何非奇异局势都可以转化为奇异局势，我可以让对手处于奇异局势。

前几个奇异局势为：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）

我们设局势为（a_k，b_k），则奇异局势的通式为：a_k =[k *（1+√5）/2]，b_k= a_k + k  （k=0，1，2，…,n  且 方括号表示向下取整  仅限于 威佐夫博弈 ）

 下面对“奇异局势”与“非奇异局势”的内容为摘抄部分，原网地址：https://www.cnblogs.com/kuangbin/archive/2011/08/28/2156426.html

1、任何自然数都包含在一个且仅有一个奇异局势中。

由于a_k是未在前面出现过的最小自然数，所以有a_k > a_k - 1 ，而 b_k= a_k + k > a_k - 1 + k - 1 = b_k - 1 > a_k - 1 。所以性质1。成立。

2、任意操作都可将奇异局势变为非奇异局势。

 事实上，若只改变奇异局势（a_k，b_k）的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。如果使（a_k，b_k）的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。
3。采用适当的方法，可以将非奇异局势变为奇异局势。

假设面对的局势是（a,b），若 b = a，则同时从两堆中取走 a 个物体，就变为了奇异局势（0，0）；如果a = a_k ，b > b_k，那么，取走b  – b_k个物体，即变为奇异局势；如果 a = a_k ，  b < b_k ,则同时从两堆中拿走 a_k – a_b + a_k个物体,变为奇异局势（ a_b – a_k , a_b – a_k+ b – a_k）；如果a > a_k ，b= a_k + k,则从第一堆中拿走多余的数量a – a_k 即可；如果a < a_k ，b= a_k + k,分两种情况，第一种，a=a_j （j < k）,从第二堆里面拿走 b – b_j 即可；第二种，a=b_j （j < k）,从第二堆里面拿走 b – a_j 即可。

从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜，因为我可以用一种方式让对方处于奇异局势；反之，则后拿者取胜。

 故判断一开始的石子是否为奇异局势，就可以知道先手是否胜利。

 

模板题：洛谷 P2252

 

#include<iostream>  // 洛谷 P2252
#include<algorithm>
#include<string.h>
#include<cmath>
using namespace std;
typedef long long ll;
ll t,n,m;
int main()
{
    while(~scanf("%lld%lld",&n,&m)){
        if(n>m) swap(n,m);
        ll t=m-n;
        ll temp=t*(sqrt(5.0)+1)/2;
        if(temp==n) printf("0\n");
        else printf("1\n");
    }
}

 

4、斐波那契博弈

 模型：有一堆石子，两个人取石子，满足条件：

1、先手拿任意石子，但是先手第一次不能全部拿完。

2、若前一个人拿了 a 个石子，那么后一个人只能拿 1 ~ 2a 个石子（包括 1 和 2a）。

先拿完的人获胜。两人足够聪明。

 

结论：当石子数为 斐波那契数 时，则该先手必输，反则必赢。

前几个斐波那契数为：1  2  3  5  8  13  21  34

证明：

比如石子数为 2 ，我只能取 1 个石子（因为不能取完），对手直接拿完，则必输。

比如石子数为 3 ，我无论拿多少个石子，对手都能直接拿完，则必输。

比如石子数为 5 ，则我无论拿多少石子，对手都能拿去一些石子，使得我再次处于 “斐波那契数” ，则我必输。

故处于 “斐波那契” 局势的人必输，因为无论拿去多少石子，对手都会再拿去一些石子，使得自己一直处于 “斐波那契” 局势。相反，如果不处于 “斐波那契” 局势，则必可以通过一种方法拿去一些石子，使得对手处于 “斐波那契” 局势。（大家可以自己试试，不是 “斐波那契数” 则一定可以减去一个数，变成 “斐波那契数”）

 

模板题：HDU 2516

 

#include<iostream>　　// HDU 2516
#include<algorithm>
#include<string.h>
#include<map>
using namespace std;
typedef long long ll;
ll n;
map<int,bool> m;
void biao()
{
    ll f1=1,f2=2;
    m[f1]=m[f2]=true;
    for(int i=3;i<=50;i++){
        m[f1+f2]=true;
        ll t =f2;
        f2=f1+f2,f1=t;
    }
}
int main()
{
    biao();
    while(~scanf("%lld",&n)&&n){
        if(!m[n]) printf("First win\n");
        else printf("Second win\n");
}
}

 

5、尼姆博弈

模型：有三堆石子，两个人。每次可以从任意一堆中取石子，至少取一个，数量不限。取完所有石子的人获胜。两人足够聪明。

 

这里又要引入 “奇异局势” 与 “非奇异局势” 的概念。（上面 威佐夫博奕 有提到）

当任何一方处于 “奇异局势” 时，则必输。因为无论他怎么取石子，之后的对手都可以将局势再次转化为 “奇异局势” ，使得先手方必输。

设 （a，b，c） 表示局势状态。则第一个 “奇异局势” 是 （0，0，0），面对该局势的人无法再取，即上一个人已经取完并获胜，则已输。

更特别的 “奇异局势”是 （0，n，n） ，当一方处于该状态时，无论我取哪一堆，拿多少，对手都可以从另一堆再拿走相同个数的石子，使得先手方又进入 （0，m，m）的 “奇异局势” 当中，直到我使局势变成（0，0，0），故我取完，即必赢。（ n > m ）。

意思就是说，对于任意不相等的非负整数 a b ，当某一方面对局势 （0，a，b） 时，石子只要取到两堆相等时，即（0，n，n） ，那么对手就处于 “奇异局势”，故先手必胜。故（0，a，b） 为 “非奇异局势” （a != b）

同样我们可以试着分析到：对于局势 （1，2，3） 也为 “奇异局势” ，因为你无论怎么拿，拿完后对手都可以给你转化为 （0，n，n） 状态。

我们可以发现，对于 尼姆博弈 ，局势为（a，b，c），它的 “奇异局势” 满足 ：a ^ b ^ c == 0 。拓展到 n 堆亦是如此。

那么现在，我们可以判断 “奇异局势” 了，那 “非奇异局势” 是如何转化为 “奇异局势” 的呢？

我们上面知道了， “奇异局势” 与 “非奇异局势” 的特点：

1、“奇异局势” 只能转化为 “非奇异局势” 。（这跟 必败点 只能走到 必胜点 是一个道理，因为对手始终会有方法让你处于 必败 状态）

2、“非奇异局势” 可以通过某种方法转化为 “奇异局势” 。

那对于 尼姆博弈 的 “非奇异局势” 为 （a，b，c）时，如果要将它转化为 “奇异局势” ，即每堆石子数异或起来值为 0 。（设 a <= b <= c 且 为 “非奇异局势”）

而由于任意两个非负整数异或值为 0 ，当且仅当这两个数相等。故如果这里有 a ^ b ^ c 为 0 的话，我们只需要将 c 变成 a ^ b 即可。由于 c 最大，故可以拿去 c - a ^ b 个石子，使得局势转化为 （a，b，a ^ b）的 “奇异局势” ，使得对手必输。

 

模板题：HDU 1849

 

#include<iostream>　　// HDU 1849
#include<algorithm>
#include<string.h>
#include<map>
using namespace std;
typedef long long ll;
ll n,m,ans;
int main()
{
    while(~scanf("%lld",&n)&&n){
        ans=0;
        for(int i=1;i<=n;i++){
        scanf("%lld",&m);
        ans^=m;
    }
    if(!ans) printf("Grass Win!\n");
    else printf("Rabbit Win!\n");
    }
}

 

对 “奇异局势” 与 “非奇异局势” 的总结

经过对上面的学习我们能看出 博弈 的一个核心点，那就是：

每当某方处于 “奇异局势” 时，他只能转化为 “非奇异局势” ，而由于对手足够聪明，所以必能再次将局势转化为 “奇异局势” ，使得先手必输。

这种两两相制的关系，对于 “必败点” 与 “必胜点” 有着异曲同工的妙处。

巴士博弈、斐波那契博弈 也亦是如此。

你会发现，每当先手处于 输的情况（奇异局势），将必败的情况转移出来后（非奇异局势），后手都能再次让先手处于 输的局面（奇异局势）。

故此类博弈的思想就是找出 “奇异局势” ，看 “非奇异局势” 如何转化为 “奇异局势” ，然后对规律总结并码出来。