Day 3. AI 趨勢 - 搜尋和邏輯推理 - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天

2022 iThome 鐵人賽

DAY 4

AI & Data

OH～ AI 原來如此，互助就此開始！系列第 4 篇

Day 3. AI 趨勢 - 搜尋和邏輯推理

14th鐵人賽 ai alphago

henry_chen

2022-09-18 09:30:04

2678 瀏覽

分享至

昨天的 AI 歷史讓我們知道，AI 已經在棋盤遊戲上贏過世界頂尖棋士甚至擊敗世界冠軍。那麼你知道當初在黑白棋，西洋棋，將棋，圍棋哪個是 AI 最難擊敗人類的嗎？先讓我們看看 AI 是如何辦到的。

搜尋樹（Search Tree）

在第一次 AI 浪潮中，最先想到的是試著讓電腦解決迷宮問題。所以需要將迷宮轉換成電腦看得懂的形式。像這樣將每個分歧點以及死路給一個符號，並將路線連結起來成為一個樹的結構，這個樹我們稱為搜尋樹。

本系列文的說明範例，為了方便理解，盡可能製作比較簡單的圖例來說明。

要從起點走到出口，基本2種的走法就是先橫著走（廣度優先搜尋）和先往下走（深度優先搜尋）。

廣度優先搜尋（簡稱 BFS，Breadth First Search）
先把這層的走完再走下一層。
- 優點：想要找到離出口的最短距離為幾層時可以使用這個搜尋。
  以這個例子而言可以看出最短距離為 2（層）
- 缺點：比起深度優先搜尋需要更多記憶體去記憶要走的點。
  因為每走一個點需要先把這個點的下一層節點都先記憶起來，才知道這層走完下一層有哪些節點要走。走 1，記憶 23。走 2，記憶 45。走 3，記憶 6G，以此類推層數越多越耗記憶體。
深度優先搜尋（簡稱 DFS，Depth First Search）
總之先往下一層走，直到不能走再回上一層換方向。
- 優點：省記憶體。
  因為借助連結線只需要回上一個點就知道往哪走，所以不用記憶接下來需要走哪些點。
- 缺點：速度完全憑運氣。方向對的話可能很快，也可能非常慢。

BFS 和 DFS 都可以選擇先從左或先從右走，如果出口靠右的話，先從右走會比較快找到答案。

利用這兩種搜尋法只要一直走，總有一天可以把所有路線組合走完找到出口。像這種沒有什麼技術，把所有可能性列出來靠著計算能力硬跑完一遍實在太暴力了，所以又叫做暴力法（Brute force）。但是這種解法蠻直觀的，早期還沒有最佳解的演算法時找答案都是靠這種方法。

河內塔（Tower of Hanoi）

搜尋樹也可以用來解河內塔問題，河內塔問題是有3個柱子，在第一個柱子套上大小圓盤。

一次只能搬一個圓盤
大圓盤不能在小圓盤上面

找出把圓盤搬到最右邊柱子的方法。
所以把河內塔轉換成電腦看得懂的形式，把三個柱子當成 A， B， C。把2個圓盤標示所在柱子（A, A），那麼將小圓盤移到 B 就變成（B, A），或是將小圓盤移到 C 就是（C, A），於是河內塔的搜尋樹就產生了。

河內塔號稱工程師一生要爬一次的塔（笑）。第一次 AI 浪潮誕生了很多有用的演算法，搜尋樹就是基本的演算法之一。

棋盤遊戲

還記得一開始問的問題嗎，棋盤遊戲對 AI 來說哪個最難呢？棋盤遊戲基本上也是採用搜尋樹的方法，所以關鍵就在於棋盤的大小和棋子的種類共有多少可能性的組合。

黑白棋：8×8的棋盤，棋子可以黑白翻轉。
組合數為 $10^{60}$
西洋棋：8×8的棋盤，黑白各6種棋子。
組合數為 $10^{120}$
將棋：9×9的棋盤，棋子各8種，加上捕獲的棋子也能使用。
組合數為 $10^{220}$
圍棋：19×19的棋盤，棋子是黑與白。
組合數為 $10^{360}$

