Day10 著手分析與優化

今天來分析一下前幾天介紹的演算法，還有討論一些優化方式。

Worst Case

在某些情況下使用Alpha-Beta Pruning卻會完全得不到效果，如下圖：

在這個範例當中等於搜索了整個對局樹，因為我們總是優先搜到較差的節點(對Max層的子節點先搜索最小值，對Min層的子節點先搜索最大值)，造成Alpha-Beta的區間範圍沒辦法有效剪枝，這樣就跟原版的Minimax Algorithm一樣了。

著手(合法走步)排序

就像是當年學Quick Sort時一樣，選定的Pivot會影響到Quick Sort的效能，所以會用一些方法去選Pivot避免產生worst case，例如花

$O(n)$ 的成本去找出Median of Medians，我們使用剪枝演算法也得要想辦法避免worst case，且更要想辦法造出best case。

完美排序

既然總是先搜索較差的節點會使效率變差，那假設我們有個方法可以對當前所有節點(當前的所有合法走步)進行評估，然後將其排序，這邊跟Scout一樣，我們評估節點的成本必須小於我們直接將其展開的成本。

下圖是將節點排序過，所有節點的第一個子節點都是最佳著手：

當 B 節點的值更新完回傳給 A 時，發現小於當前的Alpha值4，這樣我們就可以將 C 節點給剪掉。

因為最佳結果的分支總是先被搜索，更新的Alpha 和 Beta 值就可以有效的剪裁掉後續較差的節點，那這樣完美排序就是Alpha-Beta剪枝效果最佳的排序方式了吧？

很可惜，其實完美排序不一定是能夠最有效剪枝的方式。
大家可以先看著這張梗圖，思考一下是為什麼再繼續往下看。

最佳排序

這邊有一點反直覺，明明已經將最佳著手排序了，為什麼剪枝效果卻不是最佳呢?
我們再把上面的範例重新排過一次，如下圖：

B 節點回傳值給 A 節點時，發現小於當前的Alpha值4，就會把 C 節點與其分支都剪掉了。

前面的完美排序例子需要搜索6個節點，而這個例子只需要搜索4個節點，可以證明完美排序其實並不一定是最佳，那有沒有完美又同時是最佳的例子呢?

完美且最佳排序

樹的深度為d，子節點數為b的話，最佳的情況會是

$O(b^{d/2})$
假設有一個對局樹深度為4每個節點都有3個子節點，並且所有的節點的第一個子節點都是最佳著手，如下圖所示：

使用minimax的話需要搜索全部

$3^4$ 個節點，而此例子只需要搜索

$3^2$ 個節點。

應用

但實際上在應用時，我們並不用糾結在找出最佳排序，像是五子棋15x15的棋盤大小，要對所有的節點做精準的評估再加上排序，可能會消耗大量的成本，與其耗費成本找到最佳值跟最佳走步，我們只需要快速找到一個夠好的走步就可以了。

我們已知手拔(遠離當前雙方落子的區域)是較差的策略，那我們就可以將目前所有的合法走步做個排序。
例如直接用範圍限定，將紅框內的走步排序在前面，這就是一個非常快速不怎麼花費成本的方式，效果也會比從左上角1-1開始按照順序搜索好得多。

Iterative Deepening Search

還有一種優化方式為 Iterative Deepening Search(逐層加深搜索)，使用逐層加深的主要原因是我們不確定在「有限的時間內」應該探索多深。
由於不同的初始盤面會導致遊戲樹大小存在巨大差異，逐層加深提供了一個靈活且可靠的方案。此外，逐層加深造成的額外時間浪費幾乎可以忽略不計。考慮到每層搜索的節點數量呈指數增長，我們比較兩者的時間複雜度：

$b^n$ 和

$b^n+b^{n-1}+...+b^1$，相除後得到：

$$\frac{b^n+b^{n-1}+...+b^1}{b^n}=1+\frac{1}{b}+{\left(\frac{1}{b}\right)}^2+...$$

這是一個無窮級數，其和為

$\frac{b}{b-1}$，表示逐層加深帶來的時間開銷是

$b/(b-1)$ 倍，相對而言非常小。

既然逐層加深所造成的額外時間花費幾乎可以忽略，那麼我們還可以利用這個過程來進行優劣手順的排序，達到一石二鳥的效果。
下棋是一個連續的過程，除了少數的重大失誤外，大部分的著手都會跟前一手有關係，通常會導致局面有利與不利，都是連續數手造成的結果，每次增加搜索深度，並在新的深度中重用前一層次的搜索結果，利用前一層次中搜索出的較佳走步順序進行當前深度的搜索。

結論

不管是使用Alpha-Beta Pruning或是Scout Algorithm，搜索的順序都是很重要的，如果能有一個快速挑出較佳走步的方法，將會大幅增加效率。