引言

在《博弈圣經》中博弈論的定義：我們把動物利用大自然移動的癮魂，在決策人期待的空間里，形成三維均衡的語文學理論，稱為博弈論。
博弈論又被稱為對策論（Game Theory）既是現代數學的一個新分支，也是運籌學的一個重要學科。
博弈論主要研究公式化了的激勵結構間的相互作用。是研究具有斗爭或競爭性質現象的數學理論和方法。 博弈論考慮游戲中的個體的預測行為和實際行為，并研究它們的優化策略。生物學家使用博弈理論來理解和預測進化論的某些結果。
本文只是討論了信息學競賽中博弈方面最基本最簡單的幾個方法和結論。
由于這一類博弈問題都有一個共同的要求就是博弈雙方都是“絕對聰明”的，所以據說只有“絕對聰明”的人才能學好博弈論哦。
下面就讓我們一起來感受博弈問題的美妙吧。

Nim游戲

從一個問題進入。

描述

今天我們要認識一對新朋友，Alice與Bob。
Alice與Bob總是在進行各種各樣的比試，今天他們在玩一個取石子的游戲。
在這個游戲中，Alice和Bob放置了N堆不同的石子，編號1..N，第i堆中有Ai個石子。
每一次行動，Alice和Bob可以選擇從一堆石子中取出任意數量的石子。至少取1顆，至多取出這一堆剩下的所有石子。
Alice和Bob輪流行動，取走最后一個石子的人獲得勝利。
假設每一輪游戲都是Alice先行動，請你判斷在給定的情況下，如果雙方都足夠聰明，誰會獲得勝利？

討論

這是一個古老而又經典的博弈問題：Nim游戲。

Nim游戲是經典的公平組合游戲(ICG)，對于ICG游戲我們有如下定義：

• 兩名選手
• 兩名選手輪流行動，每一次行動可以在有限合法操作集合中選擇一個
• 游戲的任何一種可能的局面(position)，合法操作集合只取決于這個局面本身，不取決于輪到哪名選手操作、以前的任何操作、骰子的點數或者其它因素；局面的改變稱為“移動”(move)
• 如果輪到某名選手移動，且這個局面的合法的移動集合為空（也就是說此時無法進行移動），則這名選手負

對于第三條，我們有更進一步的定義Position，我們將Position分為兩類：

• P-position：在當前的局面下，先手必敗
• N-position：在當前的局面下，先手必勝

它們有如下性質：

• 合法操作集合為空的局面是P-position
• 可以移動到P-position的局面是N-position
• 所有移動都只能到N-position的局面是P-position

在這個游戲中，我們已經知道A[] = {0,0,…,0}的局面是P局面，那么我們可以通過反向枚舉來推導出所有的可能局面，總共的狀態數量為A1?A2?...?AN。并且每一次的狀態轉移很多。
雖然耗時巨大，但確實是一個可行方法。

當然，我們這里會講這個題目就說明肯定沒那么復雜。沒錯，對于這個游戲有一個非常神奇的結論：

對于一個局面，當且僅當A1 xor A2 xor ... xor AN =0時，該局面為P局面。

對于這個結論的證明如下：

• 全0狀態為P局面，即Ai=0，則A1 xor A2 xor … xor AN = 0
• 從任意一個A1 xor A2 xor … xor AN = k ≠0的狀態可以移動到A1 xor A2 xor … xor AN = 0的狀態。由于xor計算的特殊性，我們知道一定有一個Ai最高位與k最高位的1是相同的，那么必然有Ai xor k <Ai<script type="math/tex" id="MathJax-Element-24">< A_i</script>的，所以我們可以通過改變Ai的值為A′i，使得A1 xor A2 xor … xor A′i xor … xor AN = 0
• 對于任意一個局面，A1 xor A2 xor … xor AN = 0，則不存在任何一個移動可以使得新的局面A1 xor A2 xor … xor AN = 0。由于xor計算的特殊性，我們可以知道，一定是存在偶數個1時該位置的1才會被消除。若只改變一個Ai，無論如何都會使得1的數量發生變化，從而導致A1 xor A2 xor … xor AN ≠ 0。

