28 天自制你的 AlphaGo (1) : 圍棋 AI 基礎
知乎對於人機大戰的關注度很高,希望這個系列能讓大家對於人工智慧和圍棋有更多的了解。如果有收穫,請記得點一下贊。
大家都知道 AlphaGo v13 的三大組件是:
- MCTS(蒙特卡洛樹搜索)
- CNN (卷積神經網路,包括:策略網路 policy network、快速走子網路 playout network、價值網路 value network)
- RL (強化學習)
現有的強的圍棋 AI 也都是這個思路了,我們也會按這個思路講。在這一篇先看看圍棋和博弈 AI 的一些基本常識。
本系列已更新多篇,其它幾篇的傳送門:
- (2) : 安裝 MXNet 搭建深度學習環境 知乎專欄
- (3) : 訓練策略網路,真正與之對弈 知乎專欄
- (4) : 對於策略網路的深入分析(以及它的弱點所在) 知乎專欄
- (4.5):後文預告(Or 為什麼你應該試試 Batch Normalization 和 ResNet)知乎專欄
- (5):結合強化學習與深度學習的 Policy Gradient(左右互搏自我進化的基礎) 知乎專欄
- (6):蒙特卡洛樹搜索(MCTS)基礎 知乎專欄
- (6.5): 在瀏覽器 Javascript 中直接運行策略網路(附第78手分析圖)28 天自制你的 AlphaGo (6.5) : 在瀏覽器 Javascript 中直接運行策略網路(附第78手分析圖)
一、圍棋規則
圍棋博大精深,但基本規則很簡潔。推薦這個在線教程:
熊貓圍棋網 - 遊戲的內容 - 第一天 圍棋的介紹 - 十天即可掌握!『PANDANET圍棋入門』
正常來說,黑棋的第 1 手要下到你的右上角,比如說右上角的"星位"或者"小目"。雖然棋盤是對稱的,下其它三個角也可以,但這是對弈的一種禮貌,這樣下對方就知道你是懂規矩的(當然,也可以第 1 手下在邊上,或者中腹,但目前人類一般認為是虧的)。
如果等不及,看完教程的"第一天"內容,其實就可以立刻玩一下了。下圖是我做的純神經網路走棋(稱為策略網路 Policy Network),這是電腦從幾十萬局人類高手棋譜所訓練得到的數據,棋力不錯,有奕城段位的水準。大家可以點擊打開:
點擊打開:Analyzing Go with Policy Network 圍棋策略網路預測演示
打開後,123456789代表電腦對於下一手的推薦選點的前9位。試試先按電腦的建議走一走,培養一下"棋感"吧!例如,你將會看到,電腦認為,人類高手最喜歡下的第一手在右上角的"星位"(下圖中的1號點):
看個有趣的事情。人機大戰第四局第78手後,其實策略網路給出的應對是正確的(1號點)。當時AlphaGo犯錯(選擇了5號點),說明當時價值網路和Rollout的判斷出現了問題:
二、圍棋規則的細節,目前市面的程序
圍棋規則實際有很多細節,而且並沒有世界統一的規則。現有的規則有中國、韓國、日本、應式等等,在大多數情況下不影響勝負的判斷結果,但還是有微妙區別,比如說中國是數子,有"粘劫收後",日韓是數目,終局有死活的判斷問題。
較為簡潔,適合電腦描述的可能是 Tromp-Taylor 規則: Tromp-Taylor Rules 。不妨做幾個調整:
a. 再簡化一點,去掉"全局禁同形再現",改成"罕見循環局面由裁判決定"(畢竟三劫以上循環的可能性很小),這樣程序就不一定要存一個每個局面的hash表。
b. 禁止自殺,這樣更接近其它規則。
c. 雖然目前看最佳貼目可能更接近 5.5,但還是按中國現有規則的 7.5 吧,方便大家統一。
目前市面最強的程序是 銀星17 和 Zen6,不過價錢也比較高(雖然都有X版)。而目前免費軟體中最強的是 Leela,棋力也還不錯,請點擊: chess, audio and misc. software
而且 Leela 有 console 的介面,可以接上目前常用的圍棋 GTP 協議。如果你有興趣,現在還有一個電腦圍棋的天梯,可以連進去與其它程序對戰,看自己的排名: 19x19 All Time Ranks 。
三、關於蒙特卡洛樹搜索
關於蒙特卡洛樹搜索,有一個常見的錯誤認識,在此先糾正。
在棋類博弈 AI 中,很多年前最早出現的是蒙特卡洛方法,就是到處隨機走,然後看哪裡的勝率最高。但這有一個問題,舉個例子:
a. 如果走在 A,人有100種應對,其中99種,電腦會立刻贏,只有1種電腦會立刻輸。
b. 如果走在 B,人有100種應對,但局勢很複雜,大家都看不清,如果隨機走下去,後續的勝率雙方都是50%。
那麼如果計算蒙特卡洛的勝率,電腦會發現走在 A 的勝率是 99%,走在 B 的勝率是 50%。
可是,電腦的正解是應該走 B!因為如果走了 A,人如果夠聰明,就一定會走電腦立刻輸的變化。如果電腦執意要走 A,就只能稱之為"騙著"了。
於是有的人會說蒙特卡洛方法有缺陷。但是,蒙特卡洛樹搜索在理論上解決了這個問題。
怎麼把人想像得盡量聰明?這就要靠博弈樹。蒙特卡洛樹搜索是博弈樹和蒙特卡洛方法的結合,它不會犯 A 和 B 的問題,它很快就會發現 B 比 A 好。容易證明,如果給定足夠的計算時間和足夠的存儲空間,蒙特卡洛樹搜索可以收斂到完美的博弈樹,成為圍棋之神。
然而,實際的計算和存儲資源是有限的,實際的 A (不妨稱之為陷阱)也會更複雜。比如說:
c. 如果走在 A,經過博弈樹的模擬,電腦幾乎是怎麼走都怎麼贏;但是人更清楚後續的走法,人會走出完美的應對,在許多步後電腦一定會突然死亡。
這時,電腦要走遍了博弈樹的許多層,才能發現原來走到 A 會存在致命缺陷,掉入陷阱。這種情況下,蒙特卡洛樹搜索就容易在 A 和 B 的問題上給出錯誤的答案。這有好多種表現,比如說"地平線效應",又像 AlphaGo 被擊中的第 78 手。
圍棋中是有很多陷阱局面的,比如說"大頭鬼"。人工智慧如何正確應對陷阱局面,或者避免進入陷阱局面?這就需要 策略網路(policy network)、價值網路(value network)、強化學習 的共同作用。在後續的文章將會逐步介紹,包括具體的訓練方法。
四、第一篇的作業
1. 上面的那個純神經網路走棋是開源的,請改它的代碼,做一個基本的圍棋界面,包括吃子、打劫、點目等等基本規則。
2. 請閱讀它的論文: http://jmlr.org/proceedings/papers/v37/clark15.pdf 。
3. 請做一個傻瓜版的 策略網路,比如說會做眼,會吃子。可以參考 GnuGO 的 6. Move generation 。
4. 請做一個傻瓜版的 價值網路,比如說可以用"棋子向外輻射影響"的方法。可以參考 GnuGO 的 13. Influence Function 和 Bouzys 5/21 algorithm 。
本系列已更新多篇,其它幾篇的傳送門:
- (2) : 安裝 MXNet 搭建深度學習環境 知乎專欄
- (3) : 訓練策略網路,真正與之對弈 知乎專欄
- (4) : 對於策略網路的深入分析(以及它的弱點所在) 知乎專欄
- (4.5):後文預告(Or 為什麼你應該試試 Batch Normalization 和 ResNet)知乎專欄
- (5):結合強化學習與深度學習的 Policy Gradient(左右互搏自我進化的基礎) 知乎專欄
- (6):蒙特卡洛樹搜索(MCTS)基礎 知乎專欄
- (6.5): 在瀏覽器 Javascript 中直接運行策略網路(附第78手分析圖)28 天自制你的 AlphaGo (6.5) : 在瀏覽器 Javascript 中直接運行策略網路(附第78手分析圖)
如需轉載本系列,請先與本人聯繫,謝謝。小廣告:晚上工作學習是否覺得光線不夠舒服,精神不夠集中,眼睛容易疲勞?不妨點擊看看我們的自然全光譜燈系列:Blink Sunshine護眼LED燈泡 高顯指97顯色指數無頻閃學習檯燈床頭 如果需要好用的耳機或錢包,我們也有
推薦閱讀:
※先贏圍棋,再勝刀塔,跟遊戲較勁的人工智慧要怎麼趕超人類?
※首戰告負:王者不戀戰,機器無哀言
※圍棋人機大戰一周年:被AlphaGo改變的世界
※Master 橫掃圍棋各路高手,是時候全面研究通用人工智慧了!
TAG:人工智能 | AlphaGo | 深度学习DeepLearning |