在国际象棋上复现AlphaZero的设计和失败的心得

柏舟   新冠4年 12-19

#人工智能

2015年以来，DeepMind公司发展了围棋人工智能AlphaGo及其各种演化版本，这些算法取得了一系列令人瞩目的成绩：AlphaGo Lee于2016年战胜李世石，AlphaGo Master于2017年战胜柯洁。之后，DeepMind公司在 2017年又推出了AlphaGo Zero，它不需要人类示例或指导，通过强大的自学能力，在36h后就超越了AlphaGo Lee。

AlphaZero从随机对弈开始训练，在没有先验知识、只知道基本规则的情况下，成为史上最强大的棋类人工智能。它适用于国际象棋、日本将棋、围棋等。AlphaZero凸显了深度强化学习在解决控制决策问题中的广泛适用性。

蒙特卡洛树搜索

AlphaZero基于蒙特卡洛树搜索（Monte Carlo Tree Search）框架。传统MCTS使用蒙特卡洛方法进行随机模拟获取动作的价值，而AlphaZero使用深度神经网络评估局势减少随机搜索计算量，提高动作价值评估的准确性，使用于更大的状态空间计算。

与DQN等方法相比，AlphaZero的框架更适用于稀疏的奖励的任务场景，并能够通过搜索的方式获得更准确的动作价值。

MCTS框架

MCTS树节点记录信息包括：

MCTS算法包含以下行为：

flowchart TD A0["从根节点开始"] -->|"动作选择"| A1["到达一个叶子节点"] --> A2["扩展该叶子节点所有行动"] A2 --> A3["蒙特卡洛方法或深度神经网络采样动作价值"] A3 --> A4["递归更新父节点"] A4 --> Cond{"终止条件？"} --> A0 Cond --> AE["结束"]

动作选择

MCTS会从根节点开始，通过类似多臂赌博机问题中的UCB（upper confidence bound）最优算法确定动作抵达某个尚未完全展开的节点。

\[ a_k=\arg\max_{a}\left(Q(s_k,a)+ c\sqrt\frac{N(s_k,b)}{N(s_k,a)}\right) \]

第1项代表利用，Q（s,a）的值越大，则相应动作越容易被选取；第2项代表探索，动作访问次数N（s,a）越小，则该动作越容易被选择到。$N(s_k,b)$为父节点访问次数，$N(s_k,a)$为当前节点访问次数。

但在AlphaZero中，它的实现如下：

\[ a_k=\arg\max_{a}\left(Q(s_k,a)+ cP(s_k,a)\frac{\sqrt{N(s_k,b)}}{1+N(s_k,a)}\right) \]
\[ c(s_k)=\lg\frac{1 + N (s) + cbase}{c base}   + cinit \]

最初算法会倾向于选择具有高先验概率和低访问次数的动作，随着节点访问次数的增多，它会逐渐倾向于具有高动作价值的动作。在最初的AlphaGo中，先验概率p(s,a)使用监督学习神经网络拟合。AlphaZero还尝试过评估动作价值函数Q(s,a)，虽然胜率更高，但是选择的多样性不如前者，所以没有采用。

但在AlphaZero中，使用联合策略-价值网络。

叶节点扩展

在新扩展的节点处，将它的每个可行动作的统计信息初始化为0。

叶节点评估

叶节点评估步骤估计新叶节点位置 s的动作价值 Q（s, a）即胜率，采用蒙特卡洛随机模拟（playout）得到，从s开始，通过某种策略（如随机策略）进行模拟直到游戏结束。在AlphaZero中，使用基于模式特征的浅层推演策略神经网络拟合策略函数π：p(a|s)。

国际象棋动作空间设计

国际象棋一共有6种棋子：兵、车、马、象、后、王。输入：最近两步局面信息和先手方。将棋盘编码成6x8x8的点集，一共13x8x8的输入。每一层代表一种棋子，+1代表白棋在棋盘上有棋子，-1代表黑棋在棋盘上有棋子。

输出分为两部分：

策略层动作编码设计

输出的策略层大小为7 x 8 x 8，1层棋子选择，6层动作选择。这样设计的原因是因为棋子有多种走法，并且可能走到同一个位置。这个方案比较复杂，但是暂时没有想到更好的方案。

动作可以写成a=(from,to)这样一个有序序列，可以用条件概率表示。

\[ p(a|s) = p(to|from,s) p(from|s) \]

MCTS动作编码

MCTS生成的是一系列动作的概率p(a|s)，需要将其编码成p(from|s),p(to|from,s)。

p(from|s)即选择棋子，它满足：

\[ p(from|s) = \sum_{from}p(a|s) \]

等于动作中起始位置为from的和。

而p(to|from,s)的求法如下：

\[ p(to|from,s) = \frac{p(a|s)}{p(from|s)} \]

网络设计

使用残差卷积神经网络，分为公用层，选择棋子层，选择动作层，局势评估层。

flowchart TD; Input["局势和走子方"] --> A["公用层"]; A --> B["选择棋子层"] & C["选择动作层"] & D["局势评估层"]; B --> C; B & C --> O2["策略"]; D --> O1["走子方胜率"];

共用层：

层名 in out kernel
卷积层 13 64 1
残差卷积层 64 128 5
卷积层 128 256 1

选择棋子层：

层名 in out kernel
残差卷积层 256 128 3
卷积层 128 1 1

softmax输出

选择动作层综合了公用层和选择棋子层的输入：

层名 in out kernel
残差卷积层 256 128 3
卷积层 128 16 1
全连接层 17x64 6x64 输入合并选择棋子

sigmoid输出，理论上动作的概率应该存在约束，但是很难建模。

局势评估层设计使用了图像分类的神经网络的思路，但是效果很差：

层名 in out kernel
残差卷积层 256 512 3
卷积层 512 1024 1
池化层 4 - -
全连接层 1024 - -

tanh输出。

训练

自我对弈和MCTS对弈产生数据。采用模仿学习MCTS的策略训练神经网络。对弈数据包括当前局面棋子分布，走子的概率，对弈结束后会标注每一步局面信息，胜者为1，败者为-1。

损失函数

损失函数包含三部分：棋子、动作选择的损失函数，局势评估的损失函数。

棋子和动作的选择函数用交叉熵表示

\[ H(P,Q) = -\sum_xp(x)log_2q(x) \]

它其实反映了两个概率分布的距离：KL散度定义如下：

\[ D(P||Q)=\sum_xp(x)log_2\frac{P(x)}{Q(x)}=H(P,Q) - H(P) \]

因为H(P)是目标的概率分布，大小不影响，所以将H(P,Q)作为损失函数。

实际计算的损失也是很小的，只有0.18左右。

而局势评估使用MSE评估。按道理来说每步棋会有更细腻的胜负变化，但是标注数据从始自终只有-1，1，0三个数，学习就像噪声一样，神经网络学不会。损失一直在0.86左右降不下来。

因为最近很忙，也不是专门搞这个的，如果还有机会的话会重新设计局势评估的数据生成，比如使用棋子的价值和状态值的衰减。原本这篇文章是想写强化学习和控制的关系，但是发现REINFORCEMENT LEARNING AND OPTIMAL CONTROL这本书，只好以后再写。