传统的蒙特卡洛树搜索(这里主要指PUCT算法)是一个收敛速度很慢的算法.关于这方面的优化主要集中在搜索层面.本话题希望对蒙特卡洛树节点更新的层面进行较为详细的讨论,并展示这一方面相关的潜力.
我从郑天烁学长的报告里了解了多臂老虎机问题的发展.传统的UCB类算法有如下假设:每个动作节点取得的价值反馈应该服从相同独立分布.这就决定了,如果固定一个动作,获得的价值反馈依次为 Q_1,Q_2,\cdots,Q_n,那么最合理的价值估计值应该是
但出于存储与计算的考虑,在这篇文章中我们主要考虑其等价形式
我在这次报告之前大致就有了这样的印象:蒙特卡洛树是一个收敛得非常慢的算法,但毕竟是一个收敛的算法.那么可以认为 Q_n 的方差应该随着n增大而减小,均值不变(从后面的观点来看,这并不完全正确).
出于这个假设,我修改了 Q_n 的权重.当时先尝试了一个保守的权重
实际使用的是 n\to\infty 时等价的近似算法
这在象棋(不使用神经网络,每个叶节点尝试跑到底作为价值函数,魔改了走法算法可以在两倍于经典走法算法的时间内算出是否有一步杀,2000playouts/step)项目中相对于原更新算法有微弱的优势.
在这个项目中,我同时留下了如下印象:
过于激进了.
问题归结于 \overline{Q}_n=\overline{Q}_{n-1}+\alpha_n(Q_n-\overline{Q}_{n-1}) 中 \alpha_n 的选取
当时我向学长请教了这样的问题:对某个动作列表 \{a_1,\cdots,a_n\},相应地每个动作 a_i 第m次探索的奖励服从分布 N(\mu_i, (\sigma_i^{(m)})^2),当m趋于无穷时,\sigma_i^{(m)} 趋于零,那么我们的悔值是否可以有更好的估计.具体到这个问题,如果动作的价值序列也如此由某个蒙特卡洛树产生,是否会有更好的估计.这是一个递归的问题,我们当时并未解决这一问题.
对这一问题最后一个非本质的改进来自于我对使用蒙特卡洛树解决2048和组合设计问题的尝试.与二元博弈问题不同,这种一元博弈问题的价值均值随着搜索过程的进行在稳定而缓慢的上升.这改变了我对蒙特卡洛树搜索的价值均值的认识.在组合设计问题中,我采用了更激进的更新算法
这比 \alpha_n=\frac{1.5}{n} 在这一问题表现得更好.
对这一问题本质上的改进来自于我在约两周前将这些经验先用在围棋AI上的尝试.最初我尝试 \alpha_n=\frac{(1+\ln(n))}{n},它在5秒一步的计算中表现得很好,但是进一步的测试中表明,当计算量提高到1600visits/step时,先前过度更新的结果反而影响到了搜索的进一步进行.这让我意识到问题的关键或许不在于节点更新得有多快,而是节点更新得有多准,确切地,是让合适的节点拥有合适的更新速率.
我在考虑这样的问题,假定 Q_n 在[-1,1]上随机连续地行走,为了体现行走的概念,以后下标改为t,那么如何用 \overline{Q}_t 合理地追踪 Q_t,这大致就变为了时间序列方面的问题.确切地,认为 Q_{t}=Q_{t-1}+u(t)+b(t)+w(t),其中w(t)是白噪声,u(t)是在探索过程中消去的不确定性,b(t)是神经网络造成的系统误差,我猜测b(t)类似于一个以随机速率旋转的向量.
那么卡尔曼滤波的知识大致可以在这里用起来.唯一的问题是,我们没有白噪声和系统误差的先验估计.虽然这样,但是我们大致可以知道,最优的学习率应该接近于信噪比,确切地说,如果我们采样到某种反映残差的量 x_t,那么最好的学习率大致是
那么我们大致有这样的算法,系统维护状态 \overline{Q},e,d,接受外界输入 Q 其中 e 代表残差均值, d 代表残差的平方平均
初始状态
递推地
下面要明确这个算法中尚有模糊性的参数在这里的选取
f_t 是对学习率的裁剪,蒙特卡洛树搜索有多个节点的依赖关系,需要保证学习率的稳定,且要处理NAN.在本算法中简单选择为 f_t(a)=\max\{a+\frac{1}{t},\frac{1}{\sqrt{t}}\}
e,d 有必要拥有与 \overline{Q} 不同的学习率(最初取 \beta_t=\alpha_t 引起了 \overline{Q} 的强震荡).我们考虑$x_t$为纯粹噪声的情况,此时对 \overline{Q},合适的学习率应该为最保守的 \frac{const}{t}.那么 \beta_t 合适的取法应该是 \beta_t:=\frac{1}{t},在这方面的相关测试表明,对 \beta_t 稍微激进的调整(如 \frac{1+log(1+log(t))}{t})均会降低1600次搜索时的棋力.
这个算法的关键在于 x_t 的选取,直觉上应该采用 Q_t-\overline{Q}_{t-1} ,但是注意到 Q_t 有界,这一算法最终会退化为 \alpha_t=(1+\epsilon)/t ,实际上对棋力的提升并未达到预期.以下的改进版本大多采用 x_t=A(Q_t-\overline{Q}_{t-1}),这里A是一个精心选取的奇函数,起到类似神经网络中激活函数的作用.
一个更好的尝试是 \sqrt[3]{Q_t-\overline{Q}_{t-1}},与 (Q_t-\overline{Q}_{t-1})^3 可以观察到棋力有提升,但尚未达到的我预设的目标(1400visits/step执黑战胜原算法1600visits/step执白).
第一个达到目标的尝试是 x_t:=th(Q_t-\overline{Q}_{t-1}), th作为效果不错的函数是可以解释的.在短期,th(x)\sim x,算法会加速更新持续向一边移动的节点;长期下,如上,短期移动x被平均忽略不计,th(x)\sim x-\frac{x^3}{3},三次项会捕捉这样的特征:移动均值为零,但是向一个方向低频大幅移动,另一个方向高频小幅移动,这往往意味着计算错误.
在对th尚未跑完测试时,我想到了一个大概更好的方案 x_t:=sh(Q_t-\overline{Q}_{t-1}),它拥有与th相同的优点,但是三次项符号相反,这意味着它的短期效应与长期效应方向是相同的,这就意味着,搜索时,用sh会快一拍.测试结果符合预期.
能达到的效果:
- 棋力:可以在1400visits/step下执黑战胜1600visits的KataGo,或600playouts/step下战胜800playouts/step下的KataGo,从胜率曲线来看,实际棋力应该更强,我跑过的测试样例毕竟有限
- 印象:从自对弈的棋谱分析,双方似乎与传统靠算力取胜的印象不同,似乎是用某种手段预言了未来的胜率,并提前按照未来的方向行动.
- 局限性:尝试与绝艺作战,失败.事后的分析认为,适当的提高学习率可以很好地纠正神经网络在局部上的系统误差(复杂局面下可以纠正约10%的胜率误差),但不能纠正网络先验选点分布不均匀造成的全局性的系统误差,这应该通过训练阶段对样本的重采样进行处理.
附: 如果通过自行修改KataGo实现本算法的话有如下注意点:
- BeginSearch函数中有一行recursivelyRecomputeStats(node);记得注释掉.它通过递归地求平均更新所有节点,这会破坏我们通过搜索维护的状态
- 任何试图使用平均后的节点信息更新的行为都应该视为某种噪声,请尽量使用原始未更新的叶节点
- playoutDescend中有两段if语句,表明若边搜索量远小于子节点搜索量则直接返回的优化.这两段代码应该注释掉,它对原版KataGo棋力影响不大,但在这里对学习率引入了极为严重的噪声.
-----------以下为对算法的进一步改进
链接：https://pan.quark.cn/s/5ac2f937e314
提取码：GAEs(30天内有效)
文件夹sqsh的改进思路
激活函数仍然使用sh
简记 a=\frac{e^2}{d}
使用 \alpha_t=\min(\sqrt{a^2+(1/t)^2},\max(\sqrt{\frac{1}{t}},1/e)) 裁剪学习率
新的裁剪函数相当平滑,在测试中表现得很好.这一算法选择了相信MCT的收敛性,允许学习率有更高的上界
.
文件夹rbtasqsh的改进思路
我们考虑两个问题.第一个是 \beta_t=1/t 选取是否合理.另一个是使用大学习率意味着某种预测,是在提前使用未来的价值来做现在的搜索,预测正确会有收益,若预测错误,我们需要多少时间覆盖之前错误的结果.
\beta_t=1/t 的合理性在于,每次搜索,都只在叶节点调用一次神经网络,只在这里产生了信息增量.假定 x_t 确实表达了这一信息增量,采用 \beta_t=1/t 一方面意味着我们使用了无偏差的信噪比,另一方面,这是学习率 \alpha_t 下降得最快的方案,有利于维持系统的稳定.
问题在于,在蒙特卡洛树的活跃分支中,实际上叶节点的价值是接近平衡的.这意味着 x_t 会以一定的速率衰减.
我的想法是,既然 x_t 反映的信息量是对的,只是不服从独立同分布,那么我们可以对 x_t 进行类似信号增幅的操作,使得其接近独立同分布.
我使用的是经验公式 x_t=t\alpha_tA(Q_t-\overline{Q}_{t-1}),这里A取为sh.
以上的修改相对于sqsh会有一定增幅,但并不会太多.
我们接下来要考虑后悔与节拍的问题来讨论实际发生的现象,并给出解决方案.
后悔与节拍实际上是从不同的角度考虑是同一个问题.即若之前的搜索有错误,准备花费多少代价来修正这个错误.节拍从波的角度考虑,后悔从热的角度考虑.
经验公式 x_t=t\alpha_t*A(Q_t-\overline{Q}_{t-1}),存在的问题是,若某个因素导致过量更新,会产生累积的 x_t,此时,若搜索结果想要修正这个值(可能由于发现对方的一个更好应对),那么学习率 \alpha 会迅速下降,因此,由于 x_t 中有系数 \alpha, x_t 需要相当长的时间来重新启动.此时局部的行为类似于解二阶线性方程组,实际胜率曲线图中观测到类似的震荡现象(事实上,sqsh等引擎也存在这一现象)
从物理的角度出发,抑制振动的关键在于提供一个合适的阻尼.从而将波的过程转化为热的过程.具体的思路是当向反方向更新时,维持学习率在一个较高的水平,起到加快后悔的效果.
出于这一点,我重新设计了算法,增加了量m,存储某种意义下,最大偏差的平均值,算法如下
递推地(\beta_t=1/t)
超参数的选取同前.
观测到分析模式中胜率振幅明显减小.对棋谱分析表明,一选率有很大提高.