等等...10的3次方就是3個零也就是1千，10的8次方就是1億了。上面的數字是在開玩笑嗎？這些組合數字實在大到像天文數字，已經沒有辦法靠暴力法解決一切問題了。光是計算所有組合可能有生之年都看不到結果，所以有效的減少搜尋的次數就是一個很重要的議題。

這邊就需要投入成本的概念，就像台北移動到高雄可以搭高鐵，坐巴士，根據所選擇的手段從時間和金錢來評估成本。成本高的路線就捨棄不碰。這種事先靠經驗判斷成本來減少搜索的方式稱為啟發式（Heuristic），因為成本是靠人給的猜想分數，找出的可能不會是最佳解，但可以大幅減少需要的計算時間。

這邊的猜想分數就是讓電腦參考過去比賽的棋譜，由人告訴電腦這樣的局面分數高還是低。

MIN-MAX 法

由於棋盤遊戲和迷宮問題不同，是有對手的，所以搜尋樹就變成你這回合下什麼位置，下回對方可能會下什麼的位置的組合所形成。而為了擊敗對手，需要取得最高的分數（成本），因此在自己的回合應該選擇下在分數最高的那一格（MAX）。但是對手不是笨蛋，他的回合肯定會下在讓你分數最少的那一格（MIN），這就是 MIN-MAX 法。

而透過 MIN-MAX 法，我們可以將像修剪樹木一樣將不需要搜索的樹枝給剪掉，減少搜索的次數。這種修剪法我們稱作 Alpha–beta 修剪（Alpha–beta pruning）。

Beta Cut
選擇最大分數時，前一回合已經有更小分數的節點出現，則省略不搜尋。
上圖假設使用左邊開始的深度優先搜尋。
- 搜尋到 A=3，繼續搜尋 B=-1, 你的回合會選擇分數最大，所以 C=3
- 搜尋到 D=6，你的回合會選擇分數最大，所以 E 至少會大於等於6
- C 和 E 是對手回合，對手選擇分數最小，所以對手不可能選擇 E，E 底下的 F 可以省略不搜尋
- 對手回合選擇 C，所以 G=3
Alpha Cut
選擇最小分數時，前一回合已經有更大分數的節點出現，則省略不搜尋。
- 搜尋到 H=1，繼續搜尋 I=-1, 你的回合會選擇分數最大，所以 J=1
- 對手的回合會選擇分數最小，所以 K 至少會小於或等於1
- G 和 K 是你的回合，選擇分數最大，所以不可能選擇 K，K 底下的 L 可以省略不搜尋

早期的黑白棋，西洋棋，AI 使用這種手法都得到了不錯的效果。但是大魔王的圍棋還是沒能有效獲勝人類玩家，所以又延伸出其他方法。

蒙地卡羅方法（Monte Carlo method）

蒙地卡羅這名字其實是一個賭場的名字。我每次看到這個名字都忘記是幹嘛的，所以都用賭場來聯想。簡單來說就是使用大量的隨機抽樣，來逼近真實情況的方式。例如拋硬幣會隨機出現正反面，如果只拋一次出現正面，那正面以統計來看就是機率100%，但是我們知道正反面應該是要各50%的機率，而拋了無數次之後，正反面出現的機率會趨近於理論值的一半一半。

圍棋有分 19×19 棋盤和 9×9 棋盤，可就算是 9×9 棋盤，明明組合數比西洋棋少了，還是很難贏初階的職業棋手。這個原因在於圍棋的分數（成本）的評估問題。以往的方法是事先輸入各種對戰棋譜，由人先來評價該情況得多少分，因為是人憑著經驗去給的猜想分數，導致對戰的結果不同。

之後 AI 完全放棄傳統事先靠人評估分數的方法，而是採用蒙地卡羅方法，由電腦模擬兩個人對戰，雙方隨機下在某個位置，總之先讓遊戲進行到結束（Playout）, 這樣讓遊戲結束好幾次，計算哪種下法勝率最高來獲得分數。結果利用這種方法，9×9 的圍棋，AI 可以達到等同職業棋士的水準。

但即便使用蒙地卡羅法，19×19 棋盤的圍棋組合還是太龐大了，最後還是加上深度學習自動找到更好的特徵才完成擊敗頂尖棋士的創舉。