# 2021暑訓 組合賽局講義
## 零、課程簡介
賽局，有人說他是經商致富的不二法門，有人說他是處理人際問題最好用的利器，精通賽局不一定能讓你玩遊戲百戰百勝，全球化競爭壓力下的今天，能得出理性思考的最佳化策略而百戰不殆才是賽局理論授與人類最偉大的禮物。
這堂課將透過簡單的小遊戲帶各位同學認識賽局理論的趣味。
## 壹、賽局理論簡介
賽局理論（Game Theory）又稱博弈論，是個體經濟學的一個分支，討論遊戲或競爭中的個體的預測行為和實際行為，並研究它們的最佳化策略。
### 策略
策略，或稱戰略，是決定及實行基本和長期目標及目的的過程，或是為了實現目標所需資源的配置行為。
在賽局理論中，我們定義的策略即為某個實體根據目前所擁有的資訊，對達成目標的一切思考及行動。
其中，最佳化策略即為客觀認為最能有效達成目標的一種策略。
### 分類
#### 依照遊玩形式
> 靜態(static)：指玩家同時出招，只進行一次的賽局，如猜拳、囚徒困境。
> 動態(dynamic)：玩家之行動有先後順序，並通常進行多次的賽局，如一般棋類遊戲、Nim。
#### 依照玩家競爭模式
> 零和賽局：指某玩家的收益必定造成某玩家的損失，並維持遊戲總價值不變，如麻將遊戲（玩家付錢給另一位玩家）、德州撲克。
> 非零和賽局：玩家可共同獲益或共同損失的賽局模型，如囚徒困境、吃角子老虎機。

另外還有許多種分類方法，在此就不多加贅述。
## 貳、組合賽局基本概念
組合賽局，是為賽局理論的一個分支，其直觀定義如下：
> * 兩位玩家輪流進行操作
> * 賽局盤面資訊完全公開
> * 任何盤面下的任何操作皆不含機率成分
> * 賽局結果存在三一律，A勝B敗、B勝A敗、AB平手

看完以上定義可能還是對組合賽局有些模糊，一個組合賽局最簡單的例子就是大家小時候應該都玩過的井字棋(tic-tac-toe)，另外，常見的棋類遊戲（如圍棋、象棋、西洋棋...）也都是組合賽局，但像猜拳遊戲就不屬於組合賽局的範疇，因為其兩位玩家必須同時出拳。

組合賽局之規則較為簡單，故能應用數學方法研究部分最佳解，本章之後的小節將介紹組合賽局的一些基本定理。

以下是兩個組合賽局的經典例子
#### 井字棋
> 或圈圈叉叉，是在一個3*3的棋盤中進行的遊戲，兩位玩家分別持圈圈與叉叉，輪流占下棋盤中的格子，先在棋盤中畫出同樣圖形三個連線者獲勝。

相信各位聰明的學員已經知道，井字棋並沒有必勝策略，雙方在理智的狀況下玩遊戲理論上會打成平手。
#### 搶21
> 一個我不確定他名字的經典遊戲，開始有一個數字零，兩位玩家輪流在此數字上做加1、加2或加3的操作，剛好把數字加到21的玩家獲勝。

可能很多人都推敲過，這個經典遊戲事實上是存在先手必勝的，先手玩家僅需在第一局搶下1，之後每局加$(4-$對手加的數字$)$就能保證取得$21$。

另外，若將此題的數字限制繼續推廣，將發現，操作包含加$1$、加$2$、...、加$k$，且搶到$n$者勝的此類遊戲，在$n$為$k+1$的倍數時有後手必勝，其餘皆為先手必勝。

### 勝利失敗條件
在一場組合賽局中，某個狀態下要贏過對手的條件為：
> 此狀態下存在一種可行的操作使得對手不存在能達成勝利或平手的操作。
>
而輸的條件為：
> 對於所有在此狀態下可行的操作，對手都存在至少一種能贏的操作。

其餘不符合上述兩者的盤面都存在能打成平手的策略。

