英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料

---

基于ADP与MCTS算法的五子棋

唐振韬，赵冬斌，邵坤，吕乐

中国科学院自动化研究所复杂系统管理与控制国家重点实验室。北京100190

tangzhentao2016@ia.ac.cn，dongbin.zhao@ia.ac.cn，shaokun2014@ia.ac.cn，iamlvle@126.com

摘要

受AlphaGo核心思想的启发，我们将自适应动态规划（ADP）方法训练的神经网络与运用于五子棋的蒙特卡罗树搜索（MCTS）算法相结合。MCTS算法基于蒙特卡罗模拟方法，经过大量模拟并生成游戏搜索树。 我们展开该树并搜索其中叶节点的结果。结果，我们获得了MCTS获胜率。ADP和MCTS方法分别用于估算获胜率。我们对这两个中奖率进行加权，以选择最大一个的作用位置。实验结果表明，该方法可以有效地消除神经网络评价函数的“短视”缺陷。使用我们提出的方法，游戏的最终预测结果更准确，并且它优于基于ADP算法的五子棋。

关键词：自适应动态规划; 蒙特卡洛树搜索;五子棋

一，导言

电脑棋盘游戏长期以来一直是人工智能研究的重点。五子棋是一款受欢迎的双玩家战略棋盘游戏。传统上，我们在15x15交叉的棋盘上用棋子（黑色和白色的石头）玩。获胜者是首先水平，垂直或对角地获得连续五颗棋子的玩家。为了解决这类游戏，一些典型的方法被提了出来，如证明号搜索[1]，基于依赖关系搜索[2]和线程空间搜索[3]。玩五子棋的最经典的算法之一是游戏树搜索，它基于结合了叶子盘面情况的盘面评估函数的min-max树。然而，正如William所说[4]，对n次走子深度的完整搜索需要p！/（p-n）！次盘面评估，其中p是当前合法走子的数量。因此，完全完成一次搜索是一项不可能完成的任务。幸运的是，结合alpha-beta搜索的历史启发式算法已被用于加速游戏树搜索[5]。虽然我们都知道一个算法在游戏树中搜索得越深，它就越有效。这些方法有一个明显的缺陷：时间和空间复杂度随着搜索深度呈指数级增长。换句话说，搜索深度总是成为瓶颈。

为了解决这个问题，我们提出了一种将浅层神经网络与蒙特卡罗模拟相结合的五子棋新算法。使用ADP来训练神经网络并与自己对抗可以为五子棋产生专业的玩家。在训练之后，神经网络可以获得任何可能的棋盘状况的胜利概率。事实上，我们使用神经网络来评估盘面情况，并获得合理数量的候选走子以备选择。然后，我们将这些候选走子作为MCTS的根节点，并尝试将我们的走子预测网络与MCTS进行整合。因此，我们分别从神经网络和MCTS获得两个获胜概率结果。预测的最终获胜概率是加权神经网络和MCTS结果中的最大总和。

剩余论文的组织安排如下：在第二部分，我们讨论了一些使用神经网络或强化学习研究五子棋的相关工作。第三部分简要介绍了MCTS。第四部分详细介绍了MCTS的使用和ADP的实施。第五部分给出了显示ADP与MCTS算法的性能的实验结果以及比较结果。最后，我们提出讨论并总结论文，同时指出未来研究的方向。

二，相关工作

早在20世纪90年代，Freisleben提出了一个神经网络，它有能力学习下五子棋[6]。它的本质是脱胎于一种特殊的强化学习算法，通过奖励或惩罚来训练一个网络，这个算法被称之为比较训练[7]。强化学习是一种新颖的机器学习方法，它涉及软件应该如何在环境中采取行动，以最大化累积奖励的一些概念。强化学习的最具竞争优势在于它不需要关于马尔可夫决策过程（MDP）的知识，并且可以在确切方法变得极其复杂时针对大型MDP运用，如德州扑克[8]和围棋 [9]。此外，强化学习已被用作解释大脑行为选择机制的模型[10]。时序差分（TD）学习主要用于强化学习问题，这是一种基于预测的机器学习方法。Mo[11]和Gong[12]将TD学习算法应用于五子棋。尽管如此，实验结果表明，这种方法适用于五子棋不如TD-Gammon[13]那样有效。

