# 第六章 Adversarial Search

## Games

在人工智慧中，「Games」被視為一種特殊的多代理人（Multi-agent）環境

- 對手（adversary）：會嘗試阻止你達成目標
- 通常是零和遊戲：一方獲勝即另一方失敗
- 最常見的形式就是各種棋類遊戲，如西洋棋、圍棋、井字棋、跳棋等。

### 為什麼要研究 Games？

- **歷史悠久且有趣**：Games 是 AI 歷史早期的研究重點之一（如 IBM Deep Blue）
- **難度高**：代表 AI 的推理與決策能力
- **動作有限**：遊戲通常行動空間較小（有限合法步驟），適合做完整分析
- **真實世界模擬**：在商業策略、軍事決策等領域有高度相關性

### Games vs. 一般搜尋

| 面相 | 一般搜尋 | Games |
| -------- | -------------------------- | -------------------------------------------- |
| 對手 | 無（只有單一代理人） | 有（另一位玩家與你對立） |
| 解的形式 | 一條路徑（從起點走到終點） | 一個策略（針對所有對手可能的行動都要有應對） |
| 評估方式 | 啟發式函數估算「目標距離」 | 評估「當前局勢的好壞」，或是否能勝出 |
| 解法 | A\*、BFS、DFS、CSP 等 | Minimax、Alpha-Beta、Monte Carlo 等 |
| 例子 | 迷宮、路徑規劃 | 西洋棋、圍棋、井字棋、跳棋等 |

### Games 的種類

| | 決定的 | 隨機的 |
| ---------- | -------- | -------------- |
| 完美資訊 | 棋類遊戲 | 大富翁、雙陸棋 |
| 不完美資訊 | | 撲克牌、橋牌 |

## Minimax 演算法

- 兩位玩家（Player）：MAX 和 MIN
- MAX：想要獲得最大的分數
- MIN：想要獲得最小的分數
- MAX 先手，接著輪流行動直到結束
- Game 的搜尋結構
- 初始狀態：遊戲的開局狀態
- `Successor` 函數：對每個狀態給出所有合法走法及其結果
- 一個 `(move, state)` 的 pair 列表表示所有合法走法
- `Terminal` 測試：判斷遊戲是否結束
- `Utility` 函數：給出當前狀態的評分
- 例如：`+1`（贏）、`0`（平手）、`-1`（輸）

### 最佳策略（Optimal Strategy）

尋找一種策略，盡可能的取得最佳結果

- 兩位玩家皆是理性的，都會採取對自己最有利的策略
- MAX 會選擇能獲得最大分數的走法
- MIN 會選擇能獲得最小分數的走法
- 策略不一定是固定動作，而是對於每種情況都有應對的辦法

Game tree 的每個節點都有一個 `minimax` 值，並可使用以下函數計算：

$$
Minimax(n) = \\
\begin{cases}
Utility(n) & \text{if } n \text{ is a terminal} \\
\max_{s \in Successor(n)} Minimax(s) & \text{if } n \text{ is a MAX node} \\
\min_{s \in Successor(n)} Minimax(s) & \text{if } n \text{ is a MIN node}
\end{cases}
$$

- 如果有多位玩家，則 `minimax` 的值將會是一個向量

### 為什麼這個策略是「最佳」的？

- 你已經假設對手會做出**最糟糕的反擊**
- 所以你選的是「在最壞情況下，還能取得的最佳結果」
- 這種思維也被稱為：
Maximin 原則：最大化最小可能得分。

### 如果 MIN 沒玩得那麼好，會怎樣？

那麼你的實際結果只會比 Minimax 更好，不會更差！

所以：

- Minimax 策略是「保守而穩定的最佳策略」
- 若 MIN 玩錯誤，MAX 反而有可能得到更高分

### Minimax 的性質

- 完整性：是（如果 tree 是有限的）
- 最佳性：是
- 時間複雜度：$O(b^m)$
- 空間複雜度：$O(bm)$（使用 DFS）

## Alpha-Beta 剪枝

Minimax 演算法的時間複雜度為 $O(b^m)$，在西洋棋等遊戲中根本走不完。$\alpha$-$\beta$ 剪枝可以大幅減少需要展開的節點數量，而不影響最終決策結果。

