博弈論基礎(chǔ)

博弈論又被稱為對(duì)策論(Game Theory)，既是現(xiàn)代數(shù)學(xué)的一個(gè)新分支，也是運(yùn)籌學(xué)的一個(gè)重要學(xué)科。博弈論主要研究公式化了的激勵(lì)結(jié)構(gòu)間的相互作用，是研究具有斗爭(zhēng)或競(jìng)爭(zhēng)性質(zhì)現(xiàn)象的數(shù)學(xué)理論和方法。博弈論考慮游戲中的個(gè)體的預(yù)測(cè)行為和實(shí)際行為，并研究它們的優(yōu)化策略。

引入：囚徒困境

囚徒困境的故事講的是,兩個(gè)嫌疑犯小A、小B作案后被警察抓住,分別關(guān)在不同的屋子里接受審訊。警察知道兩人有罪,但缺乏足夠的證據(jù)。警察告訴每個(gè)人:如果兩人都抵賴,各判刑一年;如果兩人都坦白,各判五年;如果兩人中一個(gè)坦白而另一個(gè)抵賴,坦白的放出去,抵賴的判十年。

于是,每個(gè)囚徒都面臨兩種選擇:坦白或抵賴。

在不和小B商量的情況下，作為小A的你是選擇招供坐牢5年或0年，還是會(huì)選擇抵賴坐牢10年或1年呢？

一般的人都會(huì)選著保險(xiǎn)一點(diǎn)的招供吧。

反觀小B，也一定會(huì)做出同樣的選擇，也就是招供。換句話說(shuō)，只要兩名囚徒都是自私且理性的，那么雙方都會(huì)同時(shí)選擇招供，結(jié)果就是雙方各判5年。

在這個(gè)場(chǎng)景中，雙方都無(wú)法單方面改變自己的博弈策略（單方面改變只會(huì)讓自己蒙受損失），使得局面進(jìn)入了一個(gè)微妙而又穩(wěn)定的平衡，這個(gè)平衡被稱為納什均衡。

在現(xiàn)實(shí)中,也有很多類似的現(xiàn)象,比如家長(zhǎng)給孩子報(bào)越來(lái)越多的課外班,比如高三考生備戰(zhàn)高考,卷起來(lái)了啊.從局外人看來(lái),許多競(jìng)爭(zhēng)都是顯而易見(jiàn)雙輸?shù)木置?但是我們沒(méi)有辦法,因?yàn)槲覀兌际菂⑴c博弈的“囚徒”。

ICG博弈

所討論的博弈問(wèn)題滿足以下條件：

玩家只有兩個(gè)人，輪流做出決策。

游戲的狀態(tài)集有限，保證游戲在有限步后結(jié)束，這樣必然會(huì)產(chǎn)生不能操作者，其輸。

對(duì)任何一種局面，勝負(fù)只決定于局面本身，而與輪到哪位選手無(wú)關(guān)。

取石子游戲：取石子游戲是一個(gè)古老的博弈游戲，發(fā)源于中國(guó)，它是組合數(shù)學(xué)領(lǐng)域的一個(gè)經(jīng)典問(wèn)題。它有許多不同的玩法，基本上是兩個(gè)玩家，玩的形式是輪流抓石子，勝利的標(biāo)準(zhǔn)是抓走最后的石子。玩家設(shè)定：先取石子的是玩家A（先手A），后取石子的是玩家B（后手B）。

經(jīng)典的三種玩法

一、巴什博奕(Bash Game)

二、尼姆博奕(Nimm Game)

三、威佐夫博奕(Wythoff Game)

（一）巴什博弈

1堆n個(gè)石子每次最多取m個(gè)、至少取1個(gè)

Case 1:如果n=m+1，那么由于一次最多只能取m個(gè)，所以，無(wú)論先取者拿走多少個(gè)，后取者都能夠一次拿走剩余的物品，后者取勝。

Case 2:n=(m+1)*r+s，(r為任意自然數(shù)，s≤m),那么先取者要拿走s個(gè)物品，如果后者拿走k(1≤k≤m)個(gè)，那么先取者再拿走m+1-k個(gè)，結(jié)果剩下(m+1)(r-1)個(gè)，以后保持這樣的取法，那么先取者肯定獲勝。

Case 3:n=r*(m+1)，先手拿走k(1≤k≤m)個(gè)，那么后手再拿走m+1-k個(gè)，結(jié)果剩下(m+1)(r-1)個(gè)，以后保持這樣的取法，則后手勝，先手必?cái)　?/p>

