算法合集之淺談如何解決不平等博弈問題-展示頁
2024-10-25 20:35本頁面
【正文】 以及不存在 使得 。 ? 通常情況下，我們會(huì)將 surreal number寫作 { L | R }，其中 L表示左集合， R表示右集合。 引言 ? 本文所要探討的正是如何解決這類兩個(gè)玩家的 可選決策集合不相同的博弈問題，也稱之為不 平等博弈問題（ Partizan Games） 概覽 ? 第一部分：介紹如何利用 Surreal Number分析一類不平等組合游戲 ? 第二部分：介紹如何通過動(dòng)態(tài)規(guī)劃、迭代等方法解決不平等博弈問題 ? 第三部分：總結(jié)全文 Surreal Number的定義 ? 一個(gè) surreal number由兩個(gè)集合組成。 加上上述規(guī)則后，玩家 L和玩家 R的可選決策就不相同了。 Hack This 引言 ? 對(duì)于上述問題，根據(jù) The SpragueGrundy Theorem，我們可以輕松地設(shè)計(jì)出一個(gè)時(shí)間復(fù)雜度為 O(n)的算法。淺談如何解決不平等博弈問題 廣東省中山市第一中學(xué) 方展鵬 引言 ? 給出 n棵竹子，高度分別為 a1, a2 … a n，玩家 L和 R在這些竹子上面進(jìn)行游戲，規(guī)則如下： ① 兩人輪流操作，玩家 L先手； ② 對(duì)于每次操作，先選定一棵高度不為 0的竹子，然后砍掉該竹子的某一段，并且將與竹子底部不相連的部分也去掉； ③ 最先無法進(jìn)行操作的人輸。 假設(shè)玩家 L和 R都采取最優(yōu)策略，問對(duì)于給出的局面誰 會(huì)獲勝。 ? 詳見 2021年王曉柯前輩的論文 )() . . .()(),...,( 2121 nn xgxgxgxxxg ???引言 ? The SpragueGrundy Theorem能在本題使用的前提條件 ? 對(duì)于任意局面，玩家 L和玩家 R的可選決策都相同 ? 如果兩者的可選決策不相同會(huì)怎樣 ? ? 我們不妨在游戲規(guī)則處再多加一條：竹子的每一段都被標(biāo)上了 L或者 R，玩家 L只能砍被標(biāo)上 L的段，玩家 R只能砍被標(biāo)上 R的段。 同時(shí)我們還發(fā)現(xiàn) The SpragueGrundy Theorem在上述問 題上也不再成立。我們稱這兩個(gè)集合為“左集合”與“右集合”。 ? 左集合和右集合中的元素也為 surreal number，且右集合中不存在元素 x使得左集合中存在元素 y滿足 x ? y。 ? 得出 ?的定義后，我們還可以定義 、 = ? 我們稱 x y表示 ? 我們稱 x = y表示 yx ? LL Xx ?Lxy ? RR Yy ?xyR ?)( xyyx ????xyyx ???Surreal Number的構(gòu)造 ? 第一個(gè) surreal number： ? 構(gòu)造出 0后，嘗試?yán)?0構(gòu)造新的 surreal number，可得： ? { 0 | }， { | 0 }以及 {0 | 0} ? 因?yàn)?0 ? 0，所以 { 0 | 0 }不是一個(gè)合法的 surreal number。 }|{ ?? {|}? 0?Surreal Number的構(gòu)造 ? 利用 0,1,1作為左集合與右集合的元素，我們可以構(gòu)造出 17個(gè)合法的 surreal number ? 因?yàn)?{ 1 | } 1， { | 1} 1，所以令 { 1 | } = 2， { | 1} = 2。 ? 同理我們可以得出 { 1 | 0 } = 1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1