AI 筆記29 - Genetic Algorithms

8-Queens again

仍然使用8-queens來當作講解genetic algorithms的範例。
這邊比較不一樣的是board representation，用一個list表示從左至右的column上的queen的位置，index 1在下，index 8在上！

如果找出兩倆queens能互相攻擊的組合，則8-queens有choose(8,2) = 28種可能的pair attacks。這邊利用genetic algorithm來解決這個問題。

Genetic Algorithms

之前在Columbia AI課程筆記中已經有記錄，這邊做一點補充。fitness function就像之前講的那樣 = 28 - 目前#attacking pairs。

一開始怎麼從基因庫中選擇親代？我們假設有基因庫如下：

這四個gene的fitness score = 24, 23, 20, 10。這個population的總共適應能力 = 24+23+20+10 = 78。
根據適應自然的能力，也假設較有交配權（dominant male)，所以可以簡單地用佔比的方式算出交配機率：24/78 = 31%，以此類推：

接下來就是靠交配機率來真的選親代，這就看怎麼implement機率，最簡單方法就是randomInt(1,101)，然後看出來的範圍落在哪就選哪個gene，此例中選了前三個genes，而第二個gene被選中了兩次，所以有兩次的基因傳遞機會：

注意這邊固定一對父母只能生出兩個孩子（二胎政策？！），這關乎於algorithm convergence的速度，算是一個可以調控的參數，這邊不多做討論。

剩下的基因交換過程稱為crossover：

當然最後就來個突變的機率吧，因為有解答的gene有可能永遠不會被選成親代，總之隨機性是這類演算法（例如simulated annealing) 的特色：

這個演算法的主要研究重點在到底要產生多少代的子代才能得到答案。

AI 筆記28 - Simulated Annealing

Iterative Improvement to find Optimal Solution

某些NP-hard problems 可以用iteratively improve的方式(可能）找到optimal solution，例如所謂的travelling salesman problem。

這種iterative improve的方法包括simulated annealing, genetic algorithm, random restart。

search技巧在此類problem中通常因為search space太大而失去功能。
舉4-queens board為例：

透過iterative improvement先解除最多攻擊關聯的queen，再找出次者，兩個步驟就能解出一個答案，但是search要花費的時間就遠不止：

N-Queens

這種解題方式算是有點嘗試錯誤法，假設我們有N-queen board如下，並且我們也知道每次在某個column移動一個queen的話，互相攻擊的次數會有怎樣的改變：

既然說是嘗試錯誤法，那就可以random選一個queen來走！

Hill Climbing

這類algorithm牽涉到找到如何對一個objective function找出optimal值，這在此function幾何空間中類似爬山的行為（假設要maximize objective function):

由於每次爬山可能都會卡在shoulder或是local maximum，所以通常會random重選出發點重做，看要做幾次，也可以有些方法減少重做的次數。

這邊要考慮step size: 太小則一來花費時間多，二來卡在shoulder時可能動彈不得，因為演算法通常會對shoulder或是平台加個no-improvement次數限制，所以step size太小時就只能卡在平台。step size太大又可能錯過maximum，甚至導致infinite loop，如果剛好在某個山峰的兩側來回震盪的話。

怎麼解決這個問題？

Simulated Annealing

annealing意思是退火，是鍛冶產業的專有名詞，在高溫（增加分子動能）逐漸冷卻過程中，讓欲打造的事物形成穩定的結構，通常是最能量節約的結構。

所以AI從物理學偷用了這個概念，不過這邊把提高溫度用增加隨機性代替，當然冷卻過程就是減少隨機性。有趣。

演算法如下：

這演算法有一個T(t)的溫度-時間函數，我們仍然隨機選擇能從目前此地能抵達的下一步。如果下一步比目前所在好（兩地的評分差deltaE > 0來衡量），則就前往下一步，否則就根據e^(deltaE/T)來計算是否前往下一步的機率。

一開始溫度T(t)會是趨近無限大使得此機率值趨近於1，也就是必然發生，不論deltaE是正或是負值。這代表一開始即變遇到較差的方向，也是會前往，這就像是退火過程中的升溫狀態，分子跳動的自由度極大且較為隨機性。這保證了我們能夠脫離local maximum或是shoulder的窘境。

當t漸漸變大，T(t)會趨近零，則e^(deltaE/T) = 2.78^會趨近+- inf。這時候其實就是正常的hill climbing了，因為deltaE > 0，則機率竟然爆炸 > 1，反之則趨近於零，所以永遠只會往更好（positive gradient)的方向爬去。

