AlphaGo背後的搜索演算法：蒙特卡羅樹搜索
本文首發於 微信公眾號號「編程派」 。微信搜索「編程派」，獲取更多Python編程一手教程及優質資源吧。
昨天（3月9日）下午，經過三個多小時的較量，韓國棋手李世石宣布向谷歌人工智慧AplphaGo認輸，意味著人工智慧獲得了這場人機世紀之戰的第一場勝利。而此前AlphaGo已經以平等條件擊敗了歐洲圍棋冠軍樊麾。
有專家在賽後評論說，AlphaGo的勝利只能算是演算法的勝利，因為人工智慧目前只是一種演算法程序，沒有道德，也沒有情感，更談不上情感。
小編其實認為這並沒有錯，而且就算李世石最後輸給了AlphaGo，這樣不代表人類輸給了機器人。因為這台打敗了人類最高智能代表的機器，是由人類一手精心打造的，其內部的演算法也是眾多科學家一步一步改進得來的。
本文的主題，就是AlphaGo能夠成功擊敗專業棋手的功臣之一：蒙特卡羅樹搜索（Monte Carlo Tree Search）。
蒙特卡羅搜索樹的貢獻，從谷歌AlphaGo的官方網站上就可見一斑。
我們知道，圍棋有著明確的遊戲規則，其中不存在隨機或運氣成分（如擲骰子或洗牌）。這類遊戲都可以歸類為所謂的完美信息博弈（perfect information games）。在完美信息博弈中，每時點參與人採取一個行動，每個參與人在其決策的同時知道以前所有的行動。
因此，理論上我們是可以構建一個包含了所有可能結果的樹，因為遊戲中所有的一切都是有規則可循的（fully determined）。幾乎所有的弈棋程序，都是依靠其強大、精確的計算能力，來預測好的下法。
為什麼之前的弈棋程序沒有征服圍棋？AlphaGo並不是第一個智能弈棋程序。1997年時，已有超級電腦深藍戰勝國際象棋棋王卡斯帕羅夫的先例。那麼為什麼深藍沒有乘勝追擊，挑戰圍棋呢？這是因為IBM在比賽結束後就讓深藍退役了。O(∩_∩)O~
說正經的，這很大程度上與圍棋的極大可能性和此前弈棋程序的演算法限制有關。
我們知道，圍棋棋盤橫豎各有19條線，共有361個落子點，雙方交替落子，這意味著圍棋總共可能有10^171(1後面有171個零)種可能性。這超過了宇宙中的原子總數是10^80(1後面80個零)！
而傳統AI一般採用的是暴力搜索方法（深藍就是這樣乾的），就所有可能存在的下法構建一個樹。這樣自然根本無法應對圍棋遊戲啦。
什麼是蒙特卡羅樹搜索？「蒙特卡洛樹搜索」是一種啟發式的搜索策略，能夠基於對搜索空間的隨機抽樣來擴大搜索樹，從而分析圍棋這類遊戲中每一步棋應該怎麼走才能夠創造最好機會。
一位名叫蘇椰的知乎用戶舉了這樣一個例子，以通俗的語言進行了解釋：假如筐里有100個蘋果，讓我每次閉眼拿1個，挑出最大的。於是我隨機拿1個，再隨機拿1個跟它比，留下大的，再隨機拿1個……我每拿一次，留下的蘋果都至少不比上次的小。拿的次數越多，挑出的蘋果就越大，但我除非拿100次，否則無法肯定挑出了最大的。這個挑蘋果的演算法，就屬於蒙特卡羅演算法：盡量找好的，但不保證是最好的。
需要說明的是，蒙特卡羅樹搜索並不是只有一種演算法，而是一類演算法。其中最流行的演算法之一就是UCT（upper confidence bounds applied to trees）。
AlphaGo是第一個使用該演算法的弈棋程序嗎？AlphaGo不是第一個使用蒙特卡羅樹搜索的弈棋程序。
據senseis.xmp.net網站介紹，第一個使用UCT演算法的圍棋程序是MoGo。而且，MoGo在2008年的美國圍棋公開賽上，第一次在19x19的全尺寸棋盤上擊敗了職業選手（當然與AlphaGo不同，這位職業選手讓了9個子）。
AlphaGo是如何使用蒙特卡羅樹搜索的？雖然「蒙特卡洛樹搜索」在此前一些弈棋程序中也有採用，在相對較小的棋盤中能夠很好地發揮作用，但在正規的全尺寸棋盤上，這種方法的缺陷也體現出來了，因為涉及的搜索樹實在太大了。
但AlphaGo採用了很聰明的策略，利用深度學習的方法降低搜索樹的複雜性。因此「深度學習」和「蒙特卡洛樹搜索」就成為它的兩個關鍵因素。在每個模擬遊戲中，AlphaGo都有兩個大腦指引它進行搜索：價值網路（value network）和政策網路（policy network）。「政策網路」觀察棋盤布局企圖找到較好的下法，「價值網路」則預測這樣下的話對方棋手贏棋的可能。結合這兩個建議，AlphaGo最終決定怎樣落子才是勝算最大的。
當然可以，而且一個使用UCT演算法實現的Python弈棋程序只有400行代碼左右哦！想要下載試玩的話，就看本期另外一篇推送吧。
參考資料：https://jeffbradberry.com/posts/2015/09/intro-to-monte-carlo-tree-search/
http://senseis.xmp.net/?MonteCarlo
http://senseis.xmp.net/?UCT
http://tech.huanqiu.com/news/2016-03/8668752.html
https://www.zhihu.com/question/20254139
http://googleresearch.blogspot.com/2016/01/alphago-mastering-ancient-game-of-go.html
推薦閱讀：
※用圖片搜索視頻是一種什麼樣的技術？
※五行缺人---我司招人啦
※哈希表總結及其高級話題討論
※Google 2018搜索指南-RankBrain演算法（一）