原帖地址：
http://www.wutianqi.com/?p=1081

---

 

以下是我從網(wǎng)上收集的關(guān)于組合博弈的資料匯總：

有一種很有意思的游戲，就是有物體若干堆，可以是火柴棍或是圍棋子等等均可。兩個
人輪流從堆中取物體若干，規(guī)定最后取光物體者取勝。這是我國民間很古老的一個游戲
，別看這游戲極其簡單，卻蘊(yùn)含著深刻的數(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ù)，就能最后獲勝。
    這個游戲還可以有一種變相的玩法：兩個人輪流報(bào)數(shù)，每次至少報(bào)一個，最多報(bào)十
個，誰能報(bào)到100者勝。
（二）威佐夫博奕（Wythoff Game）：有兩堆各若干個物品，兩個人輪流從某一堆或同
時(shí)從兩堆中取同樣多的物品，規(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>    事實(shí)上，若只改變奇異局勢（ak，bk）的某一個分量，那么另一個分量不可能在其
他奇異局勢中，所以必然是非奇異局勢。如果使（ak，bk）的兩個分量同時(shí)減少，則由
于其差不變，且不可能是其他奇異局勢的差，因此也是非奇異局勢。
    3。采用適當(dāng)?shù)姆椒ǎ梢詫⒎瞧娈惥謩葑優(yōu)槠娈惥謩荨?/p>

    假設(shè)面對的局勢是（a,b），若 b = a，則同時(shí)從兩堆中取走 a 個物體，就變?yōu)榱?br>奇異局勢（0，0）；如果a = ak ，b > bk，那么，取走b  – bk個物體，即變?yōu)槠娈惥?br>勢；如果 a = ak ，  b < bk ,則同時(shí)從兩堆中拿走 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，若都不是，那么就不是奇異局勢。然后再按照上述法則進(jìn)行，一定會遇到奇異
局勢。

（三）尼姆博奕（Nimm Game）：有三堆各若干個物品，兩個人輪流從某一堆取任意多的
物品，規(guī)定每次至少取一個，多者不限，最后取光者得勝。

    這種情況最有意思，它與二進(jìn)制有密切關(guān)系，我們用（a，b，c）表示某種局勢，首
先（0，0，0）顯然是奇異局勢，無論誰面對奇異局勢，都必然失敗。第二種奇異局勢是
（0，n，n），只要與對手拿走一樣多的物品，最后都將導(dǎo)致（0，0，0）。仔細(xì)分析一
下，（1，2，3）也是奇異局勢，無論對手如何拿，接下來都可以變?yōu)椋?，n，n）的情
形。

    計(jì)算機(jī)算法里面有一種叫做按位模2加，也叫做異或的運(yùn)算，我們用符號（+）表示
這種運(yùn)算。這種運(yùn)算和一般加法不同的一點(diǎn)是1+1=0。先看（1，2，3）的按位模2加的結(jié)
果：

1 =二進(jìn)制01
2 =二進(jìn)制10
3 =二進(jìn)制11 （+）
———————
0 =二進(jìn)制00 （注意不進(jìn)位）

    對于奇異局勢（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,即可,因?yàn)橛腥缦碌倪\(yùn)算結(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個物體即可達(dá)
到奇異局勢（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。我們來實(shí)際進(jìn)行一盤比賽看看：
        甲:(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ī)定每次只能從一堆中取若干根，
可將一堆全取走，但不可不取，最后取完者為負(fù)，求必勝的方法。
嘿嘿，這個游戲我早就見識過了。小時(shí)候用珠算玩這個游戲：第一檔撥一個，第二檔撥兩個，依次直到第五檔撥五個。然后兩個人就輪流再把棋子撥下來，誰要是最后一個撥誰就贏。有一次暑假看見兩個小孩子在玩這個游戲，我就在想有沒有一個定論呢。下面就來試著證明一下吧
先解決第一個問題吧。
定義：若所有火柴數(shù)異或?yàn)?，則該狀態(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表示成二進(jìn)制，記它的二進(jìn)制數(shù)的最高位為第p位，則必然存在一個A(t),它二進(jìn)制的第p位也是1。（否則，若所有的A(i)的第p位都是0，這與c的第p位就也為0矛盾）。
    那么我們把x = A(t) xor c,則得到x < A(t).這是因?yàn)榧热籄(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
      進(jìn)而推出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)變都可以有己方控制，對方只能被動地實(shí)現(xiàn)由T態(tài)轉(zhuǎn)變?yōu)镾態(tài)。故S態(tài)必贏。
[定理4]：T態(tài)，只要對方法正確，必?cái)　?
  由定理3易得。
