算法合集之淺談如何解決不平等博弈問題(編輯修改稿)
2025-11-12 20:35 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 2, … G n，使得對(duì) G的每次操作等價(jià)于從 n個(gè)子游戲中選取一個(gè)來進(jìn)行操作，那么我們稱游戲 G是游戲 G1, G2, … Gn的和，寫作 G = G1 + G2 +…+ G n。 ? 定理 如果游戲 G等于 surreal number x，游戲 H等于surreal number y，那么游戲 G + H等于 surreal number x + y。 Procrastination ? 有一個(gè)叫 Procrastination的游戲，規(guī)則如下： ? 游戲一開始有四座由正方體疊成的塔，且所有的正方體要么黑色，要么白色。 ? 有兩個(gè)玩家 L和 R，兩個(gè)人輪流進(jìn)行操作。 ? 每次操作，玩家要選定一個(gè)正方體，然后拿走該正方體以及位于該正方體上面的所有正方體，并且規(guī)定玩家 L只能選定白色的正方體，玩家 R只能選定黑色的正方體。 ? 最先不能進(jìn)行操作的人輸。 B B B B B B Choose this Procrastination ? 對(duì)于一個(gè)局面，如果玩家 L無論先手還是后手都能獲勝，那么我們稱這是一個(gè) L局面。 ? 定義子局面 C表示一個(gè)由三座塔組成的局面。一個(gè)完整的游戲局面可以由一個(gè)子局面 C以及一座塔 T構(gòu)成，寫作 (C, T)。 ? 對(duì)于兩個(gè)子局面 C1和 C2，我們稱 C1不差于 C2當(dāng)且僅當(dāng)對(duì)于任意的一座塔 T，當(dāng) (C2, T)為 L局面時(shí) (C1, T)也為 L局面。 ? 給出兩個(gè)子局面 C1和 C2，問是否 C1不差于 C2。 Procrastination ? 考慮只有一座塔的情況： 0{ |} ??G1|}0{ ??G2|}1,0{ ??GProcrastination ? 不難得出： n個(gè) … nG ?n個(gè) … nG ??Procrastination ? 考察： ? 當(dāng) m=1時(shí)： m個(gè) C1 C1 C2 … … n個(gè) n個(gè) … 21}|1{}|1,...1,0{ ?????? nnnnnGProcrastination ? 考察： ? 當(dāng) m=1時(shí)： m個(gè) C1 C1 C2 … … n個(gè) n個(gè) 21}|1,...1,0{ ???????? nnnG… Procrastination ? 當(dāng) m1時(shí)： m個(gè) C1 C1 C2 … … n個(gè) u muG 21??m個(gè) C1 C1 C2 … … n個(gè) u muG 21??設(shè) u為由最下面的 n+m1個(gè)正方體疊成的塔對(duì)應(yīng)的 surreal number Procrastination SurrealNumber(T) //T[i]表示塔 T從下往上數(shù)第 i個(gè)正方體的顏色 1. x ← 0 2. i ← 1 3. n ← 塔 T的大小 4. while i ? n and T[i] = T[1] 5. if T[i] = 白色 then x ← x + 1 else x ← x 1 6. i ← i + 1 7. k ← 2 8. while i ? n 9. if T[i] = 白色 then x ← x + 1/k else x ← x 1/k 10. i ← i + 1 11. k ← k * 2 12. return x B B B 1?1?1?21?41?161?321?Procrastination ? 考慮局面 G由 n座塔
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1