从基于博弈树与α-β剪枝到使用自对弈强化学习训练的Gobang AI

type

status

date

summary

slug

基于博弈树与α-β剪枝的人机对弈系统

贪心算法 Greedy Algorithm

贪心算法是一种在问题求解过程中，总是做出当前看来最好的选择的算法。在五子棋中，贪心算法通过评估每个空白交叉点的得分，选择得分最高的位置作为AI的落子位置。这种算法的思想是在局部范围内寻找最优解，而不考虑整体最优解。

该算法中贪心策略的选择直观重要。在计算评分时，会遍历每个空白交叉点，并统计其周围八个方向的玩家和AI连成子的数量。根据连子的长度和周围的空白位数量，为每个空白交叉点计算得分。根据得分的高低，选择得分最高的位置作为最优落子点。

在评分规则中，不同长度和周围空白位数量的连子会被赋予不同的加权得分。例如，活四、活三等对棋局的威胁会被赋予较高的得分，以便AI能够更好地判断落子位置。通过修改评分函数中各种棋局的加权值，我们可以调整AI的进攻与保守程度，从而改变其落子策略。

Minimax算法

Minimax算法是一种经典的决策树搜索算法，通常用于零和博弈游戏。该算法的核心思想是在博弈树中搜索并选择最优的决策，以最大化自己的收益同时最小化对手的收益。

在局面确定的双人对弈里，常进行对抗搜索，构建一棵每个节点都为一个确定状态的搜索树。奇数层为己方先手，偶数层为对方先手。搜索树上每个叶子节点都会被赋予一个估值，估值越大代表我方赢面越大。我方追求更大的赢面，而对方会设法降低我方的赢面，体现在搜索树上就是，奇数层节点（我方节点）总是会选择赢面最大的子节点状态，而偶数层（对方节点）总是会选择我方赢面最小的的子节点状态。

博弈树 Game Tree

博弈树是在博弈论中使用的树结构，用于描述两个或多个对手在游戏中可能采取的各种决策和行动。对于五子棋这样的棋类游戏，博弈树可以帮助模拟玩家和AI之间的决策过程。

在博弈树中，每个节点表示游戏的一个状态，每个边表示在游戏中的一个可能的行动或决策。博弈树通常是一个树的结构，其中根节点表示游戏的初始状态，每个节点的子节点表示玩家或对手在该状态下可能采取的行动，直到达到游戏结束的状态。

α-β 剪枝算法

考虑到复杂的五子棋对局会使得博弈树变得异常庞大，我们可以通过alpha-beta剪枝算法对Minimax算法进行优化，在搜索过程中通过剪枝来减少搜索空间，提高搜索效率。

在搜索过程中，维护两个值：alpha和beta，分别表示Max局面和Min局面的最佳选择，可以理解为alpha为最大下界，beta为最小上界。alpha只能在轮到Max局面时更新，beta只能在轮到Min局面时更新。当搜索到一个局面时，如果当前节点的值超出了范围(alpha, beta)之外，则可以剪枝，不再搜索该节点的子节点。当极大层的值超过beta时，剪枝，因为极小层的最佳选择已经不会选择这个节点了；当极小层的值小于alpha时，剪枝，因为极大层的最佳选择已经不会选择这个节点了。通过不断地剪枝，可以在不影响搜索结果的前提下大大减少搜索空间，提高搜索效率。

AlphaGo Zero → Alpha Gobang Zero

谷歌公布的围棋程序AlphaGo Zero在训练过程中没有使用任何人类棋谱，一切从零开始，接下来将从AlphaGo Zero 的基本原理出发，设计并训练一个五子棋机器人。

策略-价值(policy-value)网络

输入

棋盘尺寸：19*19

输入：19*19*17

此处17指（8 + 8 + 1）：

① 8个当前玩家过去的8个落子位置特征平面

② 8个对手过去的8个落子位置特征平面

③ 如果当前玩家使用黑棋，则特征平面值均为1；否则均为0

输出

得到移动概率向量和当前玩家胜率

19 * 19 = 361，向量p的前361维的每一个元素代表在361维棋盘的第i维的落子概率，最后一维代表停一手的概率

即，为在棋盘的某一处落子未来的收益；为在棋盘某一处落子的概率

AlphaGo Zero 模型总体结构

