hackMD原稿
再麻煩將背景調為淺色，深色背景會看不太到圖。

看完了古人的操作，換我們來打造一個自動下棋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，因此總共有 種可能的棋盤狀態，通常都會以此方式快速評估一個遊戲的狀態複雜度。

• 實際合法狀態數：
  考慮到以下因素，實際的狀態數會更少。

  • 玩家次序：X 和 O 的數量差不能超過 1。
  • 勝負條件：一旦有玩家獲勝，遊戲即結束，後續的行動不再合法。
  • 對稱性：旋轉和鏡像對稱的棋盤狀態被重複計算，下圖三種情況可以視為同個狀態。
    

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

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

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

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

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

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

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

常見遊戲的複雜度

遊戲	狀態空間複雜度	對局樹複雜度
井字遊戲	約	約
Connect 4	約	約
Othello (黑白棋)	約	約
象棋	約	約
西洋棋	約	約
將棋	約	約
五子棋	約	約
圍棋	約	約
六子棋	約	約

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

結論

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

Reference

• 電腦對局導論
• 賽局複雜度wiki