以上三條滿足ICG游戲中N,P局面的轉移性質，所以該結論的正確性也得到了證明。

而根據這些性質，我們可以在O(n)的時間內判斷一個Nim的局面的性質，且如果它是N-position，也可以在O(n)的時間內找到所有的必勝策略。Nim問題就這樣基本上完美的解決了。

擴展和延伸

從上文可以看出，Nim游戲有著極其簡單的規則和無比優美的結論。但如果把Nim的規則略加改變，你還能很快找出必勝策略嗎？比如說：有n堆石子，每次可以從第1堆石子里取1顆、2顆或3顆，可以從第2堆石子里取奇數顆，可以從第3堆及以后石子里取任意顆……這時看上去問題復雜了很多，但其實，類似的千變萬化的問題都是不成問題的。
而這一問題的應用，就要用到下文即將介紹的SG(Sprague-Garundy)函數。

SG函數

同樣從一個問題進入。

描述。

給定一個有向無環圖和一個起始頂點上的一枚棋子，Alice和Bob交替的將這枚棋子沿有向邊進行移動，無法移動者判負。問是否有必勝策略。

討論

事實上，這個游戲可以認為是所有ICG游戲的抽象模型。也就是說，任何一個ICG游戲都可以通過把每個局面看成一個頂點，對每個局面和它的子局面連一條有向邊來抽象成這個“有向圖游戲”。下面我們就在有向無環圖的頂點上定義SG(Sprague-Garundy)函數。

SG函數的建立

• 首先定義mex(minimal excludant)運算，這是施加于一個集合的運算，表示最小的不屬于這個集合的非負整數。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

• 對于一個給定的有向無環圖，定義關于圖的每個頂點的SG函數sg如下：sg(x)=mex{ sg(y) | y是x的后繼 }。也就是說，一個點的SG函數為在它所有后繼中都未出現的最小的值。

SG函數的性質

來看一下SG函數的性質。首先，所有的沒有出邊的頂點，其SG值為0，因為它的后繼集合是空集。然后對于一個sg(x)=0的頂點x，它的所有后繼y都滿足 sg(y)≠ 0。對于一個sg(x)≠ 0的頂點，必定存在一個后繼y滿足sg(y)=0。

這個時候你就應該有所發現了！SG函數的性質和N,P局面的性質非常相似！
以上表明，頂點x所代表的postion是P-position當且僅當sg(x)=0（跟P-positioin/N-position的定義是完全對應的）。

擴展

但是，SG函數的用途遠沒有這樣簡單。如果將有向圖游戲變復雜一點，比如說，有向圖上并不是只有一枚棋子，而是有n枚棋子，每次可以任選一顆進行移動，這時，怎樣找到必勝策略呢？

讓我們再來考慮一下頂點的SG值的意義。當sg(x)=k時，表明對于任意一個0≤i<k，都存在x的一個后繼y滿足sg(y)=i。也就是說，當某枚棋子的SG值是k時，我們可以把它變成0、變成1、…、變成k-1，但絕對不能保持k不變。
不知道你能不能根據這個聯想到Nim游戲，Nim游戲的規則就是：每次選擇一堆數量為k的石子，可以把它變成0、變成1、…、變成k-1，但絕對不能保持k不變。這表明，如果將n枚棋子所在的頂點的SG值看作n堆相應數量的石子，那么這個Nim游戲的每個必勝策略都對應于原來這n枚棋子的必勝策略！

對于n個棋子，設它們對應的頂點的SG值分別為(a1,a2,...,an)，再設局面(a1,a2,...,an)時的Nim游戲的一種必勝策略是把ai變成k，那么原游戲的一種必勝策略就是把第i枚棋子移動到一個SG值為k的頂點。這聽上去有點過于神奇——怎么繞了一圈又回到Nim游戲上了。

其實我們還可以證明這種多棋子的有向圖游戲的局面是P-position當且僅當所有棋子所在的位置的SG函數的異或為0。這個證明與上節的Nim游戲的證明幾乎是完全相同的，只需要適當的改幾個名詞就行了。

繼續延伸

