雷锋网注:本文作者彭博,Blink·禀临科技联合创始人。文章由雷锋网整理自作者知乎专栏,获授权发布。
一、围棋 AI 基础
大家都知道 AlphaGo v13 的三大组件是:
MCTS(蒙特卡洛树搜索)
CNN (卷积神经网络,包括:策略网络 policy network、快速走子网络 playout network、价值网络 value network)
RL (强化学习)
现有的围棋 AI 也都是这个思路了,我们也会按这个思路讲。在此先看看围棋和博弈 AI 的一些基本常识。
1、首先是围棋规则。
围棋博大精深,但基本规则很简洁。推荐这个在线教程:
第一天 围棋的介绍 - 十天即可掌握!『PANDANET围棋入门』
注意,正常来说,黑棋的第 1 手要下到你的右上角,比如说右上角的"星位"或者"小目"。虽然棋盘是对称的,下其它三个角也可以,但这是对弈的一种礼貌,这样下对方就知道你是懂规矩的(当然,也可以第 1 手下在边上,或者中腹,但目前人类一般认为是亏的)。
如果等不及,看完教程的"第一天"内容,其实就可以立刻玩一下了。下图是纯神经网络走棋,你持黑,电脑持白(因为黑棋先走,有优势,所以最后要倒贴几目给白棋,叫做贴目),大家可以点击打开:
Play Go Against a DCNN
这个网页第一次打开会比较慢,因为要加载一个 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 数据集,这是很经典的模型,可以看到准确率在随着训练不断提高:
安装之前先看个好玩的:gi是在浏览器直接运行 MXNet 的效果。TensorFlow 也有类似的东西:transcranial/keras-js。也就说,我们训练好模型后,可以直接在网页里面可视化,这样就可以轻松跨平台。
1、Windows的安装
第一次装深度学习环境经常会遇到一些坑,这里看一个实际安装 MXNet 的过程。先看 Windows 的安装,比较简单和快速,因为不需要编译。
说句无关的,我个人是推荐 Windows 的,因为显卡还可以用于娱乐(这几年的新游戏的图像进步很大),有兴趣还可以玩个 VR 啥的。
1) 首先装了 VC2015,安装时语言记得选上 C++。
2)然后如果你有 nVidia 的 GPU,装一下 CUDA:CUDA 8.0 Downloads
3)再下载 cuDNN,这个要注册一个帐号。注册一个吧: NVIDIA cuDNN
4)下载 MXNet 的编译好的包:gi
5)装个 python 吧,推荐 Anaconda,选 Python 2.7 的版本: Download Anaconda Now!
6)进开始的 MXNet 目录的 python 子目录,执行 python install 。会发现提示要装一个 Microsoft Visual C++ Compiler for Python 2.7,去装了。
7)然后再执行 python install,可能会发现提示缺头文件,把他们从你的 VC2015 的 include 目录拷贝到 Microsoft Visual C++ Compiler for Python 2.7 的 include 目录即可。要根据提示拷贝好几个头文件。然后就可以成功编译了。
8)运行 python,然后 import mxnet 然后 ((2,2), mxnet.cpu)*100).asnumpy然后 ((2,2), mxnet.gpu)*100).asnumpy 如果全部成功,恭喜你,装好了。
9)再下载 dmlc/mxnet
10)再测试 VC++ 的环境。下载 MXNet.cpp
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 服务器即可。
4)装 MXNet: Installing MXNet on OS X
5)按它说的编译(非常慢)。在 con 中加:
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
祝安装成功!在下一篇我们会看看从棋谱提取训练特征。
小作业:
1. 介绍围棋基础的纯神经网络走棋是开源的,请改它的代码,做一个基本的围棋界面,包括吃子、打劫、点目等等基本规则。
2. 请阅读它的论文: 。
3. 请做一个傻瓜版的 策略网络,比如说会做眼,会吃子。可以参考 GnuGO 的 6. Move generation 。
4. 请做一个傻瓜版的 价值网络,比如说可以用"棋子向外辐射影响"的方法。可以参考 GnuGO 的 13. Influence Function 和 Bouzy's 5/21 algorithm 。