網(wǎng)上找一些博弈知識(shí)匯總

1、 HYPERLINK /?p=1081 博弈知識(shí)匯以下是我從網(wǎng)上收集的關(guān)于組合博弈的資料匯總?cè)?。（一）巴什博奕（BashGae）：只有一堆n個(gè)物品，兩個(gè)人輪流從這堆物品中取物，規(guī)定每次至少取一個(gè)，最多取m個(gè)。最后取光者得勝。顯然，如果 n=m+1，那么由于一次最多只能取 m 個(gè)，所以，無(wú)論先取者拿走多少個(gè)， 后取者都能夠一次拿走剩余的物品，后者取勝。因此我們發(fā)現(xiàn)了如何取勝的法則：如n=（m+1）r+s，（r 為任意自然數(shù)，sm),那么先取者要拿走 s 個(gè)物品，如果后取者拿走 k（m)個(gè)，那么先取者再拿走 m+1-k 個(gè)，結(jié)果剩下（m+1）（r-1）個(gè)，以后保持這樣的個(gè)，誰(shuí)能報(bào)到100者勝（二

2、）威佐夫博奕（Wythff ame）：有兩堆各若干個(gè)物品，兩個(gè)人輪流從某一堆或同時(shí)從兩堆中取同樣多的物品，規(guī)定每次至少取一個(gè)，多者不限，最后取光者得勝。這種情況下是頗為復(fù)雜的。我們用（ak，bk）（akbk,k=0，1，2，,n)表兩堆物品的數(shù)量并稱其為局勢(shì)，如果甲面對(duì)（0，0），那么甲已經(jīng)輸了，這種局勢(shì)我們稱為奇異局勢(shì)。前幾個(gè)奇異局勢(shì)是：（0，0）、（1，2）、（3，5）、（4，7）、（6， 10）、（8，13）、（9，15）、（11，8）、（12，20）?？梢钥闯?a0=b0=0,ak未在前面出現(xiàn)過(guò)的最小自然數(shù)bkakk，奇異局勢(shì)有1。任何自然數(shù)都包含在一個(gè)且僅有一個(gè)奇異局勢(shì)中由于ak未在

3、前面出現(xiàn)過(guò)的最小自然數(shù)，所以有akak-1 ，而bkakk-1k-1bk-1ak-1所以性質(zhì)1。成立。 事實(shí)上，若只改變奇異局勢(shì)（ak，bk）的某一個(gè)分量，那么另一個(gè)分量不可能在他奇異局勢(shì)中，所以必然是非奇異局勢(shì)。如果使（ak，bk）于其差不變，且不可能是其他奇異局勢(shì)的差，因此也是非奇異局勢(shì)。3。采用適當(dāng)?shù)姆椒?，可以將非奇異局?shì)變?yōu)槠娈惥旨僭O(shè)面對(duì)的局勢(shì)是（a,b），若ba，則同時(shí)從兩堆中取走a物體，就變?yōu)槠娈惥謩?shì)（0，0）；aak，bbk，那么，取走bbk物體，即變?yōu)槠娈惥謩?shì)；如果a = akbbk則同時(shí)從兩堆中拿走akabak物體,變?yōu)槠娈悇?shì)（abakabakbak）；如果aak ，bakk

4、,則從第一堆中拿走多余的數(shù)量a ak 即可；如果a ak ，b= ak + k,分兩種情況，第一種，a=aj （j k）,從第二堆里面bbj可；第二種，a=bj（jk）,從第二堆里面拿走ba j 即可。從如上性質(zhì)可知，兩個(gè)人如果都采用正確操作，那么面對(duì)非奇異局勢(shì)，先拿者必；反之，則后拿者取那么任給一個(gè)局勢(shì)（a，b），怎樣判斷它是不是奇異局勢(shì)呢？我們有如下公式akk（1+5）/2，bkakk（k=0，1，2，,n括號(hào)表示取整函數(shù)奇妙的是其中出現(xiàn)了黃金分割數(shù)（1+5）/21。618,因此ak，bk成的矩形近似為黃金矩形，由于 2/（1+5）=（5-1）/2，可以先求出 j=a（5-1）/2，若 a

5、= j（1+5）/2，那么a = aj，bj = aj + j，若不等于，那么a = aj+1，bj+1 = aj+1j1，若都不是，那么就不是奇異局勢(shì)。然后再按照上述法則進(jìn)行，一定會(huì)遇到奇異（三）尼姆博奕（NimmGae）：有三堆各若干個(gè)物品，兩個(gè)人輪流從某一堆取任意多的物品，規(guī)定每次至少取一個(gè)，多者不限，最后取光者得勝。這種情況最有意思，它與二進(jìn)制有密切關(guān)系，我們用（a，b，c）表示某種局勢(shì)，先（0，0，0）顯然是奇異局勢(shì)，無(wú)論誰(shuí)面對(duì)奇異局勢(shì)，都必然失敗。第二種奇異局勢(shì)（0，n，n），只要與對(duì)手拿走一樣多的物品，最后都將導(dǎo)致（0，0，0）。仔細(xì)分析一下，（1，2，3）也是奇異局勢(shì)，無(wú)論對(duì)手

