28 天自制你的 AlphaGo（一）

本文作者：彭博

2017-01-23 11:19

導(dǎo)語：前段時(shí)間AlphaGo人機(jī)大戰(zhàn)的關(guān)注度很高，希望這個(gè)系列能讓大家對(duì)人工智能和圍棋有更多的了解。

雷鋒網(wǎng)注：本文作者彭博，Blink·稟臨科技聯(lián)合創(chuàng)始人。文章由雷鋒網(wǎng)整理自作者知乎專欄，獲授權(quán)發(fā)布。

一、圍棋 AI 基礎(chǔ)

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

MCTS（蒙特卡洛樹搜索）
CNN （卷積神經(jīng)網(wǎng)絡(luò)，包括：策略網(wǎng)絡(luò) policy network、快速走子網(wǎng)絡(luò) playout network、價(jià)值網(wǎng)絡(luò) value network）
RL （強(qiáng)化學(xué)習(xí)）

現(xiàn)有的圍棋 AI 也都是這個(gè)思路了，我們也會(huì)按這個(gè)思路講。在此先看看圍棋和博弈 AI 的一些基本常識(shí)。

1、首先是圍棋規(guī)則。

圍棋博大精深，但基本規(guī)則很簡潔。推薦這個(gè)在線教程：

第一天圍棋的介紹 - 十天即可掌握！『PANDANET圍棋入門』

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

如果等不及，看完教程的"第一天"內(nèi)容，其實(shí)就可以立刻玩一下了。下圖是純神經(jīng)網(wǎng)絡(luò)走棋，你持黑，電腦持白（因?yàn)楹谄逑茸?，有?yōu)勢(shì)，所以最后要倒貼幾目給白棋，叫做貼目），大家可以點(diǎn)擊打開：

Play Go Against a DCNN

這個(gè)網(wǎng)頁第一次打開會(huì)比較慢，因?yàn)橐虞d一個(gè) 50M 的神經(jīng)網(wǎng)絡(luò)數(shù)據(jù)。

28 天自制你的 AlphaGo（一）

圖中的顏色可以點(diǎn)擊 "Show Analysis" 打開，是神經(jīng)網(wǎng)絡(luò)的最終輸出。越紅的地方，代表神經(jīng)網(wǎng)絡(luò)認(rèn)為越可能成為下一手。你也可以把 "Auto Move" 關(guān)掉，自己和自己下。

試試先按電腦的建議，走在紅的地方，培養(yǎng)一下"感覺"吧！

如果有多個(gè)紅點(diǎn)，可以任選一個(gè)。當(dāng)然，不可迷信，它的紅點(diǎn)時(shí)常是錯(cuò)的，也時(shí)常不全面！

這個(gè)電腦不會(huì)計(jì)算，完全沒有搜索，全部都是靠神經(jīng)網(wǎng)絡(luò)的“感覺”，用圍棋的話說，可以說是按照"定式"和"常型"等等，所以死活弱（就是你可能會(huì)有機(jī)會(huì)把它的棋吃掉?。苓m合新人找感覺。

2、圍棋規(guī)則實(shí)際有很多細(xì)節(jié)，而且并沒有世界統(tǒng)一的規(guī)則。

現(xiàn)有的規(guī)則有中國、韓國、日本、應(yīng)式等等，在大多數(shù)情況下不影響勝負(fù)的判斷結(jié)果，但還是有微妙區(qū)別，比如說中國是數(shù)子，有"粘劫收后"，日韓是數(shù)目，終局有死活的判斷問題。

較為簡潔，適合電腦描述的可能是 Tromp-Taylor 規(guī)則： Tromp-Taylor Rules 。不妨做幾個(gè)調(diào)整：

a. 再簡化一點(diǎn)，去掉"全局禁同形再現(xiàn)"，改成"罕見循環(huán)局面由裁判決定"（畢竟三劫以上循環(huán)的可能性很?。@樣程序就不一定要存一個(gè)每個(gè)局面的hash表。
b. 禁止自殺，這樣更接近其它規(guī)則。
c. 雖然目前看最佳貼目可能更接近 5.5，但還是按中國現(xiàn)有規(guī)則的 7.5 吧，方便大家統(tǒng)一。

目前市面最強(qiáng)的程序是銀星17 和 Zen6，不過價(jià)錢也比較高（雖然都有X版）。而目前免費(fèi)軟件中最強(qiáng)的是 Leela，棋力也還不錯(cuò)，請(qǐng)點(diǎn)擊：chess, audio and misc. software

