博弈論是很有意思的數(shù)學(xué)問題，如果能夠懂其道理，短短幾行代碼就能將其本質(zhì)表示出來。

目前我的感受就是：在一場博弈之中，從結(jié)果向前推，會(huì)出現(xiàn)一個(gè)必?cái)B(tài)，我們需要做的就是推測是先手還是后手能讓對方變成必?cái)B(tài)。

一、巴什博奕（Bash Game）
有一堆n個(gè)物品，A、B兩人輪流從中?。?~m）個(gè)物品，最后取光者獲勝。
逆向思考，當(dāng)對手面對（m+1）這種情況時(shí)，無論如何不能獲勝【一定是m+1】，所以只要你能想辦法讓對手面對k（m+1）這種情況即可，即當(dāng)你面對（k（m+1）+r）時(shí)取走r，易證r<m.

如果開局n=k（m+1），那么先手必輸。
如果開局n=k（m+1）+r，那么先手必贏。

 //A為先手
//N為總數(shù)，K為最多取的個(gè)數(shù)，輸出勝者
#include <cstdio>
int main()
{
    int n;
    int N,K;
    scanf("%d", &n);
    while(n--)
    {
        scanf("%d %d",&N,&K);
        if(N%(K+1)) printf("A\n");
        else printf("B\n");
    }
    return 0;
}

這是最簡單的博弈問題，我們可以思考一下如果將題目改為最后取的人失敗，同時(shí)我們將題目中的取東西的上下限改為更加普遍的（p~q）。
在此，找了一道HDU-2897的題。

//有n個(gè)物品，一次最少取p個(gè)，最多q個(gè)
//問先手是否必贏
#include <stdio.h>
int main()
{
    int n,p,q;
    while(scanf("%d %d %d",&n,&p,&q)==3)
    {
        if(n%(p+q)==0) printf("WIN\n");
        else if(n%(p+q)<=p) printf("LOST\n");
        else printf("WIN\n");
    }
}

當(dāng)n%（p+q）==0時(shí)，先手只需要拿q個(gè)即可必贏。（當(dāng)后手取i個(gè)時(shí)，只需要保證一輪【后-先】取走之和為p+q）
當(dāng)n%（p+q）=k<=p時(shí)，先手拿i個(gè)，后手只需要拿（p+q-i）個(gè)，就能讓最后剩k個(gè)，即先手必輸，即后手必贏。
當(dāng)n%（p+q）=k>=p【n=k*(p+q)+p+r】時(shí)，先手去p個(gè)后，與上種情況剛好相反，先手必贏，即后手必輸。

（將其轉(zhuǎn)換的套路掌握，就可有任意變換）

二、威佐夫博弈（Wythoff Game）
有兩堆各若干的物品兩人輪流從中其中一堆取至少一件物品，至多不限，或從兩堆中同時(shí)取相同件物品，規(guī)定最后取完者勝利。

結(jié)論：若兩堆物品的初始值為（x，y），且x<y,則另z=y-x；
記w=(int)[((sqrt(5)+1)/2)*z]; //變化方式
若w=x，則先手必?cái)?，否則先手必勝?！?/p>

（奇異局）
當(dāng)（0，0）時(shí)，先手必?cái)?，?】
當(dāng)（1，2）時(shí)，先手必?cái)。?】
當(dāng)（3，5）時(shí)，先手必?cái)。?】
當(dāng)（4，7）時(shí)，先手必?cái)?，?】
當(dāng)（6，10）時(shí)，先手必?cái)?，?】
當(dāng)（8，13）時(shí)，先手必?cái)?，?】
當(dāng)（9，15）時(shí)，先手必?cái)?，?】
當(dāng)（11，18）時(shí)，先手必?cái)?，?】
......

#include <cstdio>
#include <cmath>

int main()
{
    long long n1,n2,n,temp;
    scanf("%lld",&n);
    while(n--)
    {
        scanf("%lld %lld",&n1,&n2);
        if(n1>n2)
        {
            temp=n1;
            n1=n2;
            n2=temp;
        }
        temp=(n2-n1)*(1+sqrt(5))/2;
        if(temp==n1) printf("B\n");
        else printf("A\n");
    }
    return 0;
}

提示：1.618=（sqrt（5）+1）/ 2。
勝者只需要將非奇異局變?yōu)槠娈惥旨纯伞?/p>

三、尼姆博弈（Nimm Game）
有任意堆物品，每堆物品的個(gè)數(shù)是任意的，雙方輪流從中取物品，每一次只能從一堆物品中取部分或全部物品，最少取一件，取到最后一件物品的人獲勝。
結(jié)論：將每堆物品全部異或起來，如果得到的值為0，先手必?cái)?，否則先手必勝。

個(gè)人認(rèn)為可以通過逆向判斷，直接判斷奇偶數(shù)（用異或）。

# include<stdio.h>

int main()
{
    int N,n,ans=0;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&N);
        ans=ans^N;
    }
    if(ans) printf("A");
    else printf("B");
    return 0;
}

四、斐波那契博弈
有一堆n個(gè)物品，兩個(gè)人輪流取物品，先手最少取一個(gè)，至多無上限，但不能把物品取完，之后每次取的物品數(shù)量不能超過上一次取的物品數(shù)的兩倍且至少為一件，取走最后一件物品的人獲勝。

結(jié)論：先手勝當(dāng)且僅當(dāng)n不是斐波那契數(shù)（需要存儲(chǔ)斐波那契數(shù)）。

//HDU2516 此時(shí)涵蓋了所有int數(shù)（？？）
#include <stdio.h>

int ans[55];

int main()
{
    int n;
    ans[0]=1;
    ans[1]=1;
    for(int i=2;i<55;i++)
    {
        ans[i]=ans[i-1]+ans[i-2];
    }
    while(scanf("%d",&n)==1 && n)
    {
        int flag=0;
        for(int i=0;i<55;i++)
        {
            if(ans[i]==n)
            {
                flag=1;
                break;
            }
        }
        if(flag) printf("Second win\n");
        else printf("First win\n");
    }
}