這是什麼意思呢？
其實是很直觀的，我要贏那就必須保證對手不能有必勝策略，要輸就是不管我怎麼操作對手都存在必勝策略。
> 從剛才的例子來看，若圈圈叉叉遊戲已進行到以下盤面：
>
> <img src="https://i.imgur.com/uCFSwfs.png=10%x" height="200px" class='a'>
>
> 盤面目前輪到叉叉的回合：
> 此狀態下叉叉存在一種可行的操作(右上角)使得對手不存在能達成勝利或平手的操作(若對手畫中上，我畫左下獲勝;若對手畫左下，我畫中上獲勝)即此盤面叉叉勝利。
### 一些賽局分類
標準(normal) vs. 匱乏(misère)
標準(normal)，是指進行最後一個操作的玩家贏得遊戲的賽局，相對於標準的匱乏(misère game)，即是進行最後一個操作的玩家輸掉遊戲，但要注意的是，標準和匱乏並沒有構成所有的賽局。

無偏(impartial)，是指兩名玩家對於同樣的盤面可進行的操作是一樣的，像nim遊戲就是無偏賽局，而圍棋(分為黑白兩種)、井字遊戲就不是。
下一章節我們要討論的就是同時滿足以上條件的標準無偏賽局啦。
### Zermelo's theorem
一個似乎顯然的定理。
> 對於一個組合賽局，以下三者必有一成立。
> 1.先手擁有必勝策略
> 2.後手擁有必勝策略
> 3.兩人都有平手策略

證明亦很直覺，假設A與B兩個人參與組合賽局，如果A不能必勝，代表B能必勝或存在平手策略，而弱B也不能必勝，則表示A存在平手策略。

這個定理若運用在棋類遊戲上，即是先後手擁有必勝或是雙方都有和局策略，人類已經證明了五子棋存在先手必勝，等於是否定了這個遊戲，但後來又加入禁手規則增加了遊戲可玩性，而像圍棋、象棋、西洋棋等遊戲雖然已經有強大的AI能打敗人類，但目前人們還不清楚其是否存在先手必勝。

另外，對於一些不存在平手的組合賽局遊戲，如前面介紹過的標準賽局與匱乏賽局，其因為不存在平手，由於Zermelo's theorem，其必定存在先手必勝或是後手必勝，因此下一章節將介紹的標準無偏賽局僅需討論擁有必勝策略的一方到底是先手還是後手即可。

## 參、標準無偏賽局
聰明的小學員會發現我們一步步的在把主題聚焦在一個小範圍上，這其中的主因首先當然還是我們相聚的時間只有短短的三小時，另外就是其實真的已經被解決的賽局問題只占非常小的一部份，其他類型的賽局可能只能有個還不錯的策略，但也不保證能怎樣，因此我們決定將主題放在已經被解決的這些賽局上。當然還有一個重要的原因是講師很弱。
另外，接下來的東西可能會稍微有點難度，講師也是看了很久才稍微領略其中的皮毛，大家加油！
### Nim遊戲
又稱拈(ㄋㄧㄢˇ)，是最基本的一種標準無篇賽局。遊戲規則如下：
一開始有好幾堆石頭(或硬幣、或隨便你想要甚麼)，兩位玩家輪流進行操作，每次可以從其中一堆取任意數量的石頭，至多將整堆取完，但每一次操作至少要從其中一堆拿取一個。進行最後一次操作的玩家即可獲得勝利。

據說一開始是從某一間酒吧傳出來的，人們以一堆堆的硬幣作為賭注，贏者可以將所有硬幣拿走，然而這個遊戲其實是根據初始盤面就可以知道是先手必勝還是後手必勝，只要巧妙的設定初始盤面並進行有策略的操作就必定能獲勝，因此就變成了解箇中奧妙的人騙錢的手段。

接下來將對這個遊戲深入的分析。
符號說明：括號中的每個數字即為目前每堆有的石頭數量。

