深入理解alpha go的方法并应用到中国象棋
Sat, May 05, 2018 in Interesting Python
ps: 本草稿配合 https://github.com/bupticybee/icyChessZero 食用
我训练了两种policy network,一种如alpha-go-zero论文中一样,policy的目标是棋子(from-to)的笛卡尔积,另一种方法是我的一个idea,在这个idea中我把policy network分为两部分,select网络和move网络,一个负责选择要移动的棋子,另一个负责选择棋子移动的位置,但是从表现来看,我给予很大希望的select-move two-stage网络并没有比alpha-go zero的网络表现出色。
单纯policy网络在测试集上的表现:
网络深度 | 准确率 | 备注 |
---|---|---|
3 | 44 | alpha-go-zero version |
5 | 49 | alpha-go-zero version |
6 | 49 | alpha-go-zero version |
20 | 49 | select-move two stage net |
并且我发现在网络层数大于5时,继续加深网络并不会对结果产生更好的作用,对网络结构其实还有一些想法,主要在于提速并且保持精度,有时间也会去做。
一个细节:
在value网络overfit的处理上alpha-go 使用分离value和policy network,并且一局游戏只抽取一个局面的方法避免过拟合,而alpha-go-zero声明将value和policy network合成一个多目标网络,并且减少value网络的权重就可以避免过拟合。我使用了第二种方案。
我在网络上抓抓取了5W多条的人类对弈棋局,作为网络初始权重训练的样本数据。
在预训练policy和value联合网络时遇到问题:
- value目标的mse一直很高,在测试集在0.56左右,对比alpha-go的0.234差别非常大。在分析了一些case之后我认为象棋的棋局在主观上并不像围棋那样好判断优劣势,并且value网络在棋局后期对局势的判断还是很准的。
- 由于中国象棋棋谱多记录以红胜为结果的棋局,value目标对棋局刚开始的局面判定一直偏向红方优势,这与实际情况不符,实际情况开局应该基本均势,应对方案:加入分stage训练,在使用5W条人类对弈棋局时,先训练一个batch的policy目标,然后再训练一个batch的value目标,在训练value目标时,随机交换红黑双方,这样可以让训练的结果更倾向于平衡。
可视化工作
可视化工作是不可避免的,通过matplotlib这样的工具我很轻松的完成了可视化象棋棋谱的工作。
此处应该有图
除了使用matplotlib进行可视化之外,我还使用cbf格式的文件存储自对弈棋谱,cbf的文件格式可以被象棋桥软件读取,非常方便分析自对弈棋局,我还采用gif动画化棋谱,同样为了方便分析。
第一个自对弈网络
使用策略网络自对弈,坏棋很多,经常走出莫名其妙的步子。但是在棋局初期走出的都是比较靠谱的步子,可以理解为初期的布局模型基本都见过,但是一到中后期就面临没见过的棋局,单纯的policy network就不行了。
实现mcts搜索
第一版实现的mcts搜索网络,我采用了alpha-go zero相同的参数,1600次搜索后下一步棋,mcts使用训练的5层的alpha-go-zero version的policy-value多目标网络,首先我让mcts和单纯的policy network进行了29场对局,结果如下:
- one the 29 gameplay between mcts tree and policy network:
Name | win | peace | lose |
---|---|---|---|
MCTS | 24 | 5 | 0 |
policy network | 0 | 5 | 24 |
平的5局都是超出当时的步数限制(100步,为了节省时间)判和的,判和时无一例外都是mcts优势。
然后我使用mtcs进行了几场自对弈
马上遇到的第二个问题是:
mcts搜索的时候经常陷入长将或者长捉的循环出不来,而我又觉得写很多规则太过复杂,于是我一劳永逸的写了一条规则:先同局三现者判负,于是mcts不会再陷入长将或者长捉的怪圈了,但是也和中国象棋的亚洲规则或中国规则跑偏了。
效率
实现了mcts搜索算法后,其效率令人发指,20多秒才能下一步棋
组batch训练
单纯的单线程搜索太慢,采用了alphago-zero类似的异步组batch训练的方法之后,mcts算法走一步仍然需要8~10秒。这里的异步采用了redis + celery的方案,在网络传输上亏掉了很多时间。
另外mcts的算法仍然会有很多坏棋,他已经知道怎么将死人了,但是还是有时候会走出不可理喻的步子,还没到可以和水平正常的人类对弈的地步。
(考虑采用协程是否能进一步减少时间?)
虚拟损失函数
虚拟损失函数我并没有用标准的写法,而是直接在Q+U计算的时候减去一个固定值,结果我写出的第一版带虚拟损失函数的协程版的mcts经常作出不可思议地弱智的举动,送子是家常便饭。。。
于是我静下心来分析了虚拟损失函数和mcts搜索表现好坏的关系:
thread number | virtual loss | time | diff |
---|---|---|---|
1 | - | 100+ | 0 |
16 | 1 | 9.16 | 227 |
32 | 1 | 8.46 | 274 |
32 | 0.5 | 8.33 | 234 |
32 | 0.3 | 8.76 | 217 |
32 | 0.1 | 8.91 | 124 |
32 | 0.05 | 9.55 | 72 |
32 | 0.03 | 9.81 | 57 |
16 | 0.02 | 11.98 | 11 |
32 | 0.02 | 10.25 | 57 |
16 | 0.01 | 19.68 | 4 |
32 | 0.01 | 10.74 | 30 |
32 | 0.001 | 31.17 | 12 |
32 | 0.0 | 27.83 | 10 |
我们没有必要知道diff的具体含义,只需要知道diff是一个代表实际结果和但进程状态下mcts差别的参数,越大代表越不准表格中很明显的可以看出,当虚拟损失太小的时候,时间成本会变大,而当虚拟损失太大的时候,蒙塔卡罗树会变得不准。又是一个trade-off。最后我选择了16协程0.02virtual loss的方案,同时兼顾准确和时间成本。
协程方案
虽然已经对celery方案做了很多优化,但是我认为它还是不够快。于是在redis+celery消息队列来处理单线程的方案上浪费了很多时间后,我根据另一个开源项目实现了一版协程的方案,结果效果很好,而且不像celery的方案中多进程self-play显卡利用率不高的情况。
长将陷阱
在进行了一段时间自对弈后,我在review棋谱的时候发现经常出现长将致胜的现象,但是不同于之前遇到的长将的时候循环出不来,而是红方或者黑方“有意的”让对方被“先同局三现者判负”的规则判负,而先长将的依然是自己,【此处应该有示例棋局】。最后的解决方案是改了策略,改成当同局三现的时候,如果最后一步动的不是将军,那么才判负。
蒙特卡罗树可视化
比如下面这个局面,我400次模拟的mcts居然走出了马九进七的棋,导致车被打掉,局面大劣,
但是想要知道mcts作出判断的依据以及改进的方法,必须要对蒙塔卡洛树进行可视化,然而我灵机一动,脑图的结构不就是树结构吗?如果可以把蒙特卡罗树写成脑图文件,那似乎就可以通过脑图软件直接可视化了?
经过分析,发现可能是mcts步数太少导致的。
闲庭信步的将军
在结解决了长将陷阱不久,我发现自对弈开始生成一种新的“神奇”作和的情况,就是有时即使在局势不均衡时,双方也会一直移动将军,重复相同的局面,而为了解决之前的长将陷阱,我已经制定规则,让同局三现的时候,如果移动将军不判负,于是就这样超出判和步数,而出现和棋的情况。于是又需要制定新规则了,我加入的新规则是如果移动将军的话,重复步数超过5步的步数限制,那么判和棋。
蒙特卡洛树的超参数
蒙特卡洛树的超参数在alpha go zero的论文里描述是使用贝叶斯过程来找的,就是传说中的cut human out of the loop那篇论文的内容。但是我并不打算使用这种方法来寻找优质的超参数。因为需要的计算量很大。
蒙特卡罗树的超参数不多,但仍需要考究的调整。我主要关注了两个参数:
c_puct
这个参数关乎搜索的优先级,是优先探索还是优先评估,我尝试了几组值,并且让不同取值的蒙特卡洛树进行了互相的对弈, 互相对弈的胜率表如下:
c_puct | 1.5 | 5 | 15 |
---|---|---|---|
1.5 | 0.5 | 0.36 | - |
5 | 0.63 | 0.5 | 0.82 |
15 | - | 0.18 | 0.5 |
显然c_puct为5的情况探索-评估达到了一个更好的平衡。
狄利克雷噪声分布参数
狄利克雷分布的参数在alpha go zero中是0.03,然而0.03这个值在象棋中会造成非常极端的分布,即一个数趋近于1,其他的趋近于0,所以说需要调整这个参数使其在中国象棋中达到和围棋中相近的探索程度,围棋开局有大约400个可以走的位置,而中国象棋大约有40个,考虑这个差距,再结合分布实验,我认为0.3对于中国象棋是一个比较合理的参数。
分布式训练
这里的所谓“分布式”并不是指要把一个蒙特卡罗树跑到多台机器上,而仅仅是让多台机器分别产生棋谱,自动拉取最新的权重,然后自动推送棋谱到master,是的,这是一个master-slave的经典分布式集群,因为单台机器即使装备了多块显卡,算力仍然不够,这一部分实现非常简单,就不多描述了。
整体流程就是各个slave会在每盘棋局完成的时候通过http接口推送到master,顺便问一下master有没有新的模型,如果有的话就顺便拿下来加载一下权重。