Udacity AI Project 2 - Isolation Game Agent (2)

Horizon effect

如果電腦計算的深度不夠深，在某些時候，人腦有相當大的優勢，例如以下isolation棋局，輪到O下子：

人腦可以看出來(但是可能要花超過兩秒... XD) O往(-1,-1)移動的話，之後X基本上只能在右邊空格移動了，因為左邊的路都被堵死了：

精確的說O至少可以有7格移動空間在左半部，X只能往(+1,+1)的方向移動，而右半部最多也只有六格空白可以移動。此時兩者都不能自由進入左右半部，等於棋盤被做出兩個partitions，但是勝負已經在這個ply決定了，而人腦是可以察覺出來的（兩秒內？應該可以）。

問題是對電腦來說，勝負end state必須還需要在13個moves才能決定，也就是還要往下搜尋13個深度，而根據之前所算的，depth-limited search平均兩秒內最大搜尋深度d = 9，所以在這邊，電腦會輸了。

這種效應稱為horizon effect，意思是（我猜）只能看到地平線上的東西，cannot see anything beyond the horizon。

更甚者，如果O往(-1,-1)移動，如果搜尋未能抵達end state就回傳值的話，我們的evaluation function會回傳3（此方格只有三個自由活動空間），而可能會往（-2,-2)移動，因為那個方格有六個自由活動空間：

死得更快！

修改evaluation function?

一個可能的方法是在evaluation function中加入partition是否形成的檢查（要找出connected squares!)，不過這增加了複雜度，可能會減少相同時間內的搜尋深度，反而得出反效果。不過這其實還是取決於各個遊戲的規定，很難說此舉好或不好。

另外一些“簡單”但是可能的evaluation functions:

第一個function: 根本是讓對方贏？！
第二個function: 沒有勝負指標
第三個function: 如果my_moves變大，此回傳值就變小，所以一樣是要讓對方贏
第四個function: 鼓勵my_moves以及懲罰opponent_moves，所以是四者中唯一可行的

這邊牽扯到了，要怎麼評估一個evaluation function好壞的問題：
以第四個function來說，我們甚至可以weight opponent_moves更多，這樣比較aggressive去阻止對方贏勝過我方贏:

如果採用此兩個定義，我們來看電腦在這個state是否會選中(-1,-1)這個致勝下子：

看起來的確會！
不過這也是只是針對這個state有好的結果，我們還是應該要大量測試每種evaluation function，然後藉由經驗數據採取最好者。

Alpha-Beta Pruning & Reordering

之前在columbia AI課程已經詳細講過了。
課程中沒特別講要用DFS，但是應該是要用DFS，要不然應該不會work。

來看一下reordering，假設以下是原本的minimax tree:

這個tree中，我們可以prune掉第四個leaf (score = 4)。
如果做reordering tree的話，能不能增進prune的量？可以的只要替換最右邊兩個max node的順序就可以（要自己手動去算才知道）。

由於DFS的搜尋順序所致，reordering的一個原則就是：min node要先找到最小的upper bound，所以底下的max children node最好先回傳最小者。同理max node要先找到最大的lower bound，所以底下的min children node最好先回傳最大者。

alpha-beta pruning透過reordering可以把minimax縮減成O(b^d/2)：