原帖地址：
http://www.wutianqi.com/?p=1081
以下是我從網(wǎng)上收集的關(guān)于組合博弈的資料匯總：
有一種很有意思的游戲，就是有物體若干堆，可以是火柴棍或是圍棋子等等均可。兩個
人輪流從堆中取物體若干，規(guī)定最后取光物體者取勝。這是我國民間很古老的一個游戲
，別看這游戲極其簡單，卻蘊含著深刻的數(shù)學(xué)原理。下面我們來分析一下要如何才能夠
取勝。
（一）巴什博奕（Bash Game）：只有一堆n個物品，兩個人輪流從這堆物品中取物，規(guī)
定每次至少取一個，最多取m個。最后取光者得勝。
顯然，如果n=m+1，那么由于一次最多只能取m個，所以，無論先取者拿走多少個，
后取者都能夠一次拿走剩余的物品，后者取勝。因此我們發(fā)現(xiàn)了如何取勝的法則：如果
n=（m+1）r+s，（r為任意自然數(shù)，s≤m),那么先取者要拿走s個物品，如果后取者拿走
k（≤m)個，那么先取者再拿走m+1-k個，結(jié)果剩下（m+1）（r-1）個，以后保持這樣的
取法，那么先取者肯定獲勝。總之，要保持給對手留下（m+1）的倍數(shù)，就能最后獲勝。
這個游戲還可以有一種變相的玩法：兩個人輪流報數(shù)，每次至少報一個，最多報十
個，誰能報到100者勝。
（二）威佐夫博奕（Wythoff Game）：有兩堆各若干個物品，兩個人輪流從某一堆或同
時從兩堆中取同樣多的物品，規(guī)定每次至少取一個，多者不限，最后取光者得勝。
這種情況下是頗為復(fù)雜的。我們用（ak，bk）（ak ≤ bk ,k=0，1，2，…,n)表示
兩堆物品的數(shù)量并稱其為局勢，如果甲面對（0，0），那么甲已經(jīng)輸了，這種局勢我們
稱為奇異局勢。前幾個奇異局勢是：（0，0）、（1，2）、（3，5）、（4，7）、（6，
10）、（8，13）、（9，15）、（11，18）、（12，20）。
可以看出,a0=b0=0,ak是未在前面出現(xiàn)過的最小自然數(shù),而 bk= ak + k，奇異局勢有
如下三條性質(zhì)：
1。任何自然數(shù)都包含在一個且僅有一個奇異局勢中。
由于ak是未在前面出現(xiàn)過的最小自然數(shù)，所以有ak > ak-1 ，而 bk= ak + k > ak
-1 + k-1 = bk-1 > ak-1 。所以性質(zhì)1。成立。
2。任意操作都可將奇異局勢變?yōu)榉瞧娈惥謩荨?br> 事實上，若只改變奇異局勢（ak，bk）的某一個分量，那么另一個分量不可能在其
他奇異局勢中，所以必然是非奇異局勢。如果使（ak，bk）的兩個分量同時減少，則由
于其差不變，且不可能是其他奇異局勢的差，因此也是非奇異局勢。
3。采用適當?shù)姆椒ǎ梢詫⒎瞧娈惥謩葑優(yōu)槠娈惥謩荨?/p>
假設(shè)面對的局勢是（a,b），若 b = a，則同時從兩堆中取走 a 個物體，就變?yōu)榱?br>奇異局勢（0，0）；如果a = ak ，b > bk，那么，取走b – bk個物體，即變?yōu)槠娈惥?br>勢；如果 a = ak ， b < bk ,則同時從兩堆中拿走 ak – ab – ak個物體,變?yōu)槠娈惥?br>勢（ ab – ak , ab – ak+ b – ak）；如果a > ak ，b= ak + k,則從第一堆中拿走多余
的數(shù)量a – ak 即可；如果a < ak ，b= ak + k,分兩種情況，第一種，a=aj （j < k）
,從第二堆里面拿走 b – bj 即可；第二種，a=bj （j < k）,從第二堆里面拿走 b – a
j 即可。
從如上性質(zhì)可知，兩個人如果都采用正確操作，那么面對非奇異局勢，先拿者必勝
；反之，則后拿者取勝。
那么任給一個局勢（a，b），怎樣判斷它是不是奇異局勢呢？我們有如下公式：
ak =[k（1+√5）/2]，bk= ak + k （k=0，1，2，…,n 方括號表示取整函數(shù))
奇妙的是其中出現(xiàn)了黃金分割數(shù)（1+√5）/2 = 1。618…,因此,由ak，bk組成的矩形近
似為黃金矩形，由于2/（1+√5）=（√5-1）/2，可以先求出j=[a（√5-1）/2]，若a=[
j（1+√5）/2]，那么a = aj，bj = aj + j，若不等于，那么a = aj+1，bj+1 = aj+1
+ j + 1，若都不是，那么就不是奇異局勢。然后再按照上述法則進行，一定會遇到奇異
局勢。
（三）尼姆博奕（Nimm Game）：有三堆各若干個物品，兩個人輪流從某一堆取任意多的
物品，規(guī)定每次至少取一個，多者不限，最后取光者得勝。
這種情況最有意思，它與二進制有密切關(guān)系，我們用（a，b，c）表示某種局勢，首
先（0，0，0）顯然是奇異局勢，無論誰面對奇異局勢，都必然失敗。第二種奇異局勢是
（0，n，n），只要與對手拿走一樣多的物品，最后都將導(dǎo)致（0，0，0）。仔細分析一
下，（1，2，3）也是奇異局勢，無論對手如何拿，接下來都可以變?yōu)椋?，n，n）的情
形。
計算機算法里面有一種叫做按位模2加，也叫做異或的運算，我們用符號（+）表示
這種運算。這種運算和一般加法不同的一點是1+1=0。先看（1，2，3）的按位模2加的結(jié)
果：
1 =二進制01
2 =二進制10
3 =二進制11 （+）
———————
0 =二進制00 （注意不進位）
對于奇異局勢（0，n，n）也一樣，結(jié)果也是0。
任何奇異局勢（a，b，c）都有a（+）b（+）c =0。
如果我們面對的是一個非奇異局勢（a，b，c），要如何變?yōu)槠娈惥謩菽兀考僭O(shè) a < b
< c,我們只要將 c 變?yōu)?a（+）b,即可,因為有如下的運算結(jié)果: a（+）b（+）(a（+）
b)=(a（+）a)（+）(b（+）b)=0（+）0=0。要將c 變?yōu)閍（+）b，只要從 c中減去 c-（
a（+）b）即可。
例1。（14，21，39），14（+）21=27，39-27=12，所以從39中拿走12個物體即可達
到奇異局勢（14，21，27）。
例2。（55，81，121），55（+）81=102，121-102=19，所以從121中拿走19個物品
就形成了奇異局勢（55，81，102）。
例3。（29，45，58），29（+）45=48，58-48=10，從58中拿走10個，變?yōu)椋?9，4
5，48）。
例4。我們來實際進行一盤比賽看看：
甲:(7,8,9)->(1,8,9)奇異局勢
乙:(1,8,9)->(1,8,4)
甲:(1,8,4)->(1,5,4)奇異局勢
乙:(1,5,4)->(1,4,4)
甲:(1,4,4)->(0,4,4)奇異局勢
乙:(0,4,4)->(0,4,2)
甲:(0.4,2)->(0,2,2)奇異局勢
乙:(0,2,2)->(0,2,1)
甲:(0,2,1)->(0,1,1)奇異局勢
乙:(0,1,1)->(0,1,0)
甲:(0,1,0)->(0,0,0)奇異局勢
甲勝。
取火柴的游戲
題目1：今有若干堆火柴，兩人依次從中拿取，規(guī)定每次只能從一堆中取若干根，
可將一堆全取走，但不可不取，最后取完者為勝，求必勝的方法。
題目2：今有若干堆火柴，兩人依次從中拿取，規(guī)定每次只能從一堆中取若干根，
可將一堆全取走，但不可不取，最后取完者為負，求必勝的方法。
嘿嘿，這個游戲我早就見識過了。小時候用珠算玩這個游戲：第一檔撥一個，第二檔撥兩個，依次直到第五檔撥五個。然后兩個人就輪流再把棋子撥下來，誰要是最后一個撥誰就贏。有一次暑假看見兩個小孩子在玩這個游戲，我就在想有沒有一個定論呢。下面就來試著證明一下吧
先解決第一個問題吧。
定義：若所有火柴數(shù)異或為0，則該狀態(tài)被稱為利他態(tài)，用字母T表示；否則，
為利己態(tài)，用S表示。
[定理1]：對于任何一個S態(tài)，總能從一堆火柴中取出若干個使之成為T態(tài)。
證明：
若有n堆火柴，每堆火柴有A(i)根火柴數(shù)，那么既然現(xiàn)在處于S態(tài)，
c = A(1) xor A(2) xor … xor A(n) > 0;
把c表示成二進制，記它的二進制數(shù)的最高位為第p位，則必然存在一個A(t),它二進制的第p位也是1。（否則，若所有的A(i)的第p位都是0，這與c的第p位就也為0矛盾）。
那么我們把x = A(t) xor c,則得到x < A(t).這是因為既然A(t)的第p位與c的第p位同為1,那么x的第p位變?yōu)?,而高于p的位并沒有改變。所以x < A(t).而
A(1) xor A(2) xor … xor x xor … xor A(n)
= A(1) xor A(2) xor … xor A(t) xor c xor … xor A(n)
= A(1) xor A(2) xor… xor A(n) xor A(1) xor A(2) xor … xor A(n)
= 0
這就是說從A(t)堆中取出 A(t) – x 根火柴后狀態(tài)就會從S態(tài)變?yōu)門態(tài)。證畢
[定理2]：T態(tài)，取任何一堆的若干根，都將成為S態(tài)。
證明：用反證法試試。
若
c = A(1) xor A(2) xor … xor A(i) xor … xor A(n) = 0；
c’ = A(1) xor A(2) xor … xor A(i’) xor c xor … xor A(n) = 0;
則有
c xor c’ = A(1) xor A(2) xor … xor A(i) xor … xor A(n) xor A(1) xor A(2) xor … xor A(i’) xor c xor … xor A(n) = A(i) xor A(i’) =0
進而推出A(i) = A(i’)，這與已知矛盾。所以命題得證。
[定理 3]：S態(tài)，只要方法正確，必贏。
最終勝利即由S態(tài)轉(zhuǎn)變?yōu)門態(tài)，任何一個S態(tài)，只要把它變?yōu)門態(tài)，（由定理1，可以把它變成T態(tài)。）對方只能把T態(tài)轉(zhuǎn)變?yōu)镾態(tài)(定理2)。這樣，所有S態(tài)向T態(tài)的轉(zhuǎn)變都可以有己方控制，對方只能被動地實現(xiàn)由T態(tài)轉(zhuǎn)變?yōu)镾態(tài)。故S態(tài)必贏。
[定理4]：T態(tài)，只要對方法正確，必敗。
由定理3易得。
接著來解決第二個問題。
定義：若一堆中僅有1根火柴，則被稱為孤單堆。若大于1根，則稱為充裕堆。
定義：T態(tài)中，若充裕堆的堆數(shù)大于等于2，則稱為完全利他態(tài)，用T2表示；若充裕堆的堆數(shù)等于0，則稱為部分利他態(tài)，用T0表示。
孤單堆的根數(shù)異或只會影響二進制的最后一位，但充裕堆會影響高位（非最后一位）。一個充裕堆，高位必有一位不為0，則所有根數(shù)異或不為0。故不會是T態(tài)。
[定理5]：S0態(tài)，即僅有奇數(shù)個孤單堆，必敗。T0態(tài)必勝。
證明：
S0態(tài)，其實就是每次只能取一根。每次第奇數(shù)根都由己取，第偶數(shù)根都由對
方取，所以最后一根必己取。敗。同理, T0態(tài)必勝#
[定理6]：S1態(tài)，只要方法正確，必勝。
證明：
若此時孤單堆堆數(shù)為奇數(shù)，把充裕堆取完；否則，取成一根。這樣，就變成奇數(shù)個孤單堆，由對方取。由定理5，對方必輸。己必勝。 #
[定理7]：S2態(tài)不可轉(zhuǎn)一次變?yōu)門0態(tài)。
證明：
充裕堆數(shù)不可能一次由2變?yōu)?。得證。 #
[定理8]：S2態(tài)可一次轉(zhuǎn)變?yōu)門2態(tài)。
證明：
由定理1，S態(tài)可轉(zhuǎn)變?yōu)門態(tài)，態(tài)可一次轉(zhuǎn)變?yōu)門態(tài)，又由定理6，S2態(tài)不可轉(zhuǎn)一次變?yōu)門0態(tài)，所以轉(zhuǎn)變的T態(tài)為T2態(tài)。 #
[定理9]：T2態(tài)，只能轉(zhuǎn)變?yōu)镾2態(tài)或S1態(tài)。
證明：
由定理2，T態(tài)必然變?yōu)镾態(tài)。由于充裕堆數(shù)不可能一次由2變?yōu)?，所以此時的S態(tài)不可能為S0態(tài)。命題得證。
[定理10]：S2態(tài)，只要方法正確，必勝.
證明：
方法如下：
1） S2態(tài)，就把它變?yōu)門2態(tài)。（由定理8）
2） 對方只能T2轉(zhuǎn)變成S2態(tài)或S1態(tài)（定理9）
若轉(zhuǎn)變?yōu)镾2, 轉(zhuǎn)向1）
若轉(zhuǎn)變?yōu)镾1, 這己必勝。（定理5）
[定理11]：T2態(tài)必輸。
證明：同10。
綜上所述，必輸態(tài)有： T2,S0
必勝態(tài)： S2,S1,T0.
兩題比較：
第一題的全過程其實如下：
S2->T2->S2->T2-> …… ->T2->S1->T0->S0->T0->……->S0->T0(全0)
第二題的全過程其實如下：
S2->T2->S2->T2-> …… ->T2->S1->S0->T0->S0->……->S0->T0(全0)
下劃線表示勝利一方的取法。 是否發(fā)現(xiàn)了他們的驚人相似之處。
我們不難發(fā)現(xiàn)(見加黑部分)，S1態(tài)可以轉(zhuǎn)變?yōu)镾0態(tài)（第二題做法），也可以轉(zhuǎn)變?yōu)?
T0（第一題做法）。哪一方控制了S1態(tài)，他即可以有辦法使自己得到最后一根（轉(zhuǎn)變?yōu)?
T0）,也可以使對方得到最后一根（轉(zhuǎn)變?yōu)镾0）。
所以，搶奪S1是制勝的關(guān)鍵！
為此，始終把T2態(tài)讓給對方，將使對方處于被動狀態(tài)，他早晚將把狀態(tài)變?yōu)镾1.
推薦HDOJ題目
http://acm.hdu.edu.cn/showproblem.php?pid=1907
http://acm.hdu.edu.cn/showproblem.php?pid=2509
看完上面的結(jié)論，就能順利解決上面2道了
S-Nim
http://acm.hdu.edu.cn/showproblem.php?pid=1536http://acm.hdu.edu.cn/showproblem.php?pid=1944 博弈算法入門小節(jié) 1536 1517 1907
小子最近迷途于博弈之中。。。感觸頗深。
為了讓大家能夠在學(xué)習(xí)博弈的時候少走彎路，最重要的也是為了加深自己的影響，溫故而知新，特發(fā)此貼與大家共勉。
學(xué)博弈先從概念開始：
特別推薦LCY老師的課件：博弈入門。
下載地址：
http://acm.hdu.edu.cn/forum/read.php?tid=6875這個課件個人認為從博弈的基本思想，一直到解博弈的中心算法做了很好的詮釋。但是特別要注意的是。課件后面一部分英語寫的講義是重中之重。小子英語很弱，在這困擾很久。現(xiàn)在為大家大概介紹一下。
主要是后繼點和SG值的問題:
SG值：一個點的SG值就是一個不等于它的后繼點的SG的且大于等于零的最小整數(shù)。
后繼點：也就是按照題目要求的走法（比如取石子可以取的數(shù)量，方法）能夠走一步達到的那個點。
具體的有關(guān)SG值是怎么運用的希望大家自己多想想。
課件后面有一個1536的代碼。可以放在后面做做
看到這里推薦大家做幾道題：1846（最簡單的博弈水題）
1847（求SG值）
有了上面的知識接下來我們來看看組合博弈（n堆石子）
推薦大家看個資料：
博弈-取石子游戲(推薦等級五星級)
http://acm.hdu.edu.cn/forum/read.php?fid=20&tid=5748
http://hi.baidu.com/netnode/blog/item/30932c2edc7384514fc226ea.html
這里提出了一個奇異狀態(tài)的問題。看了這篇文章你會發(fā)現(xiàn)異或運算在博弈中使用的妙處。當然這里指出的只是組合博弈中一種特殊情況。
王道還是對SG值的求解，但是知道這么一種思路無疑對思維的廣度和深度擴展是很有幫助的。
ZZ博弈
http://acm.hdu.edu.cn/forum/read.php?fid=9&tid=10617
這里介紹了組和博弈的兩種大的類型，一種是最后取的是N狀態(tài)一種是最后取的是P狀態(tài)，兩個狀態(tài)的解題方法能看懂很有幫助。當然，能夠把推導(dǎo)過程理解，吃透無疑是大牛級的做法~小子也佩服的緊~
1536題推薦做做這題，這題前面提醒大家是一個求SG值的題目，題目前面是對異或運算運用在組合博弈問題中的很好的解釋。當然題目本身是有所不同的。因為在這里面對取法有所要求。那么這樣就回歸到了解決博弈問題的王道算法——求SG值上。
有關(guān)運用求SG值的博弈題目有： 1850（也可基于奇異狀態(tài)異或）
1848（中和的大斐波那契數(shù)列的典型求SG值題）
1517（個人認為有點猥瑣的題目。。。。在此題上困擾很久。當然搞出來很開心。小子是用比較規(guī)矩的求SG值的方法求出來的，但是論壇有人對其推出來了規(guī)律，這里佩服一下，大家可以學(xué)習(xí)一下）
1079（更猥瑣的題目，對新手要求較高，因為按傳統(tǒng)方法需要比較細致的模擬加對邊角狀態(tài)的考慮，同樣有人推出來了公式）
當你全部看完以上的東西。做完以上的題目的話。。。小子恭喜你~你博弈入門了~~~~
這里小子告訴大家。博弈很強大。學(xué)習(xí)要耐心~謝謝
Current System Time : 2008-12-11 19:16:03
ACM課作業(yè)：
1001 Brave Game
1002 Good Luck in CET-4 Everybody!
1003 Fibonacci again and again
1004 Rabbit and Grass
1005 Being a Good Boy in Spring Festival
1006 Public Sale
1007 悼念512汶川大地震遇難同胞——選拔志愿者
1008 kiki’s game
1009 Calendar Game
1010 A Multiplication Game
1011 Digital Deletions
1012 S-Nim
http://acm.hdu.edu.cn/forum/read.php?tid=11339&fpage=0&toread=&page=1
1536的參考代碼
1
//博弈-基于求SG值
2//Accepted 1536 578MS 416K 904 B
3#include”iostream”
4using namespace std;
5int f[101],sg[10001],k;
6int mex(int b)
7
{
8
int a[101]={0},i;
9
for(i=0;i<k;i++)
10 {
11 if(b-f<0)//b-f后繼點
12 break;
13 if(sg[b-f]==-1)
14 {
15 sg[b-f]=mex(b-f);
16
}
17 a[sg[b-f]]=1;
18 }
19 for(i=0;i<k;i++)
20 if(!a)
21 {
22 return i;
23 }
24
}
25int main()
26{
27 int i,t,n,s,bead,j;
28 while(cin >> k,k)
29 {
30 for(i=0;i<k;i++)
31 {
32 cin >> f;
33 }
34 memset(sg,-1,sizeof(sg));
35 for(i=0;i<k;i++)
36 for(j=i+1;j<k;j++)
37 if(f>f[j])
38 {
39 f+=f[j];
40 f[j]=f-f[j];
41 f-=f[j];
42 }
43 sg[0]=0;
44 cin >> t;
45 while(t–)
46 {
47 cin >> n;
48 s=0;
49 while(n–)
50 {
51 cin >> bead;//該堆的成員個數(shù)
52 if(sg[bead]==-1)
53 sg[bead]=mex(bead);
54 s=s^sg[bead];
55 }
56 if(s==0)
57 cout << “L”;
58 else
59 cout << “W”;
60 }
61 cout << endl;
62 }
63 return 0;
64}
65
1517參考代碼
1
2//博弈-基于求SG值
3//Accepted 1517 234MS 0K 837 B
4#include”iostream”
5using namespace std;
6int main()
7{
8 __int64 a[7000]={1},min,n;
9 int p[10],sg[7000],i,j,k;
10 for(i=2;i<10;p=0,i++);
11 for(i=1;i<7000;i++)
12 {
13 for(j=2,min=-1;j<10;j++)
14 if(min==-1||a[p[j]]*j<a[p[min]]*min)
15 min=j;
16 a=a[p[min]]*min;
17 min=a[p[min]]*min;
18 if(a>=5000000000)
19 break;
20 for(j=2;j<10;j++)
21 if(a[p[j]]*j==min)
22 p[j]++;
23 }//從小到大求出所有乘積
24 while(scanf(“%I64d”,&n)!=EOF)
25 {
26 for(i=0;i<7000;i++)
27 {
28 sg=0;
29 if(a>=n)
30 break;
31 }
32 for(j=i-1;a[j]*9>=n&&j>=0;j–)
33 sg[j]=1;
34 while(j>=0)
35 {
36 for(k=j+1;k<i&&a[j]*9>=a[k];k++)
37 if(a[k]%a[j]==0&&sg[k]==0)
38 {
39 sg[j]=1;
40 break;
41 }
42 j–;
43 }
44 puts(sg[0]?”Stan wins.”:”Ollie wins.”);
45 }
46 return 0;
47}
48
1907參考代碼
1#include”iostream”
2using namespace std;
3int main()
4{
5 int temp,t,n,s,x,i;
6 cin >> t;
7 while(t–)
8 {
9 cin >> n;
10 for(i=s=temp=0;i<n;i++)
11 {
12 cin >> x;
13 if(x>1) temp=1;
14 s^=x;
15 }
16 if((s&&temp)||(!s&&!temp))
17 cout << “John” << endl;
18 else
19 cout << “Brother” << endl;
20 }
21 return 0;
22}
23
posted on 2010-08-20 13:09
Tanky Woo 閱讀(1797)
評論(0) 編輯 收藏 引用