機器學習 alphaGo — monte carlo search tree（1）

摘要： alphaGo alphaGo可能已經漸漸地淡出了人們的視野。但是他出現是有一定歷史意義。alphaGo 兩次登上自然雜誌封面。第二次是因為 alpha zero 而登上自然雜誌， 這次分享以 alphaGo 為基礎進行分享，分別是兩個話題一個是 神...

alphaGo可能已經漸漸地淡出了人們的視野。但是他出現是有一定歷史意義。alphaGo 兩次登上自然雜誌封面。第二次是因為 alpha zero 而登上自然雜誌， 這次分享以 alphaGo 為基礎進行分享，分別是兩個話題一個是 神經網路，一個是今天將的蒙特卡羅搜尋樹方法。

我們回顧一下機器學習的歷史，早在 1996 年，深藍就曾經戰勝過人類國際象棋冠軍。在沉浸了將近 20 年後才再次在圍棋上戰勝人類。在過去的 20 年，究竟發生了什麼，為什麼 alphaGo 姍姍來遲呢？ 答案是我們在技術上遇到瓶頸，而這些年隨著一些新技術和新概念出現的支援，才出現了alphaGo。

國際象棋和圍棋比起來，

國際象棋的規則是由人類創造的，而圍棋規則設計是如此的優雅，優雅經常被用來形容程式碼，這裡也被用來形容圍棋規則。這說明圍棋規則嚴謹，他不僅屬於人類。

我們通過一些數值來看一看國際象棋和圍棋的複雜度對比國際象棋棋盤 8 * 8而圍棋棋盤19*19 每一步考慮因數圍棋是 250 而國際象棋是 35。 所以圍棋根據狀態的選擇就像天上的星星是數不盡的。

在國際象棋中我們用到了minmax 規則，就是將決策樹按層劃分為分別屬於自己和輸入對手

由於國際象棋的複雜度遠遠不如圍棋，所以通過決策樹，就能計算所有的可能來做出正確的選擇。

browne Cb 和 Edward powly 在 2012 提出了蒙特卡羅樹搜尋方法，為 AI 點亮一盞明燈。

第一次接觸蒙特卡羅這個概念，是在渲染效果圖時使用到蒙特卡羅演算法來進行渲染。蒙特·卡羅方法（Monte Carlo method），也稱統計模擬方法，是二十世紀四十年代中期由於科學技術的發展和電子計算機的發明，而被提出的一種以概率統計理論為指導的一類非常重要的數值計算方法。是指使用隨機數（或更常見的偽隨機數）來解決很多計算問題的方法。與它對應的是確定性演算法。

在正式切入正題前，我想問大家一個問題就是什麼是 pi 。我們在高中或是初中就已經學過如何計算pi 。今天我們通過隨機模擬方式來演示一種全新的方式來算 pi 。我們畫一個方形，方形中在畫一個圓形，他們中心重合，並且圓的直徑等於方形的變長。然後隨機畫點，點在園內外的數量比來獲取 pi 的值。

蒙特卡洛搜尋樹分為四個階段，如圖 選擇 展開 模擬 和 更新

由於我們這裡是根節點，沒有選擇的餘地，所以選擇根節點，然後進行展開。

在模擬階段，然後我們以選中的節點，隨機地進行展開其子節點，一層一層地展開樹的直到結束的得出這次模擬的結果，可以是真假或者是贏或輸。

然後我們把隨機模擬得到值（w 我們用 w 表示贏）放回給這個節點值為 1/1 第一個 1 表示贏而第二個 1 表示進行 1 次模擬。

當所有子節點，也就是葉節點都遍歷出之後，我們在這一個級別選擇一個節點作為選擇的節點，以此節點進行更深入的研究。這個三個節點值分別為 1/1 0/1 0/1。

通過對比 1/1 0/1 和 0/1 ，我們會選擇第一個 1/1 這個節點，以此節點為基礎，迴圈 expansion simulation update 這幾個階段

隨著模擬次數增加我們的值也也就更接近真實值，待續