simulated annealing保證會converge在global maximum，如果T一開始購大，且逐漸冷卻的話。

AI 筆記24 - A* search

Search

search適合有用來解決“一連串選擇形成的最終事物”，怎麼找出這“一串”選擇，以及找到最好的這一串。

problem formulation

這個其實就是從AMA book摘錄出來的，畢竟主講人Peter Norvig也是書的作者，不過Columbia AI課程已經講過，就節錄ppt畫面就好：

Uniform-cost search

這邊有些有趣的圖，首先uniform-cost是建築在step cost上，會形成lcountour
-based search:

但是我們幾乎得搜尋平均來說半個search space才能reach goal! 因為他是漫無目的的地毯式搜索(實際上bfs/dfs都是，因為沒有heuristics)。

如果要改善這種無效率，uniform cost search可以加上"先expand最接近goal的node"的approach變成greedy search:

不過他不一定會找到optimal path，例如導航可能沿著河流繞一大圈才到目的地:

A* search

主要的重點還是在A*，他保證optimality 但是又比uniform cost快速，如果搭配一個 "好的" evaluation function f。

A*簡單來說就是以下這張圖而已:

他是greedy的，但是是"best estimated cost first" greedy，而不是naive greedy。

注意在把goal node放入frontier時 ，search並未結束喔!!! 要在goal node被goal test之後才算結束，這主要是演算法的結構所致，另外f是estimated cost，並非真實的cost，如果reach goal就停止會導致non-optaml result發生。

Admissible / Optimistic / No-OverEstimate Heuristics

A*只有在h function < true cost時才能保證optimality，這個已經在Columbia AI課程中證明過了。

怎麼確定一個heuristics是不是admissible?
以我們之前提到過的n-puzzle為例:

h1中，n個mispaced block至少要移動n次，所以一定小於真正要解決謎題的移動次數。
h2中，同理。

所以h1和h2都是admissible，而且h2優於h1因為h2(State) >= h1(State)，所以會減少node expansion數量，更快抵達goal。

不過如果search AI只能靠人類給他們heuristics才有辦法解決問題的話，那智慧在哪?
有沒有辦法AI自己長出heuristics?

Generating a relaxed problem

如果對n-puzzle的formal problem description為:

這可以看成是幾個constraints，限制state到state間的transition可能。

如果relax這個定義變成如下的話:

事實上這就(implies)是h2，因為adjacent implies box-to-box distance，而去除掉blank又implies euclidean distance，這個relaxed description使得h2變得自然。

如果relax到只有以下一句話:

這就是h1(當然也包括h2)，因為能從A移動到B的block就是misplaced blocks。

所以找出h1和h2是可以自動產生的!!!! 某種relaxing problem演算法可以找出candidate heuristics，如果給予某種formal problem description的規則的話。

這些candidate heuristics因為是relaxed problem下可以做的動作，所以相當於提供了state間的跳躍，或說新的transition的可能性:

所以candidates一定是admissible的，因為只會減少cost，不會增加。
另外更好的是可以採用max(h1(S),h2(S),...)當作每次的h(S)，這會更快接近goal state，但是壞處是要同時計算許多heuristics，不見得節省runing time。

使用Search的時機

其實search是最基本的AI工具，因為它只能解決很限制性的問題:
1. 我們需要有每個state的資訊
2. 我們需要知道所有可行的actions
3. actions必須是finite set
4. actions的結果不可是隨機性
5. 環境不可動態改變

所以基本上，玩棋類遊戲或是routing好像比較適合這類search AI。

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

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

Udacity AI Project1: Solving Sudoku

什麼是數獨？

9x9棋盤上，每個3x3方塊，把1~9不重複填入，但是對9x9棋盤而言，每個row或是column也不能遊戲會是先幫玩家填入幾個，當作是constraint：

Board representation

在課程中，教材內容把9x9 board encode成string 'A1' ... 'I9'，以下三種組合(unit)是可能需要在解題過程中考慮的：

對一個方格(box)來說，跟他同row, 同column, 同3x3 block的其他方格（稱為peers)都是必須要檢查的項目，因為遊戲規則所致，所以對上圖紅色box來說，他總共有20個peers，這對任意box都是一樣的數目。

可以用字串來encode目前board填入數字的狀況，例如以下：

左圖右上到下，由左至右可以encode成：
..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3..

右圖全部填入數字後，就可以把 . 符號換成填入的數字：
483921657967345821251876493548132976729564138136798245372689514814253769695417382

