淺談蒙特卡洛樹搜索（MCTS）

1] 圍棋軟件AlphaGo的3個主要系統

最近打敗世界圍棋手李世石的圍棋軟件AlphaGo主要由以下3個系統組成：

1. 策略網絡（Policy Network）：落子選擇機制，它着眼於每一步弈棋的下法。

2. 估值網絡（Value Network）：局面評估機制，它注重於對全局形勢的判斷。

3. 蒙特卡洛樹搜索（Monte Carlo Tree Search，MCTS）：實現圍棋這樣超高複雜博弈機制的一種隨機算法。

前兩個系統容易理解。蒙特卡洛樹搜索則有些讓人不好理解。本想看到內行的介紹文章，但這類文章一直沒有出現。故不揣冒昧，先寫一篇，以拋磚引玉。

2] 什麼是搜索樹和樹搜索？

由於棋類活動的每一步一般可以有好幾種走法，因此可以把這個思考過程描述成一棵“樹”的形狀，術語就稱為“搜索樹” [search tree]，見圖：

而發現這棵“樹”中的每一步好棋，就稱為“樹搜索”（tree searching）。

簡單的棋類，如“井字棋”、“五子棋”，可以把所有能走的全部棋步都找出來，然後把對手的回應棋步也全都找出來，然後找出第3步、第4步、……，並對每步都進行評估，這樣就形成了比較正確的走法。這是人們下棋時思考的過程。想得越深、越廣，就越容易贏棋。

電腦軟件模仿人類下棋，也是採用這種方法；只是它把每個棋步都評分成數值，比較這些數值的大小。數值越大的棋步表明贏的希望越大，就成為軟件走棋的依據。

但是對於中國象棋、國際象棋和圍棋來說，這棵“樹”就太大，根也太深了，寫出這樣算法的軟件就比較難。

特別是圍棋，由於它的棋盤上有361個點之多，因此把這些棋步全部找出來，是不現實的。

由此就引入了蒙特卡洛搜索。

3] 蒙特卡洛搜索樹及其原理

蒙特卡洛樹搜索，簡單地說，就是只在全部可以走的棋步“樹”中，隨機地選取若干棋步，從中挑選出最好的那步棋走。等對方回應的棋步走出後，再繼續隨機地選取相應的棋步，重複這樣的過程；而不是找出所有可能的棋步。

因為摩納哥（Monaco）的蒙特卡洛是世界有名的賭城之一，而這樣的搜索有些像賭博那樣碰運氣，因此得名。

有人舉了一個生動的例子來描述蒙特卡洛搜索樹。

在一個密封的筐里有100個蘋果，人們每次拿出1個蘋果，目的是從筐中挑出最大的蘋果來。

人們最先想到的做法就是：隨機拿出1個蘋果，再隨機拿出另1個蘋果與它相比，從中挑出較大的那個蘋果來；然後再從筐中拿出第3個蘋果，把它與那個大的蘋果相比，挑出大的那個……。這樣重複以上的過程。

人們每次挑出的蘋果都至少不比上次的小。拿出的蘋果越多，就能找到越大的蘋果。但是除非人們挑選完所有的100個蘋果，他們無法肯定挑出了筐里最大的蘋果，但是卻能保證能挑出已經拿出來的蘋果中最大的那個。

這個挑蘋果的算法，就是蒙特卡羅樹的算法：儘量選出好的，但不能保證是最好的。

由於蒙特卡洛樹搜索僅隨機選取了某幾個棋步進行比較，因此，它走出的棋步也並非是最佳的棋步，但是卻是比較好的棋步。對AlphaGo來說，至少是可以取勝的棋步；最壞的情形，大概是能保證它不會輸的棋步。

具體反映到AlphaGo上，這就是為什麼它有時會走出一些“弱手”而讓9段高手們看不起的原因。但是高手們不了解的是，軟件走出的那些“弱”的棋步其實並非不會取勝，只是為了減少計算，它可能選擇了當時棋手們看來只是第二好、第三好，甚至第n好的棋步；只要保證它能贏棋，一步的好壞對它來說是無所謂的。

這也解釋了為什麼AlphaGo僅在幾個月前贏了2段棋手，而在幾個月後卻能以4:1贏了9段棋手李世石（第4盤中，李世石也只能說是險勝）。實際上，軟件是根據對手的棋步來相應地走棋的。對手弱，它選擇的棋步就會弱，而不是像人類棋手那樣，根據自己的水平走出自己的最好走法。遇到9段高手，它也是如此。這顯示出它“遇強則強，遇弱則弱”的特點。

蒙特卡洛算法由數學家烏拉姆（Stanisław M. Ulam，1909-1984）最早提出，再經科學天才馮·諾伊曼（John von Neumann，1903-1957）發展和完善。

烏拉姆曾利用這個蒙特卡羅方法計算裂變材料的中子擴散問題。

4] 題外話

因為AlphaGo是人寫的，因此它肯定有弱點。就是說，它並非不可戰勝的。

AlphaGo軟件的估值網絡，據報道可達13層之多；就是說，它可以看到13步棋步那麼遠。

而在開局階段，由於AlphaGo軟件採用的蒙特卡洛樹搜索的那棵“樹”太大，因此可能會犧牲掉一些搜索的深度，而達不到13層之多，以此來保證有足夠的搜索的廣度。

由此可以看出，AlphaGo的開局是比較弱的。其實這也是所有棋類對弈軟件的普遍弱點。有關資料顯示，AlphaGo這個“軟弱的”開局階段大概持續20手左右，以後隨着棋盤上的棋子越來越多，它的棋力也會越來越強。

因此，人類棋手需要在開局階段儘量找到能占優勢的棋步，而不能寄希望在中盤甚至收官階段來打敗它；或者想把局面弄複雜些來打敗軟件。

從資料來看，平常的比賽時，AlphaGo經常打開一個5x5個局部棋盤的窗口；就是說，它一般能把這25個格子裡的變化都研究得透透的了。這個水平，估計人類9段棋手是做不到的；他們可以根據經驗來大致評估雙方的棋勢，而不能把每個點（目）的各種情況都算透了。

棋類對弈軟件的全局觀較差

有人可能會說，這次AlphaGo與李世石的比賽中，感到軟件的全局觀是不錯的。其原因可能是，據說李的棋，局部計算較好，全局上面則較差。對比之下，反而是軟件更強些。

想想也能明白，畢竟整個棋盤的全局的計算量巨大，而局部的計算量則較小。

棋類對弈軟件沒有主動進攻意識

棋類對弈軟件主要根據對手的走法找出相應的棋步來應對。它們普遍缺乏主動地在某個局部挑起戰爭的意識。尤其在前段棋局時是如此。這也是由於主動挑戰需要的計算量太大，應付局面則需要的計算量小多了。

作為軟件的人類對手，就要利用軟件的這個弱點，主動挑起戰爭。

這也是李世石感到軟件在執黑時弱、執白時強的原因：先手時它不知道走什麼好；而應戰時則比較好走。

多展開幾個局部的戰爭。讓軟件不知道應該把主要精力放在哪兒。

電腦軟件大多是“一根筋”思路。它可以把事情計算得很深層，但是不善於應付多局面的事務。要至少展開2個以上的局部戰爭。

參考連接

https://www.zhihu.com/question/20254139

http://songshuhui.net/archives/94410