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有機會搜尋到更深的深度，而事實上接近終局的時機，正是我們想要搜尋更深的時機，因為那足以決定勝負，但是在開局的時候，或許不需要搜尋這麼深。