剛才，為了使問題看上去更容易一些，認為n枚棋子是在一個有向圖上移動。但如果不是在一個有向圖上，而是每個棋子在一個有向圖上，每次可以任選一個棋子（也就是任選一個有向圖）進行移動，這樣也不會給結論帶來任何變化。

所以我們可以定義有向圖游戲的和(Sum of Graph Games)：設G1、G2、…、Gn是n個有向圖游戲，定義游戲G是G1、G2、…、Gn的和(Sum)，游戲G的移動規則是：任選一個子游戲Gi 并移動上面的棋子，則sg(G)=sg(G1) xor sg(G2) xor … xor sg(Gn)。也就是說，游戲的和的SG函數值是它的所有子游戲的SG函數值的異或。

其實，任何一個ICG都可以抽象成一個有向圖游戲。所以“SG函數”和“游戲的和”的概念就不是局限于有向圖游戲。我們給每個ICG的每個position定義SG值，也可以定義n個ICG的和。所以說當我們面對由n個游戲組合成的一個游戲時，只需對于每個游戲找出求它的每個局面的SG值的方法，就可以把這些SG值全部看成Nim的石子堆，然后依照找Nim的必勝策略的方法來找這個游戲的必勝策略了！

回到上一節提出的問題。有n堆石子，每次可以從第1堆石子里取1顆、2顆或3顆，可以從第2堆石子里取奇數顆，可以從第3堆及以后石子里取任意顆。
我們可以把它看作3個子游戲，第1個子游戲只有一堆石子，每次可以取1、2、3顆，很容易看出x顆石子的局面的SG值是x%4。第2個子游戲也是只有一堆石子，每次可以取奇數顆，經過簡單的畫圖可以知道這個游戲有x顆石子時的SG值是x%2。第3個游戲有n-2堆石子，就是一個Nim游戲。對于原游戲的每個局面，把三個子游戲的SG值異或一下就得到了整個游戲的SG值，然后就可以根據這個SG值判斷是否有必勝策略以及做出決策了。其實看作3個子游戲還是保守了些，干脆看作n個子游戲，其中第1、2個子游戲如上所述，第3個及以后的子游戲都是“1堆石子，每次取幾顆都可以”，稱為“任取石子游戲”，這個超簡單的游戲有x顆石子的SG值顯然就是x。其實，n堆石子的Nim游戲本身不就是n個“任取石子游戲”的和嗎？

至此，我們對于Nim游戲和SG函數的討論基本結束。

幾類經典的博弈問題

階梯博弈

描述

有許多硬幣任意分布在樓梯上，共n階樓梯從地面由下向上編號為0到n。Alice和Bob輪流取操作，操作時可以將樓梯j(1<=j<=n)上的任意多但至少一個硬幣移動到樓梯j-1上。無法移動者判負。

討論

這個問題與Nim游戲的區別在于移走的硬幣不是被扔掉而是被放進了另一堆硬幣之中，考慮能否將這一部分樓梯排除考慮范圍。奇數號樓梯只能將硬幣扔到偶數號樓梯之中，同樣偶數號樓梯上的硬幣也只會被扔上奇數號樓梯。只考慮奇數號樓梯Nim，若偶數樓梯只作容器，那么游戲變為Nim。我們仍然可以用Nim的方法判斷必敗狀態。

翻轉硬幣

描述

• N枚硬幣排成一排，有的正面朝上，有的反面朝上。我們從左開
  始對硬幣按1到N編號。
• Alice和Bob輪流根據某些約束翻硬幣（如：每次只能翻一或兩枚，或者每
  次只能翻連續的幾枚），但他所翻動的硬幣中，最右邊的必須是
  從正面翻到反面。
• 誰不能翻誰輸。

討論

基于轉化的思想，如果將正面朝上，位置i的硬幣看作一堆規模為i的石子，我們就能看到游戲與Nim的相似點。
不過有許多Nim中的合法操作在這個游戲中是無法實現的，比如說，我們就無法從一堆規模為10的石子中取出其中的5個。不過我們將10與5同時翻轉，所得到的狀態，對應的Nim狀態SG值與從10中取5是相同的。因此我們猜想這個游戲的狀態SG函數值與對應的Nim相同。
事實上，雖然這個游戲無法實現Nim的所有操作，但它的狀態所能到達的狀態SG函數值集合與對應的Nim游戲狀態相同。因此，它的狀態SG函數值與對應Nim相同。
實際上，有這樣的結論：

