《淺談如何解決不平等博弈問題》ppt課件

1、淺談如何處理不平等博弈問題引言給出n棵竹子，高度分別為a1, a2 an，玩家L和R在這些竹子上面進(jìn)展游戲，規(guī)那么如下：兩人輪番操作，玩家L先手；對于每次操作，先選定一棵高度不為0的竹子，然后砍掉該竹子的某一段，并且將與竹子底部不相連的部分也去掉； 最先無法進(jìn)展操作的人輸。假設(shè)玩家L和R都采取最優(yōu)戰(zhàn)略，問對于給出的局面誰會獲勝。Hack This引言對于上述問題，根據(jù)The Sprague-Grundy Theorem，我們可以輕松地設(shè)計出一個時間復(fù)雜度為O(n)的算法。詳見2007年王曉柯長輩的論文)().()(),.,(2121nnxgxgxgxxxg引言The Sprague-Grund

2、y Theorem能在此題運(yùn)用的前提條件對于恣意局面，玩家L和玩家R的可選決策都一樣 假設(shè)兩者的可選決策不一樣會怎樣?我們無妨在游戲規(guī)那么處再多加一條：竹子的每一段都被標(biāo)上了L或者R，玩家L只能砍被標(biāo)上L的段，玩家R只能砍被標(biāo)上R的段。 加上上述規(guī)那么后，玩家L和玩家R的可選決策就不一樣了。 同時我們還發(fā)現(xiàn)The Sprague-Grundy Theorem在上述問 題上也不再成立。 引言本文所要討論的正是如何處理這類兩個玩家的可選決策集合不一樣的博弈問題，也稱之為不平等博弈問題Partizan Games 概覽第一部分：引見如何利用第一部分：引見如何利用Surreal NumberSurre

3、al Number分析一類不平等分析一類不平等組合游戲組合游戲第二部分：引見如何經(jīng)過動態(tài)規(guī)劃、迭代等方法處理不平第二部分：引見如何經(jīng)過動態(tài)規(guī)劃、迭代等方法處理不平等博弈問題等博弈問題第三部分：總結(jié)全文第三部分：總結(jié)全文Surreal Number的定義一個surreal number由兩個集合組成。我們稱這兩個集合為“左集合與“右集合。 通常情況下，我們會將surreal number寫作 L | R ，其中L表示左集合，R表示右集合。左集合和右集合中的元素也為surreal number，且右集合中不存在元素x使得左集合中存在元素y滿足x y。 的定義 對于surreal number x

4、= XL | XR 和y = YL | YR ，我們稱 當(dāng)且僅當(dāng)不存在 使得 以及不存在 使得 。得出 的定義后，我們還可以定義、=我們稱x y表示 我們稱x = y表示yx LLXx Lxy RRYy xyR)(xyyxxyyxSurreal Number的構(gòu)造第一個surreal number： 構(gòu)造出0后，嘗試?yán)?構(gòu)造新的surreal number，可得： 0 | ， | 0 以及0 | 0 由于0 0，所以 0 | 0 不是一個合法的surreal number。由于 | 0 0 1， | -1 -1，所以令 1 | = 2， | -1 = -2。由于0 0 | 1 0，那么無論先

5、手還是后手，玩家L都會獲勝。假設(shè)G 1時：m個C1C1C2n個umuG21m個C1C1C2n個umuG21設(shè)u為由最下面的n+m-1個正方體疊成的塔對應(yīng)的surreal numberProcrastinationSurrealNumber(T) /Ti表示塔T從下往上數(shù)第i個正方體的顏色x 0i 1n 塔T的大小while i n and Ti = T1if Ti = 白色 then x x + 1 else x x - 1i i + 1k 2while i nif Ti = 白色 then x x + 1/k else x x - 1/ki i + 1k k * 2return xBBB11

6、12141161321Procrastination思索局面G由n座塔T1, T2, Tn組成T1, T2, Tn對應(yīng)的surreal number為x1, x2, xn nxxxG.21ProcrastinationG為L局面G 0C1不差于C2當(dāng)C2 + H 0時，C1 + H 0判別能否C1 C2 !總結(jié)從上面的例子可以看出，利用surreal number分析不平等博弈問題，不僅思緒明晰，而且程序的實現(xiàn)也相當(dāng)簡約，但不同的不平等博弈問題分析思緒也不盡一樣，在我的論文中提供了多種分析思緒。希望本文能為大家翻開一扇窗，在遇到博弈問題的時候多一些處理問題的手段。The Easy Chase玩

