算法合集之組合游戲略述——淺談sg游戲的若干拓展及(已修改)
2025-05-28 22:06 本頁(yè)面
【正文】 組合游戲略述 —— 淺談組合游戲的若干拓展及變形 石家莊二中 北校區(qū) 高三 18班 賈志豪 6/16/2021 石家莊二中 賈志豪 第 2頁(yè) 內(nèi)容概述 content introduction ?組合游戲的規(guī)則 拓展 ? 走完最后一步者輸 —— AntiSG游戲和 SJ定理 ? 可以將一堆石子分成多堆 —— MultiSG游戲 ? 每一個(gè)可移動(dòng)的棋子都要移動(dòng) —— EverySG游戲 ?組合游戲的模型 變形 ? 翻硬幣游戲 ? 無(wú)向圖刪邊游戲 每一個(gè)可移動(dòng)的棋子都要移動(dòng) —— 游戲無(wú)向圖刪邊游戲6/16/2021 石家莊二中 賈志豪 第 3頁(yè) EverySG游戲 ?何為 EverySG游戲？？？ ? 有 N個(gè)單一游戲，游戲者輪流進(jìn)行決策； ? 游戲者的決策必須滿足：對(duì)于所有還沒(méi)有結(jié)束的單一游戲，游戲者必須對(duì)該單一游戲進(jìn)行一步操作； ? 無(wú)路可走者輸 怎么辦？ 怎么辦？？ 怎么辦？？？ 6/16/2021 石家莊二中 賈志豪 第 4頁(yè) EverySG游戲 ?貪心策略： ? 對(duì)于某一個(gè)單一游戲，如果當(dāng)前是先手必勝局，那么先手不會(huì)放棄游戲的勝利?。?！ ? 那么，游戲者需要做的，就是讓自己可以取得勝利的游戲盡可能 長(zhǎng) 的玩下去，讓自己不能取得勝利的游戲盡可能 短 的玩下去！??！ 6/16/2021 石家莊二中 賈志豪 第 5頁(yè) EverySG游戲 ?解決方法： ? 對(duì)于 SG值為 0的點(diǎn)，我們需要知道最少幾步能將游戲帶入終止?fàn)顟B(tài) ； ? 對(duì)于 SG值不為 0的點(diǎn)，我們需要知道最多幾步游戲會(huì)被帶入終止?fàn)顟B(tài) ； ? 以上兩個(gè)值，我們都用 step來(lái)表示 ? ?? ???????????????的后繼狀態(tài)為的后繼狀態(tài)為為終止?fàn)顟B(tài)vuvSGus t e puSGvuvSGus t e pvvs t e p0)(1)(m
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1