總之，要保持給對(duì)手留下（m+1）的倍數(shù)，就能最后獲勝。

術(shù)語(yǔ):正經(jīng)人稱(m+1)的局面為奇異局勢(shì)

變相的玩法

兩個(gè)人輪流報(bào)數(shù)，每次至少報(bào)一個(gè)，最多報(bào)十個(gè)，誰(shuí)能報(bào)到100者勝。（等價(jià)于從一堆100個(gè)石子中取石子，最后取完的勝）

例題：2368 — Buttons (poj.org)

題面：

題面意思：有一堆k個(gè)的石頭，每人輪流拿1,2，..L個(gè)石頭，數(shù)據(jù)范圍是3 <= K <= 100 000 000 ，2 <= L < K。輸入k的值，要求輸出最小的L，使得后者勝。

在理解了巴什博弈之后來(lái)看這題還是思路比較清晰的，首先想讓后手勝，就必須把（1+L）的局面留給先手。這題沒(méi)問(wèn)我們誰(shuí)會(huì)贏，問(wèn)的是后手要贏的最小L值為多少。那我們就找到能被k整除的最小大于2的因數(shù)，之后減1輸出就是答案了。

于是有了以下代碼注意下（poj用不了萬(wàn)能頭文件，編譯器要求有點(diǎn)嚴(yán)格。）：

//#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=100005;
ll n;//石子數(shù)量
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    ll i;
    for(i=2;i<n;i++)//依次找最小的因子
    {
        if(n%(i+1)==0)
        {
            cout<<i<<endl;
            break;
        }
    }
    if(i==n) cout<<0<<endl;//找不到的情況下輸出0
    return 0;
}

就是說(shuō)數(shù)據(jù)范圍1e8，就超時(shí)快樂(lè)，TEL了哈哈哈哈哈哈。由于循環(huán)2~n，時(shí)間復(fù)雜度是O(n)。

再有一個(gè)新的思路就是，遍歷一遍所有的n的因數(shù)，存起來(lái)，在輸出最小大于等于3的因數(shù)減一。一下代碼時(shí)間復(fù)雜度為O(log n)。AC快樂(lè)。

//#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long ll;
const int N=100005;
ll n,a[N];//n為石頭總數(shù)，a[i]存n的因數(shù)
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    int temp=0;
    for(int i=1;i*i<=n;i++)
    {
        if(n%i==0&&i*i!=n) a[temp++]=i,a[temp++]=n/i;
        //注意要區(qū)別開(kāi)類似n=4時(shí)，因數(shù)為1,2,4.而不是1,2,2,4的情況
        else if(n%i==0&&i*i==n) a[temp++]=i;
    }
    sort(a,a+temp);//從小到大排序一下
    for(int i=0;i<temp;i++)
    {
        if(a[i]>=3)//找到最小大于等于3的因數(shù)，減一輸出
        {
            cout<<a[i]-1<<endl;
            break;
        }
    }
    return 0;
}

（二）尼姆博弈

有n堆石子，每堆石子的數(shù)量是a1,a2,a3……，二個(gè)人依次從這些石子堆中的一個(gè)拿取任意的石子，至少一個(gè)，最后一個(gè)拿光石子的人勝利

n=1: 先手全拿，先手必勝。

n=2:有兩種情況，一種可能相同，一種情況一堆比另一堆少（多）

(m,m) 按照“有一學(xué)一，照貓畫(huà)貓”法，先手必輸。

(m,M)先手先從多的一堆中拿出(M-m)個(gè)，此時(shí)后手面對(duì)(m,m)的局面先手必勝。

術(shù)語(yǔ):正經(jīng)人稱(m,m)的局面為奇異局勢(shì)

n=3:(m,m,M)先手必勝局，先手可以先拿M,之后變成了(m,m,0)的局面，是不是很熟悉~

(a1,a2,a3)的話，舉個(gè)例子(1,2,3),先手取完之后可能的局面為(0,2,3),(1,1,3),(1,0,3),(1,2,2),(1,2,1),(1,2,0)都是之前講過(guò)的，情況如下：

前人告訴我們的規(guī)律是：異或的結(jié)果均為0

獲勝情況的討論

面對(duì)異或結(jié)果為0的玩家必輸。

結(jié)果不為0，則玩家有獲勝的取法。

