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