Day2 淺談電腦對局
===

## 電腦對局

電腦對局是AI領域中非常重要的一個分支，自電腦被發明以來，就有非常多人熱衷於研究如何讓電腦學會下棋，希望讓電腦能夠在各種遊戲中展現出「智慧」，電腦對局的研究也為AI在其他領域的應用奠定了基礎。

對局遊戲除了大家比較常見的棋牌類遊戲之外，還包含各式解謎遊戲，根據不同類型的對局會有不同的做法，每種類型的對局都有自己的特性，以下做一些簡單的分類跟名詞介紹。
### 依照人數分類：
* 單人對局
數獨、魔術方塊、nonogram、15-puzzle等
* 雙人對局
圍棋、象棋、將棋、西洋棋、愛因斯坦棋、暗棋、五子棋、六子棋、黑白棋、蜜月橋牌等
* 多人對局
麻將、橋牌、鬥地主、德州撲克等

### 零和對局 (Zero-Sum Game)
雙方的利益和為0的對局，一方的利益會等於另一方的損失，雙方不存在合作關係的對局。

### 合作對局 (Cooperative Game)
所有玩家通過合作來共同達成某一目標，而非互相競爭。
大部分的棋牌類遊戲都還是互相競爭為主，就算是橋牌、鬥地主等中雖然有跟隊友合作的環節，但是同時存在著對手需要互相競爭，也不能算是合作對局。
像是桌遊[花火](https://zh.wikipedia.org/zh-tw/%E8%8A%B1%E7%81%AB_(%E5%8D%A1%E7%89%8C%E9%81%8A%E6%88%B2))就是所有人的目標一致，沒有任何競爭關係，這就是合作對局。
但我這次分享的內容都會以零和對局為主。

### 完全資訊對局 (Perfect Information Game)
玩家可以得知全局的資訊
例如：圍棋、象棋、西洋棋等
### 不完全資訊對局 (Imperfect Information Game)
玩家無法知道所有的資訊
例如：橋牌、鬥地主、麻將等

### 發散型對局 (Divergent Game)
合法盤面的可能組合數會隨著雙方移動次數增加而愈來愈多。
### 收斂型對局 (Convergent Game)
合法盤面的可能組合數會隨著雙方移動次數增加而愈來愈少。

其實很多遊戲都會同時存在發散與收斂的情況。
比如井字遊戲 (Tic-Tac-Toe)，每回合的合法盤面組合數總和算法為：

$$f(x) = \binom{9}{\lceil \frac{x}{2} \rceil} \binom{9 - \lceil \frac{x}{2} \rceil}{\lfloor \frac{x}{2} \rfloor}$$

$x$：表示目前雙方（X 和 O）移動的總步數。

${\lceil \frac{x}{2} \rceil}$：取上限表示 X 的移動步數。因為 X 先手，當總步數為奇數時，X 會比 O 多下一步。

${\lfloor \frac{x}{2} \rfloor}$：取下限表示 O 的移動步數。當總步數為奇數時，O 的步數比 X 少一步。

這邊公式的小括號就是計算組合的C，等於 $f(x) = C^9_{\lceil \frac{x}{2} \rceil} C^{9 - \lceil \frac{x}{2} \rceil}_{\lfloor \frac{x}{2} \rfloor}$

| $x$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|
| $f(x)$| 9 | 72 | 252 | 756 |1260 |1260 | 756 | 252 | 72 |

可以看到井字遊戲一開始為發散型，盤面變化量會隨著 $x$ 變大跟著變大，但到了有6手棋後就變成收斂型了，又開始漸漸變小。
通常發散型的對局會較收斂型來得複雜，很多遊戲到了最後都會變成收斂型對局，就有機會將其破解，然後儲存這些結果建立成殘局庫，我後面也會介紹到殘局庫的做法。

### 機率型對局 (Stochastic Game)
對局含有機率成分，玩家無法控制所有情況。
許多不完全資訊對局也都是機率型對局。
例如：麻將，你沒有辦法知道你下一張會摸到什麼牌，甚至連摸牌順序都有可能改變。
完全資訊對局的話有：[愛因斯坦棋](https://zh.wikipedia.org/zh-tw/%E6%84%9B%E5%9B%A0%E6%96%AF%E5%9D%A6%E6%A3%8B)，能移動哪顆棋子是靠擲骰子決定的，所以不管優勢多大都有機會因為運氣不好而被逆轉，想起6年前曾經聽研究所學長說過愛因斯坦棋是個~~糞game~~好遊戲。

## Reference
* 電腦對局導論