局面的SG值為局面中每個正面朝上的棋子單一存在時的SG值的異或和。

Anti-SG游戲和SJ定理

我們不妨從最本質的Anti-Nim游戲入手。

描述

Alice和Bob輪流取N堆石子。每次只能從一堆中取出任意數目的石子，但不能不取。取走最后一個石子者敗。

討論

這個問題有一個結論，先手必勝當且僅當：

• 所有堆的石子數都為1且游戲的SG值為0
• 有些堆的石子數大于1且游戲的SG值不為0

下面給出證明。
游戲分三種情況：

• 每個堆只有一個石子
  
  • 如果異或值=0，即有偶數個堆，則先手必勝（A）
  • 如果異或值≠0，即有奇數個堆，則先手必敗（B）
• 只存在一堆石子數>1，則先手必勝（C）
  可以發現在這種情況下，異或值一定≠0。并且可以發現，在這種情況下先手一定有一種方法使得剩下奇數個石子個數都為1的堆，即轉化為B狀態。所以先手必勝。
• 存在至少2堆石子數>1
  
  • 當異或值=0時，先手必敗（D）
  • 當異或值≠0時，先手必勝（E）
    關于這一步的證明應該把這兩個狀態結合來看。
    首先，參考Nim游戲的證明，當異或值=0時，無論進行怎樣的操作都會使異或值≠0；而當異或值≠0時，一定存在一種移動方案，使得異或值=0，這個性質符合N,P狀態的轉換。
    而不斷地進行這種轉換，總會有一個時刻局面變成了C狀態，而C狀態一定是從D狀態轉移過來的。所以可以證明D狀態總會在一個時刻必須轉移到先手必勝態，即D狀態是先手必敗態。相應地，我們就可以證明E狀態是先手必勝態。

證明結束。

延伸

我們來定義Anti-SG游戲

• Anti-SG游戲規定，決策集合為空的游戲者贏。
• Anti-SG其他規則與SG游戲相同

定理：SJ定理

對于任意一個Anti-SG游戲，如果我們規定當局面中所有的單一游戲的SG值為0時，游戲結束，則先手必勝當且僅當：
（1）游戲的SG函數不為0且游戲中某個單一游戲的SG函數大于 1；
（2）游戲的SG函數為0且游戲中沒有單一游戲的SG函數大于1。

其實我們可以類比Nim游戲與SG函數的證明方法，來感性地理解一下SJ定理的正確性。這里mex和sg的定義都是完全相同的，不再給出證明。

Multi-SG游戲

同樣從一個最簡單的問題出發。

描述

Alice和Bob輪流取N堆石子，每一次可以從任意一堆中拿走任意個石子，也可以將一堆石子分為兩個小堆。先拿完者獲勝。

討論

這個問題實際上是一個經典的Lasker’s Nim游戲：每一輪允許兩會中操作之一：①從一堆石子中取走任意多個②將一堆數量不少于2的石子分成都不為空的兩堆。
這個問題可以用SG函數來解決。首先，操作①其實和Nim游戲沒什么區別，對于一個石子數為k的點來說，后繼可以為0…k-1。而操作②實際上是把一個游戲分成了兩個游戲。根據上文提到的游戲的和的概念，這兩個游戲的和應該為兩個子游戲的SG函數值的異或。而求某一個點的SG函數要利用它的后繼，它的后繼就應該為當前局面能產生的所有單一游戲，以及當前局面所有能分成的多個單一游戲的游戲的和。
比如說，狀態3的后繼有：0、1、2、（1，2），他們的SG值分別為0、1、2、3，所以sg(3) = 4。
那么這樣，我們就能用SG函數解決這個問題。
但是，如果數據范圍非常大的時候SG函數就不能用了，通過打表可以發現一個更優美的結論：

sg(x)=???x?1,x,x+1,x%4=0x%4=1∨x%4=2?x%4=3
那么這就是一道結論題？

