AlphaGo Zero

在击败了世界冠军李世石之后,AlphaGo吸引了大量的关注,也证明了人工智能的实力。之后AlphaGo在战胜目前世界排名第一的围棋选手柯杰后退出了职业围棋界。而在2017年,AlphaGo Zero再次出现在nature杂志中,而这一次它更为强大,而且仅用40天就把许多人类上千年积累出来的经验摸索出来,同时还自己发现了不少新的策略。

从零学起

在最近,AlphaGo以一篇题为Matering the game of go without human knowledge的论文重回大家的视线。这一次AlphaGo变得更强了,所需的计算资源也更少,更重要的是,这一次AlphaGo是从零学起。

之前版本的AlphaGo都是先对人类现有的棋谱和棋局进行学习,然后再进行强化学习,以能达到超越人类的水平。而这一次AlphaGo则是从零学起,在仅知道围棋的基本规则的情况下自己摸索,然后到达了围棋界的一个顶峰,所以这一版本的AlphaGo被命名为AlphaGo Zero。

AlphaGo Zero概览

AlphaGo Zero采用了一个深层神经网络\(f_{\theta}\),其中\(\theta\)代表的是神经网络的参数。这个神经网络只接受当前棋盘的下子的情况和其历史,\(s\),作为输入。这个神经网络会返回两个值,一个代表下每一步棋的概率向量\(\boldsymbol{p}\),还有一个评估目前玩家胜率的\(v\),即\((\boldsymbol{p},v)=f_{\theta}(s)\)。而神经网络的训练数据是完全由AlphaGo自己产生的,简单来说就是AlphaGo Zero自己和自己下棋。

而最终决定AlphaGo Zero要下哪一步棋的是蒙特卡洛树搜索(MCTS)。而这一MCTS的特别之处在于其搜索是在神经网络的引导之下进行的。在每一步\(s\),AlphaGo Zero就会执行若干次MCTS,然后返回一个下每一步棋概率向量\(\boldsymbol{\pi}\)。

神经网络的作用就相当于是对棋盘局势的判断,而MCTS则相当于是对棋局之后发展的预测。而两个结合起来则成为了AlphaGo Zero下子的根据。

AlphaGo Zero的先期知识储备

AlphaGo Zero的训练中没有运用到人类的棋谱、棋局等,但是AlphaGo Zero也不是对围棋一无所知的。为了使AlphaGo下棋遵守已有规则,提高训练效果,AlphaGo中是有一定的“知识储备的”。

  • 围棋的规则。也就是哪里可以下子,哪里不可以。
  • 一种叫Tromp–Taylor scoringis的围棋评分方法,以用于对AlphaGo产生的棋局的胜者作判断。
  • 棋盘上当前落子情况,还有一些落子的历史记录。
  • 围棋规则在旋转和镜像中的不变性。这是用来提高训练集的数据的质量的。而且围棋在执子颜色不同时下法也基本相同,AlphaGo Zero训练中也用到了这一点。

AlphaGo Zero关于围棋的知识就只有这么多了。所以说AlphaGo基本上是从对围棋一无所知慢慢摸索的。

MCTS

首先我们说一下起到预判作用的MCTS。

在AlphaGo每一次下棋的时候,它都会构建一棵树。树的每一个结点\(s\),对应着棋盘中的一种落子情况\(a\)。除根节点外,每一个结点都只有一个父结点,而根结点则没有父结点。每一个结点指向其子结点的边都代表在对应的棋局下落子的一种可能,而该边指向的子结点自然就是在那样落子之后所形成的棋局。就是说,\(s, a \rightarrow s’\),在\(s\)中按\(a\)落子后形成\(s’\)。

如果目前棋局为\(s_{t}\),则这棵树的根结点就对应着\(s_{t}\)。在AlphaGo做决策的时候,AlphaGo将会先对这棵树进行一次搜索。树的每一条边都存了4个值,\(\{N (s,a), W(s,a), Q(s,a), P(s,a)\}\),分别对应着该边被访问的次数、动作值总值、平均动作值和先验概率。在对树的搜索的过程中,AlphaGo会对每一条边进行评分,然后选择得分最大的一条边。其评分标准为\(Q(s,a)+U(s,a)\)。也就是说,AlphaGo会选择\( \DeclareMathOperator*{\argmax}{\arg\!\max} a=\underset{a}\argmax(Q(s,a)+U(s,a))\)。而U是根据PUCT算法算得的
$$
U(s,a) = c_{puct}P(s,a)\frac{\sqrt{\sum_{b}N(s,b)}}{1+N(s,a)}
$$
其中的\(c_{puct}\)是一个参数。可以看到在一开始当\(N(s,a)\)相对总的搜索次数,即\(\sum_{b}N(s,b)\),较小的时候,而\(P(s,a)\)又相对较大,AlphaGo就会倾向于选择这些边。也就是说在一开始的时候,AlphaGo会探索那些它觉得会有利于棋局但是又没有被充分探索过的落子位置。而当搜索次数增加之后,\(\frac{\sqrt{\sum_{b}N(s,b)}}{1+N(s,a)}\)会逐渐变小,而AlphaGo会倾向于选取那些动作值\(Q(s,a)\)较大的边。而\(c_{puct}\)的值就决定了要探索到什么时候才让\(Q(s,a)\)的值占整个评分值主导地位,从而可以控制对不同边探索的程度。

