算法合集之淺談如何解決不平等博弈問(wèn)題-wenkub
2022-10-31 20:35:02 本頁(yè)面
【正文】 滿(mǎn)足 x ? y。 同時(shí)我們還發(fā)現(xiàn) The SpragueGrundy Theorem在上述問(wèn) 題上也不再成立。 假設(shè)玩家 L和 R都采取最優(yōu)策略，問(wèn)對(duì)于給出的局面誰(shuí) 會(huì)獲勝。 Hack This 引言 ? 對(duì)于上述問(wèn)題，根據(jù) The SpragueGrundy Theorem，我們可以輕松地設(shè)計(jì)出一個(gè)時(shí)間復(fù)雜度為 O(n)的算法。 引言 ? 本文所要探討的正是如何解決這類(lèi)兩個(gè)玩家的 可選決策集合不相同的博弈問(wèn)題，也稱(chēng)之為不 平等博弈問(wèn)題（ Partizan Games） 概覽 ? 第一部分：介紹如何利用 Surreal Number分析一類(lèi)不平等組合游戲 ? 第二部分：介紹如何通過(guò)動(dòng)態(tài)規(guī)劃、迭代等方法解決不平等博弈問(wèn)題 ? 第三部分：總結(jié)全文 Surreal Number的定義 ? 一個(gè) surreal number由兩個(gè)集合組成。 ? 的定義 ? 對(duì)于 surreal number x = { XL | XR }和 y = { YL | YR }，我們稱(chēng) 當(dāng)且僅當(dāng)不存在 使得 以及不存在 使得 。 ? 因?yàn)?0 { 0 | 1 } 1，且 { 0 | 1 } + { 0 | 1 } = 1，因此我們令 { 0 | 1 } = 1/2。 ? 例子： ? { 2, 3 | 4, 5} = { 3 | 4, 5} = { 2, 3 | 4} = { 3 | 4 }。 ? 游戲總會(huì)在有限步數(shù)之內(nèi)結(jié)束 (沒(méi)有平局 )。 ? 例子：當(dāng)前所處的狀態(tài)： P 玩家 L可以到達(dá)的狀態(tài)： A B C 玩家 R可以到達(dá)的狀態(tài)： D 則： P = { A B C | D } Surreal Number與游戲 ? 如果 G 0，那么無(wú)論先手還是后手，玩家 L都會(huì)獲勝。 ? 定理 如果游戲 G等于 surreal number x，游戲 H等于surreal number y，那么游戲 G + H等于 surreal number x + y。 ? 最先不能進(jìn)行操作的人輸。 ? 對(duì)于兩個(gè)子局面 C1和 C2，我們稱(chēng) C1不差于 C2當(dāng)且僅當(dāng)對(duì)于任意的一座塔 T，當(dāng) (C2, T)為 L局面時(shí) (C1, T)也為 L局面。 The Easy Chase ? 玩家 L與玩家 R很喜歡玩一個(gè)雙人的棋類(lèi)游戲，游戲規(guī)則如下： ? 在一個(gè)大小為 n*n的棋盤(pán)上，有一個(gè)白色的棋子，初始位置為 (wx, wy)，與一個(gè)黑色的棋子，初始位置為(bx, by)。 The Easy Chase ? 玩家 L與玩家 R都采取同樣的策略行棋：如果一方能贏，一定會(huì)用盡量少的步數(shù)去贏；如果一方會(huì)輸，一定會(huì)拖盡量多的步數(shù)才輸。 The Easy Chase ? 邊界： f(x, y, x, y, L) = infinite， f(x, y, x, y, R) = infinite。 ? ({ 0 | } ? 0) ? 先證明： 0 ? 0 定理１證明 ? ?a ? A : a {A|B} ? ? ?b ? B : b {A|B} ? ?a ? A : a ? {A|B}① 。類(lèi)似地可以得出 ②也是正確的。 Surreal Number加法運(yùn)算的基本性質(zhì) ? 對(duì)于 surreal numbe
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1