淺談如何解決不平等博弈問(wèn)題

1、淺談如何解決不平等博弈問(wèn)題,廣東省中山市第一中學(xué) 方展鵬,引言,給出n棵竹子，高度分別為a1, a2 … an，玩家L和R在這些竹子上面進(jìn)行游戲，規(guī)則如下：兩人輪流操作，玩家L先手；對(duì)于每次操作，先選定一棵高度不為0的竹子，然后砍掉該竹子的某一段，并且將與竹子底部不相連的部分也去掉； 最先無(wú)法進(jìn)行操作的人輸。假設(shè)玩家L和R都采取最優(yōu)策略，問(wèn)對(duì)于給出的局面誰(shuí)會(huì)獲勝。,,,,,,,,,Hack This,引言,對(duì)于上述

2、問(wèn)題，根據(jù)The Sprague-Grundy Theorem，我們可以輕松地設(shè)計(jì)出一個(gè)時(shí)間復(fù)雜度為O(n)的算法。詳見(jiàn)2007年王曉柯前輩的論文,引言,The Sprague-Grundy Theorem能在本題使用的前提條件對(duì)于任意局面，玩家L和玩家R的可選決策都相同 如果兩者的可選決策不相同會(huì)怎樣?我們不妨在游戲規(guī)則處再多加一條：竹子的每一段都被標(biāo)上了L或者R，玩家L只能砍被標(biāo)上L的段，玩家R只能砍被標(biāo)上R的段

3、。 加上上述規(guī)則后，玩家L和玩家R的可選決策就不相同了。 同時(shí)我們還發(fā)現(xiàn)The Sprague-Grundy Theorem在上述問(wèn) 題上也不再成立。,引言,本文所要探討的正是如何解決這類(lèi)兩個(gè)玩家的可選決策集合不相同的博弈問(wèn)題，也稱(chēng)之為不平等博弈問(wèn)題（Partizan Games）,概覽,第一部分：介紹如何利用Surreal Number分析一類(lèi)不平等組合游戲第二部分：介紹如何通過(guò)動(dòng)態(tài)規(guī)劃、迭代等方法解決不平

4、等博弈問(wèn)題第三部分：總結(jié)全文,Surreal Number的定義,一個(gè)surreal number由兩個(gè)集合組成。我們稱(chēng)這兩個(gè)集合為“左集合”與“右集合”。 通常情況下，我們會(huì)將surreal number寫(xiě)作{ L | R }，其中L表示左集合，R表示右集合。左集合和右集合中的元素也為surreal number，且右集合中不存在元素x使得左集合中存在元素y滿(mǎn)足x ? y。,,? 的定義,對(duì)于surreal number x

5、 = { XL | XR }和y = { YL | YR }，我們稱(chēng) 當(dāng)且僅當(dāng)不存在 使得 以及不存在 使得 。得出 ?的定義后，我們還可

6、以定義<、=我們稱(chēng)x < y表示 我們稱(chēng)x = y表示,,,,,,,,,,Surreal Number的構(gòu)造,第一個(gè)surreal number： 構(gòu)造出0后，嘗試?yán)?構(gòu)造新的surreal number，可得：{ 0 | }，{ | 0 }以及{0 | 0} 因?yàn)? ? 0，所以{ 0 | 0 }不是一個(gè)合法的surreal number。因?yàn)閧 | 0 } < 0 <

7、 { 0 | }，所以令{ | 0 } = -1，{ 0 | } = 1。,,Surreal Number的構(gòu)造,利用0,1,-1作為左集合與右集合的元素，我們可以構(gòu)造出17個(gè)合法的surreal number因?yàn)閧 1 | } > 1，{ | -1} < -1，所以令{ 1 | } = 2，{ | -1} = -2。因?yàn)? < { 0 | 1 } < 1，且{ 0 | 1 } + { 0 | 1 } = 1

8、，因此我們令{ 0 | 1 } = 1/2。同理我們可以得出{ -1 | 0 } = -1/2。,Surreal Number的構(gòu)造,如此類(lèi)推，我們可以構(gòu)造出所有形如j/2k的有理數(shù)。具體而言，我們可以定義如下函數(shù)來(lái)建立部分有理數(shù)與surreal number的對(duì)應(yīng)關(guān)系，我們稱(chēng)這個(gè)函數(shù)為達(dá)利函數(shù)：,,Surreal Number的基本定理,定理 對(duì)于一個(gè)surreal number x = { L | R }，若集合L中有最大元素lm

