北京大學(xué)ACM暑期課講義-lcc-博弈

ACM中的博弈北京大學(xué)ACM隊(duì)最常見(jiàn)情況：SG博弈1二人博弈2對(duì)于同一局面,兩個(gè)游戲者可操作的集合完全相同3游戲總可以在有限步之內(nèi)結(jié)束4假定:兩個(gè)人都"足夠聰明"5無(wú)法進(jìn)行任何操作時(shí)游戲結(jié)束,不能操作的一方為負(fù)----5的反面條件：不能操作勝為另一種博弈取石子類經(jīng)典問(wèn)題取石子1：有一堆n個(gè)石子兩人輪流取每次可以取1..m個(gè)沒(méi)得取的判負(fù)取石子2：有K堆石子，每堆ni個(gè)，兩人輪流取，每次可以從某一堆中取1..m個(gè)沒(méi)法取石子的判負(fù)N局面和P局面必在有限步結(jié)束在雙方都采用最佳策略的前提下,任一局面不是先手必勝就是后手必勝規(guī)定:先手勝為N局面,后手勝為P局面此類問(wèn)題一般問(wèn)某一個(gè)局面是先手必勝還是先手必?cái)「郊訂?wèn)題：先手必勝時(shí)，輸出當(dāng)前一步可選步最終局面都是P局面對(duì)于一個(gè)局面,若至少有一種操作使它變?yōu)镻局面,則它是N局面如果當(dāng)前是我的回合，我有一種操作選擇，使得下回合對(duì)方面對(duì)的局面是個(gè)必輸局面，那么我的局面就是必勝局面問(wèn)題：如何尋找這一步操作選擇？（輸出解）對(duì)于一個(gè)局面,無(wú)論如何操作都使它變?yōu)镹局面,則它是P局面如果當(dāng)前是我的回合，無(wú)論怎么做，輪到對(duì)方時(shí)，對(duì)方都存在一種必勝策略，那么當(dāng)前我面對(duì)的局面就是必?cái)【置胬喝∈訂?wèn)題有一堆n個(gè)石子兩人輪流取每次可以取1..m個(gè)沒(méi)得取的判負(fù)在游戲中，n不斷變化，m是定值一個(gè)局面可以用當(dāng)前的石子數(shù)n來(lái)表示n=0必?cái)=1..m都是必勝局面n=m+1是必?cái)【置妫槭裁?？）n=m+2..2m+1是必勝局面（為什么？）將博弈游戲看做圖將游戲中間的狀態(tài)看做頂點(diǎn)性質(zhì)2：對(duì)于同一局面,兩個(gè)游戲者可操作的集合完全相同點(diǎn)對(duì)當(dāng)前執(zhí)行者是無(wú)差別的將狀態(tài)的轉(zhuǎn)移看做邊

性質(zhì)3：游戲總可以在有限步之內(nèi)結(jié)束

這是一個(gè)有向無(wú)環(huán)圖N=0N=2N=mN=m+1N=1取石子問(wèn)題示例頂點(diǎn)與必勝必?cái)B(tài)每個(gè)頂點(diǎn)都會(huì)對(duì)應(yīng)N局面必勝或/P局面必?cái)點(diǎn)（必勝點(diǎn)）或者P點(diǎn)（必?cái)↑c(diǎn)）如果頂點(diǎn)有邊指向P點(diǎn)，則該點(diǎn)為N點(diǎn)（必勝點(diǎn)）如果頂點(diǎn)沒(méi)有邊指向P點(diǎn)（所有出邊指向N點(diǎn)）則該點(diǎn)為P點(diǎn)（必?cái)↑c(diǎn)）N=0N=2N=mN=m+1N=1取石子問(wèn)題示例N=0N=1N=2N=mN=m+1判斷先手必勝還是必?cái)D是有向無(wú)環(huán)圖通過(guò)拓?fù)渑判驅(qū)D的每個(gè)點(diǎn)進(jìn)行染色，從而確定每個(gè)點(diǎn)的狀態(tài)必勝時(shí)要輸出一步可行解：尋找該狀態(tài)對(duì)應(yīng)的N節(jié)點(diǎn)指向的P節(jié)點(diǎn)的那條邊（一定存在）算法復(fù)雜度和狀態(tài)數(shù)有關(guān)一堆石子的狀態(tài)數(shù)為NK堆石子的狀態(tài)是一個(gè)K維向量<n1,n2,…nk>狀態(tài)數(shù)為n1*n2*…*nk太多了吃不消！SG函數(shù)對(duì)頂點(diǎn)賦一個(gè)SG值設(shè)頂點(diǎn)v，有v->v1,v->v2,…v->vtsg(v)=min(N–{sg(v1),sg(v2),…,sg(vt)})sg(v)定義為沒(méi)有出現(xiàn)在{sg(v1)..sg(vt)}中的最小自然數(shù)同樣可以用拓?fù)湫驅(qū)?jié)點(diǎn)計(jì)算sg值SG函數(shù)與NP局面的關(guān)系初始節(jié)點(diǎn)（必須是P節(jié)點(diǎn)）沒(méi)有出邊， sg=0若v有邊指向某sg(vi)=0的vi，則sg(v)>0若v沒(méi)有邊指向某sg(vi)=0的vi，則sg(v)=0所有P節(jié)點(diǎn)sg=0所有N節(jié)點(diǎn)sg>0N=0N=2N=mN=m+1N=1取石子問(wèn)題示例N=0N=1N=2N=mN=m+1Sg(0)=0Sg(1)=1Sg(2)=2Sg(m)=mSg(m+1)=0取石子游戲一維：只有一堆石子sg(n)=min(N–{sg(n-1),sg(n-2),…sg(n-m)})n先手必勝當(dāng)且僅當(dāng)sg(n)>0二維的石子游戲:兩堆石子n1,n2狀態(tài)：<n1,n2>sg(<n1,n2>)=?斷言：sg(<n1,n2>)=sg(n1)^sg(n2)為兩個(gè)一維sg函數(shù)的異或sg(<n1,n2>)=sg(n1)^sg(n2)證明要點(diǎn)：sg(<n1,n2>)=sg(n1)^sg(n2)滿足sg函數(shù)的性質(zhì)1若sg(<n1,n2>)=x則存在操作使得 <n1,n2>-><n3,n4>且sg(<n3,n4>)=0..x-12若sg(<n1,n2>)=x不存在操作使得 <n1,n2>-><n3,n4>且sg(<n3,n4>)=x1若sg(<n1,n2>)=x則存在操作使得<n1,n2>-><n3,n4>且sg(<n3,n4>)=0..x-1

