BakaGo


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下棋的步骤:

  1. 收到STDIN的genmove B命令,解析(go-ai, gtplib)
  2. 派发给对应的engine处理(go-ai)
  3. engine收到解析好的命令,调用libuct,传入当前棋盘状态
  4. libuct传入棋盘,启动多个线程进行MCTS搜索(libuct)
  5. 每个线程先从Root根据Tree Policy(通俗的来说就是有个UCT(node)函数,选取最大的孩子),一路下行,直到走到孩子不满的一个节点。
  6. 如果这个节点之前没有计算过candidate,且被访问超过16次,那么通过socket调用libpolicy-server,其通过CNN计算出当前局面状态下人类最可能下的若干个点,传回libuct,在节点上记录下这些candidate。如果访问不到16次,终止该次搜索。
  7. 之后,选取candidate中最可能的一个,加入ch
  8. 利用libfastrollout评估这个ch对哪一方有利(Q值)。这一步是利用近似随机落子(有一个启发函数)下10盘,然后评估最终状态的情况取平均。然后Back propagation回树根,对黑方Q +=,对白方Q -=
  9. 本次搜索结束。
  10. 在时间到后,选取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,她一直没有出现能让我专心投入在这个项目上