28 天自制你的 AlphaGo(一)

雷鋒網註:本文作者彭博,Blink·稟臨科技聯合創始人。文章由雷鋒網整理自作者知乎專欄,獲授權發佈。

一、圍棋 AI 基礎

大家都知道 AlphaGo v13 的三大組件是:

  • MCTS(蒙特卡洛樹搜索)

  • CNN (卷積神經網絡,包括:策略網絡 policy network、快速走子網絡 playout network、價值網絡 value network)

  • RL (強化學習)

現有的圍棋 AI 也都是這個思路了,我們也會按這個思路講。在此先看看圍棋和博弈 AI 的一些基本常識。

1、首先是圍棋規則。

圍棋博大精深,但基本規則很簡潔。推薦這個在線教程:

注意,正常來說,黑棋的第 1 手要下到你的右上角,比如說右上角的"星位"或者"小目"。雖然棋盤是對稱的,下其它三個角也可以,但這是對弈的一種禮貌,這樣下對方就知道你是懂規矩的(當然,也可以第 1 手下在邊上,或者中腹,但目前人類一般認為是虧的)。

如果等不及,看完教程的"第一天"內容,其實就可以立刻玩一下了。下圖是純神經網絡走棋,你持黑,電腦持白(因為黑棋先走,有優勢,所以最後要倒貼幾目給白棋,叫做貼目),大家可以點擊打開:

這個網頁第一次打開會比較慢,因為要加載一個 50M 的神經網絡數據。

圖中的顏色可以點擊 "Show Analysis" 打開,是神經網絡的最終輸出。越紅的地方,代表神經網絡認為越可能成為下一手。你也可以把 "Auto Move" 關掉,自己和自己下。

試試先按電腦的建議,走在紅的地方,培養一下"感覺"吧!

如果有多個紅點,可以任選一個。當然,不可迷信,它的紅點時常是錯的,也時常不全面!

這個電腦不會計算,完全沒有搜索,全部都是靠神經網絡的「感覺」,用圍棋的話說,可以說是按照"定式"和"常型"等等,所以死活弱(就是你可能會有機會把它的棋吃掉!),很適合新人找感覺。

2、圍棋規則實際有很多細節,而且並沒有世界統一的規則。

現有的規則有中國、韓國、日本、應式等等,在大多數情況下不影響勝負的判斷結果,但還是有微妙區別,比如說中國是數子,有"粘劫收后",日韓是數目,終局有死活的判斷問題。

較為簡潔,適合電腦描述的可能是 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

3、關於蒙特卡洛樹搜索

有一個常見的錯誤認識,在此先糾正。

在棋類博弈 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)、強化學習 的共同作用。在後續的文章將會逐步介紹,包括具體的訓練方法。

二、安裝 MXNet 搭建深度學習環境

介紹完圍棋 AI 的基本常識,咱們開始搭建深度學習環境。

目前的環境很多,最多人用的是 Google 的 TensorFlow;不過 MXNet 感覺也蠻不錯,比較省資源(當然,最好兩個都裝)。配圖是 MXNet 的例子裡面的 LeNet 訓練 MNIST 數據集,這是很經典的模型,可以看到準確率在隨着訓練不斷提高:


安裝之前先看個好玩的:github.com/dmlc/mxnet.js 是在瀏覽器直接運行 MXNet 的效果。TensorFlow 也有類似的東西: transcranial/keras-js。也就說,我們訓練好模型后,可以直接在網頁裡面可視化,這樣就可以輕鬆跨平台。


1、Windows的安裝

第一次裝深度學習環境經常會遇到一些坑,這裡看一個實際安裝 MXNet 的過程。先看 Windows 的安裝,比較簡單和快速,因為不需要編譯。

