2017年11月3日 星期五

加藤英樹談圍棋AI的過去.現在與未來(3)


使用蒙地卡羅法來模擬

大橋:
到深度學習出現為止,電腦圍棋是以蒙地卡羅法為主流吧。

星合:
何謂蒙地卡羅法?

加藤:
蒙地卡羅原本是摩納哥非常有名賭場的名字,也是這樣,歐美國家有把使用亂數進行運算的演算法的名字前面加上蒙地卡羅的習慣。

大橋:
換句話說,在圍棋程式中為了表示這也是一種使用亂數的手法,所以才會稱為蒙地卡羅圍棋程式吧。

加藤:
2006年幾乎是可以稱為蒙地卡羅革命的一年,因為在這一年中圍棋軟體的寫法發生了重大變化。在這以前,程式師得先做出「空三角是惡形」之類的程式出來,然後去進行局部死活搜尋。至於判斷形勢的評價函數也得是人類自己人工硬做出來的。然而這樣的程式,還是無法寫出判斷「厚勢」之類感覺的評價判斷。好比說,厚勢最終相當於多少的實地,這是無法判斷出來的。

星合:
現在的圍棋AI反而是非常會判斷厚勢的威力呢。這到底是發生了甚麼變化啊?

加藤:
這個問題問的很好。1990年時德國的馬克思.樸朗克研究所的布留克曼博士想到了「既然途中進行判斷很困難,那就乾脆讓程式下到完來看結果就好了」的作法。換句話說,就是使用模擬,讓程式去算雙方如果順勢走到最後會出現甚麼結果。在某個局面下,將數個可能的候補落點分別利用亂數的方法算一千次的模擬,然後選出勝率最高的落點當作次一手。這就是原始的蒙地卡羅法。

星合:
就是一種地毯式搜索的模擬對嗎?

加藤:
不是喔,詳細的內容這裡就省略不談,但它是用亂數去隨機選擇落點來下。也是這樣,一開始跑出來的結果非常不正確。這個模擬的適切性、可以模仿出多少實際真正會出現的手順,對於棋力的強弱有決定性的影響。此外,搜尋樹也是一般在討論蒙地卡羅法時一個很重要的因素。所謂的搜尋樹是指在某個局面下,先把很有力的落點集中到好比十個點。然後再針對這十個落點進行模擬。前述的亂數模擬因為很不正確,所以才會用搜尋樹來集中模擬並且獲得比較正確的結果。

大橋:
這些搜尋模擬分枝看起來很像樹木,所以也被稱為蒙地卡羅搜尋樹。

加藤:
將蒙地卡羅搜尋樹導入圍棋AI之中的,就是創作出狂石(Crazy Stone)這套圍棋程式的雷米.庫隆先生。在2007年狂石參加了電腦奧林匹亞競賽的九路圍棋項目,結果奪下冠軍,而讓蒙地卡羅法一夕成名。

星合:
這就是蒙地卡羅革命了吧?

加藤:
是的。不過,由於19路棋盤實在太廣大了,所以使用這個方法還是無法打敗人類。所以雷米.庫隆先生又使用了新的手法。星合小姐有在阿罵爽等網路商店買過東西嗎?

星合:
有啊。特別是有「推薦給你的商品」的指示非常便利。

加藤:
就是這種手法。它是利用了買某種商品的人也會買另一種商品的屬性來表示出推薦商品。這個手法將之應用在圍棋程式上,就像是下了某一著之後,就會跟著出現另一著的情形。

大橋:
好比說打吃必粘這種情形。

加藤:
靠著這個手法,就讓圍棋程式達到了業餘初段以上的水準。這樣就知道雷米.庫隆先生有多偉大了吧。

===



相關系列文章:

沒有留言:

張貼留言