博弈論入門
漫談一些簡單博弈論題目
博弈論大概就是指兩人取石子或者下棋，求先手或者後手必勝的遊戲，往往有多組資料，主人公經常是
Alice
和
Bob
。
這類遊戲有一個學名叫做公平組合遊戲(ICG)。定義就是兩人輪流操作一個局面，直至不能操作而判負的遊戲。
1. 手推博弈論
簡單的博弈論往往可以通過找規律就得出答案。
P3150 pb的遊戲
結論1：最終局面為一個數1，是奇數，為必敗情況。
結論2：奇數隻能選擇拆分成奇數+偶數，但偶數既可以選擇拆為奇數也可以選擇拆為偶數。
如果是以如果先手拿到偶數，就把他分割為兩個奇數，後手隻能将奇數分為一奇一偶，先手又可以取出偶數分割，最後的1一定會留給後手，是以先手必勝，反則先手必敗。
#include <bits/stdc++.h>
using namespace std;
int T,N;
int main()
{
cin >> T;
while (T--)
{
cin >> N;
cout << (N&1 ? "zs wins" : "pb wins") << endl;
}
}
P4136 誰能赢呢？
如果雙方不會走到到死胡同裡，那顯然每個格子都會被經過，一共有\(N^2\)個格子，與\(N\)的奇偶性相同。
顯然偶數格時先手會剛好走掉最後一個格子，是以N為偶數即先手必勝，否則後手必勝。
而雙方如果遇到自己必勝的局面，是一定會阻止死胡同形成的。如圖，不可能形成死胡同。
稍微複雜些的博弈遊戲就需要用到一些貪心或者數學知識了。
P1199 三國遊戲
這道題稍微接近貪心。
對于每一個武将，他所能達到的最大值是一定取不到的。是以隻能将每個武将能達到的次大值取到。
找到最大的"每行次大值"，選取該值對應的一個武将，電腦會選擇該武将默契值最高的武将，接下來就能将次大值取到。
接下來就要防止電腦取到更大的值，每次如果電腦選了每行最大值的一路，把另一路拿下就可以了，每行最大值一定是一人一半。計算機不可能取得勝利。
P1290 歐幾裡德的遊戲
本題特點在于操作後的數是固定的，但是可以一次進行多次輾轉相減。
1:25 7
2:18 7
3:11 7
4:7 4
5:4 3
6:1 3
7:1 0
如果每次隻能進行一次操作，那麼根據一共能進行的操作次數就能判斷勝負。
但是先手能掌控步驟1~4的順序，相當于可以把
4: 7 4
的局面選擇留給自己或者後手，兩種局面一定有一個必勝局面。
是以，隻要出現能夠多次輾轉相減的情況，即
a >= 2b
，目前操作者就是必勝的。
#include <bits/stdc++.h>
#define long long long
using namespace std;
int T,k,f;
long N,M;
void work(const long x,const long y)
{
k++;
if (x%y==0) return;
if (x/y > 1)
{
f = 1;
return;
}
work(y,x%y);
}
int main()
{
scanf("%d",&T); while (T--)
{
scanf("%lld%lld",&N,&M); k = f = 0;
if (N < M) N ^= M ^= N ^= M;
work(N,M);
puts(k&1 ? "Stan wins" : "Ollie wins");
}
}
其他練習題：
P4860 Roy&October之取石子II
P4018 Roy&October之取石子
P1288 取數遊戲II
2. SG函數
SG函數是專門為博弈論設計的一種函數。
設x是一種局面，SG(x)就可以表示當面局面的SG值。
這裡講一講自然數集合的mex運算。mex(S) = 不屬于S的最小自然數。
比如\(mex({0,2,3}) = 1, mex({1,4} = 0)\)
mex的意義就好比lowbit對于樹狀數組的意義一樣。
一個局面的SG值就是它能達到的所有局面的SG值集合的mex運算。
即\(SG(x) = mex({SG(y_1,y_2,...y_i)})\)，終止輸局的SG值為0.
顯然若子局面全為必勝(SG>0)，則目前必敗(正整數集合的mex值為0)。
若子局面有一個必敗(SG = 0)，則目前必勝(含有0的集合mex值大于0)。
是以SG值為0，則目前必敗，大于0則目前必勝。
需要注意的是，稍有難度的博弈題，都會面臨極多的狀态。不可能直接用SG函數求解。
SG函數本身隻能用于小資料是暴力，輔助找規律。
3. NIM博弈
現有N堆石子，第i堆有\(a_i\)個，每次可從任意一堆裡取任意多個石子，取走最後一個石子者獲勝。
如果隻有一堆石子，先手全部取完就赢了。這相當于一個\(SG(x) = x,x ∈ N\)。
這裡的多堆石子相當于有多個遊戲在同時進行。我們用類似第一題的方法來證明一個結論;
- 若所有石子全被取光，則\(0\ xor\ 0 ... \ xor\ 0 = 0\)是必敗局面。
- 若\(a_1\ xor\ a_2 ...\ xor\ a_n = x,x≠0\),那麼所有\(a_i\)中至少有一個與\(x\)最高位1相同，這樣就能使得\(a_i\ xor\ x \le a_i\)。我們就可以把\(a_i\)修改為\(a_i\ xor\ x\)。此時就能滿足\(a_1\ xor\ a_2 ...\ xor\ a_n = 0\)。
- 若\(a_1\ xor\ a_2 ...\ xor\ a_n = 0\)，因為\(a_1\ xor\ ...a_{i-1}\ xor\ a_{i+1}\ xor ...\ a_n=a_i\)，如果修改了\(a_i\)，等式左邊不變，式子無法滿足。則此時\(a_1\ xor\ a_2 ...\ xor\ a_n\)一定不為0.
異或不為0可以轉化為異或為0，異或為0隻能轉化為異或不為0，最終必敗時異或為0。
是以異或為0就是必敗局面，不為0就是必勝局面。
NIM博弈反映了多個獨立的博弈同時進行時的勝負情況。推廣到所有博弈：
若有n個同時進行的獨立博弈遊戲，初始局面分别為\(a_1...a_n\)，則總SG值\(SG_{sum} = SG(a_1)\ xor\ SG(a_2)\ ...\ xor\ SG(a_n)\)
階梯NIM
現有階梯0-N，其中1-N上各有\(a_i\)個石子每次可以任選一堆石子，選任意多個，向下移動一階，不能移動者失敗。
結論：若\(a_1\ xor\ a_3\ ...\ xor\ a_{2k+1} = 0\)（即奇數位置上的石子異或為0），則先手敗，否則先手勝。
最低階0是偶數，把所有奇數堆看成一個NIM遊戲。那麼從奇數移到偶數就相當于丢棄棋子。
如果異或和不為0，先手就按照NIM的政策，移動奇數放入下一個偶數。
如果後手也玩NIM，那他就輸了，最後會導緻隻有偶數位有棋子且輪到後手。此時後手每将棋子往下移，我們就把他移動過的棋子再向下移，最後一次移動一定在先手手裡。
如果後手将偶數位的棋子，下移到奇數位，我們就繼續把後手移動過的棋子移到下一個偶數位，對NIM局面沒有影響，最後情況将根上一個相同。
P2148 [SDOI2009]E&D
每組石子是獨立的，我們可以分别算出SG值，再異或合并。
有\(SG(x,y) = mex(\{\forall SG(a,b),a+b=x|a+b=y\})\)，這個式子不能拿去遞推。
但是可以用來輔助打表，快速找到規律\(SG(x,y)= \_\_builtin\_ctz(-(x|y)+1)\)，即x|y最低位0所在位。
當然有閑心可以參考第二篇題解的嚴格證明：
\(設S_z為滿足x+y+1=z的SG(x,y)構成的集合，則S_z等于z二進制下1的位置集合，f取最低0所在位\)
\(證：若有x+y+1=z，且有f(x|y)=k,那麼x,y的第k位都是0,0～k-1位中兩個數至少有1個是1\)
\(因為x|y\le x+y，x|y的0～k-1位均為1，是以x+y+1(=z)一定能向k位進位\)
\(是以隻要z的第k位是1，就可以找到符合條件的x,y\)
\(SG(x,y)=mex(S_x∪S_y)=mex(S_{x ∣ y}),0為未出現，1為出現，mex與f定義相同\)
\(是以有SG(x,y)=f(x|y)\)
證明其實很難，我是跟着題解想的。
是以學會借助SG的定義打表找規律就變得很重要。
P2575 高手過招
每行是獨立的，算完異或合并。
每行的空格數是不變的，那麼把每個空格看成一個分割符，就是一個階梯nim。
P1247 取火柴遊戲
這題更裸，掃一遍算出異或值，再掃一遍找到二進制最高位與sum相同的，減去\(d_i-d_i\ xor\ sum\) 即可。
從以上幾道題可以看出，SG函數的意義更多在于輔助思維，友善打表，而不是直接用來出解。
P2197 【模闆】nim遊戲
CF1194D 1-2-K Game
CF1215D Ticket Game