算法合集之淺談如何解決不平等博弈問題-在線瀏覽
2024-12-03 20:35本頁面
【正文】 /2。具體而言，我們可以定義如下函數(shù)來建立部分有理數(shù)與 surreal number的對應關系，我們稱這個函數(shù)為達利函數(shù)： ????????????????????????0,2) } ,21(|)21({0) } ,1({|0| } ,)1({0{ | } ,)(kZkjjxjjZxxxZxxxxxkkk?????Surreal Number的基本定理 ? 定理 對于一個 surreal number x = { L | R }，若集合 L中有最大元素 lmax，那么 { lmax | R } = x；類似地，若集合 R中有最小元素 rmin，那么 { L | rmin } = x。 Surreal Number的加法運算 ? 對于 surreal number x = { XL | XR }和 y = { YL | YR }，它們的加法運算被定義為： ? 其中對于集合 X與 surreal number y， ? 邊界情況： },|,{}|{}|{ RRLLRLRL YxyXYxyXYYXXyx ????????}:{ XxyxyX ???????? n?① ② 游戲的定義 ? 游戲有 2名參與者，兩人輪流操作。 ? 參與者操作時將游戲從當前狀態(tài)轉(zhuǎn)移到另一狀態(tài)，規(guī)則規(guī)定了在任意一個狀態(tài)時，參與者可以到達的狀態(tài)集合。 ? 參與者擁有完全的信息。 游戲的表示 ? 對于一個游戲，如果它當前處于狀態(tài) P，玩家 L可以轉(zhuǎn)移到的狀態(tài)的集合為 PL，玩家 R可以轉(zhuǎn)移到的狀態(tài)的集合為 PR，那么我們把這個游戲?qū)懽?P = { PL | PR }。 ? 如果 G 0，那么無論先手還是后手，玩家 R都會獲勝。 Surreal Number與游戲 ? 游戲的和 ? 如果一個游戲 G可以被分解成 n個不相交的子游戲 G1, G2, … G n，使得對 G的每次操作等價于從 n個子游戲中選取一個來進行操作，那么我們稱游戲 G是游戲 G1, G2, … Gn的和，寫作 G = G1 + G2 +…+ G n。 Procrastination ? 有一個叫 Procrastination的游戲，規(guī)則如下： ? 游戲一開始有四座由正方體疊成的塔，且所有的正方體要么黑色，要么白色。 ? 每次操作，玩家要選定一個正方體，然后拿走該正方體以及位于該正方體上面的所有正方體，并且規(guī)定玩家 L只能選定白色的正方體，玩家 R只能選定黑色的正方體。 B B B B B B Choose this Procrastination ? 對于一個局面，如果玩家 L無論先手還是后手都能獲勝，那么我們稱這是一個 L局面。一個完整的游戲局面可以由一個子局面 C以及一座塔 T構(gòu)成，寫作 (C, T)。 ? 給出兩個子局面 C1和 C2，問是否 C1不差于 C2。希望本文能為大家打開一扇窗，在遇到博弈問題的時候多一些解決問題的手段。玩家 L執(zhí)白先行，玩家 R執(zhí)黑后行，兩人交替行棋。一個人取得勝利當且僅當他的棋子走到了對方的棋子當前所在的位置。 ? 假設玩家 L與玩家 R都絕頂聰明，行棋中途均不犯錯誤，你能提前預測最終的勝者以及棋局持續(xù)的步數(shù)嗎？ ? 數(shù)據(jù)規(guī)模： 2 ? n ? 20 The Easy Chase ? 用一個五元組 (x1, y1,
教學課件相關推薦
鄂ICP備17016276號-1