bash game

兩人玩遊戲，總共有 \(N\) 顆石頭，兩個人輪流拿，
每次只能拿 1~3 顆，拿走最後一顆石頭的人獲勝

問先手贏還是後手贏?

分析題目

1. 遊戲有剛好兩人參與，兩人輪流做出決策，並且兩人做出的決策都是對自己最優的
   \(\to\) 兩人玩遊戲且輪流拿，誰能拿走最後一顆石頭
2. 當有一人無法決策的時候，該人失敗。
   \(\to\) 拿走最後一顆之後就不能再拿了
3. 遊戲沒有平手，必然會在有限時間內結束。
   \(\to\) 每次都一定會少石頭，最後一定會被拿完
4. 遊戲是公開透明的，沒有不確定或隨機的因素。
   \(\to\) 能知道對方拿多少石頭，且沒有不確定因素

因此此題為無偏賽局

必勝態與必輸態

拿走最後一顆石頭的人贏，換句話說沒石頭拿的人輸

我們可以把當下剩下的石頭數量 \(x\) 當成一種狀態

當 \(x\) = 0 代表必輸態

而 x=0 可以由 x = 1,2,3 轉移過來

x = 1,2,3 為必勝態，因為他們可以轉移給必輸態

必勝態與必輸態

狀態為必勝態與必輸態其中一種，且兩種互相相反的

玩家對於當下所有任何操作都能把對手轉移到必勝態，則當下為必輸態

玩家對於當下存在至少一種操作都能把對手轉移到必輸態，則當下為必勝態

白話一點，
如果玩家當下做任何操作結果都會輸，則當下為必輸態

如果玩家當下存在一種操作會讓自己贏，則當下為必勝態

回到剛剛的石頭遊戲

當剩下的石頭數量剩下 \(x\) 顆時，則玩家可以把局面
變成 \(x\)-1, \(x\)-2, \(x\)-3 其中一種狀態

且

玩家對於當下所有任何操作都能把對手轉移到必勝態，則當下為必輸態

玩家對於當下存在一種操作都能把對手轉移到必輸態，則當下為必勝態

因此可以推出下面的表格

結果用數學歸納法可以得到

\[ S(n) = \begin{cases} -1, & \text{$n\mod 4 = 0$} \\ 1, & \text{otherwise} \end{cases} \]

由於勝負只跟當下狀態有關，因此勝負決定的因素只跟先後手有關

game graph

由於遊戲一定會在有限時間結束，因此狀態最後都會到 0 (結束)
因此會是一張有向無環圖(DAG)，狀態轉移則用一條有向邊連接

在此遊戲中，每堆石頭都分別為獨立的子遊戲 ( sub game )

如果把每個子遊戲的狀態都只設成先後手獲勝，則對於整個賽局沒有意義

因此要重新定義每堆石頭的狀態對於整場賽局的意義

但也必須符合前面的定義

必輸態所有任何操作都能把對手轉移到必勝態

必勝態存在一種操作都能把對手轉移到必輸態

我們可以用非負整數代表每個子遊戲的狀態
定義 0 為必輸態， 所有正整數為必勝態

而我們可以用 xor 去滿足以上性質
必輸態所有任何操作都能把對手轉移到必勝態
必勝態存在一種操作都能把對手轉移到必輸態

當 0(必輸態) xor 任何非0整數都會變成非0整數(必勝態)
任何非0數字(必勝態)都可以 xor 得到 0(必輸態)

Nim sum

回到 Nim game

假設有三堆 \(5 (101_2), 8(1000_2), 22(10110_2)\)

Nim sum 為每個狀態 xor 起來的結果 (\(a_1\) ^ \(a_2\) ^ … ^ \(a_n\))
變成 \(27(11011_2)\)

而當下狀態為必勝態(非0整數)，我們可以藉由 xor 之後變成必輸態\((0_2)\)

把 \(22(10110_2)\) 變成 \(13(1101_2)\)

如此一來整個賽局變成必輸態 (xor 後為 0)
再經由任一個操作(拿取任意顆數石頭)又可以把當前狀態變成必勝態

Nim Game

• 多個獨立的子賽局組成
• 最後結果為必輸態(Nim sum = 0)
• 必勝態與必輸態是能互相轉換的
• 能由當前局面計算出先手勝/後手勝

game graph

n 級勝態

來看 Nim game 每個子遊戲的狀態，當某堆石頭有 \(a_i\) 時，
則他可以藉由操作得到 \(0\) ~ \(a_i-1\) 的狀態