9、ax，那么{ lmax | R } = x；類(lèi)似地，若集合R中有最小元素rmin，那么{ L | rmin } = x。例子：{ 2, 3 | 4, 5} = { 3 | 4, 5} = { 2, 3 | 4} = { 3 | 4 }。,Surreal Number的加法運(yùn)算,對(duì)于surreal number x = { XL | XR }和y = { YL | YR }，它們的加法運(yùn)算被定義為：

10、 其中對(duì)于集合X與surreal number y， 邊界情況：,,,,?①,②,游戲的定義,游戲有2名參與者，兩人輪流操作。游戲過(guò)程中的任意時(shí)刻有確定的狀態(tài)。 參與者操作時(shí)將游戲從當(dāng)前狀態(tài)轉(zhuǎn)移到另一狀態(tài)，規(guī)則規(guī)定了在任意一個(gè)狀態(tài)時(shí)，參與者可

11、以到達(dá)的狀態(tài)集合。游戲總會(huì)在有限步數(shù)之內(nèi)結(jié)束(沒(méi)有平局)。參與者擁有完全的信息。本文只討論最先不能進(jìn)行操作者輸?shù)那闆r。,游戲的表示,對(duì)于一個(gè)游戲，如果它當(dāng)前處于狀態(tài)P，玩家L可以轉(zhuǎn)移到的狀態(tài)的集合為PL，玩家R可以轉(zhuǎn)移到的狀態(tài)的集合為PR，那么我們把這個(gè)游戲?qū)懽鱌 = { PL | PR }。例子：當(dāng)前所處的狀態(tài)：P 玩家L可以到達(dá)的狀態(tài)：A B C 玩家R可以到達(dá)的狀態(tài)：D 則：P = {

12、A B C | D },Surreal Number與游戲,如果G > 0，那么無(wú)論先手還是后手，玩家L都會(huì)獲勝。如果G < 0，那么無(wú)論先手還是后手，玩家R都會(huì)獲勝。如果G = 0，那么誰(shuí)后手誰(shuí)獲勝。,Surreal Number與游戲,游戲的和如果一個(gè)游戲G可以被分解成n個(gè)不相交的子游戲G1, G2, … Gn，使得對(duì)G的每次操作等價(jià)于從n個(gè)子游戲中選取一個(gè)來(lái)進(jìn)行操作，那么我們稱(chēng)游戲G是游戲G1, G2,

13、… Gn的和，寫(xiě)作G = G1 + G2 +…+ Gn。 定理 如果游戲G等于surreal number x，游戲H等于surreal number y，那么游戲G + H等于surreal number x + y。,Procrastination,有一個(gè)叫Procrastination的游戲，規(guī)則如下：游戲一開(kāi)始有四座由正方體疊成的塔，且所有的正方體要么黑色，要么白色。有兩個(gè)玩家L和R，兩個(gè)人輪流進(jìn)行操作。每次操作，玩

14、家要選定一個(gè)正方體，然后拿走該正方體以及位于該正方體上面的所有正方體，并且規(guī)定玩家L只能選定白色的正方體，玩家R只能選定黑色的正方體。最先不能進(jìn)行操作的人輸。,,B,,,B,,B,B,,,,,B,B,,Choose this,,Procrastination,對(duì)于一個(gè)局面，如果玩家L無(wú)論先手還是后手都能獲勝，那么我們稱(chēng)這是一個(gè)L局面。定義子局面C表示一個(gè)由三座塔組成的局面。一個(gè)完整的游戲局面可以由一個(gè)子局面C以及一座塔T構(gòu)成，寫(xiě)作(

15、C, T)。對(duì)于兩個(gè)子局面C1和C2，我們稱(chēng)C1不差于C2當(dāng)且僅當(dāng)對(duì)于任意的一座塔T，當(dāng)(C2, T)為L(zhǎng)局面時(shí)(C1, T)也為L(zhǎng)局面。 給出兩個(gè)子局面C1和C2，問(wèn)是否C1不差于C2。,Procrastination,考慮只有一座塔的情況：,,,,,,,,,,,,,Procrastination,不難得出：,,,,,,n個(gè),…,,,,,,,,n個(gè),…,,,Procrastination,考察：當(dāng)m=1時(shí)：,m個(gè),C1,