歸納法：

設(shè)a1=sg(n1)a2=sg(n2)

假設(shè)對(duì)子狀態(tài)成立，sg(<n3,n4>)=sg(n3)^sg(n4)

那么必然有n3=n1,n4<n2

或n3<n1,n4=n2 (對(duì)應(yīng)從某一堆里面取走一些石子)

根據(jù)sg函數(shù)的定義

存在n3使得sg(n3)=0..a1-1

存在n4使得sg(n4)=0..a2-1

對(duì)0<=y<x存在sg(n3)^a2=y或a1^sg(n4)=y擴(kuò)展到K維的情況若a1^a2^…^ak=x,任取y<x存在i，使得存在bi<ai，且a1^a2^..^a(i-1)^bi^a(i+1)…^ak=y這要求：bi=ai^(x^y)如何找出ai?設(shè)x^y的最高位是t位（有t+1比特）X的t位必須是1（為什么？注意y<x）a1..ak中必須有一個(gè)ai的t位是1ai^(x^y)<ai（為什么？）當(dāng)y=0時(shí)注意這里我們解決了“輸出一個(gè)解的問(wèn)題”<n1,n2…nk>的子狀態(tài)的sg函數(shù)形成的集合包含{0..x-1}但是2：不包含x為什么？令y=xai^(x^x)=ai<ai矛盾這樣一來(lái)就有sg(<n1,n2,..nk>)=x=sg(n1)^..^sg(nk)成功降維維度變化的局面取石子問(wèn)題3：有n個(gè)石子排成一列每次可以拿走1..m個(gè)連續(xù)的石子<10><4,4><4,1,2>Sg函數(shù)的應(yīng)用場(chǎng)景多維理解：一個(gè)游戲局面經(jīng)過(guò)一步變換后可以變成幾個(gè)同樣規(guī)則的子游戲一般是一維變成多維每個(gè)子游戲是一維類比：遞歸思想？DP中的重復(fù)子結(jié)構(gòu)？雙方每步可以從并行存在的多個(gè)子游戲中選擇一個(gè)操作維度可以進(jìn)一步變得更多可能存在一個(gè)子游戲，由同一個(gè)玩家連續(xù)兩次對(duì)其操作對(duì)sg函數(shù)來(lái)說(shuō)：怎么變都無(wú)所謂，它只關(guān)心所有子局面的異或值Sg(x)的變量x永遠(yuǎn)是一維的。競(jìng)賽中的博弈題策略利用最簡(jiǎn)單的N-P圖染色來(lái)判定博弈搜索：用搜索方式來(lái)對(duì)圖染色

可以看做α-β剪枝的特例轉(zhuǎn)化為規(guī)則的sg函數(shù)類問(wèn)題

如果還是狀態(tài)太多，需要進(jìn)一步尋找sg函數(shù)的規(guī)律，而不是直接用公式算打表尋找P局面的規(guī)律其他類型的博弈Sg函數(shù)的博弈是最基礎(chǔ)的博弈問(wèn)題競(jìng)賽中常出現(xiàn)非sg函數(shù)問(wèn)題前面提到的沒(méi)有辦法操作反而獲勝的情況需要現(xiàn)場(chǎng)構(gòu)造策略的問(wèn)題有些問(wèn)題與斐波那契數(shù)列，黃金分割數(shù)有關(guān)思考題加強(qiáng)版取石子有K堆每堆ni個(gè)每人可以每次選最多P堆從選出的每堆取走不超過(guò)m個(gè)石子沒(méi)得取的輸思考：p=1變成sg異或P的時(shí)候這一位上的變數(shù)從0-1變到0-P將異或操作改為：對(duì)每個(gè)二進(jìn)制位單獨(dú)累加mod(P+1)2011成都賽區(qū)A題AliceandBobK堆石子兩人操作可以1從某一堆拿走一個(gè)如果該堆在此之后沒(méi)有石子了，就消失2合并