ACM之博弈論.ppt

1、博弈論,湖南師范大學(xué) 羅迅,博弈論（Game Theory）,孫子兵法 馮諾依曼 約翰納什,囚徒困境,A、B兩個(gè)嫌疑人分別單獨(dú)接受審訊 其中一個(gè)坦白，而另一個(gè)抵賴，則坦白人釋放，抵賴者判刑10年 雙方都坦白，均判刑8年 雙方都抵賴，由于沒(méi)有其他證據(jù)以證明更嚴(yán)重的罪行，雙方均判刑2年,合作案例,100個(gè)參會(huì)人，1個(gè)主持人 每個(gè)參會(huì)人分別單獨(dú)的繳納一定的會(huì)費(fèi) 如果總會(huì)費(fèi)超過(guò)499元，則主持人將向每參會(huì)人返還6元 如果總會(huì)費(fèi)未超過(guò)499元，則全部歸公，一分不還 這是一個(gè)有趣的實(shí)驗(yàn)，有條件可以做一下,ACM之博弈問(wèn)題,POJ1085 雙方輪流連線 如果能夠完成一個(gè)三角形，則再走一步 給定殘局，問(wèn)，誰(shuí)能

2、獲勝 動(dòng)態(tài)規(guī)劃,博弈論題目的一般性想法,首先，雙方都是高手且理性 每一步都全局最優(yōu) 即使輸，也要走全局最優(yōu)，使得輸?shù)米钌?動(dòng)態(tài)規(guī)劃每個(gè)局面，唯一確定一個(gè)狀態(tài) 局面可以是不同初始條件的開(kāi)局 也可以是同一初始下不同的殘局,博弈題目的一般性想法,令勝負(fù)結(jié)果是一個(gè)整數(shù)分值，雙方得分高者獲勝 站在先手角度，每一步都希望得到最大分 站在后手角度，每一步都希望對(duì)方得到最小分 顯然，你不能只考慮一步或者兩步,最大最小值函數(shù),負(fù)值最大函數(shù),Nim游戲,POJ2234 若干堆、若干個(gè)石子 雙方輪流從一堆中取出可取的數(shù)目 拿走最后石子者獲勝，取無(wú)可取者失敗 給定初始條件，先手能否獲勝 3，Yes 1，1，No,Ni

3、m問(wèn)題,Impartial Combinatorial Games，ICG 兩個(gè)人參與，交替走棋 可能的走法在一個(gè)有限集合里選取 游戲局面無(wú)后效性，未來(lái)與過(guò)去無(wú)關(guān) 如果某選手無(wú)法走動(dòng)，則判負(fù),Nim理論,任何一個(gè)局面必然二屬其一：當(dāng)前先手必勝（N位置）、當(dāng)前先手必?cái)。≒位置） 數(shù)學(xué)定義： 終態(tài)是P位置 能夠移動(dòng)到P位置的狀態(tài)是N位置 只能去N位置的狀態(tài)是P位置 注解：走投無(wú)路就是必?cái)?，就是P啊,示例,Nim問(wèn)題中的（3,3），這是一個(gè)P 這個(gè)位置往下有3種走法 （3,0），顯然是N （3,1），也是N；因?yàn)閺模?,1）可以走到（1,1），而（1,1）是P （3,2），簡(jiǎn)單枚舉就知道也是N 所以

4、，（3,3）無(wú)論怎么走都走到N，則（3,3）是P 反過(guò)來(lái)，（3,1）既可以走到（1,1），也可以走到（2,1）或者其他狀態(tài)，但只要（1,1）是一個(gè)P位置，（3,1）就是一個(gè)N位置,Nim問(wèn)題的解法,所有堆的石子數(shù)目求異或，為0則是P位置 證明： 終態(tài)滿不滿足該條件？滿足 異或非0的N位置能不能移動(dòng)到異或?yàn)?的P位置？能，找到非零的最高位進(jìn)行操作 異或?yàn)?的P位置是不是只能移動(dòng)到異或非0的N位置？是，因?yàn)闊o(wú)論怎么移，異或和一定變成非0,Mex函數(shù),運(yùn)算對(duì)象是一個(gè)集合 最小的不屬于該集合的非負(fù)整數(shù) mex(0,1,2,4) = 3 mex(2,3,5) = 0 mex(空集) = 0,SG函數(shù),定

5、義在有向無(wú)環(huán)圖 g(x) = mex( g(y) | y是x的后繼 ),SG的性質(zhì),所有終態(tài)的sg為0 如果已知一個(gè)點(diǎn)的sg是0，則它的所有后繼的sg均不為0 如果已知一個(gè)點(diǎn)的sg非0，則它必然有一個(gè)后繼sg為0 通過(guò)這三條定義可知： sg為0的點(diǎn)就是P位置,SG 的應(yīng)用,首先判斷是否可以使用SG 其次將游戲分解成多個(gè)獨(dú)立的小游戲 再次計(jì)算每個(gè)小游戲的SG值 前驅(qū)與后繼的關(guān)系 游戲總的SG值是各小游戲SG值的異或和,題目列表,hdu1404，DP + DFS POJ2960，SG函數(shù) hdu1729，SG函數(shù)，SG函數(shù)的求法 hdu1730，極其簡(jiǎn)單 hdu1760，DP+DFS，建立SG函數(shù)的概念 hdu1809，與上題類似，體現(xiàn)SG的價(jià)值 POJ2425,hdu1524，SG函數(shù)可解，應(yīng)該有更好的實(shí)現(xiàn)思想,題目列表,ZOJ191