Udacity AI Project 2 - Isolation Game Agent (3)

AI的有趣弔詭

AI領域中嘗試解決的問題通常都是exponential running time problem，所以我們事實上是要找出怎麼hack exponential的方法，但是弔詭的是一但找到了，通常人們就不再認為這是一個AI問題 @@

關於Minimax的小疑問

minimax的令人奇怪的一點是，我們幫min node猜想他的optimal choice的時候，用的是我們的heuristics，對手又不見得會採取一樣的思維，這樣minimax為什麼有用？

理想的search結果是直接search到end state，再讓search tree中的root來判斷一個最好的選擇。問題是我們會用一大堆類似alphabeta-pruning的原因就在於我們無法search到end state，花的時間太大了（除非量子電腦？！）。所以我們才會用heuristics在某個中間state就要評估分數了。

理論上如果我們的heuristics能給出對目前state一個接近真正的判斷分數的話，不論對手是用哪種 heuristics，都能“猜出”對手在每個search depth中的optimal的選擇。因為對手的heuristics如果遜於你，他heuristics中最好的optimal move可能只是你的heuristics的suboptimal move，這樣你幫他猜測的選擇是勝於他的，所以你的選擇已經建立在對手是選optimal move的基礎上。如果對手的heuristics勝於你，那情況仍然是正面的，因為這事你在有限的能力中能猜到對方最好的move，但是可能只是對方的suboptimal move，所以你的猜想錯了，輸了也不冤枉。

3-player game

三人以上的game，minimax就不適用了，這時候game tree還是類似，但是會多一個layer給第三個player，每個layer就update對應的player選擇evaluation score最高者，leaf node就回傳三個player各自觀點的evaluation score，然後往上propagate:

Isolation的小秘訣

isolation還有一些implementation的小技巧：

1. symmetric
由於isolation board是一個square，意思就是如果旋轉棋盤，

旋轉0度：

AI筆記20 - Linear regression models

Supervised Learning

regression和classification都是supervised learning的一種。
regression是找出一個function f (稱為regressor)，然後將input d-dimensional vector map到某一個實數：

而classification是將找出一個function f (稱為classifier)，map input vector到某幾個categories:

Linear Regression

有一些label好的data yi：

我們要learn 一個function f來 best fit這些data。
為什麼稱作linear regression? 因為此function f可以用一個線性方程式表示。舉例來說，一個1-d vector，可以在2-d平面上找出一條直線方程式：

當然我們知道此直線方程式有y=ax+b的型態，用這邊的符號寫成：

同樣的如果data是2-d vectors，我們再加上y value組成的3-d空間中可以找出一個hyperplane best fit：

當然此平面方程式如下：

我們可以歸納出通式，而實際上所謂的learning linear regression model，是在找出optimal 係數（係數扮演著每一個vector element的權重）：

要找出最適當的係數的話，可以使用least squares當作loss function，平方意義是不用擔心負值：

圖示的話如下，我們要對所有的loss的和做minimization:

我們定義要minimize的function稱為risk或是cost function，下面是一個平均loss的cost function，多乘一個1/2係數是之後微分可以cancel掉：

Linear Regression Learning範例

如果有一個1-d vector labeled dataset，我們知道其linear regression function會是以下的形式：

loss function採用least squares的話，則cost function或說risk如下：

如果把f(x)的定義帶入上式，則R變成一個beta的function，因為我們要求的是最適當的beta，所以beta變成了變數了：

注意雖然f是linear function，但是cost function是一個二元二次方程式，在空間中是一個bowl:

可以看到讓risk最小的(beta0, beta1)處於bowl正中心，所以有一個global minimum。

找出能minimize risk的beta，數學上可以寫成以下：

根據微積分，找出最小值就是偏微分各變數，並在等於零的時候算出：

Normal equations

我們可以把Risk function R寫成matrix form：

則R可以重寫成：

做偏微分：

做二次微分判斷有無極小值：

極小值只發生在二次導數為零時：

所以我們可以直接從learning dataset X算出optimal beta! 

不過當(X^T)X沒有inverse時，就無法算出來。另外用演算法去找此inverse在vector dimension很大的時候，會是O(d^3)！

Gradient Descent

