Day4 讓電腦下棋
===
看完了古人的操作，換我們來打造一個自動下棋AI了。
那除了把人塞進電腦裡之外，要怎麼讓電腦下棋呢？
以現今的科技要讓電腦下棋已經是稀鬆平常的事了，但是要怎麼讓電腦把棋下得好，甚至於遠超人類就是值得研究的問題了，不過這邊我們還是先從讓電腦可以下棋開始吧。

## 如何讓電腦下棋
### 工人智慧
直覺能想到的應該就是先學習人類的思維，我們怎麼下棋就讓電腦怎麼下棋。
以五子棋為例，我們要阻止對方連成五個，就得在對方連成三個時去阻擋對方。
那可能就會有像是以下的策略：

if 對方有活三 or 死四:
    擋住對方
else:
    幫自己造活三 or 死四

接下來根據遊戲的特性跟你的經驗可以寫出更多的規則，然後你的「AI」可能就會長得像下圖這樣。


會有滿滿的`if` `else`
但不管怎樣第一個會下棋的「AI」也算是完成了，又沒人說AI一定得用到什麼高深的演算法呢。
只是這麼做有個問題，那就是這樣的「AI」可能會有很多的「bug」，例如，自己可以連成活五，但對手有活三或死四，這個程式不會獲勝，而是去擋對方。不同的遊戲變化千變萬化，如果只判斷當前盤面，可能會產生無數種的例外情況。
而且AI的棋力會受到開發者棋力很大的影響，你寫的**程式棋力最強就是跟你棋力相當而已**，規則都是你寫的，你想不到的AI也下不出來，當然你也可以尋求棋力更強的玩家來幫助你寫規則，只是這樣終究有個上限。

### 暴力窮舉
既然寫規則有其極限，那我們乾脆暴力窮舉吧，不考慮效能的前提下，把所有可能的下法都試一遍總能找到最佳解的。
但現實是殘酷的，我們不可能不考慮效能，如果要窮舉完所有可能的下法需要100年的話，那我們按下執行後就可以開始寫遺囑了，只能**拜託自己的孫子將運算結果還有獵人的完結篇一起燒給你**，所以在我們使用暴力窮舉之前也得先做一些評估才行。

## 對局樹 (Game Tree)
對局樹是一種用來表示遊戲中所有可能行動和結果的樹狀結構。
這邊以井字遊戲(Tic-Tac-Toe)為例：
* 根節點 (root node)：代表初始的棋盤狀態，可以是空白棋盤或是下到一半的棋盤。
* 節點 (node)：每個節點代表一個特定的棋盤狀態。
* 邊 (edge)：從一個節點到下一個節點的邊代表玩家的一次行動(在棋盤上下一個子)。
* 層級 (level/depth)：樹的層級表示遊戲的進展，奇數層通常是玩家 X 的回合，偶數層是玩家 O 的回合。
* 葉節點 (leaf node)：代表遊戲結束的狀態，可能是 X 勝、O 勝或平局。

我們只要生成一顆對局樹，就可以透過遍歷整個對局樹，找到最佳的下法。
下面的示意圖為從盤面已經有6手棋開始展開。


## 對局複雜度 (Game Complexity)
跟我們在學習演算法時分析的時間複雜度與空間複雜度類似，當我們分析遊戲的複雜度時，就叫做對局複雜度。
對局複雜度通常包含兩個主要部分：**狀態空間複雜度**和**對局樹複雜度**，用這兩個指標來衡量遊戲的策略空間和決策過程的複雜性。

### 狀態空間複雜度 (State-space Complexity)
狀態空間複雜度是指遊戲中所有可能的棋盤狀態的總數，下面三張圖都是其中一種棋盤狀態，或是我更習慣稱為盤面。