接著來解決第二個問題。
定義：若一堆中僅有1根火柴，則被稱為孤單堆。若大于1根，則稱為充裕堆。
定義：T態(tài)中，若充裕堆的堆數(shù)大于等于2，則稱為完全利他態(tài)，用T2表示；若充裕堆的堆數(shù)等于0，則稱為部分利他態(tài)，用T0表示。
 
孤單堆的根數(shù)異或只會影響二進(jìn)制的最后一位，但充裕堆會影響高位（非最后一位）。一個充裕堆，高位必有一位不為0，則所有根數(shù)異或不為0。故不會是T態(tài)。
[定理5]：S0態(tài)，即僅有奇數(shù)個孤單堆，必?cái)　0態(tài)必勝。
證明：
S0態(tài)，其實(shí)就是每次只能取一根。每次第奇數(shù)根都由己取，第偶數(shù)根都由對
方取，所以最后一根必己取。敗。同理,  T0態(tài)必勝#
[定理6]：S1態(tài)，只要方法正確，必勝。
證明：
若此時(shí)孤單堆堆數(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)?，所以此時(shí)的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.
兩題比較：
第一題的全過程其實(shí)如下：
S2->T2->S2->T2->  ……  ->T2->S1->T0->S0->T0->……->S0->T0(全0)
第二題的全過程其實(shí)如下：
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=1536
http://acm.hdu.edu.cn/showproblem.php?pid=1944
 
 
 
博弈算法入門小節(jié) 1536 1517 1907
小子最近迷途于博弈之中。。。感觸頗深。
為了讓大家能夠在學(xué)習(xí)博弈的時(shí)候少走彎路，最重要的也是為了加深自己的影響，溫故而知新，特發(fā)此貼與大家共勉。
學(xué)博弈先從概念開始：
特別推薦LCY老師的課件：博弈入門。
下載地址：http://acm.hdu.edu.cn/forum/read.php?tid=6875
這個課件個人認(rèn)為從博弈的基本思想，一直到解博弈的中心算法做了很好的詮釋。但是特別要注意的是。課件后面一部分英語寫的講義是重中之重。小子英語很弱，在這困擾很久。現(xiàn)在為大家大概介紹一下。
主要是后繼點(diǎn)和SG值的問題:
SG值：一個點(diǎn)的SG值就是一個不等于它的后繼點(diǎn)的SG的且大于等于零的最小整數(shù)。
后繼點(diǎn)：也就是按照題目要求的走法（比如取石子可以取的數(shù)量，方法）能夠走一步達(dá)到的那個點(diǎn)。
具體的有關(guān)SG值是怎么運(yùn)用的希望大家自己多想想。
課件后面有一個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)異或運(yùn)算在博弈中使用的妙處。當(dāng)然這里指出的只是組合博弈中一種特殊情況。
王道還是對SG值的求解，但是知道這么一種思路無疑對思維的廣度和深度擴(kuò)展是很有幫助的。
ZZ博弈
http://acm.hdu.edu.cn/forum/read.php?fid=9&tid=10617
這里介紹了組和博弈的兩種大的類型，一種是最后取的是N狀態(tài)一種是最后取的是P狀態(tài)，兩個狀態(tài)的解題方法能看懂很有幫助。當(dāng)然，能夠把推導(dǎo)過程理解，吃透無疑是大牛級的做法~小子也佩服的緊~  
    1536題推薦做做這題，這題前面提醒大家是一個求SG值的題目，題目前面是對異或運(yùn)算運(yùn)用在組合博弈問題中的很好的解釋。當(dāng)然題目本身是有所不同的。因?yàn)樵谶@里面對取法有所要求。那么這樣就回歸到了解決博弈問題的王道算法——求SG值上。
    有關(guān)運(yùn)用求SG值的博弈題目有： 1850（也可基于奇異狀態(tài)異或）
1848（中和的大斐波那契數(shù)列的典型求SG值題）
1517（個人認(rèn)為有點(diǎn)猥瑣的題目。。。。在此題上困擾很久。當(dāng)然搞出來很開心。小子是用比較規(guī)矩的求SG值的方法求出來的，但是論壇有人對其推出來了規(guī)律，這里佩服一下，大家可以學(xué)習(xí)一下）
1079（更猥瑣的題目，對新手要求較高，因?yàn)榘磦鹘y(tǒng)方法需要比較細(xì)致的模擬加對邊角狀態(tài)的考慮，同樣有人推出來了公式）
當(dāng)你全部看完以上的東西。做完以上的題目的話。。。小子恭喜你~你博弈入門了~~~~
    這里小子告訴大家。博弈很強(qiáng)大。學(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的參考代碼
 

1517參考代碼

 
1907參考代碼