而且 Leela 有 console 的接口，可以接上目前常用的圍棋 GTP 協(xié)議。如果你有興趣，現(xiàn)在還有一個(gè)電腦圍棋的天梯，可以連進(jìn)去與其它程序?qū)?zhàn)，看自己的排名： 19x19 All Time Ranks 。

3、關(guān)于蒙特卡洛樹搜索

有一個(gè)常見的錯(cuò)誤認(rèn)識(shí)，在此先糾正。

在棋類博弈 AI 中，很多年前最早出現(xiàn)的是蒙特卡洛方法，就是到處隨機(jī)走，然后看哪里的勝率最高。但這有一個(gè)問題，舉個(gè)例子：

a. 如果走在 A，人有100種應(yīng)對(duì)，其中99種，電腦會(huì)立刻贏，只有1種電腦會(huì)立刻輸。
b. 如果走在 B，人有100種應(yīng)對(duì)，但局勢(shì)很復(fù)雜，大家都看不清，如果隨機(jī)走下去，后續(xù)的勝率雙方都是50%。

那么如果計(jì)算蒙特卡洛的勝率，電腦會(huì)發(fā)現(xiàn)走在 A 的勝率是 99%，走在 B 的勝率是 50%。

可是，電腦的正解是應(yīng)該走 B！因?yàn)槿绻吡?A，人如果夠聰明，就一定會(huì)走電腦立刻輸?shù)淖兓?。如果電腦執(zhí)意要走 A，就只能稱之為"騙著"了。

于是有的人會(huì)說蒙特卡洛方法有缺陷。但是，蒙特卡洛樹搜索在理論上解決了這個(gè)問題。

怎么把人想象得盡量聰明？這就要靠博弈樹。蒙特卡洛樹搜索是博弈樹和蒙特卡洛方法的結(jié)合，它不會(huì)犯 A 和 B 的問題，它很快就會(huì)發(fā)現(xiàn) B 比 A 好。容易證明，如果給定足夠的計(jì)算時(shí)間和足夠的存儲(chǔ)空間，蒙特卡洛樹搜索可以收斂到完美的博弈樹，成為圍棋之神。

然而，實(shí)際的計(jì)算和存儲(chǔ)資源是有限的，實(shí)際的 A （不妨稱之為陷阱）也會(huì)更復(fù)雜。比如說：

c. 如果走在 A，經(jīng)過博弈樹的模擬，電腦幾乎是怎么走都怎么贏；但是人更清楚后續(xù)的走法，人會(huì)走出完美的應(yīng)對(duì)，在許多步后電腦一定會(huì)突然死亡。

這時(shí)，電腦要走遍了博弈樹的許多層，才能發(fā)現(xiàn)原來走到 A 會(huì)存在致命缺陷，掉入陷阱。這種情況下，蒙特卡洛樹搜索就容易在 A 和 B 的問題上給出錯(cuò)誤的答案。這有好多種表現(xiàn)，比如說"地平線效應(yīng)"，又像 AlphaGo 被擊中的第 78 手。

圍棋中是有很多陷阱局面的，比如說"大頭鬼"。人工智能如何正確應(yīng)對(duì)陷阱局面，或者避免進(jìn)入陷阱局面？這就需要策略網(wǎng)絡(luò)（policy network）、價(jià)值網(wǎng)絡(luò)（value network）、強(qiáng)化學(xué)習(xí) 的共同作用。在后續(xù)的文章將會(huì)逐步介紹，包括具體的訓(xùn)練方法。

二、安裝 MXNet 搭建深度學(xué)習(xí)環(huán)境

介紹完圍棋 AI 的基本常識(shí)，咱們開始搭建深度學(xué)習(xí)環(huán)境。

目前的環(huán)境很多，最多人用的是 Google 的 TensorFlow；不過 MXNet 感覺也蠻不錯(cuò)，比較省資源（當(dāng)然，最好兩個(gè)都裝）。配圖是 MXNet 的例子里面的 LeNet 訓(xùn)練 MNIST 數(shù)據(jù)集，這是很經(jīng)典的模型，可以看到準(zhǔn)確率在隨著訓(xùn)練不斷提高：

28 天自制你的 AlphaGo（一）

安裝之前先看個(gè)好玩的：github.com/dmlc/mxnet.js 是在瀏覽器直接運(yùn)行 MXNet 的效果。TensorFlow 也有類似的東西： transcranial/keras-js。也就說，我們訓(xùn)練好模型后，可以直接在網(wǎng)頁里面可視化，這樣就可以輕松跨平臺(tái)。