6、如何拿，接下來(lái)都可以變?yōu)椋?，n，n）形。計(jì)算機(jī)算法里面有一種叫做按位模 2 加，也叫做異或的運(yùn)算，我們用符號(hào)（+）表這種運(yùn)算。這種運(yùn)算和一般加法不同的一點(diǎn)是 1+1=0。先看（1，2，3）的按位模 2 加的結(jié)1 =二進(jìn)制2 =二進(jìn)制3 =二進(jìn)制110二進(jìn)制00（注意不進(jìn)位對(duì)于奇異局勢(shì)（0，n，n）也一樣，結(jié)果也是 0任何奇異局勢(shì)（a，b，c）都有 a（+）b（+）c =0如果我們面對(duì)的是一個(gè)非奇異局勢(shì)（a，b，c），要如何變?yōu)槠娈惥謩?shì)呢？假設(shè)a(1,5,4)奇異局乙:(1,5,4甲:(1,4,4)-(0,4,4)奇異局乙:(0,4,4甲:(0.4,2)-(0,2,2)奇異局乙:(0,2,2甲

7、:(0,2,1)-(0,1,1)奇異局乙:(0,1,1甲:(0,1,0)-(0,0,0)奇異局甲勝取火柴的游題目1可將一堆全取走，但不可不取，最后取完者為勝，求必勝的方法。題目2可將一堆全取走，但不可不取，最后取完者為負(fù)，求必勝的方法。嘿嘿，這個(gè)游戲我早就見(jiàn)識(shí)過(guò)了。小時(shí)候用珠算玩這個(gè)游戲：第一檔撥一個(gè)，第二檔撥兩個(gè)，依次直到第五檔撥五個(gè)。然后兩個(gè)人就輪流再把棋子撥下來(lái)，誰(shuí)要是最后一個(gè)撥誰(shuí)就贏。有一次暑假看見(jiàn)兩個(gè)小孩子在玩這個(gè)游戲，我就在想有沒(méi)有一個(gè)定論呢。下面就來(lái)試著證明一下吧先解決第一個(gè)問(wèn)題吧定義：若所有火柴數(shù)異或?yàn)?，則該狀態(tài)被稱為利他態(tài)，用字母T 表示；否則，為利己態(tài)，用S示。定理1：對(duì)

8、于任何一個(gè)S 態(tài)，總能從一堆火柴中取出若干個(gè)使之成為 T 態(tài)。若有n 堆火柴，每堆火柴有A(i)根火柴數(shù)，那么既然現(xiàn)在處于 S 態(tài)c =A(1)xor A(2)xor xor A(n)c表示成二進(jìn)制，記它的二進(jìn)制數(shù)的最高位為第p然存在一個(gè)A(t),它二進(jìn)制的第p位也是1（否則，若所有的的第p位都是0，這與c的第p位就也為0矛盾）那么我們把xA(txorc,則得到xA(t).這是因?yàn)榧热籄(t)的第pc第p同為1,那么xp變?yōu)?,而高于 p位并沒(méi)有改變。所以x T2-S2-T2- -T2-S1-T0-S0-T0-S0-T0(全 第二題的全過(guò)程其實(shí)如下S2-T2-S2-T2- -T2-S1-S0-

9、T0-S0-S0-T0(全 下劃線表示勝利一方的取法。 是否發(fā)現(xiàn)了他們的驚人相似之處我們不難發(fā)現(xiàn)(見(jiàn)加黑部分)，S1可以轉(zhuǎn)S0（第二題做法），也可以轉(zhuǎn)變?yōu)?T0（第一題做法）。哪一方控制了S1態(tài)，他即可以有辦法使自己得到最后一根（轉(zhuǎn)變?yōu)?T0）,也可以使對(duì)方得到最后一根（轉(zhuǎn)變?yōu)镾0）。所以，搶奪S1 是制勝的關(guān)鍵為此，始終把 T2 態(tài)讓給對(duì)方，將使對(duì)方處于被動(dòng)狀態(tài)，他早晚將把狀態(tài)變?yōu)?推薦HDOJ題目 HYPERLINK /showproblem.php?pid=1907 htp:/amhd.eucnshwrole.hppi=907 HYPERLINK /showproblem.php?pid