尽管如此，我们认为在TD学习中，行为决策或价值函数也可以用连续的形式来描述，通过神经网络中的非线性函数线来近似。这是自适应动态编程（ADP）的核心思想[14-16]。通过将它与三层完全连接的神经网络进行配对，以提供适应性和自学习行为，已经改进了应用于五子棋的ADP性能。但是，神经网络的输入是按照预定的模式设计的。因此，网络只对那些具有专业知识的游戏有效。而且，它对神经网络评估函数有一个短视的缺陷。

蒙特卡罗树搜索（MCTS）是一种通过在决策空间中进行随机模拟并根据结果构建搜索树来寻找给定域中的最优决策的方法。此外，它在数值算法中有着悠久的历史，并且在诸如Scrabble[17]，Bridge[18]，特别是Go[19]等各种AI游戏中取得了重大成功，如MoGo[20]，ManGO[21]。虽然MCTS也是被推荐运用于五子棋，但它没有像预期的那样取得很好的效果。这主要是因为MCTS需要额外的复杂领域知识才能在较高水平上工作。此外，MCTS必须花费大量的时间进行模拟才能获得满意的结果。

计算机Go计划由DeepMind创建的AlphaGo在与Lee Sedol的五场比赛中赢得4：1，是世界上最好的围棋玩家。根据DeepMind的论文[22]，AlphaGo采用了一种将深度神经网络与蒙特卡洛模拟相结合的新方法来评估电路板状况并选择最佳移动。受其启发，我们将蒙特卡罗树搜索应用到五子棋中，并结合我们以前的工作[23]。因此，我们实际上获得了ADP和MCTS算法的最终胜率。

三，蒙特卡罗树搜索

蒙特卡洛树搜索（MCTS）[24]需要大量的仿真，并根据结果建立一个大型的搜索树。 MCTS的一个重要特征是随着仿真时间和节点访问量的增加，估计值会变得越来越精确。 MCTS的基本过程如图1所示。它由四个主要阶段组成：选择，扩展，模拟和反向传播。

MCTS的基本过程从第一阶段选择阶段开始。在这个阶段，它从根节点开始，递归地应用子选择策略（也称为树策略），通过树下降直到到达最紧急的可扩展节点。然后在扩展阶段，可以根据可用操作添加一个或多个子节点来扩展树。在第三阶段模拟阶段，它可以根据已解决的策略从叶节点运行模拟（或称为默认策略）来产生结果。最后，在后向传播阶段，它可以通过选定的节点将仿真结果传回来更新它们的状态值。

在本文中，我们提出了两种MCTS算法。一个被称为启发式蒙特卡洛树搜索（HMCTS），另一个被称为树的上置信区间（UCT）。基于HMCTS的五子棋算法在算法1中给出。

算法1：基于HMCTS的五子棋算法

输入：原始状态s₀;

输出：对应于MCTS的动作a的最高值;

添加启发式知识;

从状态s₀获得可能的走子M;

For可能走子M中的每一步走子：

奖赏 r_totallarr;0;

当 （模拟时间 lt; 分配时间）：

奖励r larr; 模拟(s(m));

r_total larr; r_total r;

模拟时间加1;

结束当循环

将（m，r_total）加入数据;

结束for循环

返回行动Best(data)

仿真（状态s_t）

如果（状态s_t是赢且s_t是最后一子）则 返回1.0;

否则 返回0.0;

如果（s_t满足启发式知识）

然后 获得强制行动a_f;

新状态s_{t 1}larr;f(s_t,a_f);

否则 选择随机行动a_r isin; 未尝试的动作;

新状态s_{t 1}larr;f(st,ar);

返回 模拟（s_{t 1}）

Best(data)

返回 行动a //从数据中获取m中的最大值r_total

请注意，这里f是一个函数，用于根据上一个盘面状态和动作生成新的盘面状态。对五子棋玩家来说是常识的启发式知识可以比随机抽样节省更多的模拟时间。因此，它有助于结果比以前更早地收敛。规则解释如下：

1. 如果我方产生四子相连，棋手将会将其棋子下在可能产生我方五子相连的位置
2. 如果对方产生四子相连，棋手将被迫将其棋子下在可封锁对面五子相连的位置
3. 如果我方产生三子相连，棋手将会将其棋子下在可能产生我方四子相连的位置
4. 如果对方产生三子相连，棋手将被迫将其棋子下在可封锁对面四子相连的位置

五子棋虽然是像Go一样的零和游戏，但在五子棋中很少会出现平局。事实上，最后的结果通常是赢或者输。因此，当最终结果为赢时，我们将奖励设为1，否则当最终结果为损失或平局时，奖励为0。那么行为的Q值可以代表该行为的预期回报。