我們先從一個經典的初始盤面來看看：
$(3,4,5)$
假設A從第1堆取2個
$(1,4,5)$
B從第3堆取5個
$(1,4,0)$
A從第2堆取3個
$(1,1,0)$
B從第1堆取1個
$(1,0,0)$
A從第1堆取1個
$(0,0,0)$
因為A進行了最後一個操作，所以A勝利。
如果你想要跟電腦玩一下的話，你可以去[這裡](https://www.transum.org/Software/Nim/)，只是他有點吵。

A的勝利是偶然嗎？就像前面說的，其實如果雙方都以最佳策略進行操作，初始盤面就已經決定了勝負。當然對於某方必勝的局，另外一方根本沒有所謂的最佳策略，因為怎麼玩都會輸。

接下來我們來探討怎麼樣會是先手必勝，怎麼樣會是後手必勝。

我們先看看只有一堆的情況：
如果這一堆有石頭的話，顯然先手的人直接拿完就贏了嘛。
如果沒有石頭的話，先手的人就輸了。
由此可知，先手必勝的條件是該堆石頭數量不為$0$。

接著我們來看看如果今天有很多堆呢？我們得想辦法用一些運算把這很多堆的資訊給結合起來，然後讓他在非0的時候是先手必勝，為0的時候為後手必勝。
於是呢，數學家就發現了一種方法可以滿足這些性質：將每一堆石頭的數量用異或($XOR,\oplus$，詳見附錄)結合起來，而這個值稱為nimber, nimsum, 或Sprange-Grundy value, SG value。
$XOR$具有以下好性質：

1. 交換律、結合律：直覺上交換順序顯然不能影響這個賽局的結果，因為你隨時都可以從任一堆進行操作。
2. $A\oplus0=A$：將一堆數量A加上一堆數量0等於沒加，也是挺直覺的。
3. $A\oplus A=0$：直覺上，如果有兩堆一樣多的石頭，其中一邊做甚麼操作，另一邊就跟著做，最終後手就會勝利，也符合nimsum=0為後手必勝。

之後數學家就用構造法構出了一種方式，使得nimsum非0的盤面一定能透過操作使其為0，而為0的盤面一定只能操作變成非0，而最終全部取完後的盤面為0，也就證明了非0盤面的先手必勝。

而這個必勝策略究竟要怎麼做呢？首先，目前盤面的nimsum為非$0$才有必勝策略，而我們每次都希望能把nimsum變成$0$，因此有了以下操作：
令現在的每一堆為$p_1,p_2,p_3,...,p_n$，$p_1 \oplus p_2 \oplus p_3 \oplus ... \oplus p_n=S$，而這次操作要取$k$個，
1. 將$S$以二進位表示，並找到第一個為$1$的那位。
2. 在所有$p_i$中找到那一位也是$1$的一堆，保證必定能找到，否則$S$的這位不可能為$1$。
3. 我們希望達成$S \oplus p_i \oplus (p_i-k)=0$，因此移項可得$S \oplus p_i=p_i-k$，所以$k=p_i-S \oplus p_i$。
這邊需要好好的解釋一下：
首先並不是所有運算都可以好好移項的，像是上高中之後會學的矩陣之類，其實移項就是在把兩邊同時做某個運算，而剛好$A \oplus A =0$，所以才會成立。
再來解釋那個算式是怎麼來的：因為我在$p_i$那堆取$k$個，而$S=(p_1 \oplus p_2 \oplus ... \oplus p_n)$，又$A \oplus A =0$，所以其實就是把$p_i$那項消掉變成$(p_i-k)$，這樣就很合理了吧。
最後，因為$k$一定要大於$0$，所以$S \oplus p_i<p_i$必須成立，那為甚麼呢？因為這兩個數最高的那位$1$會$XOR$掉變成$0$，然後就會$<k$了。
4. 照這樣下去，能進行最後一次操作的就一定是你。

於是我們就能在初始盤面nimsum不為$0$的nim遊戲中百戰百勝！好爽喔！

### Sprange-Grundy Theorem
所有標準無偏賽局都可以對應到一定數量的nim遊戲。

我覺得我就此打住好了，這次就先到這邊，之後有機會再來聊聊！

## 肆、賽局經典遊戲
### 囚徒困境
囚徒困境是一個經典的賽局遊戲，是賽局理論中兩個玩家對抗的問題，遊戲敘述如下：
> 警方逮捕甲、乙兩名嫌疑犯，但沒有足夠證據指控二人有罪。於是警方分開囚禁嫌疑犯，分別和二人見面，並向雙方提供以下相同的選擇：
>
> 若一人認罪並作證檢控對方（相關術語稱「背叛」對方），而對方保持沉默，此人將即時獲釋，沉默者將判監10年。
> 若二人都保持沉默（相關術語稱互相「合作」），則二人同樣判監半年。
> 若二人都互相檢舉（互相「背叛」），則二人同樣判監5年。
用表格概述如下：
>
> ||乙沉默（合作）|乙認罪（背叛）|
> | -------- | -------- | -------- |
> |**甲沉默（合作）**|二人同服刑半年|甲服刑10年；乙即時獲釋|
> |**甲認罪（背叛）**|甲即時獲釋；乙服刑10年|二人同服刑5年|

### 膽小鬼賽局
這是一個極度高風險的賽局遊戲，遊戲敘述如下：
> 遊戲中兩名車手相對驅車而行。如果兩人拒絕轉彎，任由兩車相撞，最終兩人都會死於車禍；但如果有一方轉彎，而另一方沒有，那麼轉彎的一方會被恥笑為「膽小鬼」（chicken），另一方勝出。

## 附錄A、二進位與位元運算
### 進位法
如大家所知，我們日常使用的進位法是十進位，但其實在不同的地方或語言中並不都是如此。像是在古老的美索不達米亞的巴比倫文化使用的就是六十進位，而瑪雅數字使用的則是二十進位，羅馬數字則不太一定，甚至在表示上還有右加左減的特性。扯遠了。

不論各種進位法，其實都遵守一個道理，就是數到幾就進位。因此，假設是$k$進位，從右邊數過來的第幾個數字其實就對應到$k$個幾次方(但最右邊的那個是第$0$個)，取$10$進位為例：
$5269=5\times10^3+2\times10^2+6\times10^1+9\times10^0$
$13=1\times2^3+1\times2^2+1\times2^0$
$1101$
也可以對應到中文的個十百千萬，由此可知中文是十進位系統的。
當然在每一種進位法都是可以互相換算的。

以下枚舉幾個常用的進位法與縮寫：
二進位 bin(binary)
八進位 oct(octal)
十進位 dec(decimal)
十六進位 hex(hexadecimal)
其實就是取那個數字的英文字根，我沒記錯的話好像國中或國小的英文課本裡面有(?)，或者是你在打電動的時候連殺也會出現的語音(?????)。
另外，十六進位因為數字不夠用，所以$10$~$15$是以ABCDEF表示，酷吧！
我們通常會在不是十進位的數字後面加上下標，如：$69=1000101_{(2)}=45_{hex}$
在寫程式的時候，可以透過前綴的方式指定進位法，如下：

int a=69;//dec
int b=0b1000101;//bin
int c=0105;//oct
int d=0x45;//hex

相信大家都知道電腦使用的是$2$進位，分別以$1\ 0$代表高電位和低電位，而你們寫出來的那些程式也會被轉換成二進位型式(binary form)，因此二進位對於資訊科學特別重要。

### 位元運算
位元運算是對一個二進位數字的一元運算或二元運算(維基百科)。每一種位元運算其實都對應到一種電路設計(邏輯閘)，這邊就不細究了。在電腦中，位元運算稍微比一般的加減乘除快，因此某些特別在意程式運作速度的人就會用這種方式來優化。

(以下的數字都是二進位，符號是你在寫程式的時候會用的，而不是邏輯運算子，在寫程式的時候直接寫英文縮寫也可以)
所以位元運算是甚麼呢？
一元的位元運算就是你對一個數字操作使他變成另一個數字，這種的好像只有：
1. $NOT($~$)$ 反相：所有$1$變$0$，$0$變$1$
~$0111=1000$

二元的位元運算就是你將兩個數字以某種方式結合，變成另一個數字：
1. $AND(\&)$ 且：皆為$1$才為$1$，即有$0$得$0$
$0011\&1010=0010$
2. $OR(|)$ 或：皆為$0$才為$0$，即有$1$得$1$
$0101|0110=0111$
3. $XOR($^$)$ 異或：相異為$1$，相同為$0$
$0101$^$1100=1001$
而$XOR$通常在書寫上以$\oplus$表示。
4. $a<<b$ 左移：將$a$左移$b$位，在二進位下即乘以$2^b$：
$0110<<1=1100$
5. $a>>b$ 右移：將$a$右移$b$位，在二進位下即除以$2^b$：
$0110>>1=0011$
這個部分就先到這邊，對這部分內容有興趣的學員可以上網搜尋更多資料，這是資訊科學的基礎必學之內容啊。