如果(X^T)X沒有inverse的話，另一個找出optimal minimum使得risk最小化的方式是gradient descent，這算是一個持續不斷直到收斂的過程：

R function的一次微分就是gradient function，在一個變數時稱為斜率，這也就是gradient descent的由來，我們要找出R gradient為零的時候的beta值，演算法如下：

可以看到我們必須同時update/descent 所有的beta，這樣才能在空間中同時個變量都往minimum前進，所以可以看到beta - alpha * 斜率，alpha稱為“learning grade”，用來控制descent的速度。

對1-D feature vector來說，我們之前已經算出beta0和beta1的偏微分：

所以演算法可以寫成：

Implementation忠告

第五點跟線性代數有關....之後再來補充為什麼？！

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)：

Udacity AI Project 2 - Isolation Game Agent (1)

什麼是Isolation?

在台灣好像沒什麼過這個遊戲，簡單規則可見以下youtube video:

State space / Search space estimation

先說說state space，對一個5x5 board來說，可能的組合有25*24*....*1 = 25! ~= 10^25種state! 當然這是worst case，亦即還沒有任何玩家下子的情況，隨著玩家下子之後，search space只會是state space的subset，越來越小。

這個initial state space如果以一台每秒執行1億次指令的電腦來說，也得要10^16次方秒才能完成minimax的搜尋，相當於300百萬年............ @@

不過這是overestimate，因為每個玩家下子之後（也就是第三次下子）的"valid action"就已經受限於chess皇后那樣的行動範圍了，並非可以任意選擇剩餘未佔據的空格。

所以前兩次下子的組合的確有25*24種可能，但是一但雙方確定下子的位置之後，第三次下子時，最多可能的actions的位置只有中心點，總共有16種actions:

我們最多只會有depth = 25的search tree，因為最多只會有25次下子（稱為ply）。

這個5x5的isolation平均的branching factor是8子（根據多次模擬實驗算出），所以平均expand node數目為 8^25 = 1.3百萬年，仍然相當久！

總之這邊是要講，不可能搜尋完整個search space!

Depth-limited search

如果玩這個遊戲，限定兩秒內要下子的話，對一台每秒執行10^9次指令的電腦來說，最大能expand的node數目為：

所以套上b^d = 8^d = 2 * 10^9的限制，我們可以求出最大搜尋深度（在兩秒內）：

所以假設d = 9好了（保險起見），在depth = 9的時候，我們就停止minimax search，這時候要怎麼決定哪個state是好的？ 以這個遊戲來說，最後贏家是還能移動的玩家，所以或許也可以用“玩家還能移動的action數目”來當作evaluation function:

這邊要注意evaluation function 可能會在不同搜尋深度限制回傳不一樣的minimax值！
發生這個問題不一定是evaluation function不好，也有可能單純是搜尋深度不夠深，不過如果在某個深度之後的相對score(不管絕對值如何，但是能讓我們選出路徑相同的話）不再改變的話，再往下搜尋已經沒有意義，如果在此就停住的話稱為quiscent search。

Iterative Deepening

之前我們事先找出兩秒內，某個特定運算硬體能夠抵達的最深深度d，就執行minimax直到此搜尋深度停止。

一個邏輯上更簡單的方法則是每次都重新search整個tree (從root node開始），但是每次增加一點深度限制，直到時間限制到了就回傳目前最好的搜尋結果，不過這樣聽起來，是否很沒效率？畢竟每次都要從頭開始搜尋？

答案是還好，因為node expansion是O(b^d)，只要d不大，其實改變大約只是常數倍數而已，例如以下例子為branching factor = 2:

可以看到b=2時，iterative deepening約只比depth-limited search多expand了一倍的nodes數目，不能算多。

b =3 時：

n的通式為 n = b^0 + b^1 + b^2 + ... + b^d，“可能”藉由數學歸納法證明出：

iterative deepening的好處是一個遊戲不見得是每個時候都有一樣的branching factor，以isolation來說，剛開始branching factor最大，這時候search tree在時間限制內的搜尋深度是最淺的，但是隨著遊戲進行，越來越少的valid actions可以做的時候，branching factors降低的結果使得iterative deepening有機會搜尋到更深的深度，而事實上接近終局的時機，正是我們想要搜尋更深的時機，因為那足以決定勝負，但是在開局的時候，或許不需要搜尋這麼深。