博弈概述
博弈論又被稱為對策論（Game Theory）既是現(xiàn)代數(shù)學(xué)的一個新分支，也是運籌學(xué)的一個重要學(xué)科。
博弈論主要研究公式化了的激勵結(jié)構(gòu)間的相互作用。是研究具有斗爭或競爭性質(zhì)現(xiàn)象的數(shù)學(xué)理論和方法。 博弈論考慮游戲中的個體的預(yù)測行為和實際行為，并研究它們的優(yōu)化策略。
組合游戲的定義：
ICG(Impartial Combinatorial Games)
1.有兩個玩家。
2.游戲的操作狀態(tài)是一個有限的集合（比如：限定大小的棋盤）。
3.游戲雙方輪流操作，每次玩家都會進(jìn)行對于自己的最優(yōu)操作。
4.雙方的每次操作必須符合游戲規(guī)定。
5.當(dāng)一方不能將游戲繼續(xù)進(jìn)行的時候，游戲結(jié)束，同時，對方為獲勝方。
6.無論如何操作，游戲總能在有限次操作后結(jié)束。
7.對于游戲的任何一種可能的局面，合法的移動集合只取決于這個局面本身，不取決于輪到哪名選手操作、以前的任何操作、骰子的點數(shù)或者其它什么因素.
（例如象棋就不滿足這個條件，因為紅方因為紅方只能移動紅子，黑方只能移動黑子，合法的移動集合取決于輪到哪名選手操作。）
博弈的做法一般為NP法（判斷必勝態(tài)與必敗態(tài)），與求sg值。對于這兩種方法也需要多練習(xí)才能熟練掌握。
對于博弈，需要記住幾條規(guī)則：
(1) 所有終結(jié)點是必敗點（P點）。
(2) 從任何必勝點（N點）操作，至少有一種方法可以進(jìn)入必敗點（P點）。
(3)無論如何操作， 從必敗點（P點）都只能進(jìn)入必勝點（N點）。
sg函數(shù)簡介（參考自http://baike.baidu.com/view/2855458.htm?fr=aladdin）：
給定一個有向無環(huán)圖和一個起始頂點上的一枚棋子，兩名選手交替的將這枚棋子沿有向邊進(jìn)行移動，無法移 動者判負(fù)。事實上，這個游戲可以認(rèn)為是所有Impartial Combinatorial Games的抽象模型。
也就是說，任何一個ICG都可以通過把每個局面看成一個頂點，對每個局面和它的子局面連一條有向邊來抽象成這個“有向圖游戲”。下面我們就在有向無環(huán)圖的頂點上定義Sprague-Grundy函數(shù)。首先定義mex(minimal excludant)運算，這是施加于一個集合的運算，表示最小的不屬于這個集合的非負(fù)整數(shù)。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
對于一個給定的有向無環(huán)圖，定義關(guān)于圖的每個頂點的Sprague-Grundy函數(shù)g如下：g(x)=mex{ g(y) | y是x的后繼 }。
來看一下SG函數(shù)的性質(zhì)。首先，所有的terminal position所對應(yīng)的頂點，也就是沒有出邊的頂點，其SG值為0，因為它的后繼集合是空集。然后對于一個g(x)=0的頂點x，它的所有前驅(qū)y都滿足 g(y)!=0。對于一個g(x)!=0的頂點，必定存在一個后繼y滿足g(y)=0。
以上這三句話表明，頂點x所代表的postion是P-position當(dāng)且僅當(dāng)g(x)=0（跟P-positioin/N-position的 定義的那三句話是完全對應(yīng)的）。我們通過計算有向無環(huán)圖的每個頂點的SG值，就可以對每種局面找到必勝策略了。但SG函數(shù)的用途遠(yuǎn)沒有這樣簡單。
接下來是做過的一些簡單類型的總結(jié)：
1.巴什博奕.
規(guī)則:只有一堆n個物品,兩個人輪流從這堆物品中取物,規(guī)定每次至少取一個,最多取m個.最后取光者得勝.
分析:當(dāng)物品為m個或者更少時，面對者必然可以一次取完，當(dāng)物品為m+1時，則無論如何，面對該狀態(tài)時，無法取得勝利。那么如果先手面對的不是m+1的倍數(shù)，總能讓后一個人面對m+1的類似狀態(tài)。
答案: 若(m+1) | n，則先手必敗，否則先手必勝.
2. 威佐夫博奕
規(guī)則：有兩堆各若干個物品,兩個人輪流從某一堆或同時從兩堆中取同樣多的物品,規(guī)定每次至少取一個,多者不限,最后取光者得勝.
分析:可以寫出前面幾個必敗的狀態(tài)，發(fā)現(xiàn)為（0,1），（2,3）……則令其形式為（ak,bk），ak為前面沒有出現(xiàn)過的最小自然數(shù),bk為ak+k。（k從1開始）。總結(jié)公式便可得解。
答案:奇異局勢下先手必敗，非奇異局勢下先手必勝。令奇異局為(ak,bk)，滿足ak=[k(1+√5)/2] (向下取整)，bk=ak+k;
關(guān)鍵代碼:
| 1 2 3 4 5 6 | k=b-a; temp=(floor)(k*(1.0+sqrt(5.0))/2.0); if(temp==a) cout<<"0"<<endl;//loser else cout<<"1"<<endl;//winer |
3.尼姆博弈（組合博弈變形來源）
規(guī)則：有三堆各若干個物品,兩個人輪流從某一堆取任意多的物品,規(guī)定每次至少取一個,多者不限,最后取光者得勝.
分析：對于（0,0,0）先手必敗，對于（a,0,0）顯然先手必勝（a!=0），（a,b,0）當(dāng)a=b,顯然后手贏，因為無論先手做出什么樣的操作，后手均可做出同樣操作。（此處便開始異或的思想，如果結(jié)果為0，則會輸。否則總能有一個方式使得異或結(jié)果變?yōu)?）.a!=b時則恰好相反，先手可以將局勢變?yōu)?a,a)或者（b,b）當(dāng)情況為（a,b,c）時，同只有兩種的思想。大部分acm的博弈均來源于尼姆游戲的變形，也意味著異或這個運算在博弈里的重要性。
答案：a^b^c=0，先手必輸，反之必勝。
4.階梯博弈
規(guī)則：游戲開始時有許多硬幣任意分布在樓梯上，共n階樓梯從地面由下向上編號為0到n。游戲者在每次操作時可以將樓梯j(1<=i<=n)上的任意多但至少一個硬幣移動到樓梯j-1上。游戲者輪流操作，將最后一枚硬幣移至地上（0號）的人獲勝。
答案：所有階梯上的硬幣異或后為0先手必敗，反之必勝。
5.圖博弈
規(guī)則：給定一個有向無環(huán)圖，在這些點上放上棋子，兩個人輪流將棋子沿邊移動一步。直到不能移動的人輸。
答案：求各點SG值，異或得解。對于每一個點的sg值，建立邊表，依次求出它的后繼點的sg值。
關(guān)鍵代碼：
?
| 1 2 3 4 5 6 7 8 9 10 11 | int getsg(int x){ int i; //注意i和數(shù)組都定義在里面 if (sg[x]!=-1) return sg[x]; int flag[1010]; memset(flag,0,sizeof(flag)); for (i=head[x];i!=-1;i=edge[i].next)//所有后繼節(jié)點sg flag[deal(edge[i].v)]=1; for (i=0;flag[i];++i);//注意該行分號！求sg[x]=met(); sg[x]=i; return i; } |
6.尼姆游戲變形（1）
規(guī)則：n堆石子，兩個人輪流取，但取的石子數(shù)一定在數(shù)組s{}內(nèi)，例如s{2,5},則兩人每次只能取2或者5個石子，誰先不能操作，誰輸。
答案：求出每堆石子的sg值。
關(guān)鍵代碼：
?
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | int getsg(int x){ int i,temp;//注意i,temp都定義在里面 if(sg[x]!=-1)return sg[x]; bool use[1000];//不能太大！！！ memset(use,false,sizeof(use));//同i,temp for(i=0;i<n;i++){ temp=x-s[i]; if(temp<0)break; sg[temp]=getsg(temp); use[sg[temp]]=true; } for(i=0;use[i];i++);//別漏分號 sg[x]=i; return i; } |
7.尼姆游戲變形（2）
規(guī)則：兩隊人交叉環(huán)繞在桌子旁取一堆石子堆。每個人都有自己可以取的石子的上限。
答案：還是求sg值，只不過改到了2維。sg[i][j]表示第i個人取，還有j塊石頭 。當(dāng)j為0的時候，沒有石頭，這時候是勝，為1。后繼中有必敗態(tài)的為必勝態(tài)
關(guān)鍵代碼：
?
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | Mian函數(shù)中： memset(sg,-1,sizeof(sg)); for(int i=0;i<2*n;i++) sg[i][0]=1; int ans=getsg(0,s); getsg: int getsg(int x,int S){ if(sg[x][S]!=-1) return sg[x][S]; for(int i=1;i<=a[x];i++){ int t=S-i; if(t<0) break; int yy; if(x+1>=2*n) yy=0; else yy=x+1; if(getsg(yy,t)==0) return sg[x][S]=1;//如果后繼必敗。則此時必勝 } return sg[x][S]=0; } |
8.尼姆游戲變形（3）
規(guī)則：給n堆糖，john與brother一次只能吃任一堆糖中的m顆（m>=1），誰吃了最后一堆糖就輸了。
答案：異或為0先手必輸，反之必勝，特判只有一堆糖且數(shù)目為1時先手必輸
9.下棋
規(guī)則：給一個1*M的棋盤，上面有N顆棋子，每次只能向左移動棋子，并且至少移動一步，兩人輪流操作，誰不能移動誰就輸了。注意移動棋子時，棋子之間的相對順序不能改變。
答案：對與每一個棋子的狀態(tài)，由于不能改變棋子的相對順序，所以將棋子兩兩綁成一對，如果前方的棋子移動多少步，后面的棋子一定可以移動那么多步，所以只用考慮一對棋子之間差的步數(shù)。如果棋子是奇數(shù)個，可以把第一個棋子和坐標(biāo)為1的位置綁定為一對。
代碼：ans為0先手必輸，反之必勝
?
| 1 2 3 4 5 6 7 8 9 10 | ans=0; if(n&1){ ans^=a[0]-1; for(i=2;i<n;i++) ans^=a[i]-a[i-1]-1; } else{ for(i=1;i<n;i++) ans^=a[i]-a[i-1]-1; } |
10. 取石子變形（1）
規(guī)則：有N堆石子，兩人輪流進(jìn)行操作，每一次為”操作者指定一堆石子，先從中扔掉一部分（至少一顆，可以全部扔掉），然后可以將該堆剩下的石子中的任意多顆任意移到其他未取完的堆中”，操作者無法完成操作時為負(fù)。
分析：只有一堆時先手必勝。
有兩堆時若兩堆相等則后手只用和先手一樣決策即可保證勝利，后手必勝。若不同則先手可以使其變成相等的兩堆，先手必勝。
有三堆時先手一定可以只用一次決策即可將其變成兩堆相等的局面，（從大的一堆中拿出一部分讓剩下兩堆一樣，剩余丟掉）先手必勝。
有四堆時由于三堆必勝，無論先手后手都想逼對方取完其中一堆，其實這個狀態(tài)就和兩堆時一樣，只有當(dāng)四堆可以分成兩兩相等的兩對時先手才會失敗（后手一直保持和先手相同的操作）。
答案：必敗態(tài)的條件為：堆數(shù)為偶數(shù)（不妨設(shè)為2N），并且可以分為兩兩相等的N對。
11. 取石子變形（2）
規(guī)則：給兩堆石子，兩人依次取石子，規(guī)則是：每次從石子數(shù)較多的那堆取（兩堆石子數(shù)目相等時任選一堆），取的數(shù)目只能為石子少的那一堆的正整數(shù)倍。誰能將一堆變成0就贏。問給定情況下先手勝負(fù)情況。
答案：1.x=y,先手必贏。
2.不妨設(shè)x<y,那么(x+y,y)的下一步必定為(x,y)，所以(x+y,y)和(x,y)的結(jié)果必然相反,其中有一種狀態(tài)可以先手勝，另一種后手勝,對于任意k>=2，狀態(tài)(x+ky,y)可以通過從x+ky那堆去掉(k-1)y個石子變成(x+y,y),也可以通過從x+ky那堆去掉ky個石子變成(x,y),于是這兩種選擇（注意：這是自主的選擇）必然有一種可以獲勝,所以當(dāng)k>=2時(x+ky,y)必勝.
關(guān)鍵代碼：cnt=0,cnt為奇數(shù)，先手必勝，反之必輸。
| 1 2 3 4 5 6 7 | void deal(__int64 n,__int64 m) { cnt++; if(n==m||n>=m*2)return ; deal(m,n-m); } |
當(dāng)然，博弈種類遠(yuǎn)不止如此，有興趣的同學(xué)可以深入學(xué)習(xí)
總結(jié)
