【概述】
最近的幾次比賽，博弈的題目一直不少，而且博弈問題是一塊比較復雜、龐大的內(nèi)容，因此在這里小結(jié)一下，希望能夠幫自己理清一些思路，爭取也多來幾個系列，呵呵。
競賽中出現(xiàn)的組合游戲問題一般都滿足以下特征：
1. 二人博弈游戲，每個人都采用對自己最有利的策略，并且是兩個人輪流做出決策
2. 在游戲中的任意時刻，每個玩家可選擇的狀態(tài)是固定的，沒有隨機成分
3. 游戲在有限步數(shù)內(nèi)結(jié)束，沒有平局出現(xiàn)
大部分的題目都滿足上述條件，因此這里只討論在上述條件范疇內(nèi)的博弈問題。這類博弈問題，通常還有若干分類。一種是規(guī)定移動最后一步的游戲者獲勝，這種規(guī)則叫做
Normal Play Rule；另一種是規(guī)定移動最后一步的游戲者輸，這種規(guī)則叫做
Misere Play Rule，也稱為Anti-SG游戲。此外，對于游戲的雙方，如果二者博弈的規(guī)則相同，那么稱為這類游戲是
對等(impartial games)的；否則稱為
不平等游戲(partizan games )。當初WHU的那場比賽就是由于對于這個概念不是很清晰，導致看完題目之后就用SG定理來做，浪費了很多機時。實際上，解決不平等博弈問題的方法和普通的博弈問題（SG游戲）是有區(qū)別的，一般會采用動態(tài)規(guī)劃或者surreal number。
【博弈基礎知識】
在SG游戲中，最為人熟知的是必勝必敗態(tài)，也叫NP態(tài)理論。注意的是，P態(tài)對應的是先手必敗態(tài)，N態(tài)對應的是先手必勝態(tài)。必勝必敗態(tài)理論是：
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
英文的表述非常簡潔清晰，而且這個理論也很好理解，如果在當前狀態(tài)的下一步可以走到必敗態(tài)，那么當前玩家就可以走到那個狀態(tài)，把必敗態(tài)推給另一方；如果所有可達狀態(tài)都是必勝態(tài)，那么當前玩家無論如何走，都會把必勝態(tài)讓給對方。根據(jù)必勝必敗態(tài)理論，我們可以遞歸的求出每個狀態(tài)是N態(tài)還是P態(tài)。必勝必敗態(tài)理論其實已經(jīng)把博弈問題轉(zhuǎn)化成了一個有向圖，借助圖這個模型來分析問題，使得問題變得形象了許多。需要注意的是，這種SG游戲?qū)挠邢驁D是無環(huán)的，因為如果有環(huán)，那么游戲雙方就可能在環(huán)上不停的轉(zhuǎn)換狀態(tài)，游戲不能在有限步終止，這樣就不滿足組合游戲的特征3了。
然而在很多時候僅僅知道某個狀態(tài)是必勝還是必敗是不夠的，因為如果存在多個組合游戲（比如經(jīng)典的Nim），對應的狀態(tài)集合非常大，無法直接利用必勝必敗態(tài)理論求解，因此需要用到博弈論中一個很重要的工具：SG函數(shù)。
某個狀態(tài)的SG函數(shù)值定義為當前狀態(tài)所有不可達的狀態(tài)編號中最小的編號，其中終止態(tài)的SG函數(shù)值是0。有了這個工具，就引入一個非常強大的定理——SG分解定理：
多個組合游戲的SG函數(shù)值是每個組合游戲的函數(shù)值的和。（這里的和定義為異或操作）
SG分解定理的證明不是很難，其實和Nim的證明很像。根據(jù)這個定理，我們就知道為什么Nim的解法是異或所有的石子個數(shù)了，因為每堆石子的SG值就是石子的個數(shù)。SG分解定理告訴我們?nèi)魏蜸G游戲都可以轉(zhuǎn)化成Nim游戲來做。
Nim中的一個變形就是拿走最后一塊石子的人算輸。通過修改SG的計算規(guī)則，可以得出相同的結(jié)論（因為當石子個數(shù)是1的時候SG值為0，因此要單獨處理）；當然也可以利用一個叫做SJ定理的方法來做，依然是要處理當所有堆的SG值不大于1的情況。
【博弈基本模型】
除了Nim模型，很多模型都看似復雜，最后都劃歸到了Nim模型上，然后利用SG分解來做的。在證明兩種模型等價的時候，可以通過計算SG值判斷是否相同，或者通過判斷必勝策略的走法將其轉(zhuǎn)化為Nim。許多模型非常的神奇，其獲勝策略又千差萬別，因此無法一一列舉，但是掌握一些經(jīng)典模型是必須的，這樣通過模型的轉(zhuǎn)化可以簡化問題的難度。
經(jīng)典模型1：Nim變種。包括：
(1) 樓梯Nim。把奇數(shù)臺階的石子作為Nim，二者等價，因為必勝的策略是相同的。
(2) 每次可以取k堆，這個是經(jīng)典的Moore Nim。它是泛化的Nim游戲。
(3) 兩堆石子，每次可以取一堆或兩堆，從兩堆取得時候個數(shù)必須相同，誰先取完獲勝。這個是著名的威佐夫博弈，跟黃金分割數(shù)有關(guān)，具體證明不是很清楚，但是用SG值打表可以找出規(guī)律。代碼如下：
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
const double k = (sqrt(5.0) + 1) / 2.0;
int a, b, t;
while (scanf("%d %d", &a, &b) == 2)
{
if (a > b)
swap(a, b);
t = b - a;
if (a == (int)(t * k))
puts("0");
else
puts("1");
}
return 0;
}
(4) Subtraction Games。一種通用的Nim游戲，每次從可用狀態(tài)集合中選擇下一步的狀態(tài)，有很多變形，核心思想還是計算SG函數(shù)值。
(5) Take-and-Break Game。每次把局面分成多個Nim子游戲，利用SG分解定理求出對應的SG值。
經(jīng)典模型2：翻硬幣游戲(Coin Turning Game) (1) 一維的翻硬幣游戲，每次可以翻1個或兩個。通過單獨考慮每個可以翻的硬幣發(fā)現(xiàn)，Coin Turning Game的SG值和Nim等價，因此兩個模型等價。需要注意的是，許多翻硬幣游戲根據(jù)題目的要求，一般編號從0開始。
(2) 一維的翻硬幣游戲，每次可以翻1個或兩個，限定了翻第二枚硬幣的范圍，那么就和Subtraction Game等價了。
(3) 一維的翻硬幣游戲，每次可以翻1個、2個或3個，這個游戲叫做Mock Turtles，有一個神奇的規(guī)律，是Odious Number序列。
(4) 高維的翻硬幣游戲，需要用到Nim積和Tartan定理。
翻硬幣模型的變化更多，很多模型都有一些奇妙的規(guī)律，需要打表才能發(fā)現(xiàn)。
經(jīng)典模型3：刪邊游戲(Green Hackenbush) (1) 樹的刪邊游戲：Colon原理證明這種模型和Nim依然是等價的，多個叉的SG值異或就是對應根節(jié)點的SG值。
(2) 無向圖刪邊游戲：利用Fursion定理收縮圈，然后就轉(zhuǎn)換成樹的刪邊游戲了，不過這個定理還不會證。
轉(zhuǎn)自：
http://m.shnenglu.com/sdfond/archive/2010/02/06/107364.aspxPS:最近做了好多博弈問題，但是總覺得還處在做一題，只會一題的狀態(tài)，我想是時候系統(tǒng)的學習一下了。