Alpha Go 系列文 - Minimax算法簡介
Monte Carlo Tree Search(MCTS) 是 2016 Deepmind 圍棋AI AlphaGo 的核心算法,基本上 AlphaGo 就是由神經網路和MCTS 組成的.
原本我想直接說明MCTS, 但我發現它很難在一篇文章中解釋清楚, 為了幫助理解, 我會在這篇文章中先介紹MCTS的簡易版本, MiniMax算法的運作原理.一旦你熟悉了MiniMax算法之後, MCTS 其實也會變得很比較好懂,
MiniMax — Simulation
如果今天要讓你設計一套能玩圈圈叉叉(tic tac toe)的軟體,你會怎麼做呢? 最直覺的方法是窮舉法, 如果我讓 AI 能夠在決定下一步之前, 先把所有可能的走法都先走過一遍,然後選擇會贏的那一條路線,那麼AI變能夠得到最大勝率
這樣簡單粗暴的算法被稱為Minimax algorithm,如果把他畫成圖的話會是這樣 (註：我畫的是3x1版本的圈圈叉叉(3x3版本的太難畫),3x1的版本只要兩個圈連在一起,圈就會贏)
這個窮舉的過程稱為simulation (或是 rollout),在simulation 時AI並沒有和真正的環境互動, 而只是在腦中模擬未來可能的所有情況,你可以說,這個情況下的AI 正在思考
在完成simulation 之後, AI 獲得了洞悉全局的能力,那麼我們應該如何利用這個資訊來決定哪個move 是最好的呢？
MiniMax — Backup
假設自己的對手(人類)很笨,只會隨機選一個位置來下,那麼根據模擬樹(simulation tree)的結果
如果AI選擇路線a 的話,勝率有50% (path1 tie,path2 AI win)
如果AI選擇路線b 的話,勝率有100% (path3 AI win,path4, AI win)
如果AI選擇路線b 的話,勝率有50% (path5 tie, path6, AI win)
但是,我們知道人類並不笨,所以 minmax 算法 讓AI 假設對手和自己一樣強,同樣具有洞悉全局的能力,
比方說,在 AI 選擇 下 a 的情況下, 人類因為同樣能夠洞悉全局,所以一定會選擇把圈圈下在最右邊(path 1),因為這樣子就會平手,比起讓AI贏, path 2對人類來說是更正確選擇.
在這樣的情況下,AI 假設人類會想辦法最大化人類的勝率(最小化AI 的勝率), 而非隨機選擇,所以根據模擬樹(simulation tree)的結果
如果AI選擇路線a 的話,勝率有0% (path1 tie, path2 is impossible because human won't select that action)
如果AI選擇路線b 的話,勝率有100% (path3 AI win,path4, AI win)
如果AI選擇路線b 的話,勝率有0% (path5 tie, path 6 is impossible)
所以,根據模擬結果,選擇路線b 的勝率最大
我們可以將上面這些敘述畫成這張圖
如果輪到 Human 的時候, Human 會選擇 minimize AI的勝率 (minimize AI's value), 輪到AI 的時候 會選擇 maximize AI的勝率 (maximize AI's value)
我們發現, AI 如果想要知道哪一個move 是最佳解,必須從 Tree 的最底層(leaf node)選出最大值,然後再往上一層, 因為輪到human 所以要選最小值,然後再往上一層, 因為輪到AI 所以選最大值...., 最後才抵達最上層 (root node),得出action b 是最佳解的結論,
這樣從最底層往上 update 到最高層的過程 稱為 backup
結論
就這樣我們靠著MiniMax算法得出了 最佳解,只要照著這個MiniMax Tree 的指示, 我們就可以得到最大勝率,不可能有人會下得比你更好.
所以看起來我們可以透過Minimax稱霸所有棋盤遊戲,對吧？
恩,理論上是這樣沒錯,但是我們通常沒辦法窮舉所有可能,以圍棋為例子, 如果要使用上述的方法在19x19的棋盤上做出一個 minimax tree, 那個tree 的大小至少會是 (19x19)x(19x19-1)x(19x19-2)x...x(1), 相當於361!
我不知道361!到底有多大,但我知道 100!大概等於 9.3 *10 ^ 157,而 361! 肯定比100! 的 100!倍的100!倍還要大得多,這個數字是這麼的巨大以致於我在計算機中輸入時361!它直接回傳 inf, 所以你知道電腦是沒辦法計算這樣巨量的數字,
我們不可能窮舉任何事物, 如果我們不能知道所有結果的話,那我們就只能估計他, Monte Carlo Tree Search 使用採樣(sample)的方式來估計勝率, 很好的解決了Minimax 算法過度消耗運算資源的問題,我們會在下一篇文章中說明它是如何辦到的
補充
這裡我想補充一個小技巧,在backup的時候, 如果不想要每過一層就從min 換成max,從 max 會成min .... , 其實可以每往上一層就乘上-1, 然後全部取max,
因為 max(a), min(a), max(a),min(a)... 等同於
max(a),max(-a),max(a),max(-a)...
這樣可以讓程式比較好寫一點