延伸

根據題目的描述，嘗試定義Multi-SG游戲

• Multi-SG 游戲規定，在符合拓撲原則的前提下，一個單一游戲
  的后繼可以為多個單一游戲。
• Multi-SG其他規則與SG游戲相同。

考慮更一般的Multi-SG游戲解法，發現依然和SG函數有關。
對于一個單一游戲，不同的方法可能會將其分成不同的多個單一游戲。每一方法對應的多個單一游戲的游戲的和即可以表示這種方法的NP狀態。而這個單一游戲的SG函數即為未在所有方法的SG函數值中出現過的最小值。

Every-SG游戲

又一個SG函數的變形。

描述

給定一個有向無環圖，某些定點上有一些棋子。Alice和Bob輪流移動棋子，每一次移動要求必須移動所有可以移動的棋子，無法移動的人判負。

討論和延伸

很容易想到：對于我們可以贏的單一游戲，我們一定要拿到這一場游戲的勝利！
所以，我們只需要考慮如何讓我們必勝的游戲盡可能長的玩下去。
但是對手卻不希望他必敗的單一游戲玩的太久，這就是Every-SG游戲不同于其他 SG游戲的地方：一般的 SG游戲只有勝與負之間的博弈，而 Every-SG 游戲又添加了長與短之間的博弈。

定義Every-SG游戲：

• 對于還沒有結束的單一游戲，游戲者必須對該游戲進行一步決策；
• Every-SG游戲的其他規則與普通 SG游戲相同

在通過拓撲關系計算某一個狀態點的SG函數時（事實上，我們只需要計算該狀態點的SG值是否為0），對于SG值為0的點，我們需要知道最快幾步能將游戲帶入終止狀態；對于SG值不為0的點，我們需要知道最慢幾步游戲會被帶入終止狀態，我們用step函數來表示這個值。
那么

step(u)=???0,max{step(v)},min{step(v)},u為終止狀態?sg(u)≠0∧v為u的后繼∧sg(v)=0?sg(u)=0∧v為u的后繼
定理

對于Every-SG游戲先手必勝當且僅當單一游戲中最大的step為奇數。

定理是顯然的：最大的單一游戲步數如果是奇數的話那么肯定是先手取得進行最后一步，否則一定是對手取走最后一個棋子。

樹的刪邊游戲

描述

給出一個有 N個點的樹，有一個點作為樹的根節點。游戲者輪流從樹中刪去邊，刪去一條邊后，不與根節點相連的部分將被移走。誰無法移動誰輸。

討論

我們有如下定理：

葉子節點的SG值為0；中間節點的SG值為它的所有子節點的SG值加1后的異或和。

證明（數學歸納法）

• 一個節點和兩個節點的情況顯然成立。
• 我們假設小于 K 個節點的任意情況均成立，下面證明（K+1）個節點的情況也成立。我們將證明分成兩部分：
  
  • 證明根節點只有一個孩子的情況符合要求；
  • 證明根節點有多個孩子的情況符合要求。

先證明第一部分：
我們假設樹G的根為A，A只與B相連，圖中共有N+1個節點，去掉A后以B為根節點的圖為G’，下面證明SG(G)=SG(G’+1).
若我們去掉 AB之間的邊，則所有的邊都被刪除
∴G存在 SG值為0的后繼局面；①
若我們去掉 G中的除AB外的邊 E，則刪除后總邊數小于等于K
設以B為根的G’去掉E以后的后繼局面的SG值為P
∵以A為根的G去掉E以后圖中的總邊數小于等于K
又∵中間節點的SG值為它的所有子節點的SG值加1后的異或和
∴A為根的G去掉E以后的后繼局面的SG值為P+1
∵以B為根的G’可以通過去邊操作使得后繼局面的SG值變為0到SG(G’)-1
∴以A 為根的G可以通過刪除 G’中有的邊使得后繼局面的SG值變為1到SG(G’) ②
由①②得，SG(G)=SG(G’)+1