如下图所示，策略-价值网络由 1 个 Convolutional block、19 或 39 个 Residual Block、1 个 Policy Head 和 1 个 Value Head 组成，其中 Policy Head 输出，而 Value Head 输出。

Convolutional block

策略-价值网络的第一块是 Convolitional block，它由 1 个卷积层、1 个批归一化层和 1 个 ReLU 函数组成。由于输入 stst 的维度为 19×19×17，所以卷积层包含 256 个滤波器组，每个组包含 17 个 3×3 大小的滤波器。在卷积过程中，滤波器的步长为 1，同时为了保持输入的宽高不变，需要置 padding 为 1。经过卷积模块、批归一化模块和 ReLU 处理后，Convolutional block 的输出为 19×19×256 的特征图像。

Residual block

为了提升网络的特征提取能力并防止出现梯度消失问题，在卷积层下面堆叠着 19 个或 39 个 Residual block，如下图所示，每个 Residual block 由 2 个组成类似于 Convolutional block 的子模块构成，唯一不同的就是在第二个子模块的非线性激活之前加上了skip connect，使输入与批归一化模块的输出相加再输入 ReLU 函数，最终输出 19×19×256 的特征图像。

skip connect作用： 将输出表述为输入和输入的一个非线性变换的线性叠加 随着网络深度的增加，会导致很多问题，比如：梯度爆炸（梯度呈指数级增长，变的非常大，然后导致网络权重的大幅更新，使网络变得不稳定）、梯度消散（梯度趋近于零，网络权重无法更新或更新的很微小，网络训练再久也不会有效果）；

Policy head

从最后一个残差块输出的特征图像作为 Policy head 的输入，经过 Policy head 内部的卷积层、批归一化层和全连接层的处理之后，得到维度为 19×19+1=362 的移动概率向量。实际上为了计算误差的方便，全连接层后会有一个 log_softmax，得到对数概率。

Value head

最后一个残差块的输出还会输入 Value head 中，与 Policy head 不同的是，Value head 里面有两个全连接层：第一个全连接层将输入映射为 256 维的向量，第二个全连接层再将 256 维的向量变为标量，最后经过函数将这个标量压缩到区间，得到。

Alpha Gobang Zero 网络结构

Alpha Gobang Zero 的策略-价值网络延续了 AlphaGo Zero 的架构，由于算力的限制，对 AlphaGo Zero 的神经网络作出以下修改：

使用19*19的标准棋盘，但是输入只保留当前玩家和对手过去三步的落子记录，去掉了代表当前玩家的颜色特征平面

Convolutional layer 的卷积层的输出维度减少128维；

Residual layer 只有 4 个；

p 的维度是 19×19=361 维，因为五子棋没有停一手的操作；、

Value head 的第一个全连接层将输入向量映射到 128 维，而不是 256 维。

蒙特卡洛树搜索

在 19×19 的棋盘上，要穷举出接下来的所有走法是不太现实的一件事，所以 AlphaGo 系列都使用了蒙特卡洛树搜索（MCTS）算法。

蒙特卡洛树搜索（Monte Carlo Tree Search，MCTS）是一种启发式搜索算法，在传统的树形搜索算法的基础上采用了 蒙特卡洛方法 进行价值评估，从当前状态开始不断进行随机模拟，然后计算出平均回报率作为对当前状态的估计。搜索有选择地进行迭代，根据估计值加深搜索级别的数量。

如下图所示，AlphaGo Zero 的 MCTS 包含四个步骤，分别是：选择、拓展与评估、反向传播和演绎。下面来详细介绍 MCTS 的各过程。

选择

该步骤是从树的根节点出发，递归地调用子节点选择策略向搜索树的下方延伸，直到访问到一个终止节点或者从未访问过的子节点截止。

蒙特卡洛树的每一个节点代表一种棋盘状态（下面使用状态来命名节点），树上的每一个父节点与其所有子节点的边上都存着一些变量：

代表从父节点进行动作后到达子节点的先验概率；

代表对子节点的访问次数；

代表子节点上的累计平均奖赏；

，代表在子节点上应用上限置信区间算法（UCT）得到的值，其中为探索常数，它的值越大，就越有可能探索未被访问或者访问次数较少的子节点；

假设棋盘上当前落子数为，棋盘状态表示为，那么蒙特卡洛树的根节点就对应着这个。