例題：891. Nim游戲 – AcWing題庫(kù)

題面：

看懂了尼姆博奕，這個(gè)題目就是分分鐘AC咯。

上代碼：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
ll n,a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    int ans=a[0];
    for(int i=1;i<n;i++) ans^=a[i];//^就是做異或運(yùn)算
    if(ans==0) cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    return 0;
}

(三)威佐夫博弈

有兩堆各若干個(gè)物品，兩個(gè)人輪流從任一堆取至少一個(gè)或同時(shí)從兩堆中取同樣多的物品，規(guī)定每次至少取一個(gè)，多者不限，最后取光者得勝。

舉一個(gè)例子:局勢(shì)是(1,2)，先手有四種取法，動(dòng)動(dòng)你聰明的腦子就會(huì)發(fā)現(xiàn)無(wú)論先手怎么取，后手都能勝利，也就是說(shuō)(1,2)是奇異局勢(shì)。

沒(méi)腦子的人來(lái)看看分析咯：

先手從第一堆里面拿1個(gè)，后者拿光后面的2個(gè)，后者勝。

先手從第一堆和第二堆里面同時(shí)拿1個(gè)，后者只能拿走第二堆剩下的1個(gè)，后者勝。

先手從第二堆里面拿2個(gè)，后手拿走第一堆的1個(gè)，后者勝.

先手從第二堆里面拿1個(gè)，后手從第一堆和第二堆里面同時(shí)拿走1個(gè)，后者勝。

假設(shè)現(xiàn)在的局勢(shì)是（3,5)：

（1）先手在“3”中取1個(gè)，后手就可以在“5”中取走4個(gè)，這樣就變成了（1，2）的局勢(shì)

（2）先手在“3”中取2個(gè)，后手就可以在 “5” 中取走3個(gè)，這樣也變成了（1,2）的局勢(shì)

（3）先手在“5”中取1個(gè)，后手就在 “3”和“5” 中各取走2個(gè)，這樣成了（1，2）的局勢(shì)

（4）先手在”5”中取2個(gè),后手就在 “3”和”5”中各取走3個(gè),這樣變成了(0，0)的局勢(shì)，先手輸

（5）先手在“5”中取3個(gè)，后手就在 “3”和“5” 中各取走1個(gè)，也變成了（1，2）的局勢(shì)

（6）先手在“5”中取4個(gè)，后手在“3”中取走1個(gè)，還是（1，2）的局勢(shì)

我們可以來(lái)找找那些先手必輸局勢(shì)的規(guī)律（奇異局勢(shì)）

• 第一種（0，0）
• 第二種（1，2）
• 第三種（3，5）
• 第四種 (4 ，7）
• 第五種（6，10）
• 第六種 (8，13）
• 第七種 (9 ，15）
• 第八種 (11 ，18）
• 第n種（a，b）

我們會(huì)發(fā)現(xiàn)他們的差值是遞增的，分別是0,1,2,3,4,5,6,7……n

還有一個(gè)規(guī)律(正常人都發(fā)現(xiàn)不了):a=(b-a)*1.618向下取整

就是：a = int(b – a)*1.618

注：這里的int是強(qiáng)制類型轉(zhuǎn)換，注意這不是簡(jiǎn)單的四舍五入，假如后面的值是3.9，轉(zhuǎn)換以后得到的不是4而是3，也就是說(shuō)強(qiáng)制int類型轉(zhuǎn)換得到的是不大于這個(gè)數(shù)值的最大整數(shù)。

有些題目要求精度較高，我們可以用下述式子來(lái)表示這個(gè)值:

1.618 = (sqrt(5.0) + 1) / 2

頭文件：include<math.h>

例題：1067 — 取石子游戲 (poj.org)

題面：

代碼：

//#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long ll;
const int N=100005;
ll a,b;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while(cin>>a>>b)//多組輸入！！！
    {
        double flag= (sqrt(5.0) + 1) / 2.0;//精度高一些用double來(lái)存1.618
        if(a>b) swap(a,b);//保證b要比a大，后面有用到b-a
        if(a==int((b-a)*flag))cout<<0<<endl;//先手面對(duì)奇異局勢(shì)必輸
        else cout<<1<<endl;
    }

    return 0;
}

總結(jié)

以上是生活随笔為你收集整理的数学知识——博弈论（巴什博奕、尼姆博奕、威佐夫博奕）思路及例题「建议收藏」的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。