再證明第二部分
我們假設樹G的根為A，A與T個節點相連，為B1、B2、…、BT，設去掉(T-1)個與A相連的邊（ABX保留）后，以A為根的樹為GX，第二部分即證明SG(G)=SG(G′1) xor SG(G′2) xor … xor SG(G′T)
而根據前文提到的知識，這就有相當于是一個游戲的和，或者簡單來說就是一個Nim游戲！
至此證明結束。

延伸

一個例題：Christmas Game(PKU3710)
題目大意：

• 有 N個局部聯通的圖。
• Harry 和 Sally輪流從圖中刪邊，刪去一條邊后，不與根節點相連的部分將被移走。Sally為先手。
• 圖是通過從基礎樹中加一些邊得到的。
• 所有形成的環保證不共用邊，且只與基礎樹有一個公共點。
• 誰無法移動誰輸。

這道題與我們上一節所講的內容基本相同，唯一不同的是圖中出現了環，所以，環的處理成為了解題的關鍵。
我們來分析環的性質：環保證不共用邊，且只與基礎樹有一個公共點。因此題中所有的環都是從樹中某一個點連出又連回同一個點的簡單環！
我們通過分析發現了如下奇妙的性質：

• 對于長度為奇數的環，去掉其中任意一個邊之后，剩下的兩個鏈長度同奇偶，抑或之后的SG值不可能為奇數，所以它的SG值為1
• 對于長度為偶數的環，去掉其中任意一個邊之后，剩下的兩個鏈長度異奇偶，抑或之后的SG值不可能為0，所以它的SG值為0

所以我們可以去掉所有的偶環，將所有的奇環變為長短為1的鏈，就將這道題轉化成了上面已經討論過的模型。

無向圖的刪邊游戲

描述

我們將Christmas Game這道題進行一步拓展——去掉對環的限制條件，這個模型應該怎樣處理？
無向圖的刪邊游戲：

• 一個無相聯通圖，有一個點作為圖的根。
• 游戲者輪流從圖中刪去邊，刪去一條邊后，不與根節點相連的部分將被移走。
• 誰無路可走誰輸。

討論

對于這個模型，有一個著名的定理——Fusion Principle。
定理

我們可以對無向圖做如下改動：將圖中的任意一個偶環縮成一個新點，任意一個奇環縮成一個新點加一個新邊；所有連到原先環上的邊全部改為與新點相連。這樣的改動不會影響圖的SG 值。

這個原理的證明十分復雜，這里不給出證明（記個結論吧）
這樣的話，我們可以將任意一個無向圖改成樹結構，“無向圖的刪邊游戲”就變成了“樹的刪邊游戲”。

小結

通過本文，你或許對博弈問題有了更深一層的認識。
很多博弈問題都是以Nim游戲為原型的。而Nim游戲雖然有簡單無比的結論，但是如果我們進一步探究這個結論的本質的話，你會發現有更普遍更廣泛的結論。無疑，SG函數是解決博弈問題的強有力工具。但是同樣有一些題目由于時間或空間的限制我們無法用最基本的方法求解，這時候也需要我們將問題特殊化來尋求更有用的性質。
讓我們在不斷地思考與質疑中繼續體會博弈論的美妙吧。

主要參考文獻

Thomas S. Ferguson 《GAME THEORY》
IOI2009國家集訓隊論文 賈志豪《組合游戲略述——淺談SG游戲的若干拓展及變形》
IOI2007國家集訓隊論文 王曉珂《解析一類組合游戲》

題目

每個分類難度盡量升序

并沒有什么理論基礎的機智博弈
pku 2484
bzoj 2463
bzoj 3895
pku 1740
bzoj 1982
pku 2505
Nim游戲
pku 2975
bzoj 1299
SG函數
pku 2425
pku 2960
bzoj 1874
階梯博弈
bzoj 1115
BC #90B
pku 1704
hdu 4315
hdu 3389
Anti-Nim
bzoj 1022
Multi-SG
hdu 3032
pku 2311
pku 3537
bzoj 2940
bzoj 1188
bzoj 3576
Every-SG
hdu 3595
樹的刪邊游戲
pku 3710
Anti+Multi SG 233
hdu 2509

總結

以上是生活随笔為你收集整理的关于 Nim游戏与SG函数 的一点研究的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。