- $\alpha$：
- 到目前為止，MAX 節點的最大值
- 代表 MAX 最多能拿到的分數
- $\Rightarrow$ 只會在 MAX 節點上更新
- $\beta$：
- 到目前為止，MIN 節點的最小值
- 代表 MIN 最多能讓 MAX 拿到的分數
- $\Rightarrow$ 只會在 MIN 節點上更新

### 剪枝的原理

- 當 MAX 的某個子節點的得分已經超過 $\beta$ 時
- MIN 已經有更好的選擇了
- 不會讓 MAX 拿到這個高分
- 所以可以剪掉這個子樹
- 當 MIN 的某個子節點的得分已經低於 $\alpha$ 時
- MAX 已經有更好的選擇了
- 不會讓 MIN 拿到這個低分
- 所以可以剪掉這個子樹
- 因此，對於節點 $n$，需要滿足 $\alpha < v < \beta$ 才會繼續展開

### 搜尋步驟

1. 設定初始 $\alpha = -\infty$，$\beta = +\infty$
2. 從根節點開始展開，並計算每個子節點的 `minimax` 值
3. 如果是葉節點，則：
- 回傳這個節點的 `Utility` 值
4. 如果是 MAX 節點，則：
- 選擇擁有最大 `minimax` 值的子節點
- 更新 $\alpha = \max(\alpha, v)$
- 當 $\alpha \geq \beta$ 時剪枝
- 表示 MIN 已經有更好的選擇了
5. 如果是 MIN 節點，則：
- 選擇擁有最小 `minimax` 值的子節點
- 更新 $\beta = \min(\beta, v)$
- 當 $\alpha \geq \beta$ 時剪枝
- 表示 MAX 已經有更好的選擇了

### Alpha-Beta 剪枝的性質

- 剪枝不會影響最終的結果
- 好的走訪順序可以大幅增加剪枝的效率
- 時間複雜度可以優化到 $O(b^{m/2})$
- 分支因子 $\sqrt{b}$
- 愈早剪枝，效果愈明顯
- 可能還會走到重複的狀態

## 啟發式評估（Heuristic Evaluation）

在不完美資訊的 Games 中：

- 遊戲樹太大了，很難走到所有葉節點
- Minimax 演算法和 Alpha-Beta 剪枝效率依然太低
- Shannon (1950) 建議
1. 提早終止搜尋，不要走到終局，例如走到某個深度就好
2. 用啟發式評估函數（EVAL）來估計當前局面的好壞

### 截斷搜尋（Cutting-off Search）

將原本 minimax 的終止條件「走到葉節點」改成「走到某個深度」

- 設定一個最大深度 `depth`，不讓 AI 思考太久
- 當搜尋到 `depth` 時，使用啟發式評估函數 `EVAL` 來估計當前局面的好壞
- 這樣就不需要走到葉節點了

### 啟發式評估函數（EVAL）

- 根據當前局面，給出一個期望分數（expected utility）
- EVAL 的品質決定了整體策略的表現好壞！
- EVAL 的要求
- **與終局評分一致性**：EVAL 在終局時的排序結果，應與實際 Utility 一致（誰會贏）
- **計算時間不可太久**：要足夠快速，才能在時間內進行大量搜尋
- **對非終局狀態，要有高度相關性**：分數應與「實際勝率」有強正相關性，越高分越可能贏
- 只適合「平靜狀態」（quiescent states）
- 若某狀態「接下來可能劇烈變化」（例如馬上被吃掉一個皇后），EVAL 可能會誤判
- 通常是將多個不同的「局面特徵（features）」各自評分後，加權組合成一個總分。
- 例如：棋子數量、棋子位置、控制區域、攻擊威脅等
- $Eval(s) = w_1f_1(s) + w_2f_2(s) + ... + w_n f_n(s)$
- $f_i(s)$：狀態 $s$ 的第 $i$ 個特徵函數
- $w_i$：第 $i$ 個特徵函數的權重（對於整體的影響程度）
- 每個特徵（feature）假設**彼此獨立**，這樣才能用線性加權方式評估
- 這些 feature 是可能是由神經網路自動學習的
- 權重可以用機器學習來訓練

#### 範例：西洋棋

特徵值種類：

- 棋子數量與類型
- 是否形成好陣型
- 國王是否安全（是否暴露）
- 可行動的合法步數數量
- 是否控制中心區域格子

### 蒙地卡羅評估函數（Monte-Carlo EVAL Function）