一樣以井字遊戲為例：
* **理論最大狀態數**：
棋盤有 9 個格子，每個格子可能是空白、X 或 O，因此總共有 $3^9 = 19683$ 種可能的棋盤狀態，通常都會以此方式快速評估一個遊戲的狀態複雜度。
* **實際合法狀態數**：
考慮到以下因素，實際的狀態數會更少。
* **玩家次序**：X 和 O 的數量差不能超過 1。
* **勝負條件**：一旦有玩家獲勝，遊戲即結束，後續的行動不再合法。
* **對稱性**：旋轉和鏡像對稱的棋盤狀態被重複計算，下圖三種情況可以視為同個狀態。<br>

最終真正有意義的井字遊戲合法狀態數約為 765 種。

### 對局樹複雜度 (Game-tree Complexity)

對局樹複雜度是指遊戲中所有可能的對局（從開始到結束的完整行動序列）的總數。

以井字遊戲為例：
井字遊戲的棋盤一開始是空的，玩家 X 可以選擇任何一個地方，產生 9 種可能的局面。
第二步棋玩家 O 接著在剩下的 8 個空格中選擇一個位置下，所以共有 $9×8=72$ 種可能的局面。
第三步棋玩家 X 接著在剩下的 7 個空格中選擇一個位置下子，有 7 種選擇。
所以共有 $72×7=504$ 種可能的局面。
依此類推整個**井字遊戲能產生的局面就是** $9! = 362880$

**對局樹通常都比狀態空間大得多，因為要產生同一個狀態可以有很多種方式，比如手順不同但結果卻相同。**
比如下圖的盤面，X先下在A1再下B2跟先下B2再下A1會得到相同的盤面。


雖然狀態是相同的，但在遊戲樹展開的過程是完全不同的兩條路徑，如下圖。


如果將不合法、旋轉與鏡像等情況都刪除掉的話，那**最終只有26830種對局順序**。
當落子更多時就有更多機會造成相同的盤面，所以其實對局樹會有很多重複的盤面出現，造成效能的浪費，未來會介紹到Transposition Table就能夠來處理這個問題。

### 常見遊戲的複雜度
| 遊戲 | 狀態空間複雜度 | 對局樹複雜度 |
|-----------------|------------------------------|-----------------------------------|
| 井字遊戲 | 約 $10^{3}$ | 約 $10^{5}$ |
| Connect 4 | 約 $10^{13}$ | 約 $10^{21}$ |
| Othello (黑白棋)| 約 $10^{28}$ | 約 $10^{58}$ |
| 象棋 | 約 $10^{40}$ | 約 $10^{150}$ |
| 西洋棋 | 約 $10^{47}$ | 約 $10^{123}$ |
| 將棋 | 約 $10^{71}$ | 約 $10^{226}$ |
| 五子棋 | 約 $10^{105}$ | 約 $10^{70}$ |
| 圍棋 | 約 $10^{171}$ | 約 $10^{360}$ |
| 六子棋 | 約 $10^{172}$ | 約 $10^{140}$ |

狀態空間複雜度影響了需要存儲和處理的資料量，較低的狀態空間複雜度意味著遊戲可以被完全求解。
對局樹複雜度反映了完全遍歷所有可能對局所需的計算量，較高的對局樹複雜度意味著需要更深入的策略思考。
根據電腦對局導論中寫到，以2014年的電腦硬體，可以用窮舉法破解狀態空間在 $10^{13}$~$10^{14}$ 之間的雙人對局，所以可以看到基本上是大多數的遊戲都沒有辦法直接暴力破解，就算是2024年的今天估計也是進步的有限，所以看到一個新的遊戲時，先別急著暴力窮舉，先評估看看這個遊戲的複雜度再來決定要使用什麼方法。

## 結論
寫一堆規則的AI棋力受限於寫規則的人棋力，暴力窮舉雖然可以找到最佳解，但複雜度太高的遊戲可能有生之年都窮舉不完。

## Reference
* 電腦對局導論
* [賽局複雜度wiki](https://zh.wikipedia.org/zh-tw/%E5%8D%9A%E5%BC%88%E5%A4%8D%E6%9D%82%E5%BA%A6)