博弈論進階之Multi-SG

Multi-Nim

從最簡單的Nim模型開始

它的定義是這樣的

有\(n\)堆石子，兩個人可以從任意一堆石子中拿任意多個石子(不能不拿)或把一堆數量不少于\(2\)石子分為兩堆不為空的石子，沒法拿的人失敗。問誰會勝利

博弈分析

這個問題的本質還是Nim遊戲，可以利用SG定理來解釋

通過觀察不難不發現，操作一與普通的Nim遊戲等價

操作二實際上是将一個遊戲分解為兩個遊戲，根據SG定理，我們可以通過異或運算把兩個遊戲連接配接到一起，作為一個後繼狀态

煮個栗子

SG(3)的後繼狀态有\(\{ (0),(1),(2),(1,2) \}\)他們的SG值分别為\(\{ 0,1,2,3 \}\)，是以\(SG(3)=mex\{ 0,1,2,3 \}=4\)

另外這種遊戲還有一個非常神奇的性質

\[SG\left( x\right) =\begin{cases}x-1\left( x\mod4=0\right) \\ x\left( x\mod4=1 \lor 2\right) \\ x+1\left( x\mod4=3\right) \end{cases}

\]

然後把這個結論背過就好啦233

Multi-SG

根據上面的遊戲，我們定義Multi-SG遊戲

• Multi-SG 遊戲規定，在符合拓撲原則的前提下，一個單一遊戲的

  後繼

  可以為

  多個單一遊戲

  。
• Multi-SG其他規則與SG遊戲相同。

注意在這裡要厘清楚

後繼

與

多個單一遊戲

對于一個狀态來說，不同的劃分方法會産生多個不同的後繼，而在一個後繼中可能含有多個獨立的遊戲

一個後繼狀态的SG值即為後繼狀态中獨立遊戲的異或和

該狀态的SG值即為後繼狀态的SG值中未出現過的最小值

例題

難度跨度好大啊QWQ。。

直接放題解吧

HDU 3032

POJ 2311

BZOJ 2940

BZOJ 1188

洛谷 3235

作者：自為風月馬前卒

個人部落格http://attack204.com//

出處：http://zwfymqz.cnblogs.com/

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。