当搜索中遇到叶子结点\(s_{L}\)的时候,搜索就会暂停。AlphaGo会将叶子结点展开,即根据能够落子的位置展开出新的结点。指向每个新的结点的边的值将会被初始化,\(\{N(s_{L},a)=​0, W(s_{L},a)=0, Q(s_{L},a)=​0, P(s_{L}, a)=​p_{a}\}\),其中\(p_{a}\)是神经网络给出的选该边的先验概率。而这个叶子节点\(s_{L}\)则会被神经网络评估,得到一个值\(v\)。这里的\(p_{a}\)和\(v\)其实就是之前说过的神经网络的输出,只是\(\boldsymbol{p}\)中的值被分配到了相应的边。等做完这些之后,AlphaGo就会对其搜索过程中所经过的路径上的边的值进行更新。具体步骤是:$$N(s_{t},a_{t})= N(s_{t}, a_{t})+​1,\\
W(s_{t},a_{t})=W(s_{t},a_{t})+v,\\
Q(s_{t},a_{t}) = \frac{W(s_{t},a_{t})}{N(s_{t},a_{t})}$$
就是增加计数器,然后计算平均动作值(也就是搜索中从子树的叶子结点得到的胜率的平均值)。这样,一次MCTS就完成了。AlphaGo每下一步棋要执行1600次MCTS,以对未来局势发展作充分的预测以及对不同策略进行充分的探索。同时1600次MCTS也控制了搜索树的大小,不会让其变得过大。
就如我们所知,围棋是不能通过暴力搜索的方法来解决的。一个原因就是围棋的可能性太大了。如果我们要在搜索树中包含每一种可能的下法,那么整棵搜索树将无比庞大,将拥有数量为天文数字的结点和边。而在可能性比较小的棋类,譬如说棋盘较小的五子棋,我们可以直接用类似MCTS的算法遍历每一种可能,以找到最优的策略。
在执行完搜索之后,AlphaGo就会真正的落子。那1600次MCTS大约需要0.4秒,对应这也就是每一次落子0.4秒的思考时间。选择标准是
$$
\pi(a|s_{0})=(\frac{N(s_{0},a)}{\sum_{b}N(s_{0},b)})^\frac{1}{\tau}
$$
其中\(\tau\)是温度参数,也是用来调节探索程度的。AlphaGo会按\(\pi\)值成比例的选择要下的棋。在AlphaGo自己和自己下棋的时候,前30步棋\(\tau=1\),也就是说每一条边被选的概率和它被探索过的次数是成正比的。这样在开局的时候就能保证棋局有一定的多样性,不总是选那些已有的被探索过很多次的边。在之后,\(\tau\rightarrow0\),就是说,AlphaGo总是会选择那些被探索次数最多的边。因为被探索次数多就意味着其动作值较大,也就意味着在MCTS的探索中这条边被认为是有利于当前玩家的。同时,为了再增加一些对不同策略的探索,在选择落子位置前还会给根结点每条边的先验概率值加一点随机噪声,具体做法是\(P(s,a)=(1-\epsilon)p_{a}+\epsilon\eta\),其中\(\eta\sim Dir(0.03), \epsilon=0.25\)。

神经网络

AlphaGo Zero使用了深层卷积残差网络。其实这是目前在计算机视觉领域表现比较突出的神经网络结构,而DeepMind将整个棋盘以及上面的棋子的位置的信息当作一张照片输入到神经网络当中,利用这一神经网络来提取棋盘上的特征。然后再分别输出落子的概率分布以及预测的胜率。

而这一个神经网络的训练数据是由AlphaGo Zero自己与自己下围棋产生的,每过一段时间就会训练出一个新的网络,然后用表现最好的网络来继续产生数据,以此来不断改进神经网络对棋盘特征的提取和对策略的选择。

神经网络的结构