10、=2509 htp:/amhd.eucnshwrole.hppi=509看完上面的結(jié)論，就能順利解決上面2道了S-im HYPERLINK /showproblem.php?pid=1536 htp:/amhd.eucnshwrole.hppi=536 HYPERLINK /showproblem.php?pid=1944 htp:/amhd.eucnshwrole.hppi=944博弈算法入門(mén)小節(jié) 1536157197小子最近迷途于博弈之中。感觸頗為了讓大家能夠在學(xué)習(xí)博弈的時(shí)候少走彎路，最重要的也是為了加深自己的影響，溫故而知新，特發(fā)此貼與大家共勉。學(xué)博弈先從概念開(kāi)始：特別推薦 LCY 老師

11、的課件：博弈入門(mén)下載地址 HYPERLINK /forum/read.php?tid=6875 這個(gè)課件個(gè)人認(rèn)為從博弈的基本思想，一直到解博弈的中心算法做了很好的詮釋。但是特別要注意的是。課件后面一部分英語(yǔ)寫(xiě)的講義是重中之重。小子英語(yǔ)很弱，在這困擾很久。現(xiàn)在為大家大概介紹一下。主要是后繼點(diǎn)和 SG 值的問(wèn)題SG 值：一個(gè)點(diǎn)的 SG 值就是一個(gè)不等于它的后繼點(diǎn)的 SG 的且大于等于零的最小整數(shù)后繼點(diǎn)：也就是按照題目要求的走法（比如取石子可以取的數(shù)量，方法）具體的有關(guān)SG值是怎么運(yùn)用的希望大家自己多想想。課件后面有一個(gè) 1536 的代碼。可以放在后面做看到這里推薦大家做幾道題：1846（最簡(jiǎn)單的博

12、弈水題1847（求SG值有了上面的知識(shí)接下來(lái)我們來(lái)看看組合博弈（n堆石子推薦大家看個(gè)資料： HYPERLINK /forum/read.php?fid=20&tid=5748 HYPERLINK /netnode/blog/item/30932c2edc7384514fc226ea.html 這里提出了一個(gè)奇異狀態(tài)的問(wèn)題?？戳诉@篇文章你會(huì)發(fā)現(xiàn)異或運(yùn)算在博弈中使用的妙處。當(dāng)然這里指出的只是組合博弈中一種特殊情況。王道還是對(duì) SG 值的求解，但是知道這么一種思路無(wú)疑對(duì)思維的廣度和深度擴(kuò)展是很有幫助的ZZ博 HYPERLINK /forum/read.php?fid=9&tid=10617 這里介紹

13、了組和博弈的兩種大的類型，一種是最后取的是 N 狀態(tài)一種是最后取的是 P 狀態(tài)，兩個(gè)狀態(tài)的解題方法能看懂很有幫156題推薦做做這題，這題前面提醒大家是一個(gè)求SG值的題目，題目前面是對(duì)異或運(yùn)算運(yùn)用在組合博弈問(wèn)題中的很好的解釋。當(dāng)然題目本身是有所不同的。因?yàn)樵谶@里面對(duì)取法有所要求。那么這樣就回歸到了解決博弈問(wèn)題的王道算法求SG值上。 有關(guān)運(yùn)用求SG值的博弈題目有： 1850（也可基于奇異狀態(tài)異或）1848（中和的大斐波那契數(shù)列的典型求 SG 值題1517（個(gè)人認(rèn)為有點(diǎn)猥瑣的題目。在此題上困擾很久。當(dāng)然搞出來(lái)很開(kāi)心。小子是用比較規(guī)矩的求 SG 值的方法求出來(lái)的，109（更猥瑣的題目，對(duì)新手要求較高，

14、因?yàn)榘磦鹘y(tǒng)方法需要比較細(xì)致的模擬加對(duì)邊角狀態(tài)的考慮，同樣有人推出來(lái)了公式）當(dāng)你全部看完以上的東西。做完以上的題目的話。小子恭喜你你博弈入門(mén)了這里小子告訴大家。博弈很強(qiáng)大。學(xué)習(xí)要耐心謝Current SystemTime:2008-12-11ACM課作業(yè)1001Brave1002GoodLuckinCET-4Everybody! 1003 Fibonacci again and again 1004 Rabbit and Grass1005BeingaGoodBoyinSpringFestival 1006 Public Sale1007 悼念512汶川大地震遇難同胞選拔志愿1008kikis1009Calendar1010AMultiplicationGame 1011 Digital Deletions1012S- HYPERLINK /forum/read.php?tid=11339&fpage=0&toread&page=1 1536 的參考代本部分設(shè)定了隱藏,您已回復(fù)過(guò)了,以下是隱藏的Copy /博弈-基于求