英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料
中国自动化协会第三十一届青年学术会议
中国武汉 2016年11月11日至13日
基于深度学习的五子棋移动预测
邵坤，赵冬斌，唐振韬，朱圆恒
中国科学院自动化研究所复杂系统管理与控制国家重点实验室
中国北京，100190
Emails:shaokun2014@ia.ac.cn;dongbin.zhao@ia.ac.cn;tangzhentao2016@ia.ac.cn;yuanheng.zhu@ia.ac.cn
摘要-五子棋游戏是人工智能研究的一个长期挑战。随着深度学习的发展，移动预测可以帮助提升棋盘游戏代理的智能，如AlphaGo所证明的那样。根据这个想法，我们通过监督学习训练深度卷积神经网络，以预测专业五子棋玩家从RenjuNet数据集中所做的移动。我们提出了许多具有不同架构和不同超参数的深度神经网络来解决这个问题。只有以棋盘状态作为输入，所提出的深度卷积神经网络才能够识别五子棋的一些特征并选择最可能的下一步动作。最终的神经网络在RenjuNet数据集上实现了约42％的移动预测的准确性，达到了专业五子棋玩家的水平。此外，以移动预测为指导，有望产生和人类水平相当的五子棋智能体。
关键词：五子棋;移动预测;深度学习;深度卷积网络
I.介绍
A.五子棋
五子棋1，也被称为连续五个，是源自古代中国的抽象战略棋盘游戏。一般来说，五子棋使用黑色和白色石头在有15times;15个交叉点的棋盘上进行，如图1所示。在最简单的形式中，黑棋先下，玩家在空交叉点上交替放置自己颜色的石头。要赢得比赛，你必须水平，垂直或对角地获得一排五块石头。
作为人工智能研究的合适试验平台，已经提出了许多关于五子棋的方法。其中，最流行的方法是搜索树。该方法从当前板状态的根节点搜索游戏树。一旦退出具有五行的叶板状态，它将返回移动序列。但是，完整的搜索需要评估p!/（p-n）!板状态，其中p是当前板状态下的合法移动数量，n是深度[1]。由于详尽的搜索是不可行的，Schaeffer提出了历史启发式和alpha-beta搜索来加速游戏树搜索[2]。
另一方面，研究人员尝试使用神经网络来创建高水平五子棋智能体。弗赖斯莱本训练网络使用强化学习进行五子棋对抗并通过奖励好动作和惩罚不良动作来评估棋盘状态[3]。赵应用自适应动态规划与三层全连
赵冬斌也是中国北京中国科学院大学的一员。
这项工作得到了国家自然科学基金（NSFC）的资助，资助号为No.61273136，No.61573353和No.61533017。
1https://en.wikipedia.org/wiki/Gomoku
978-1-5090-4423-8/16/$31.00 copy;2016 IEEE
图1.经过58次移动后，五子棋游戏的位置示例。可以看出白子终于赢了比赛。
接神经网络学习玩五子棋[4]。这种方法可以通过对抗自身来改善五子棋代理的性能。由于神经网络的输入由40个选定模式组成，这种代理的性能很大程度上依赖于特征选择的质量和可用的专业知识。
- 深度学习
深度学习是机器学习的一个新分支，具有多个神经网络层来模拟海量数据中的高级抽象[5]。作为一种表征学习方法，深度学习具有多层次的表征。通过组合大量简单但非线性的模块，深度网络可以将表示与原始输入转换为更高的表示，并学习非常复杂的功能。深度学习正在解决人工智能问题方面取得重大进展。事实证明，它非常擅长发现高维数据中的复杂特征，并有助于解决手工特征提取问题[6]。近年来，各种深度学习架构，如深度全连通神经网络，深度卷积神经网络，深度置信网络和递归神经网络已经应用于计算机视觉[7]，语音识别[8]和自然语言处理[9]等领域。
随着AlphaGo的成功，深度学习成为棋盘游戏人工智能的一种有前途的方法[10]。作为AlphaGo的第一阶段，策略网络经过培训，可以使用监督学习来预测专家级玩家的移动，从而大大缩短搜索范围。受此启发，我们尝试使用深度学习进行移动预测，以改善本文中的五子棋代理智能。
图2. AlphaGo的SL策略网络示例[10]。移动概率直接来自网络，并以百分比表示。
下文的组织安排如下。在第二节中，我们描述了本文中使用的移动预测方法。第三节详细介绍了五子棋移动预测的深度卷积神经网络方法。然后，第四节介绍了不同网络架构和超参数的实验结果，以及一个简短的讨论。最后，我们得出了论文的结论。
II.移动预测
一般来说，人类专家在玩游戏时严重依赖模式识别来选择动作。专家级玩家可以一目了然地获得关于当前棋盘状态的准确判断，而无需估计可能的未来位置。这种机制不同于传统的计算机算法，它模拟了数千种可能的未来动作。因此，使用模式识别对游戏进行移动预测可能是提高游戏代理性能的关键因素。到目前为止，移动预测已成功应用于Go和Hex等棋盘游戏。
- 在Go中移动预测
Go2是一款适合两名玩家的古老棋盘游戏。除了比Gomoku更大的棋盘外，Go的比赛规则也要复杂得多。由于搜索空间较大，棋盘状态评估困难，Go长期以来一直被视为最具挑战性的人工智能经典游戏。
近年来，深度学习的移动预测逐渐应用于Go。2008年，Sutskever应用了一个双层卷积网络来预测Go的运动[11]。使用当前棋盘状态和先前的移动作为输入，它实现了34％的准确度。2014年，Clark采用类似的方法，使用8层卷积神经网络实现44％的移动预测精度[12]。2015年，Maddision通过监督学习训练了一个12层卷积神经网络，网络正确预测了55％的专家动作，相当于一个6人的玩家[13]。同样在2015年，田与他的Darkforest Go计划[14]取得了几乎相同的预测结果。
在2015年底，谷歌成功地解决了Go问题，并在Nature [10]上发表了一篇论文。2016年3月晚
2https://en.wikipedia.org/wiki/Go（游戏）
图3. Hex游戏的例子[15]。黑色想要加入上下，白色想要左右加入，黑色终于赢得比赛。
些时候，AlphaGo以4：1的比分击败了Lee Sedol，并帮助计算机Go首次获得了顶级人类水平。在AlphaGo中，策略网络由13个卷积层和整流器非线性组成，softmax层输出所有合法移动的概率分布，如图2所示。网络通过KGS Go Server的3000万个位置进行训练以最大化在某种状态下选择人类移动的可能性。使用所有48个输入特征，测试精度为57.0％，55.7％仅使用原始棋盘状态和移动历史作为输入，两者都匹配最先进的预测性能。借助策略网络的移动预测，AlphaGo提高了搜索效率并成为了顶级Go游戏专家。
- 以十六进制移动预测
Hex3是两个玩家在13times;13菱形六边形细胞上玩的经典连接棋盘游戏。每个玩家被分配两个板的相对侧和石头颜色。如图3所示，获胜者是第一个将他们的双方连接在一起的连续石块的玩家。规则很简单，Hex有很深的策略和复杂的策略，可以作为人工智能算法的试验台。计算机Hex的先前方法侧重于搜索树方法，但现在也采用深度学习的移动预测。Young通过监督学习训练网络，以预测在位置数据库上产生的移动[15]。该网络由10个卷积层和一个完全连接的输出层组成。移动预测作为深度Q网络的初始化阶段[16]，并帮助neuroHex智能体实现高水平。
C.使用深度学习移动预测
移动预测与深度学习有很深的关系。由于人类专家通常以复杂的非线性方式思考，因此棋盘游戏的目标功能过去非常复杂。此外，目标函数总是不平滑的，因为对位置的微小改变可能会极大地改变最有可能的下一步行动。这些属性使这项学习任务非常具有挑战性，并激励我们尝试深度学习方法，因为深度学习非常适合学习复杂，非平滑的函数[5]。移动预测还提供了测试深度学习游戏人工智能的能力的机会。
III.深度卷积神经网络
在本文中，我们训练一个深度卷积神经网络来预测当前板状态作为输入的下一步移动。在本节中，我们将介绍数据预处理技能，不同的网络架构以及培训过程的详细信息。
A.实验平台
在以下实验中，我们选择Tensorflow和Keras作为进行移动预测研究的实验平台。作为目前最受欢迎的深度学习库，TensorFlow4深入推动了深度学习的发展。它是一个开源软件，最初用于表达机器学习算法，特别是深度学习[17]。自发布以来，越来越多的人使用TensorFlow进行机器学习和深度神经网络研究。此外，为了有效地进行深度学习实验，许多研究开始使用TensorFlow结合Keras。Keras5是一个高度模块化的神经网络库，能够在TensorFlow之上运行。它的开发重点是实现快速实验，尽可能减少从想法延迟到深度学习。
B.数据和预处理
培训数据集来自RenjuNet6。RenjuNet是五子棋游戏的在线数据库，提供图书馆中所有游戏记录的下载服务，供游戏和研究使用。所有的比赛记录和他们的相关信息以XML格式存储，带有renjunet v10 yyyymmdd.rif文件。
在本文中，我们使用renjunet v10 20160517.rif数据集。该数据集包含多达66000个五子棋游戏。对于每个游戏，从几十个到一百多个的移动数量不同。显然，当从不同游戏中提取（状态，动作）对时，它将产生重复数据。为了以有效的方式删除重复的数据，我们使用不同的哈希值迭代每个棋盘图像，该哈希值基于它们的图像灰度值。通过这种方式，我们可以比较哈希值而不是比较图像。因此，每个图像只需要访问一次，从而节省了相当多的时间。在那之后，我们得到1247582总（状态，动作）对。数据集的每个板状态被视为图像，其中标签是该特定状态下的下一个移动。也就是说，每个棋盘状态s被预处理成一组15times;15个特征平面。使用单热编码将特征值拆分为多个二进制值平面，表示交叉点是黑色，白色还是空。地面实况标签存储在与其相关状态的索引匹配的单独阵列中。标签也使用单热编码处理。这样，五子棋移动预测问题成为图像分类问题。给定特定的板配置，深度神经网络架构试图找到最可能的下一步。
4https://www.tensorflow.org/ 5https://keras.io
6http://www.renju.net/downloads/downloads.php
C.建筑
为了获得五子棋移动预测问题的最佳性能，我们尝试了许多不同的网络架构。我们使用多层全卷积神经网络，如图4所示。网络的输入包括15times;15times;3个特征平面，接着是5times; 5个滤波器卷积层。因为五子棋中的获胜策略连续形成5个宝石的模式，我们选择5times;5个第一个过滤器来捕获少于5个连续棋子的特征。以下卷积隐藏层的内核大小为3times;3，该层重复N次。所有卷积隐藏层的步幅均为1，输出为零填充，最高可达15times;15.每个卷积层后面都是整流线性单元（ReLU）非线性，
f (x) = max(0, x), (1)
其中x是ReLU的输入，f（x）是输出。最后的隐藏层卷积1个内核大小为11的过滤器，并应用softmax函数来选择下一个移动。不是使用两个softmax输出层分别预测黑白移动[13]，我们只使用一个softmax层来预测下一步移动。因为在五子棋游戏中，可以根据棋盘状态获得下一个移动颜色。值得注意的是，我们不在深度卷积网络模型中使用池化，因为它们会对之前证明的性能产生负面影响[12]。
与图像分类任务类似，softmax分类器将网络层的输出解释为每个特定移动的日志概率。第i个板位移动的损失函数是
(2)
其中zi 是第i个板位置的softmax层的输入值，在五子棋游戏中m等于225。
D.训练
RenjuNet数据集分为训练集，验证集和测试集。我们有147582个测试数据，其余的1100000个数据用于培训和评估，使用8：2分割。与AlphaGo的异步随机梯度下降优化器不同，我们使用Adam优化器来帮助收敛。Adam实现简单，计算效率高，内存需求少[19]。Adam更新规则如下所示。
(3)
(4)
(5)
目的是基于其梯度dx更新x，其中超参数beta;1 beta;2 eps和alpha;。我们采用Adam超参数的默认值，beta;1 等于0.9，beta;2 等于0.999，eps等于1e 8.学习率alpha;初始化为0.003，m和v的具体初始化方法可以在Kingma的论文中找到[19]。
图4.本文中使用的网络结构。N表示具有3times;3滤波器的卷积层的数量。
在训练之前，我们会将训练数据随机地移动到不同的游戏阶段。这确保了每批包含多样化的板状态，防止网络快速过度拟合并陷入不良的局部最优。对于每个训练步骤，我们从RenjuNet数据集中随机选择一小批样本，并应用Adam更新规则以最大化操作的对数可能性。我们使用glorot uniform函数来初始化卷积层的权重及其偏差。培训过程适用于配备4GHz Intel i7-6700k CPU，Nvidia TitanX GPU和32GB内存的计算机。
表I
不同顶层网络的结果
|
深度 |
完全连接的顶层 |
lt;
全文共11404字，剩余内容已隐藏，支付完成后下载完整资料 资料编号：[2387] |
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
