【概述】
　　最近的幾次比賽，博弈的題目一直不少，而且博弈問題是一塊比較復雜、龐大的內容，因此在這里小結一下，希望能夠幫自己理清一些思路，爭取也多來幾個系列，呵呵。

競賽中出現的組合游戲問題一般都滿足以下特征：
　　　　1. 二人博弈游戲，每個人都采用對自己最有利的策略，并且是兩個人輪流做出決策
　　　　2. 在游戲中的任意時刻，每個玩家可選擇的狀態是固定的，沒有隨機成分
　　　　3. 游戲在有限步數內結束，沒有平局出現
　　大部分的題目都滿足上述條件，因此這里只討論在上述條件范疇內的博弈問題。這類博弈問題，通常還有若干分類。一種是規定移動最后一步的游戲者獲勝，這種規則叫做Normal Play Rule；另一種是規定移動最后一步的游戲者輸，這種規則叫做Misere Play Rule，也稱為Anti-SG游戲。此外，對于游戲的雙方，如果二者博弈的規則相同，那么稱為這類游戲是對等(impartial games)的；否則稱為不平等游戲(partizan games )。當初WHU的那場比賽就是由于對于這個概念不是很清晰，導致看完題目之后就用SG定理來做，浪費了很多機時。實際上，解決不平等博弈問題的方法和普通的博弈問題（SG游戲）是有區別的，一般會采用動態規劃或者surreal number。

【博弈基礎知識】
　　在SG游戲中，最為人熟知的是必勝必敗態，也叫NP態理論。注意的是，P態對應的是先手必敗態，N態對應的是先手必勝態。必勝必敗態理論是：
　　1. All terminal positions are P-positions
　　2. From every N-position, there is at least one move to a P-position
　　3. From every P-position, every move is to an N-position
　　英文的表述非常簡潔清晰，而且這個理論也很好理解，如果在當前狀態的下一步可以走到必敗態，那么當前玩家就可以走到那個狀態，把必敗態推給另一方；如果所有可達狀態都是必勝態，那么當前玩家無論如何走，都會把必勝態讓給對方。根據必勝必敗態理論，我們可以遞歸的求出每個狀態是N態還是P態。必勝必敗態理論其實已經把博弈問題轉化成了一個有向圖，借助圖這個模型來分析問題，使得問題變得形象了許多。需要注意的是，這種SG游戲對應的有向圖是無環的，因為如果有環，那么游戲雙方就可能在環上不停的轉換狀態，游戲不能在有限步終止，這樣就不滿足組合游戲的特征3了。
　　然而在很多時候僅僅知道某個狀態是必勝還是必敗是不夠的，因為如果存在多個組合游戲（比如經典的Nim），對應的狀態集合非常大，無法直接利用必勝必敗態理論求解，因此需要用到博弈論中一個很重要的工具：SG函數。
　　某個狀態的SG函數值定義為當前狀態所有不可達的狀態編號中最小的編號，其中終止態的SG函數值是0。有了這個工具，就引入一個非常強大的定理——SG分解定理：

　　多個組合游戲的SG函數值是每個組合游戲的函數值的和。（這里的和定義為異或操作）
　　
　　SG分解定理的證明不是很難，其實和Nim的證明很像。根據這個定理，我們就知道為什么Nim的解法是異或所有的石子個數了，因為每堆石子的SG值就是石子的個數。SG分解定理告訴我們任何SG游戲都可以轉化成Nim游戲來做。
　　Nim中的一個變形就是拿走最后一塊石子的人算輸。通過修改SG的計算規則，可以得出相同的結論（因為當石子個數是1的時候SG值為0，因此要單獨處理）；當然也可以利用一個叫做SJ定理的方法來做，依然是要處理當所有堆的SG值不大于1的情況。

【博弈基本模型】
　　除了Nim模型，很多模型都看似復雜，最后都劃歸到了Nim模型上，然后利用SG分解來做的。在證明兩種模型等價的時候，可以通過計算SG值判斷是否相同，或者通過判斷必勝策略的走法將其轉化為Nim。許多模型非常的神奇，其獲勝策略又千差萬別，因此無法一一列舉，但是掌握一些經典模型是必須的，這樣通過模型的轉化可以簡化問題的難度。
　　經典模型1：Nim變種。包括：
　　　　(1) 樓梯Nim。把奇數臺階的石子作為Nim，二者等價，因為必勝的策略是相同的。
　　　　(2) 每次可以取k堆，這個是經典的Moore Nim。它是泛化的Nim游戲。
　　　　(3) 兩堆石子，每次可以取一堆或兩堆，從兩堆取得時候個數必須相同，誰先取完獲勝。這個是著名的威佐夫博弈，跟黃金分割數有關，具體證明不是很清楚，但是用SG值打表可以找出規律。代碼如下：

　　　　(4) Subtraction Games。一種通用的Nim游戲，每次從可用狀態集合中選擇下一步的狀態，有很多變形，核心思想還是計算SG函數值。
　　　　(5) Take-and-Break Game。每次把局面分成多個Nim子游戲，利用SG分解定理求出對應的SG值。
　　經典模型2：翻硬幣游戲(Coin Turning Game)
　　　　(1) 一維的翻硬幣游戲，每次可以翻1個或兩個。通過單獨考慮每個可以翻的硬幣發現，Coin Turning Game的SG值和Nim等價，因此兩個模型等價。需要注意的是，許多翻硬幣游戲根據題目的要求，一般編號從0開始。
　　　　(2) 一維的翻硬幣游戲，每次可以翻1個或兩個，限定了翻第二枚硬幣的范圍，那么就和Subtraction Game等價了。
　　　　(3) 一維的翻硬幣游戲，每次可以翻1個、2個或3個，這個游戲叫做Mock Turtles，有一個神奇的規律，是Odious Number序列。
　　　　(4) 高維的翻硬幣游戲，需要用到Nim積和Tartan定理。
　　翻硬幣模型的變化更多，很多模型都有一些奇妙的規律，需要打表才能發現。
　　經典模型3：刪邊游戲(Green Hackenbush)
　　　　(1) 樹的刪邊游戲：Colon原理證明這種模型和Nim依然是等價的，多個叉的SG值異或就是對應根節點的SG值。
　　　　(2) 無向圖刪邊游戲：利用Fursion定理收縮圈，然后就轉換成樹的刪邊游戲了，不過這個定理還不會證。

注：本文作于2009年8月3日 09點33分