假设我们打算对当前局面进行次蒙特卡洛树搜索，那么每一次搜索都会从根节点出发，根据树策略：进行动作（对应一维棋盘上的一个落点）到达子节点，接着重复上述步骤直至遇到叶节点或者游戏结束为止。

拓展与评估

当我们在选择过程中遇到叶节点时（这个节点对应的游戏还未结束）时，先前介绍的神经网络就可以派上用场了。

我们将叶节点对应的棋盘状态输入策略-价值网络，神经网络对棋局进行评估后得到移动概率向量和当前玩家获胜的胜率。需要指出的是，这里的当前玩家可能不是根节点对应的那个玩家，因为每进行一次选择动作，就会切换一次当前玩家。

反向传播

在拓展与评估步骤中我们得到了叶节点对应的玩家的获胜概率，所谓的反向传播，就是指将这个传播到从根节点到叶节点这一路的所有节点上（不包含叶节点），我们可以使用递归做到这一点。由于这些节点的当前玩家一直在切换，所以将传入递归函数。至此我们完成了一次搜索。

演绎

当我们完成次搜索后，根节点的每个子节点都被访问过若干次了，接下来就根据根节点的各个子节点的访问次数，计算选择动作的概率：

为温度常熟，根据每个节点的来随机选择一种动作并在棋盘上执行。从公式可以看出，温度常熟越小，就越有可能选择最大的那种动作，即越趋近于仅利用，而温度常熟越大，越趋近于进探索。

理解强化学习

AlphaGo Zero中的深度神经网络，使用强化学习算法在自我对弈的过程中进行训练。对于每个棋面s , 使用前一轮得到的神经网络f来指导MCTS

训练Alpha Gobang Zero

自对弈

使用自对弈来生成用于训练的数据，其中每一局的过程都是相同的：

清空棋盘，初始化三个空列表：pi_list、z_list、feature_planes_list，分别用存储在一局中每个动作对应的，这一局的赢家对每一个动作的当前玩家的奖赏值，及这一局中的每个棋盘状态；

将当前的棋盘状态添加到 feature_planes_list 中，并根据执行 500 次蒙特卡洛树搜索，得到和，注意这里的是一个向量，维数 19×19=361，代表所有动作的移动概率。将 π 添加到 pi_list 中；

使用更新棋盘并判断游戏是否结束，如果还未结束回到步骤2，如果结束进行骤4；

根据最后的赢家计算出 z_list 中的每一个元素，计算规则为：赢家与每一个动作的当前玩家相同则为 1，不同为 -1，平局为 0。

由于五子棋具有旋转不变性和镜像对称性，所以将做了旋转变换和水平镜像变换的各个 (feature_planes_list, pi_list,z_list) 添加到 self-play 数据集中，其中 feature_planes_list 中的各 feature_planes 在训练过程中将作为策略-价值网络的输入，pi_list和 z_list 的各元素将作为标签；

结束一局自对弈。

需要指出的是，根据论文中的说法，自对弈前 30 步的温度常数 τ=1，后面的温度常数 τ→0。同时为了增加探索，在拓展步骤中需要给策略-价值网络的输出添加狄利克雷噪声，使得，其中

训练

当 self-play 数据集的长度超过 start_train_size 时，就可以正式开始训练了。训练步骤为：

从数据集中随机抽出大小为 batch_size 的样本集；

将样本集含有的 feature_planes_list 作为一个 mini_batch 输入策略-价值网络，输出维度为 (batch_size, 81) 的批量和维度为 (batch_size, 1) 的批量；

根据损失函数更新神经网络的参数，其中是控制 L2 权重正则化水平的参数；

损失函数为valuehead损失+policyhead损失应该和真实的输赢收益越接近越好，采用 MSE 损失；p应该和真实的概率分布越接近越好，采用 Cross-Entropy 损失

结束一次训练。

优化器使用Adam优化器

学习衰减策略：多步长衰减 MultiStepLR，级随着训练次数的增加一定值，学习率逐渐变小，每次变小new_lr = lr * gamma

Alpha Gobang Zero 的自对弈数据始终由最新的神经网络产生，而在 AlphaGo Zero 中自对弈数据是由历史最佳的策略-价值网络产生的，但这太耗费时间了，而且在Deep Mind 后来在 Nature上发表了一篇论文《Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm》，里面的 Alpha Zero 也只使用最新模型来产生数据。