28 天自制你的 AlphaGo（一）

1、Windows的安裝

第一次裝深度學(xué)習(xí)環(huán)境經(jīng)常會(huì)遇到一些坑，這里看一個(gè)實(shí)際安裝 MXNet 的過程。先看 Windows 的安裝，比較簡單和快速，因?yàn)椴恍枰幾g。

說句無關(guān)的，我個(gè)人是推薦 Windows 的，因?yàn)轱@卡還可以用于娛樂（這幾年的新游戲的圖像進(jìn)步很大），有興趣還可以玩?zhèn)€ VR 啥的。

1）首先裝了 VC2015，安裝時(shí)語言記得選上 C++。
2）然后如果你有 nVidia 的 GPU，裝一下 CUDA：CUDA 8.0 Downloads 。選本地安裝版，建議用迅雷下比較快。如果沒有 nVidia 顯卡，買一塊吧，顯存盡量選大的，機(jī)器的電源也記得要跟上。實(shí)在沒錢就二手 750Ti 2G 顯存版吧，足夠玩玩簡單模型，因?yàn)?MXNet 省顯存。當(dāng)然，用 CPU 也可以跑，就是慢。
3）再下載 cuDNN，這個(gè)要注冊(cè)一個(gè)帳號(hào)。注冊(cè)一個(gè)吧： NVIDIA cuDNN 。解壓備用。
4）下載 MXNet 的編譯好的包：github.com/ 先下載 vc14 base package，然后下載更新包（例如 20170114_mxnet_x64_vc14_gpu.7z 注意 GPU 包就是同時(shí)支持 CPU 和 GPU）解壓進(jìn)去，然后把 cuDNN 也解壓進(jìn)去（見它的文檔）。執(zhí)行 setupenv.cmd 。
5）裝個(gè) Python 吧，推薦 Anaconda，選 Python 2.7 的版本： Download Anaconda Now! 。建議用迅雷下比較快。裝完檢驗(yàn)一下 python 命令可用。
6）進(jìn)開始的 MXNet 目錄的 python 子目錄，執(zhí)行 python setup.py install 。會(huì)發(fā)現(xiàn)提示要裝一個(gè) Microsoft Visual C++ Compiler for Python 2.7，去裝了。
7）然后再執(zhí)行 python setup.py install，可能會(huì)發(fā)現(xiàn)提示缺頭文件，把他們從你的 VC2015 的 include 目錄拷貝到 Microsoft Visual C++ Compiler for Python 2.7 的 include 目錄即可。要根據(jù)提示拷貝好幾個(gè)頭文件。然后就可以成功編譯了。
8）運(yùn)行 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 。會(huì)先下載測(cè)試數(shù)據(jù)，等下它，比較慢?？纯词欠癯晒τ?xùn)練。
10）再測(cè)試 VC++ 的環(huán)境。下載 MXNet.cpp （不需要執(zhí)行里面的 setupenv.cmd），然后打開 windows 目錄下面的 vs 下面的 MxnetTestApp，運(yùn)行試試。再試試?yán)锩嬗芯淇梢愿某?Context ctx_dev(DeviceType::kGPU, 0); 會(huì)發(fā)現(xiàn) GPU 確實(shí)比 CPU 快。
11）可以用 CPU-z 和 GPU-z 看你的 CPU 和 GPU 有沒有偷懶，是否是在全心全意工作。

2、Mac 的安裝

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

這個(gè)安裝麻煩一些，因?yàn)槭紫认旅嬗行┫螺d過程可能要 export ALL_PROXY="代理地址"（否則很慢）。另外 pip 也要換國內(nèi)源，git 也要加代理，homebrew 也可以改國內(nèi)源。

然后有時(shí)會(huì)遇到權(quán)限問題，請(qǐng) chown 一下。有時(shí)可能也要 sudo。

1）裝 XCode。最新 CUDA 已經(jīng)兼容 XCode 8 了。
2）裝 CUDA 和 cuDNN。
3）裝 homebrew（百度搜索一下）。裝 python，建議 brew install pyenv 然后用它裝 anaconda2，防止破壞系統(tǒng) python 版本：Mac OS X下安裝pyenv 。

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

4）裝 MXNet： Installing MXNet on OS X (Mac) 按照 Standard installation 走。不要執(zhí)行它的 Quick Installation 自動(dòng)腳本，因?yàn)檫€會(huì)去重新裝 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 一下再試試。