16、C1,,C2,,…,…,,n個(gè),,,,,,,n個(gè),…,,,Procrastination,考察：當(dāng)m=1時(shí)：,m個(gè),C1,C1,,C2,,…,…,,n個(gè),,,,,,n個(gè),,,,…,Procrastination,當(dāng)m>1時(shí)：,m個(gè),C1,C1,,C2,,…,…,,n個(gè),,,,u,,,m個(gè),C1,C1,,C2,,…,…,,n個(gè),,,,u,,設(shè)u為由最下面的n+m-1個(gè)正方體疊成的塔對(duì)應(yīng)的surreal number,Pro

17、crastination,SurrealNumber(T) //T[i]表示塔T從下往上數(shù)第i個(gè)正方體的顏色x ← 0i ← 1n ← 塔T的大小while i ? n and T[i] = T[1]if T[i] = 白色 then x ← x + 1 else x ← x - 1i ← i + 1k ← 2while i ? nif T[i] = 白色 then x ← x + 1/k else x ← x

18、 - 1/ki ← i + 1k ← k * 2return x,,,B,,,B,,,B,,,,,,時(shí)間復(fù)雜度：O(N),Procrastination,考慮局面G由n座塔T1, T2, … Tn組成T1, T2, … Tn對(duì)應(yīng)的surreal number為x1, x2, … xn,,Procrastination,,G為L(zhǎng)局面,G > 0,C1不差于C2,,當(dāng)C2 + H > 0時(shí)，C1 + H >

19、0,判斷是否C1 ? C2 !,總結(jié),從上面的例子可以看出，利用surreal number分析不平等博弈問(wèn)題，不僅思路清晰，而且程序的實(shí)現(xiàn)也相當(dāng)簡(jiǎn)潔，但不同的不平等博弈問(wèn)題分析思路也不盡相同，在我的論文中提供了多種分析思路。希望本文能為大家打開(kāi)一扇窗，在遇到博弈問(wèn)題的時(shí)候多一些解決問(wèn)題的手段。,謝謝！,The Easy Chase,玩家L與玩家R很喜歡玩一個(gè)雙人的棋類(lèi)游戲，游戲規(guī)則如下：在一個(gè)大小為n*n的棋盤(pán)上，有一個(gè)白色的棋子，

20、初始位置為(wx, wy)，與一個(gè)黑色的棋子，初始位置為(bx, by)。玩家L執(zhí)白先行，玩家R執(zhí)黑后行，兩人交替行棋。如果當(dāng)前是玩家L行棋，玩家L可以在上下左右四個(gè)方向中選一個(gè)并讓他的棋子在該方向前進(jìn)一格；如果當(dāng)前是玩家R行棋，玩家R可以在上下左右四個(gè)方向中選一個(gè)并讓他的棋子在該方向前進(jìn)一格或兩格（均不能走出棋盤(pán)）。一個(gè)人取得勝利當(dāng)且僅當(dāng)他的棋子走到了對(duì)方的棋子當(dāng)前所在的位置。,The Easy Chase,玩家L與玩家R都采取同樣

21、的策略行棋：如果一方能贏，一定會(huì)用盡量少的步數(shù)去贏；如果一方會(huì)輸，一定會(huì)拖盡量多的步數(shù)才輸。假設(shè)玩家L與玩家R都絕頂聰明，行棋中途均不犯錯(cuò)誤，你能提前預(yù)測(cè)最終的勝者以及棋局持續(xù)的步數(shù)嗎？數(shù)據(jù)規(guī)模：2 ? n ? 20,The Easy Chase,用一個(gè)五元組(x1, y1, x2, y2, cur)來(lái)刻畫(huà)一個(gè)局面 對(duì)于一個(gè)局面G，我們用函數(shù)f(G)來(lái)描述G的勝負(fù)情況。定義infinite為一個(gè)很大的正整數(shù)，不妨設(shè)為108。如果局