先定義 0 級勝態為必敗態
而如果一個狀態是 n 級勝態，則他能達到所有 i (for all i=0~n-1) 級勝態

example:
當前狀態可以達到 0,1,4,5 級勝態，則他是 2 級勝態
當前狀態可以達到 1,2,3 級勝態，則他是 0 級勝態
當前狀態可以達到 0,1,2,3 級勝態，則他是 4 級勝態

會發現要求出當前狀態的 n 級勝態，
即為求出 mex (所有可達到的狀態的集合)

mex(\(s\)) 為對於一個集合 \(s\)，最小未出現過的非負整數

以剛剛的例子

mex({0,1,4,5}) = 2
mex({1,2,3}) = 0
mex({0,1,2,3}) = 4

再回到 Nim game 算各自的 N 級勝態

會發現當石頭堆有 0 顆石頭，則為必敗態
而有一顆石頭，可以拿走 1 顆，而一顆石頭可以達到 0 級勝態
因此為 1 級勝態

當有 N 顆石頭時，可以達到 0 ~ N-1 的石頭數量，也就是 0 ~ N-1 級勝態

因此一堆石頭有 \(a_i\) 堆時，則他為 \(a_i\) 級勝態

再一個例子

luogu P4860

總共有 \(n(n \le 5 \cdot 10^7)\) 個石子，兩人分別可以取 \(P^k\) 顆石子
(P為任意質數 \(\land k=0或1)\)，沒石子拿了就輸了

問先手勝或後手勝?

轉換題目即為
\(N\)堆石子，每次可以能 1 顆或質數顆，問誰拿走最後一顆?

game graph

表格

N = 0 為 0 級勝態
N = 1 為 1 級勝態( 轉成 0 級勝態(N = 0)
N = 2 為 2 級勝態( 轉成 0 級勝態(N = 0)、轉成 1 級勝態(N = 1)
N = 3 為 3 級勝態( 轉成 0 級勝 態(N = 0)、1 級勝態(N = 1)、2 級勝態(N = 2)
N = 4 為 0 級勝態( 轉成 1 級勝態(N = 1)、2 級勝態(N = 2)、3 級勝態(N = 3)
以此類推

觀察即為當 N 整除 4 時，為必敗態

Coin on Chessboard Game

有一個大小為 \(15\times 15\) 的棋盤，上面有一些棋子，每格可能有多個棋子，每次可以把一個棋子往

• (x−2,y+1)
• (x−2,y−1)
• (x+1,y−2)
• (x−1,y−2)

移動，不能把棋子移出棋盤

兩個人玩遊戲，不能動的人輸，先手贏還是後手贏?

首先，先看出來他是一張 DAG
(遊戲沒有平手，必然會在有限時間內結束)

接著，就能算每個棋子的勝態

每個棋子的位置就是一個狀態，透過移動可以到下一個狀態

為 {(x−2,y+1), (x−2,y−1), (x+1,y−2), (x−1,y−2)} 四種可以走到的位置的勝態取 mex

而我們把所有子遊戲的勝態 xor 起來就會是整個遊戲的 SG value
也就是我們想求出的結果 \(\to\) 先手勝 or 後手勝

題目通常難度在於如何計算各個子遊戲的 SG value

而如果列不太出來的，通常可以透過好好觀察、通靈 ? 或者 DP
找找看是否存在規律

後手模仿先手

有 n 個整數，以及整數 k
兩個人輪流拿走一個整數，最後拿到總合為 \(k\) 的倍數贏

如果同時是或者都不是則為平手，先手贏還是後手贏?

如果 mod k 相同的整數有偶數個 ?

{10,10,10,10}
k = 3

奇數個?
{10,10,10}
k = 3

{9,9,9,9,9}
k = 3

會發現，後手模仿先手拿 mod k 相同值的不虧，
或者說，在數量為偶數的情況下能平手

只需考慮相同 mod 數量為奇數的數字有哪些

考慮奇數數量的有

• 恰好一個
• 恰好兩個
• 恰好三個

恰好一個，只需考慮這個數字跟前面總和是否為 k
決定先手是否輸

恰好兩個，
如果有一個能讓先手能得到總合為 k 的，則先手贏，
剩下的一個不能整除

恰好三個，
後手可以操作讓先手不可能贏，
而剩下兩步時，回到先手做相同的事情

會發現 \(\ge 3\) 步的情況都相同，兩玩家都會讓對方贏不了

這類的題目和一般賽局不同，比較像是思維題，
像是 xor, 整除等操作，都能模仿對手
剩下的 case 在分別討論