(1)

其中N(s,a)是从状态s中选择动作a的次数，N(s)是从状态s中游戏对局的次数，z_i是第i次模拟的结果。如果动作a在第i次对局中被选中，那么l_i(s,a)等于1，否则为0。

另一种广泛使用的MCTS算法是UCT [24]，它基于上置信区间（UCB）。 UCB被称为有能力解决多臂赌徒问题。UCB最明显的优点在于，它有助于平衡勘探和开发之间的冲突，并在早期找出最终结果。其最简单的形式是：

(2)

其中，是第j次模拟的平均奖励，n_j是节点j被访问的次数，n是到目前为止的总次数。 奖励鼓励利用更高的奖励选择，但是右边的公式鼓励探索较少访问的选择。

UCT起源于HMCTS，但与HMCTS的区别在于UCB可以比原始算法更早找出合适的叶节点，因此UCT比原始版本节省更多的时间。

基于UCT的五子棋算法在算法2中给出。

算法2：基于UCT的五子棋算法

输入：创建状态s0的根节点v0;

输出：对应于UCT的最高值动作a;

当 在计算预算内

v_llarr;树策略(v₀);

策略larr;启发式知识;

奖励rlarr;策略(s(v₁));

返回更新(v_l,r);

结束 当

返回行动a(Best Child(v0))

树策略（节点v）

当 v不处于最终状态

如果 v未完全展开，则返回Expand(v);

否则 vlarr;Best Child(v,);

结束当

返回v //这是最好的子节点

展开（节点v）

从A（s（v））中选择未尝试的随机动作a;

添加一个新的子v#39;到v

S(vrsquo;) larr; f(s(v),a)和a(v#39;) larr; a;

返回v#39; //这是扩展节点

Best Child(节点v，参数c)

返回



策略（状态s）

当 s不是最终状态

如果 s满足启发式知识 那么获得强制行动a;

否则 选择随机行为aisin;统一A(s);

slarr;f（s，a）;

结束当

返回 状态s的奖励

返回更新（节点v，奖励r）

当 v不是空的

N(v) larr; N(v) 1;

Q(v) larr; Q(v) r;

vlarr;v的父项;

结束当

这里，v表示具有四个数据的节点：状态s(v)，下一个动作a(v)，总模拟奖励Q(v)，被访问计数N(v)。 v₀是状态s₀对应的根节点，v₁是到达游戏模拟结束的最后一个节点，r是走棋策略达到最终状态的奖励，总体搜索结果为a(Best_Child(v₀))是导致根节点v₀的最佳子节点的动作。

请注意，MCTS需要重复执行足够多的时间以确保预测的准确性。MCTS中最耗时的问题是MCTS必须花费大量时间搜索一些不必要的可行操作（不必要的操作意味着它以低赢率获胜）。

四，用蒙特卡洛树搜索进行自适应动态规划

五子棋中使用的自适应动态规划（ADP）通过时序差分学习（TDL）进行训练，这是一种广泛使用的强化学习算法。 ADP训练结构如图2所示。训练ADP的细节可参见[23]。为了解决我们之前提到的问题，我们试图通过ADP获得候选走子动作。每个从ADP获得的候选走子都应该是MCTS每个进程对应的根节点。换句话说，它不仅确保了搜索的准确性，而且还减少了搜索的宽度。与仅使用MCTS相比，应该节省大量时间以找出适合五子棋的动作。

当前棋盘状态x(t)被前馈给动作选择，它产生控制动作u(t)。在u(t)的作用下，我们得到下一步转移状态x(t 1)，它被前馈到

全文共12095字，剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[15696]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

您可能感兴趣的文章

• 彩色图像中的人脸检测与识别外文翻译资料
• 一种非线性离散奇异大规模控制系统的稳定性外文翻译资料
• 融合领域特定和可训练的特征，用于人脸图像的性别识别外文翻译资料
• ASP. NET概述外文翻译资料
• 基于深度卷积激活特性的地面云分类外文翻译资料
• at89s52单片机简介外文翻译资料
• 实时多手势识别人机交互系统外文翻译资料
• 基于DTW改进算法的语音识别外文翻译资料
• 研究区域自动气象站的后端实时数据质量控制方法外文翻译资料
• 电动汽车的智能前车灯控制器设计外文翻译资料