淺談如何解決不平等博弈問題

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

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

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

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

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

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

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

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

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

11、以到達(dá)的狀態(tài)集合。游戲總會在有限步數(shù)之內(nèi)結(jié)束(沒有平局)。參與者擁有完全的信息。本文只討論最先不能進(jìn)行操作者輸?shù)那闆r。,游戲的表示,對于一個游戲，如果它當(dāng)前處于狀態(tài)P，玩家L可以轉(zhuǎn)移到的狀態(tài)的集合為PL，玩家R可以轉(zhuǎn)移到的狀態(tài)的集合為PR，那么我們把這個游戲?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，那么無論先手還是后手，玩家L都會獲勝。如果G < 0，那么無論先手還是后手，玩家R都會獲勝。如果G = 0，那么誰后手誰獲勝。,Surreal Number與游戲,游戲的和如果一個游戲G可以被分解成n個不相交的子游戲G1, G2, … Gn，使得對G的每次操作等價于從n個子游戲中選取一個來進(jìn)行操作，那么我們稱游戲G是游戲G1, G2,

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

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

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

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

17、crastination,SurrealNumber(T) //T[i]表示塔T從下往上數(shù)第i個正方體的顏色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,,,,,,時間復(fù)雜度：O(N),Procrastination,考慮局面G由n座塔T1, T2, … Tn組成T1, T2, … Tn對應(yīng)的surreal number為x1, x2, … xn,,Procrastination,,G為L局面,G > 0,C1不差于C2,,當(dāng)C2 + H > 0時，C1 + H >

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

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

21、的策略行棋：如果一方能贏，一定會用盡量少的步數(shù)去贏；如果一方會輸，一定會拖盡量多的步數(shù)才輸。假設(shè)玩家L與玩家R都絕頂聰明，行棋中途均不犯錯誤，你能提前預(yù)測最終的勝者以及棋局持續(xù)的步數(shù)嗎？數(shù)據(jù)規(guī)模：2 ? n ? 20,The Easy Chase,用一個五元組(x1, y1, x2, y2, cur)來刻畫一個局面 對于一個局面G，我們用函數(shù)f(G)來描述G的勝負(fù)情況。定義infinite為一個很大的正整數(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)時走一步可以到達(dá)的位置，(x2’, y2’)為黑色棋子在(x2, y2)時走一步可以到達(dá)的位置。,。,The Easy Chase,用

24、類似于SPFA的迭代算法來解決局面的計(jì)算順序問題,Count(G’)初始化f，對于所有的局面G，令f(G) = 0枚舉所有的終止局面Ge，確定f(Ge)的值，并將Ge放入隊(duì)列q中while q不為空 取出隊(duì)首元素，并令其為Y for 每個可以一步到達(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)②通過歸納法證明。首先當(dāng)A為空集時命題正確①等價于上述命題的右半部分顯然正確，從surreal number定義可知；其左半部分等價于

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

27、x1, x2, … | XR } 通過定義證明,定理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個正方體從上往下編號為m, m – 1, m – 2, … 0，然后分兩種情況進(jìn)行討論：,m個,,C1,C2,k,,…,…,,n個,,,,u,…,,v,Procrastination,Surreal Number的一些基本定理,定理1　對于一個surreal number x = { L | R }，x大于L中的任意一個元素且小于R中的任意一個元素。 定理2 對于一個sur

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

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