Monte-Carlo 評估是一種隨機模擬法，在搜尋時間有限或評估困難的遊戲中（如圍棋、撲克、軍棋）非常有用。

> 從當前狀態出發，隨機模擬 N 局遊戲直到結束，計算平均勝率作為該狀態的估分。

#### 步驟

1. 從當前狀態 $s$ 開始
2. 繼續隨機選擇合法走法，直到遊戲結束
3. 重複進行 $N$ 次模擬
4. 計算所有結果的平均 utility
$$Eval(s) = \frac{1}{N} \sum_{i=1}^{N} Utility(s_i)$$

#### 優點

- 不需專家知識（不需手動設計特徵與權重）
- 對複雜遊戲或未知環境特別有效（例如 AlphaGo 就使用蒙地卡羅樹搜尋）

#### 缺點

- 計算量大（模擬次數多）
- 運氣成分重，品質依賴模擬次數與隨機性
- 無法處理非常精確的局勢差異（例如某一步棋會導致立即死亡）

### 地平線效應（Horizon Effect）

AI 在有限深度搜尋時，無法預見「不久後將發生的重大變化」，導致低估或高估某些看似穩定的狀態。

#### 例子

- AI 評估一個狀態為安全，但其實再過兩步就會被將死（它看不到那麼深）
- 它選擇一個表面上沒立即問題，但實際上「只是延後痛苦」的行動

#### 成因

- 因為搜尋到了「cutoff depth」就停了
- 那之後的情況就像「地平線以外」一樣看不到
- 所以叫 Horizon Effect

#### 解決方法：Quiescence Search（穩定搜尋）

- 在評估之前，若目前狀態是「**局勢動盪**」（如剛被吃子、正要將軍）
- 就**延伸搜尋**到局勢變穩再做評估
- 讓 EVAL 不會因為剛好在轉折點而失真

## 有趣的遊戲

### 象棋的一些有趣現象

#### 不同階段會採用不同的策略

| 遊戲階段 | 策略方法 |
| ------------------- | -------------------------------------------------- |
| 開局（Opening） | 使用開局書（opening book），由專家知識決定標準走法 |
| 中局（Middle Game） | Alpha-Beta 搜尋、蒙地卡羅樹搜尋（MCTS） |
| 殘局（Endgame） | 倒推分析（retrograde analysis）終局資料庫 |

#### 評估函數的設計

- 棋子的價值
- 將（2000 分）、士/象（40）、車（200）、馬/包（90）、卒（10）
- 位置的加分
- 例如車在不同位置的價值不同

### 機率性遊戲

- 包含擲骰、抽牌等隨機元素
- 節點中除了 MAX 與 MIN 外，還出現了 Chance Node（機會節點）

#### 處理方法：期望效用（Expected Minimax Value）

$$
EMV(n) = \\
\begin{cases}
Utility(n) & \text{if } n \text{ is a terminal} \\
\max_{s \in Successor(n)} EMV(s) & \text{if } n \text{ is a MAX node} \\
\min_{s \in Successor(n)} EMV(s) & \text{if } n \text{ is a MIN node} \\
\sum_{s \in Successor(n)} P(s)EMV(s) & \text{if } n \text{ is a Chance node}
\end{cases}
$$

#### 範例

- 玩家輪流擲骰來決定可以拿多少顆石頭，誰最後拿到最後一顆石頭就輸
- 每一步都會涉及隨機值（骰子點數），必須根據每個點數可能導致的狀態來計算期望效用

#### 撲克牌

撲克處理方式：

- 假設所有可能手牌組合
- 對每個組合估算行動結果 → 取加權平均 → 作為期望效用
- 計算複雜，但能模擬不完全資訊與機率性

### 常識決策問題

> 你要選擇一條路，路 A 只有一點小金幣，路 B 是個分岔路口（可能獲得珠寶或被車撞）

- 雖然兩條路平均期望一樣，但人類會傾向選擇風險低者
- 說明期望值不一定能代表實際「合理」選擇
- 需要更進一步的推理與資訊收集

## 小結

- 遊戲是多代理系統中最有挑戰性的類型
- 完美行為 ≠ 實際可行行為 → 需取近似法
- Minimax、Alpha-Beta 是核心基礎
- 評估函數、剪枝、機率模擬是實戰必要技巧
- 博弈是 AI 世界的「F1 賽車」——複雜、速度、策略並重