22、面G的勝者為玩家L且棋局持續(xù)x步，則f(G) = infinite – x；如果局面G的勝者為玩家R且棋局持續(xù)x步，則f(G) = -infinite + x。,The Easy Chase,邊界：f(x, y, x, y, L) = -infinite，f(x, y, x, y, R) = infinite。轉(zhuǎn)移：f(x1, y1, x2, y2, L) = max{ f(x1’, y1’, x2, y2, R) – sign(f

23、(x1’, y1’, x2, y2, R)) }f(x1, y1, x2, y2, R) = min{ f(x1, y1, x2’, y2’, L) – sign(f(x1, y1, x2’, y2’, L)) },其中(x1, y1)?(x2, y2)，(x1’, y1’)為白色棋子在(x1, y1)時(shí)走一步可以到達(dá)的位置，(x2’, y2’)為黑色棋子在(x2, y2)時(shí)走一步可以到達(dá)的位置。,。,The Easy Chase,用

24、類(lèi)似于SPFA的迭代算法來(lái)解決局面的計(jì)算順序問(wèn)題,Count(G’)初始化f，對(duì)于所有的局面G，令f(G) = 0枚舉所有的終止局面Ge，確定f(Ge)的值，并將Ge放入隊(duì)列q中while q不為空 取出隊(duì)首元素，并令其為Y for 每個(gè)可以一步到達(dá)局面Y的局面Xtmp ← f(X)根據(jù)狀態(tài)轉(zhuǎn)移方程重新計(jì)算f(X)if tmp ? f(X) and X不在隊(duì)列q中 then 將X放入隊(duì)列q中ret

25、urn f(G’),證明0 < { 0 | },證明：0 ? { 0 | } ?& ? ({ 0 | } ? 0)先證明：0 ? 0,定理１證明,?a ? A : a {A|B}?a ? A : a ? {A|B}①; ?a ? A : ?({A|B} ? a)②通過(guò)歸納法證明。首先當(dāng)A為空集時(shí)命題正確①等價(jià)于上述命題的右半部分顯然正確，從surreal number定義可知；其左半部分等價(jià)于

26、 也就是：在上面命題的左邊令a’=a，則有 由歸納法的性質(zhì)可以知道該命題是正確的，所以上面命題是正確的。所以①是正確的。類(lèi)似地可以得出②也是正確的。,定理2證明,不妨設(shè)存在x = {x1, x2, … | XR }且x1 < x2證明： {x1, x2, … | XR } ? {x2, … | XR } {x2, … | XR } ? {

27、x1, x2, … | XR } 通過(guò)定義證明,定理3證明,先證明：如果surreal number x大于集合A中的任意元素且小于集合B中的任意元素，則x = { A, XL| XR, B }利用定義證明設(shè)x為a、b之間最早出生的surreal number，且x的父母為xL和xR，則有：{xL | xR } = {a, xL | b, xR } = x{ a | b } = {a, xL | b, xR } = x,,Pr

28、ocrastination,我們先將在塔T最上面的m + 1個(gè)正方體從上往下編號(hào)為m, m – 1, m – 2, … 0，然后分兩種情況進(jìn)行討論：,m個(gè),,C1,C2,k,,…,…,,n個(gè),,,,u,…,,v,Procrastination,Surreal Number的一些基本定理,定理1　對(duì)于一個(gè)surreal number x = { L | R }，x大于L中的任意一個(gè)元素且小于R中的任意一個(gè)元素。 定理2 對(duì)于一個(gè)sur

29、real number x = { L | R }，若集合L中有最大元素lmax，那么{ lmax | R } = x；類(lèi)似地，若集合R中有最小元素rmin，那么{ L | rmin } = x。定理3 如果a < x < b，且x是a到b之間最早出生的surreal number，那么{ a | b } = x。,Surreal Number加法運(yùn)算的基本性質(zhì),對(duì)于surreal number x = { XL | X

30、R }和y = { YL | YR }，x + y = { XL + y, x + YL | XR + y, x + YR }也是一個(gè)合法的surreal number。surreal number的加法滿(mǎn)足交換率。surreal number的加法滿(mǎn)足結(jié)合率。,游戲的定義,游戲有2名參與者，兩人輪流操作。游戲過(guò)程中的任意時(shí)刻有確定的狀態(tài)。 參與者操作時(shí)將游戲從當(dāng)前狀態(tài)轉(zhuǎn)移到另一狀態(tài)，規(guī)則規(guī)定了在任意一個(gè)狀態(tài)時(shí)，參與者可以到達(dá)的