作者：楊左使

2017年初，升級版的Google AlphaGo Master連勝圍棋60盤，戰敗了全世界的所有頂尖圍棋選手，各大互聯網媒體的頭條爭相報道。

除了神經網路外，MasterGo中還使用了蒙特卡洛演算法。接下來，我們為你簡單介紹一下這個「神奇」的演算法。

什麼是蒙特卡洛演算法？

通俗的解釋：

假設你需要從1000個蘋果中挑出最大的一個蘋果，你可以閉著眼睛每次只拿一個，不限制挑選次數。於是，你開始隨機的逐一比較，每次比較後留下大的蘋果，如此循環往複，拿的次數越多，挑出最大蘋果的可能性也就越大。但除非你把1000個蘋果都挑一遍，否則你無法確定最終挑出來的就是最大的蘋果。

簡而言之，在蒙特卡洛演算法中，樣本越多越能找到最佳的解決辦法，不過不能保證是最好的方法，因為如果不是1000個蘋果里挑選而是有10000個蘋果的話，或許能找到更大的。

與蒙特卡洛演算法相對是拉斯維加斯演算法：

舉例來說：假設你需要開一把鎖，有1000把鑰匙可供選擇，但只有1把能把鎖打開。於是你每次隨機拿1把鑰匙去嘗試，直到打開為止。嘗試的次數越多，打開鎖的機會就越大，但在打開之前，那些錯的鑰匙都是沒有用的。

所以，拉斯維加斯演算法要求盡量找到最好的解決辦法，但是未必能找到。假設1000把鑰匙中，不能有任何一把打開鎖，真正的鑰匙是第1001把，但是在樣本中並沒有第1001把，於是拉斯維加斯演算法就不能找到打開鎖的鑰匙。

MasterGo中的蒙特卡洛演算法

「機器人」與圍棋高手的對決，曾被稱為人工智慧的「阿波羅計劃」，因為圍棋有19×19=361個方格，棋手的每一步棋都有361種選擇，一局150個回合出現的選擇多達10170種。難度對於人工智慧來說非常大。

傳統的棋類軟體，包括IBM戰勝世界國際象棋冠軍的深藍計算機，一般都是採用暴力搜索，對所有可能的結果進行搜索。這種方法在象棋、跳棋等方面具有一定可實現性，但對於圍棋就無法實現。

MasterGo則通過蒙特卡洛樹搜索演算法和策略網路、估值網路這兩個深度神經網路合作來完成下棋。策略網路主要用於生成落子策略，在下棋的過程中，它不是考慮自己應該怎麼下，而是學習人類的高手會怎麼下。也就是說，它會根據輸入棋盤當前的一個狀態，預測人類下一步棋會下在哪兒，提出最符合人類思維的幾種可行的下法然而，策略網路並不知道落子的這步棋到底下得好還是不好，這時候就需要估值網路來發揮作用了。估值網路會為各個可行的下法評估整個盤面的情況，然後給出一個「勝率」，這些值會反饋到蒙特卡洛樹搜索演算法中，通過反覆如上過程推演出「勝率」最高的走法。蒙特卡洛樹搜索演算法決定了策略網路僅會在「勝率」較高的地方繼續推演，這樣就可以拋棄某些路線，不用一條道算到黑。

利用這兩個工具來分析局面，MasterGo就能判斷每種落子策略的優劣，就像人類棋手會判斷當前局面以及推斷未來的局面一樣；在利用蒙特卡洛樹搜索演算法分析了比如未來20步的情況下，就能判斷在哪裡下子贏的概率會高。

這就是MasterGo中的蒙特卡洛演算法，你看懂了嗎？

小結：

蒙特卡洛樹搜索演算法，是在海量樣本中找到最佳解決方案（而非唯一解決方案）的演算法；它是Google AlphaGo（Master）的核心之一，其價值在於能夠讓人工智慧的神經網路持續地在「勝率」較高的地方推演棋局（而非暴力搜索），以此大幅降低運算量，並判斷在哪裡下子贏的概率會高。

楊左使-上海谷歌社區人工智慧系列沙龍組織者，資深產品經理