首先神经网络的输入是19x19x17的图片,\(s_{t}\)。其中19x19中每一个像素对应这棋盘中的一个位置,而剩下的17由三部分组成,都是布尔值(即0,1),\(s_{t}=[X_{t},Y_{t},X_{t-1},Y_{t-1},…,X_{t-7},Y_{t-1},C]\)。\(X_{t}^i=1\)代表在时间\(t\)时在位置\(i\)有黑子,而Y向量则代表的是白子。最后的\(C\)则是代表当前要下子的颜色(1代表要下黑子,0代表要下白子)。简单来说,神经网络的输入是黑白双方最近八步的落子位置,还有当前应下子的是哪一方。接受落子的历史的输入是因为围棋是不允许进行某些重复操作的,我认为也可能能够让神经网络更好的获取当前的围棋局势。而接受落子方作为输入则是因为贴目是不能从棋盘上观察出来的,所以要接受落子方信息来辅助判断。

神经网络输入会先经过一个卷积层,然后经过19或39个带残差的卷积层。之后,神经网络将分为两路。一路经过一个卷积层后接到一个全连接层,然后输出的是\(\boldsymbol{p}\)。\(\boldsymbol{p}\)是一个\(19^2+1=362\)维向量,多出的一维代表放弃落子。另一路则连接到一个卷积层后相继接到两个个全连接层,最后输入到一个非线性函数得到\(v\)。

损失函数为
$$
l = (z-v)^2-\pi^T\log \boldsymbol{p} + c||\theta||^2
$$

合二为一

这一次AlphaGo Zero的神经网络与以往的AlphaGo不同之处在与它只使用了一个神经网络,同时输出策略和胜率,而不是分别给策略和胜率训练一个神经网络。这么做是为了是神经网络能够更好的提取棋盘上一些更加通用的特征,以达到更好的效果。这次改进后的神经网络在预测人类棋手的下子时略输给以前的AlphaGo,但是却能以绝对的优势击败之前所有的旧版本。这一方面说明了改进后的网络确实表现得更加好,而且也间接说明了AlphaGo Zero虽然不如之前精通人类的下棋技巧,但已发现一些优于目前人类策略的套路。

神经网络的训练

AlphaGo Zero会保存每一次棋局的数据。具体来说,即保存\({s_{t}, \pi_{t}, z_{t}}\)。其中\(s_{t}\)和之前一样,代表棋局的信息,\(\pi_{t}\)则是MCTS算出的概率值(在MCTS一节中有说明),\(z_{t}\)则是从当前落子方来看最终的胜者(1为自己胜利,0为对方胜利)。在AlphaGo Zero与自己下棋的过程中,如果胜率低于一定值,或者双方都放弃落子,或者棋盘下满了的时候,一盘棋就结束了,然后通过Tromp–Taylor scoringis,Alpha Go就能判断哪方胜利,继而得到\(z_{t}\)。而神经网络训练的目标是使输出值\((\boldsymbol{p},v)\)接近训练的数据\((\boldsymbol{\pi_{t}}, z_{t})\)。

AlphaGo在与自己下棋的过程中不断产生训练数据,然后它能同时拿这些数据来训练神经网络。每一千个迭代后,神经网络的参数\(\theta_{i}\)会被保存一次。之后这个神经网络将会和目前最好的进行比较。这个新的神经网络\(f_{\theta_{i}}\)按照之前描述过的方式引导MCTS,作为玩家\(\alpha_{\theta_{i}}\);目前最佳的神经网络\(f_{\theta_{*}}\)也按同样的方法作为\(\alpha_{\theta_{*}}\)应战。参数\(\tau\rightarrow0\)。如果\(\alpha_{\theta_{i}}\)在400场比赛后有55%或以上的胜率,那么它将成为新的基准,也将是新的用来产生数据的网络。也就是说新的棋手要有一定优势获胜才能被选为基准,来产生训练数据。这样可以减少一些随机因素的影响。


至此AlphaGo的整体结构基本陈述完成了。这一版本的AlphaGo在不少方面都更为简洁,但是却达到了超乎寻常的效果。这也说明了强化学习的广阔前景。

这一次AlphaGo没有使用人类在该领域的现有的知识,也没有使用人工筛选特征,基本上是从零开始。DeepMind的研究人员认为这意味着机器学习观念需要转变。之前认为只要数据足够多,算法之间的差异可以忽略。然而这一次AlphaGo Zero说明了好的算法可以胜过大量的数据(甚至是专家数据)和人工筛选的特征。这也给机器学习领域打开新的视野,不一定要有大量的数据才能有好的训练效果,好的算法可能可以做得更好。