7、家L與玩家R很喜歡玩一個雙人的棋類游戲，游戲規(guī)那么如下：在一個大小為n*n的棋盤上，有一個白色的棋子，初始位置為(wx, wy)，與一個黑色的棋子，初始位置為(bx, by)。玩家L執(zhí)白先行，玩家R執(zhí)黑后行，兩人交替行棋。假設(shè)當(dāng)前是玩家L行棋，玩家L可以在上下左右四個方向中選一個并讓他的棋子在該方向前進(jìn)一格；假設(shè)當(dāng)前是玩家R行棋，玩家R可以在上下左右四個方向中選一個并讓他的棋子在該方向前進(jìn)一格或兩格均不能走出棋盤。一個人獲得勝利當(dāng)且僅當(dāng)他的棋子走到了對方的棋子當(dāng)前所在的位置。The Easy Chase玩家L與玩家R都采取同樣的戰(zhàn)略行棋：假設(shè)一方能贏，一定會用盡量少的步數(shù)去贏；假設(shè)一方會輸，一

8、定會拖盡量多的步數(shù)才輸。假設(shè)玩家L與玩家R都絕頂聰明，行棋中途均不犯錯誤，他能提早預(yù)測最終的勝者以及棋局繼續(xù)的步數(shù)嗎？數(shù)據(jù)規(guī)模：2 n 20The Easy Chase用一個五元組(x1, y1, x2, y2, cur)來描寫一個局面 對于一個局面G，我們用函數(shù)f(G)來描畫G的勝負(fù)情況。定義infinite為一個很大的正整數(shù)，無妨設(shè)為108。假設(shè)局面G的勝者為玩家L且棋局繼續(xù)x步，那么f(G) = infinite x；假設(shè)局面G的勝者為玩家R且棋局繼續(xù)x步，那么f(G) = -infinite + x。 The Easy Chase邊境：f(x, y, x, y, L) = -infin

9、ite，f(x, y, x, y, R) = infinite。轉(zhuǎn)移：f(x1, y1, x2, y2, L) = max f(x1, y1, x2, y2, R) sign(f(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á)的位置。0, 10, 00, 1)(xxxxsign。The Eas

10、y Chase用類似于SPFA的迭代算法來處理局面的計算順序問題 Count(G)初始化f，對于一切的局面G，令f(G) = 0枚舉一切的終止局面Ge，確定f(Ge)的值，并將Ge放入隊列q中while q不為空 取出隊首元素，并令其為Y for 每個可以一步到達(dá)局面Y的局面Xtmp f(X)根據(jù)形狀轉(zhuǎn)移方程重新計算f(X)if tmp f(X) and X不在隊列q中 then 將X放入隊列q中return f(G)證明0 0 | 證明：0 0 | & ( 0 | 0)先證明：0 0定理證明a A : a A|Ba A : a A|B; a A : (A|B a)經(jīng)過歸納法證明。首先

11、當(dāng)A為空集時命題正確等價于上述命題的右半部分顯然正確，從surreal number定義可知；其左半部分等價于 也就是：在上面命題的左邊令a=a，那么有 由歸納法的性質(zhì)可以知道該命題是正確的，所以上面命題是正確的。所以是正確的。類似地可以得出也是正確的。定理2證明無妨設(shè)存在x = x1, x2, | XR 且x1 x2證明： x1, x2, | XR x2, | XR x2, | XR x1, x2, | XR 經(jīng)過定義證明定理3證明先證明：假設(shè)surreal number x大于集合A中的恣意元素且小于集合B中的恣意元素，那么x = A, XL| XR, B 利用定義證明設(shè)x為a、b之間最早

12、出生的surreal number，且x的父母為xL和xR，那么有：xL | xR = a, xL | b, xR = x a | b = a, xL | b, xR = xProcrastination我們先將在塔T最上面的m + 1個正方體從上往下編號為m, m 1, m 2, 0，然后分兩種情況進(jìn)展討論：m個C1C2kn個uvProcrastinationSurreal Number的一些根本定理 定理定理1 1對于一個對于一個surreal number x = L | R surreal number x = L | R ，x x大于大于L L中的恣意一個元素且小于中的恣意一個元素且

13、小于R R中的恣意一個元素。中的恣意一個元素。 定理定理2 2 對于一個對于一個surreal number x = L | R surreal number x = L | R ，假設(shè)集，假設(shè)集合合L L中有最大元素中有最大元素lmaxlmax，那么，那么 lmax | R = x lmax | R = x；類似地，；類似地，假設(shè)集合假設(shè)集合R R中有最小元素中有最小元素rminrmin，那么，那么 L | rmin = x L | rmin = x。定理定理3 3 假設(shè)假設(shè)a x ba x b，且，且x x是是a a到到b b之間最早出生的之間最早出生的surreal numbersurreal number，那么，那么 a | b = x a | b = x。 Surreal Number加法運(yùn)算的根本性質(zhì)對于surreal number x = XL | XR 和y = YL | YR ，x + y = XL + y, x + YL | XR + y, x