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

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

2、）威佐夫博奕（Wythff ame）：有兩堆各若干個物品，兩個人輪流從某一堆或同時從兩堆中取同樣多的物品，規(guī)定每次至少取一個，多者不限，最后取光者得勝。這種情況下是頗為復(fù)雜的。我們用（ak，bk）（akbk,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，8）、（12，20）。可以看出,a0=b0=0,ak未在前面出現(xiàn)過的最小自然數(shù)bkakk，奇異局勢有1。任何自然數(shù)都包含在一個且僅有一個奇異局勢中由于ak未在

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

4、,則從第一堆中拿走多余的數(shù)量a ak 即可；如果a ak ，b= ak + k,分兩種情況，第一種，a=aj （j k）,從第二堆里面bbj可；第二種，a=bj（jk）,從第二堆里面拿走ba j 即可。從如上性質(zhì)可知，兩個人如果都采用正確操作，那么面對非奇異局勢，先拿者必；反之，則后拿者取那么任給一個局勢（a，b），怎樣判斷它是不是奇異局勢呢？我們有如下公式akk（1+5）/2，bkakk（k=0，1，2，,n括號表示取整函數(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，若都不是，那么就不是奇異局勢。然后再按照上述法則進行，一定會遇到奇異（三）尼姆博奕（NimmGae）：有三堆各若干個物品，兩個人輪流從某一堆取任意多的物品，規(guī)定每次至少取一個，多者不限，最后取光者得勝。這種情況最有意思，它與二進制有密切關(guān)系，我們用（a，b，c）表示某種局勢，先（0，0，0）顯然是奇異局勢，無論誰面對奇異局勢，都必然失敗。第二種奇異局勢（0，n，n），只要與對手拿走一樣多的物品，最后都將導(dǎo)致（0，0，0）。仔細分析一下，（1，2，3）也是奇異局勢，無論對手

6、如何拿，接下來都可以變?yōu)椋?，n，n）形。計算機算法里面有一種叫做按位模 2 加，也叫做異或的運算，我們用符號（+）表這種運算。這種運算和一般加法不同的一點是 1+1=0。先看（1，2，3）的按位模 2 加的結(jié)1 =二進制2 =二進制3 =二進制110二進制00（注意不進位對于奇異局勢（0，n，n）也一樣，結(jié)果也是 0任何奇異局勢（a，b，c）都有 a（+）b（+）c =0如果我們面對的是一個非奇異局勢（a，b，c），要如何變?yōu)槠娈惥謩菽?？假設(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ù)，求必勝的方法。嘿嘿，這個游戲我早就見識過了。小時候用珠算玩這個游戲：第一檔撥一個，第二檔撥兩個，依次直到第五檔撥五個。然后兩個人就輪流再把棋子撥下來，誰要是最后一個撥誰就贏。有一次暑假看見兩個小孩子在玩這個游戲，我就在想有沒有一個定論呢。下面就來試著證明一下吧先解決第一個問題吧定義：若所有火柴數(shù)異或為0，則該狀態(tài)被稱為利他態(tài)，用字母T 表示；否則，為利己態(tài)，用S示。定理1：對

8、于任何一個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)c表示成二進制，記它的二進制數(shù)的最高位為第p然存在一個A(t),它二進制的第p位也是1（否則，若所有的的第p位都是0，這與c的第p位就也為0矛盾）那么我們把xA(txorc,則得到xA(t).這是因為既然A(t)的第pc第p同為1,那么xp變?yōu)?,而高于 p位并沒有改變。所以x T2-S2-T2- -T2-S1-T0-S0-T0-S0-T0(全 第二題的全過程其實如下S2-T2-S2-T2- -T2-S1-S0-

9、T0-S0-S0-T0(全 下劃線表示勝利一方的取法。 是否發(fā)現(xiàn)了他們的驚人相似之處我們不難發(fā)現(xiàn)(見加黑部分)，S1可以轉(zhuǎn)S0（第二題做法），也可以轉(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)?推薦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博弈算法入門小節(jié) 1536157197小子最近迷途于博弈之中。感觸頗為了讓大家能夠在學(xué)習(xí)博弈的時候少走彎路，最重要的也是為了加深自己的影響，溫故而知新，特發(fā)此貼與大家共勉。學(xué)博弈先從概念開始：特別推薦 LCY 老師

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

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

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

14、因為按傳統(tǒng)方法需要比較細致的模擬加對邊角狀態(tài)的考慮，同樣有人推出來了公式）當(dā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ù)過了,以下是隱藏的Copy /博弈-基于求