由於我們要依據某個box的名稱(例如'A1'或是'D7')快速找到某個box，可以用dictionary來implement lookup table。每個空格box值要填入'123456789'，因為我們待會要用消去法來消去重複的數字。

所以box dictionary在初始化的時候會變成以下形式：

{
    'A1': '123456789',
    'A2': '123456789',
    'A3': '3',
    'A4': '123456789'
    'A5': '2',
    ...
    'I9': '123456789'
}




思考邏輯

1. 消去法(elimination)：對任意一個box來說，先去除掉所有peers中不可能的值，例如以下圖示：

我們上面的範例，如果對每一個空格box依序執行對default value '123456789' 進行elimination，可以得出空格box的各種可能值（不是最optimal form，可能需要進行多次才能得到optimal form）：

def eliminate(values):
    solved_values = [box for box in values.keys() if len(values[box]) == 1]
    for box in solved_values:
        digit = values[box]
        for peer in peers[box]:
            values[peer] = values[peer].replace(digit,'')
    return values

2. 唯一可能
消去可能的選項後，如果出現唯一可能者，代表我們solve了某一個box的值，例如以下紅色unit:

有四個空格都有兩個以上的可能性，但是數字1只出現在右上角的空格！所以1只能填入右上角的box，solved!

對整個棋盤上所有的units（rows, cols, 3x3 blocks)去執行這樣的唯一可能檢查，不過這邊implementation要注意容易出錯，總之就是要exhaustively check:

def only_choice(values):
     for unit in unitlist:
        for number in '123456789':
            occurrences = [box for box in unit if number in values[box]]
            if (len(occurrences) == 1):
                values[occurrences[0]] = number

    return values

Constraint Propagation

以上的思考邏輯是用constraint來縮減search space（我們還沒開始search），這兩個步驟可以重複做（稱為propagation)，直到search space不能再被縮減為止，此時可能會找到solution，也可能不會，要檢查goal_state是否達到，以及是否再也不能having progress:

對這個specific board instance來說，constraint propagation是可以找到solution，但是對其他的board instance就不一定了，就要進入search階段。

下面的implementation為什麼要return false? 單純的constraint propagation不應該會抵達錯誤的state，意即某個box的值最後是填空的。但是下面這個reduce_puzzle是之後要當作search前處理的，所以當search選了某個child state去嘗試（也就是越俎代庖做了錯誤的only_choice)，的確有可能造成錯誤的state，就跟我們人力在玩Sudoku一樣，選了一個可能，最後發現填不下去了。

def reduce_puzzle(values):
    stalled = False    while not stalled:
        solved_values_before = len([box for box in values.keys() if len(values[box]) == 1])
        values = eliminate(values)
        values = only_choice(values)
        solved_values_after = len([box for box in values.keys() if len(values[box]) == 1])
        stalled = solved_values_before == solved_values_after
        if len([box for box in values.keys() if len(values[box]) == 0]):
            return False    return values

Search

如果一個比較複雜的board instance，無法用constraint propagation來找到solution，我們就可以進行search，例如DFS/BFS/AStar ... 。

initial state會是constrain propagation reduce之後的結果，這樣先大量減少我們的search space。root node可以選目前含有最少可能數字的box。

def search(values):
    values = reduce_puzzle(values)
    if values is False:
        return False
    if all(len(values[s]) == 1 for s in boxes):
        return values
    n,s = min((len(values[s]), s) for s in boxes if len(values[s]) > 1)
    for value in values[s]:
        new_sudoku = values.copy()
        new_sudoku[s] = value
        attempt = search(new_sudoku)
        if attempt:
            return attempt

Naked Twins 技巧

這算是only_choice的升級版，能有效縮減search space。我們在DFS search中要隨意選一個目前unsolved box value 長度最少者，當然最小值會是2，然後進行elimination和one_choice。

眾多value = 2的box candidates中，任意選擇一個就會長出至少一個錯誤的subtree，而且每次search只能100%確定這個box。，但是如果同時看兩個一樣value = 2且有相同value的boxes呢？（在同一個unit中）：

把這種box pair當作candidate的話，每ㄧ次search可以同時確定兩個boxes，因為如果某個child state return False，則明顯正確的答案就是另一個child state，當然在elimination步驟也能受惠：

Diagonal Sudoku變形

這就是Udacity AIND第一個作業啦，在課堂給的skeleton code上面，修改成更困難的Sudoku變形，也就是對角線的數字也要符合1~9不重複出現的constraint:

Sample code

到這邊下載: https://bitbucket.org/wang_sonny/aind_sudoku