剪枝技術（Pruning）#
剪枝是提升搜尋效率的關鍵策略，通過提前捨棄無效或劣質分支，大幅減少搜尋空間。
為什麼需要剪枝？#
現實問題的狀態空間往往呈指數級增長。純粹的 BFS/DFS 會走訪所有節點，計算成本無法負荷。剪枝的本質是優勝劣汰：提前捨棄那些明顯較差或無效的分支。
剪枝的運作邏輯#
當搜尋進行到某個節點時（例如面臨 50 個分支）：
- 確定性剪枝：若能確定最優解只存在於某分支，直接捨棄其他
- 優先順序剪枝：優先搜尋「區域最優」的分支，較差的延後或捨棄
常見剪枝策略#
| 策略 | 說明 | 應用場景 |
|---|---|---|
| 可行性剪枝 | 當前狀態已違反約束 | N 皇后、數獨 |
| 上下界剪枝 | 當前路徑成本已超過已知最優 | Alpha-Beta 剪枝 |
| 對稱性剪枝 | 左右對稱只需搜一邊 | 排列組合問題 |
| 常識剪枝 | 基於領域知識排除明顯劣解 | 棋類遊戲 |
案例：井字棋的剪枝思維#
人類下棋時自然會進行剪枝：
當對手落子於某位置後，你不會再考慮「對手下在其他位置」的分支。這就是最自然的剪枝——根據已知事實，剪掉不可能的未來。
從深藍到 AlphaGo#
國際象棋（深藍，1996）#
- 方法：強大計算力 + 精細剪枝規則
- 搜尋深度：30-40 步
- 複雜度：約 10^123
圍棋（AlphaGo，2016）#
- 方法：深度學習 + 蒙特卡洛樹搜尋
- 創新：神經網路充當「智慧剪枝函式」
- 複雜度：約 10^360
從西洋棋到圍棋，本質上是對抗「狀態空間爆炸」。當無法窮盡所有變化時，演算法重心從「算得快」轉向「剪得準」。
棋類遊戲複雜度排行#
| 遊戲 | 博弈樹複雜度 |
|---|---|
| 圍棋 (19x19) | 10^360 |
| 日本將棋 | 10^220 |
| 中國象棋 | 10^150 |
| 國際象棋 | 10^123 |
剪枝的難點#
剪枝的難點在於評估函式的設計：
- 剪得太狠：可能漏掉全域最優解
- 剪得太少：起不到優化效果
這需要對具體業務邏輯有深刻理解。
實戰啟發式規則#
以象棋為例：
- 開局剪枝：沒人第一步移老帥，這種「傻步」直接剪掉
- 價值交換：用車（高價值）換馬（低價值）通常不划算，賦予低優先順序
- 歷史啟發：之前產生過好結果的走法，優先嘗試