---
# System prepended metadata

title: combinatorial games
tags: [2024-acp]

---

---
tags: Training

type: slide
---

<style>
.reveal .slides {
    text-align: left;
    font-size:30px;
}
</style>

# combinatorial games
## 組合賽局

----

## 定義

需要滿足以下條件：

1. 遊戲有剛好兩人參與，兩人輪流做出決策，並且兩人做出的決策都是對自己最優的
2. 當有一人無法決策的時候，該人失敗。
3. 遊戲沒有平手，必然會在有限時間內結束。
4. 遊戲是公開透明的，沒有不確定或隨機的因素。

----

# 常見賽局種類

- 標準賽局：輪到該回合，無法操作的玩家為輸
- ~~匱乏賽局：輪到該回合，無法操作的玩家為贏~~
- 無偏賽局：在同一個局面下，雙方玩家可以做的操作皆相同
- ~~有偏賽局：在同一個局面下，雙方玩家可以做的操作可能不同~~

今天會介紹標準無偏賽局

---

## 標準賽局

輪到該回合，無法操作的玩家為輸

----

## 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 為必勝態，因為他們可以轉移給必輸態

| 剩下石頭數量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| ---------- | - | - | - | - | - | - | - | - |
| 狀態        | -1 | 1 | 1 | 1 | ? | ? | ? | ? |

----

## 必勝態與必輸態

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

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

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

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

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

----

回到剛剛的石頭遊戲

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

且

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

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

因此可以推出下面的表格

| 剩下石頭數量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 
| ---------- | - | - | - | - | - | - | - | - | - | - |
| 狀態        | -1 | 1 | 1 | 1 | -1 | 1 | 1 | 1 | -1 | 1 |

----

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

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

| 剩下石頭數量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 
| ---------- | - | - | - | - | - | - | - | - | - | - |
| 狀態        | -1 | 1 | 1 | 1 | -1 | 1 | 1 | 1 | -1 | 1 |

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

----

## game graph

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

![](https://i.imgur.com/dUrTfoo.png)

---

## Nim game

有 $N$ 堆石頭，每一堆石頭有 $a_i$ 個，每次可以選其中的一堆非空的石頭堆拿至少一顆，問先手獲勝或者後手獲勝

----

在此遊戲中，每堆石頭都分別為獨立的子遊戲 ( 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

![](https://i.imgur.com/BTNFK4S.png)

---

## Sprague-Grundy Theorem

把無偏賽局歸納成一個 SG value 以得到結果

----

## 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](https://www.luogu.com.cn/problem/P4860)

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

問先手勝或後手勝?

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

----

## game graph

![](https://i.imgur.com/qwhpd38.png)

----

## 表格

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      | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| ------ | - | - | - | - | - | - | - | - | - | - |
| N級勝態 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 |

觀察即為當 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)

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

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

----

![image](https://hackmd.io/_uploads/BJxVBunMye.png)


----

首先，先看出來他是一張 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
找找看是否存在規律

----

## [後手模仿先手](https://vjudge.net/problem/Kattis-gameofdivisibility)

有 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 在分別討論

---

## Practice

建議上面題目也做過一遍

[Homework Link](https://vjudge.net/contest/673674)