BakaGo是作为期末AI作业的一个围棋Bot,由四位小组成员共同开发。主入口是https://github.com/sjtu-ai-go/go-ai
名称来源:AlphaGo -> BetaGo(Github某项目,很弱) -> BataGo(拼写错误) -> BakaGo。
组成部分
因为想自己完全重头造轮子,所以在学期初设计时,将其分拆为几个部分:
- libgo-common: 共用的基础代码(主要是Log)
- libgoboard:棋盘库
- libfastrollout:输入棋盘,输出局面对双方谁更有利
- libuct:主算法库,输入棋盘,输出应下何处
- libpolicy-train:训练CNN
- libpolicy-server:CNN Server,接受Feature,返回Policy network对下在每一个点概率的评估
- libpolicy-grpc:原先准备采用gRPC作为main prog和CNN Server通信机制,但最后实际是存储.proto文件
此外,还依赖了一些第三方库:
- googletest, 单元测试
- spdlog,log
- Boost,主要是Program options
- gtplib,gtp协议处理
大部分依赖关系在下图中已被包含:
在项目管理中,尝试使用了CMakeLists.txt + git submodule方式进行管理,但遇到了不少问题,在之后会写一下。
做了什么
看一下我们AI下棋的步骤:
- 收到STDIN的genmove B命令,解析(go-ai, gtplib)
- 派发给对应的engine处理(go-ai)
- engine收到解析好的命令,调用libuct,传入当前棋盘状态
- libuct传入棋盘,启动多个线程进行MCTS搜索(libuct)
- 每个线程先从Root根据Tree Policy(通俗的来说就是有个UCT(node)函数,选取最大的孩子),一路下行,直到走到孩子不满的一个节点。
- 如果这个节点之前没有计算过candidate,且被访问超过16次,那么通过socket调用libpolicy-server,其通过CNN计算出当前局面状态下人类最可能下的若干个点,传回libuct,在节点上记录下这些candidate。如果访问不到16次,终止该次搜索。
- 之后,选取candidate中最可能的一个,加入ch
- 利用libfastrollout评估这个ch对哪一方有利(Q值)。这一步是利用近似随机落子(有一个启发函数)下10盘,然后评估最终状态的情况取平均。然后Back propagation回树根,对黑方Q +=,对白方Q -=
- 本次搜索结束。
- 在时间到后,选取Visit次数最大的一个根的孩子作为下的位置。
文章列表
下面列了一些我觉得比较重要的论文/资料,但因为我没有做NN这块,所以这方面的文献列的很少:
A Survey of Monte Carlo Tree Search Methods,我看到的讲Monto Carlo Tree Search(MCTS)及其最好的一篇文章,非常易懂
Mastering the Game of Go with Deep Neural Networks and
Tree Search,AlphaGo的文章
BETTER COMPUTER GO PLAYER WITH NEURAL NET –
WORK AND LONG-TERM PREDICTION,DarkForest的文章,虽然有代码但是很不推荐读
https://github.com/pasky/pachi pachi的代码,在非NN情况下可以说是非常强的,注意其用的Pattern matching和局面评估部分
http://keras-cn.readthedocs.io/en/latest/ Keras文档,我们用了这个NN前端。
效果
目前我们的模型主要优势在于选取Tree Policy扩展节点时,前期libpolicy-server的CNN能够给我们优质的初始点,所以大局上来看比较强。弱势主要在于:
- fastrollout是随机下子,效果差
- 最终评估盘面优劣没有实现完整的点目机制
- CNN对局部状态的判断较差,容易在复杂互杀局面中被采用Pattern matching的bot整波带走
经过初步的测试,我们的程序在单机上(i7 4710HQ, 850M)对DarkForest、GnuGo有很高的胜率;在服务器上(E5-2670,25线程,K8)对Pachi有一定胜率。
怎么做的
NN
特征
(boardsize - 1)
stone color
our-bool - 2
oppo-bool - 3
empty-bool - 4
turns since
1 to >=8-bool x 8 - 5-12
liberties (our)
1 to >=4-bool x 4 - 13-16
liberties (oppo)
1 to >=4-bool x 4 - 17-20
capture size
1 to >=8-bool x 8 - 21-28
self atari
1 to >=8-bool x 8 - 29-36
sensibleness
not fill own eyes - 37
ko
illegal move Ko-bool - 38
border
bool - 39
position
exp(-0.5xdistance^2)-real- 40
数据集
https://www.u-go.net/gamerecords/
6d以上人类棋手的训练集
Arch
具体之后整理
效果
Val accu~=0.5
MCTS
UCT
Candidate Selection
选择CNN返回的点中从大到小conf accu >= ACCUM_THRES的前若干个,且至少选取一个。按conf从大到小排序
Expand node selection
从大到小选取。直到Ch数达到上限32。
Tree Policy
选取UCT最高的,且fastrollout计算完成的点
工程问题
- git submodule带来了大量的冗余依赖:A -> B, C -> A, C -> B,就会有C/A/B和C/B两个B的副本。很麻烦。后期将所有依赖的第三方库的东西fork了,清除历史以减小体积
- Python Protobuf是Python native的,非常慢,慎用
- 完善的单元测试很有必要,但前期测试常常赶不上代码的变化
- 自动化测试强烈建议上docker……不然最后纠结环境非常麻烦
- Valgrant在windows下开发和统一环境很有用
- coredump调试工具:-fsanitize=address,undefined -fstack-protector-strong,valgrind,kbd。
- 性能测试:callgrind,kcachegrind,trace。
- Python性能测试cProfile
- 性能瓶颈难以被预估,只有profiling才能发现问题
- log很重要,分层log更重要
- 开发环境不同带来的成本很高
- CLion变得越来越好,从beta用到2016.3.2基本没有bug了
致谢
感谢@hjhhh3000 在libgoboard,fastrollout上利用他的围棋知识加入的大量启发式代码,以及提供的服务器资源
感谢@winterandchaiyun和@elicassion 在NN上做的主要贡献,没有他们凌晨训练网络,这个bot不可能达到现在这个强度
感谢其他同学在这个项目上的努力,没有他们我们不会认真修改增强代码
最后还要感谢我的GF,她一直没有出现能让我专心投入在这个项目上