博弈論總結

什么是博弈論：

多人進行博弈，假設每個人都采取最優策略，一定有一個人勝出，在知道初態及規則的情況下，求解出

何人勝出的一類問題的理論及方法。

博弈論的一些性質

P點：必敗點，N點：必勝點

（1）無法進行任何移動的局面（也就是terminal position）是P-position；

（2）可以移動到P-position的局面是N-position；

（3）所有移動都導致N-position的局面是P-position。

巴什博奕：

介紹：只有一堆n個物品，兩個人輪流從中取物，規定每次最少取一個，最多取m個，最后取光者為

勝。

必定可以寫成該式子 n=k*(m+1)+r；

結論：若r=0，則先手必敗，否則先手必勝。

if(n % (m + 1) == 0)cout<<"后手必勝"<<endl;elsecout<<"先手必勝"<<endl;

威佐夫博弈：

介紹：有兩堆各若干的物品，兩人輪流從其中一堆取至少一件物品，至多不限，或從兩堆中同時取相同

件物品，規定最后取完者勝利。

結論：若兩堆物品的初始值為（x，y），且x<y，則另z=y-x；

記w=（int）[（（sqrt（5）+1）/2）*z ]；（中間為熟知的黃金分割比）

若w=x，則先手必敗，否則先手必勝。

if(x > y)swap(x, y);int c = floor((y - x) * (sqrt(5) + 1) / 2);if(c == x)cout<<0<<endl;elsecout<<1<<endl;

尼姆博奕：

介紹：有三堆各若干個物品,兩個人輪流從某一堆取任意多的物品,規定每次至少取一個,多者不限,最后取

光者得勝.

結論：n堆石子全部做異或運算，結果為0則為必敗結果

SG函數：

首先定義mex(minimal excludant)運算，這是施加于一個集合的運算，表示最小的不屬于這個集合的非

負整數。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

對于任意狀態 x ， 定義 SG(x) = mex(F)，其中F 是 x 后繼狀態的SG函數值的集合（就是上述mex中的數

值）。最后返回值（也就是SG(X)）為0為必敗點，不為零必勝點。

進一步解釋一下F，就是題意中給出的可以移動的次數。舉個例子來說，一堆石子，每次只能拿1，3，

5，7個，那么S數組就是1，3，5，7。

假如說是在一個游戲中有多個石子堆該怎么辦了。我們只需要把對每個石子堆進行sg函數的調用，將得

到的所有的值進行異或。得出來的結果為0則該情形為必敗態。否則為必勝態。

int sg[MAXN];
int f[MAXM]; //可以取走的石子個數
bool Hash[MAXN];void getSG(int m)
{memset(sg, 0, sizeof(sg));for (int i = 1; i < MAXN; i++) {//枚舉石子的個數memset(Hash, false, sizeof(Hash));for (int j = 0; j < m && f[j] <= i; j++)Hash[sg[i-f[j]]] = true;//枚舉每次拿走的個數并標記for (int j = 0; j < MAXN; j++) {if (!Hash[j]) {sg[i] = j; //找到這個F[](該狀態可以達到的狀態)中不存在的最小的數break;}}}
} //例題：hdu1847
int main()
{int n, num = 1;for (int i = 0; i < MAXM; num <<= 1, i++)f[i] = num;//這里的F數組就是可以移動的步數，每次都是2的冪次getSG(MAXM);while (cin >> n){if (sg[n])cout << "Kiki" << endl;elsecout << "Cici" << endl;} return 0;
}

?

?