說句無關的,我個人是推薦 Windows 的,因為顯卡還可以用於娛樂(這幾年的新遊戲的圖像進步很大),有興趣還可以玩個 VR 啥的。

  • 1) 首先裝了 VC2015,安裝時語言記得選上 C++。

  • 2)然後如果你有 nVidia 的 GPU,裝一下 CUDA:CUDA 8.0 Downloads 。選本地安裝版,建議用迅雷下比較快。如果沒有 nVidia 顯卡,買一塊吧,顯存盡量選大的,機器的電源也記得要跟上。實在沒錢就二手 750Ti 2G 顯存版吧,足夠玩玩簡單模型,因為 MXNet 省顯存。當然,用 CPU 也可以跑,就是慢。

  • 3)再下載 cuDNN,這個要註冊一個帳號。註冊一個吧: NVIDIA cuDNN 。解壓備用。

  • 4)下載 MXNet 的編譯好的包:github.com/ 先下載 vc14 base package,然後下載更新包(例如 20170114_mxnet_x64_vc14_gpu.7z 注意 GPU 包就是同時支持 CPU 和 GPU)解壓進去,然後把 cuDNN 也解壓進去(見它的文檔)。執行 setupenv.cmd 。

  • 5)裝個 Python 吧,推薦 Anaconda,選 Python 2.7 的版本: Download Anaconda Now! 。建議用迅雷下比較快。裝完檢驗一下 python 命令可用。

  • 6)進開始的 MXNet 目錄的 python 子目錄,執行 python setup.py install 。會發現提示要裝一個 Microsoft Visual C++ Compiler for Python 2.7,去裝了。

  • 7)然後再執行 python setup.py install,可能會發現提示缺頭文件,把他們從你的 VC2015 的 include 目錄拷貝到 Microsoft Visual C++ Compiler for Python 2.7 的 include 目錄即可。要根據提示拷貝好幾個頭文件。然後就可以成功編譯了。

  • 8)運行 python,然後 import mxnet 然後 (mxnet.nd.ones((2,2), mxnet.cpu())*100).asnumpy()然後 (mxnet.nd.ones((2,2), mxnet.gpu())*100).asnumpy() 如果全部成功,恭喜你,裝好了。

  • 9)再下載 dmlc/mxnet,在 example 目錄 python train_mnist.py --network lenet 。會先下載測試數據,等下它,比較慢。看看是否成功訓練。

  • 10)再測試 VC++ 的環境。下載 MXNet.cpp (不需要執行裡面的 setupenv.cmd),然後打開 windows 目錄下面的 vs 下面的 MxnetTestApp,運行試試。再試試裡面有句可以改成 Context ctx_dev(DeviceType::kGPU, 0); 會發現 GPU 確實比 CPU 快。

  • 11)可以用 CPU-z 和 GPU-z 看你的 CPU 和 GPU 有沒有偷懶,是否是在全心全意工作。

2、Mac 的安裝

下面看 Mac 的安裝,我是 OSX 10.11。

這個安裝麻煩一些,因為首先下面有些下載過程可能要 export ALL_PROXY="代理地址"(否則很慢)。另外 pip 也要換國內源,git 也要加代理,homebrew 也可以改國內源。

然後有時會遇到權限問題,請 chown 一下。有時可能也要 sudo。

  • 1)裝 XCode。最新 CUDA 已經兼容 XCode 8 了。

  • 2)裝 CUDA 和 cuDNN。

  • 3)裝 homebrew(百度搜索一下)。裝 python,建議 brew install pyenv 然後用它裝 anaconda2,防止破壞系統 python 版本:Mac OS X下安裝pyenv

註:如果發現 pyenv 下載文件奇慢無比,可以給 pyenv 加上 -v 看到找到下載路徑,然後手工下載,然後打開 /usr/local/bin/python-build 然後在 download_tarball() 函數裡面,直接把第一行改成 local package_url="http://127.0.0.1/Anaconda2-4.2.0-MacOSX-x86_64.sh" 然後你自己開一個 http 服務器即可。

  • 4)裝 MXNet: Installing MXNet on OS X (Mac) 按照 Standard installation 走。不要執行它的 Quick Installation 自動腳本,因為還會去重新裝 homebrew,非常慢。

  • 5)按它說的編譯(非常慢)。在 config.mk 中加:

USE_BLAS = openblas

ADD_CFLAGS += -I/usr/local/opt/openblas/include

ADD_LDFLAGS += -L/usr/local/opt/openblas/lib

ADD_LDFLAGS += -L/usr/local/lib/graphviz/

USE_CUDA = 1

USE_CUDA_PATH = /usr/local/cuda

USE_CUDNN = 1

USE_NVRTC = 1

另外可能要 ln -s /usr/local/cuda/lib /usr/local/cuda/lib64 。有問題就 make clean 一下再試試。

  • 6)檢查是否裝好:

cd example/image-classification/

python train_mnist.py

祝安裝成功!在下一篇我們會看看從棋譜提取訓練特徵。

小作業:

1. 介紹圍棋基礎的純神經網絡走棋是開源的,請改它的代碼,做一個基本的圍棋界面,包括吃子、打劫、點目等等基本規則。

2. 請閱讀它的論文: http://jmlr.org/proceedings/papers/v37/clark15.pdf 。

3. 請做一個傻瓜版的 策略網絡,比如說會做眼,會吃子。可以參考 GnuGO 的 6. Move generation 。

4. 請做一個傻瓜版的 價值網絡,比如說可以用"棋子向外輻射影響"的方法。可以參考 GnuGO 的 13. Influence Function 和 Bouzy's 5/21 algorithm 。


想在手機閱讀更多電腦與科技資訊?下載【香港矽谷】Android應用
分享到Facebook
技術平台: Nasthon Systems