毕业论文

基于深度强化学习的五子棋AI

作者:论文空间  栏目:计算机论文     更新时间:2019-12-02 08:59   浏览

 
  摘要:本设计实现了一个基于深度强化学习算法的五子棋 AI。它的结构与 AlphaGo Zero、AlphaZero 相似,是一个通用的 AI 系统,只需要实现少量接口就能够被应用在其它游戏中。它不需要人工提取的特征,它的输入完全来自于原始棋盘。它也不用任何人类棋谱进行指导,完全通过自我对弈来学会如何下棋。本文中还介绍了如何通过云计算来加速 AI 的训练过程。
  关键词:人工智能;深度强化学习;强化学习;深度学习;五子棋
  第 1 章 绪论
  第 1.1 节 引言
  随着近几年来人工智能的发展,特别是深度学习领域取得的重大突破,人工智能技术的应用已经渗入到人们生活的方方面面。在 2017 年,政府工作报告明确提出要加快人工智能技术的研发和转化,做大做强产业集群。这是人工智能第一次被写入政府工作报告,表明了国家对人工智能这一新兴产业的重视。而在 2018 年的政府工作报告中,再次出现以人工智能为核心的重点内容。这两次被写入政府工作报告,足以说明国家对这一新兴产业的看好,人工智能已被提到了一个更重要的战略高度。
  第 1.2 节 深度强化学习
  深度强化学习(Deep Reinforcement Learning, DRL)是目前人工智能领域最新的前沿研究热点之一。
  2015 年 10 月,AlphaGo Fan 以 5:0 战胜职业棋手樊麾,这是围棋历史上第一次出现人工智能战胜职业棋手,而在这之前还被认为是不可能的。2016 年 3 月份,DeepMind 公司的AlphaGo Lee 以 4:1 战胜了围棋世界冠军李世乭九段,这是人工智能的里程碑式的胜利。而在那之后, DeepMind 又相继推出了 AlphaGo Master、AlphaGo Zero、AlphaZero。其中 AlphaGo Zero 和AlphaZero 与之前的所有版本都有着一个重大的不同——它不再需要人类棋谱做监督学习,也不需要人工提取的特征。这两个 Zero 版本都是在给定了游戏规则之后,完全通过自我对弈学会下棋。
  AlphaZero 与AlphaGo Zero 的区别在于前者是后者的通用版本,AlphaZero 不再仅限于围棋。 DeepMind 在论文[2]中,用AlphaZero 完全通过自我对弈学习4 个小时后超过国际象棋AI Stockfish, 不到 2 个小时的时间内超过了将棋 AI Elmo,八小时后超过 AlphaGo Lee。这些成绩足以说明AlphaZero 强大的通用性。
  不过论文中没有提到 AlphaZero 在五子棋上的效果。不使用现代规则的五子棋是一个已经被解决的问题。1992 年Victor Allis 编程证明了无禁手的五子棋是先手必胜的,2001 年Janos Wagner 证明了带禁手的五子棋也是先手必胜的。
  但五子棋仍然是一个很好的人工智能实验场。比起其它棋类,五子棋有着广泛的知名度,规则非常简单,易于实现。最重要的是,它可以灵活的改变棋局大小(如改为 9x9 棋盘上的五子棋) 和获胜所需要的连珠数目(如 3x3 棋盘上的三子棋即井字棋、Tic-Tac-Toe)。这种灵活改变棋盘复杂度的特点对AI 的实验开发,特别是基于深度强化学习的 AI 来说非常重要。因为在完整的棋盘上进行实验(如五子棋 15x15、围棋 19x19),对于个人电脑来说成本实在是过高,很可能一天下来也完成不了多少盘自我对弈,训练时所需要的(内存、显存)也让人无法接受。而将棋盘缩小后,比如缩小成井字棋,则很快就能训练至收敛。并且,由于 AlphaZero 强大的通用性,我们只要遵循一个良好的模块化的设计,就可以在五子棋上实现和验证它的算法后无缝地迁移到其它游戏中去。
  出于以上的考虑,并权衡了“要有足够的复杂度”和“可以在合理时间内看到效果”之后,
  决定选择在 9x9 的棋盘上实现一个与 AlphaZero 结构相似的基于深度强化学习的五子棋AI。
  第 1.3 节 深度学习框架的选择
  深度学习有着许多框架,常见的框架有 Google 的 TensorFlow,Facebook 的 Torch,Amazon 的 MXNET,微软的 CNTK 等。不同的框架有着不同的学习成本和开发效率,选择一个优秀的框架能节约很多的时间和精力。
  1. 最初的选择:Low-level TensorFlow API
  出于想要了解TensorFlow 底层工作原理的考虑,在第一个版本深度神经网络的实现当中我使用了 TensorFlow 的底层 API。这种做法需要手工管理底层的 Tensor 和 Session,细节繁多,容易出错,在调试神经网络结构的过程中花费了大量的时间。在完成了了解底层工作原理的目标后决定用高级API 重新实现神经网络。
  2. 错误的选择:tf.estimator
  tf.estimator 是 TensorFlow 提供的一个高级API。它通过自定义模型函数对预测、训练、评估的过程进行了封装,能够在训练的过程中自动加载和存储模型。在花费了不少时间的学习研究后, 第二个版本的深度神经网络改为了 tf.estimator 实现。进行了一段时间的实验后发现,使用tf.estimator 是个错误选择。它的API 非常不符合直觉,文档混乱,与之配套的还有一些用于数据操作的库同样增加了学习成本。总体来看 tf.estimator 所引入的复杂性超过了它所简化的工作带来的好处,没有完成选择它时想达到的目标。
  3. 最佳的选择:Keras
  Keras 是一个用 Python 编写的高级神经网络 API,可以运行在 TensorFlow, CNTK 和 Theano 之上。与那些面向机器设计的底层 API 不同,Keras 的 API 设计是面向开发者的,有着非常优秀的用户体验,易学易用,整体模块性好,可拓展性强。使用 Keras 完成的第三个版本的神经网络所使用的代码行数比起前两个版本几乎要少了一半,可读性也高了很多。
  4. 潜在的优秀选择:PyTorch
  PyTorch 是 Facebook 开源的一个深度学习框架,它有着简明、直观又非常灵活的API。截止至目前 2018 年 5 月份,PyTorch 还处于beta 阶段(版本号 0.4.0),不过官方将在接下来的几个月中发布 1.0.0 版本。因为在完成本次设计时 PyTorch 的版本(0.3.0)支持的操作系统有限,本次设计中并没有用PyTorch 实现的深度神经网络版本,但这不失为一个优秀的选择。
  第 2 章 算法的设计与结构
  第 2.1 节 AI 整体结构
  本设计中 AI 所使用的算法为深度神经网络指导下的蒙特卡洛树搜索[1]。这种算法使用深度神经网络代替了传统蒙特卡洛树搜索中的模拟步骤,直接通过神经网络评估得出局面估值 v,并且在搜索时用神经网络输出的落子概率P 作为指导。
  算法中的神经网络通过一种新型的强化学习的方法进行训练。不需要人类棋谱作为指导,直接通过自我对弈获取训练数据来训练神经网络,训练好的神经网络与蒙特卡洛树搜索配合产生更强的棋力,生成更好的自我对弈数据,再用于神经网络的训练。在这个不断迭代训练的过程中, AI 的棋力将不断提高。
  为了加速 AI 的训练过程,设计中还使用了传统的五子棋 AI 算法中的威胁空间的概念让 AI
  能够更快理解游戏目标,并使用多线程并发提升了蒙特卡洛树搜索的效率。
  第 2.2 节 传统的蒙特卡洛树搜索
  蒙特卡洛树搜索(Monte Carlo tree search, MCTS)是一种启发式搜索算法,通常在博弈游戏中被用于寻找最有可能获胜的行动。这种算法通过多次随机模拟来拓展搜索树,每次模拟使用随机策略进行到游戏结束。游戏结束后得到的胜负结果将作为节点的权重,使得之后的搜索更可能选择到那些好的节点。
  如图所示,每轮蒙特卡洛树搜索由四步组成:
  1. 选择:从根节点R 开始不断向下选择最优的子节点直到达到一个叶子节点 L。
  2. 展开:除非选中的叶子节点 L 已经分出胜负,否则创建所有可行的新节点,并选中其中的一个最优新节点C。
  3. 模拟:从新节点C 开始执行一次随机模拟。
  4. 反向传播:将随机模拟的结果从新节点C 不断向上更新直到达到根节点 R。
  选择新节点的方法有很多,传统的蒙特卡洛树搜索会在达到叶子节点创建出所有可行的新节点后,对每个节点进行k 次模拟,然后挑选其中胜率最高的节点。如果有多个节点胜率相同,则从中随机挑选一个。
  为了平衡高胜率节点的探索深度和模拟次数少的节点的探索广度,我们可以使用一种被称作UCT(Upper Confidence Bound 1 applied to trees)的算法来挑选最优子节点。UCT 算法基于UCB1 公式,挑选使得该公式值最大的节点:其中?i为执行第 i 个行动后的节点在模拟中获胜的次数;?i为执行第 i 个行动后的节点进行过的总模拟次数;?i当前局面进行过的总模拟次数;c 为探索常数,理论值为√2,实际中可凭经验选取。
  第 2.3 节 蒙特卡洛树搜索+深度神经网络
  深度神经网络指导的蒙特卡洛树搜索树与传统的蒙特卡洛树搜索相比主要有两处改进:
  1. 使用神经网络输出的局面估值替代了进行随机模拟得到的胜率估计。
  2. 使用神经网络输出的落子概率对搜索进行指导。
  在实现中,每个蒙特卡洛树的节点都保存了当前局面信息 B、当前局面估值 v、每个子节点的落子概率P、每个子节点的总行动价值W、每个子节点的平均行动价值Q、每个子节点的访问次数N、总访问次数total_visit。在选择最优子节点时使用了PUCT[6]算法的变种:
  选取使得Q + U 最大的子节点。注意公式中的 W、N、Q、P 为形状相同的向量,运算为对应位置运算。?PUCT为探索常数,取理论值√2。
  如图,每一轮搜索流程如下:
  1. 选择:从当前局面开始(若当前局面还未被神经网络求值则先进行求值),根据上述公式不断选择使得Q + U 最大的子节点,直到达到叶节点。
  2. 展开和评估:选择使得Q + U 最大的行动,得到新局面B。若新局面B 尚未分出胜负,则将 B 输入神经网络求得落子概率 P 和局面估值 v,若新局面 B 已分出胜负, 则令落子概率 P 为全 0,局面估值 v 为-1 负或 0 平(因为面临终止局面的玩家要么输要么平)。创建新的子节点,并将 B、P、v 和初始化为 0 的W、Q、N、total_visit 保存在该节点。
  3. 向上更新:将该新子节点的局面估值不断向父节点传播并更新父节点信息直到到达根节点。例如:父节点 F 获得执行行动a 后到达的子节点C 传播上来的局面估值 v, 则父节点F 的信息更新如下:
  在算法选出当前最佳行动之前,通常会进行多次这样的探索。探索次数越多,蒙特卡洛树就越枝繁叶茂,整个搜索算法对局面的判断就越全面越准确。我们可以把进行过这样的探索的次数作为衡量搜索力度的指标。
  第 2.4 节 PUCT 算法的直观理解和解释
  上述的蒙特卡洛树搜索+深度神经网络的算法中使用了 PUCT 算法的一个变种。这种算法同时利用了深度神经网络对局面评估得到的先验落子概率和当前局面已有的探索情况来决定下一步应该探索的节点。为了得到这个节点,算法需要求出平均局面估值 Q 和探索价值U,再计算 Q 与U 的和,选择使得Q + U 最大的子节点作为下一步探索的节点。的增长速度比N 要慢得多。在对同一个节点进行大量访问之后,√?????_?????与 N 的比值会不断减小,从而 U 的值变小,抑制探索。对于那些访问次数少的节点,√?????_?????增加, N 保持一个较小的数,使得U 值升高,鼓励探索。
  注意到Q 是局面估值v 的平均,v 的值属于[-1, 1],所以 Q 的值也在[-1, 1]。而通常来说 U 的值在探索次数 N 不是很大的时候对 Q + U 的大小影响还是不低的,所以在探索初期探索价值 U 有着比较大的影响力。但在搜索次数N 高了以后,U 值会越来越小,这时候 Q + U 的值又主要取决于 Q。这样看来,PUCT 算法挑选最优子节点的方法可以概括地表述为:在搜索初期,倾向于搜索那些先验落子概率高、访问次数少的节点,而在进行了足够的探索之后,算法倾向于搜索那些行动价值更高的节点。
  综上我们可以看出,这种算法很好的调控了搜索过程中的深度和广度,避免在还未对局面有一个较为完整的了解时就局限在几个高平均行动估值的节点。而且当一个节点被充分探索过后, 是否挑选该节点将主要取决于节点自身的好坏。
  这种做法也符合人类直觉:刚开始考虑一个局面时,我们应该考虑那些我们认为更可能落子
  的位置,即使在发现一两步棋能有不错的效果之后也不局限在那,同时为了不遗漏那些出人意料的招法,我们也会去考虑那些我们较少思考过的落子位置。当对局面有了一个比较完整的探索和认知后,我们会更多的考虑那些更有可能使我们走向胜利的落子位置。
  第 2.5 节 深度神经网络结构
  本文中所使用的神经网络结构与AlphaGo Zero 基本相同,在规模上有了大幅度缩小。AlphaGo Zero 有两个分别使用 19 个和 39 个残差块的版本。但对于普通的计算机来说,由于显存和显卡
  计算能力的限制,即使仅使用 19 个残差块也是难以接受的。为了能够在个人计算机上进行实验,
  本设计中选择使用 3 个残差块作为代替。
  模型的输入为M x N x k 的多维数组(数据为 channel last 格式),其中 M x N 为棋盘大小,在本设计中取M=N=9,k=2 的设定。其中 k=2 为两个 0-1 平面的叠加,第一个平面代表当前玩家的落子情况,第二个平面代表对手的落子情况。
  模型的输入将经过 1 个卷积块和 3 个残差块处理,之后分别输出到策略头 P(policy head) 和价值头v(value head)得到最终的估值。它们的结构分别如下:
  第 2.6 节 深度神经网络的训练方法
  为了训练深度神经网络,我们需要为它定义一个损失函数。对于策略头来说,输出是一个概率分布,我们可以采用交叉熵作为它的损失函数。对于价值头来说,输出是一个[-1, 1]之间的数值,我们使用均方差作为损失函数。同时为了避免神经网络过拟合,还要为神经网络中可训练的参数添加一个L2 正则项一同计算在损失函数中。
  有了合适的损失函数之后,我们还需要有训练数据和对应的训练目标。深度神经网络以编码后的棋局局面作为输入,所以我们需要用棋局局面作为训练数据,这很容易,只要把对局中经过的局面进行合适的编码就可以了。而深度神经网络的输出有两个,局面估值v 和落子概率P。
  局面估值v 是对局面输赢的一个评估,它将赢、平、输对应到 1、0、-1 上,然后把评估的过程当作是一个回归问题来考虑。对于这个,我们可以使用对局真实的胜负情况作为局面输赢的一个抽样来给神经网络当训练目标。
  落子概率P 的目标比较难找,但是考虑到蒙特卡洛树搜索中越好的节点越容易被探索到,被访问的次数也越多,或者反过来,被访问次数多的节点更可能是好的节点,这么想,将每个子节点的访问次数与总访问次数的比值得出的概率作为落子概率P 的训练目标就是自然而然的了。
  所以,我们可以将一局完整游戏中经历过的局面和它对应的蒙特卡罗树节点保存起来。对于每个局面,经由独热编码(One-Hot Encoding)编码为两个平面,第一个平面为当前玩家的落子情况(有当前玩家的落子的位置编码为 1,其它为 0),第二个平面为对手的落子情况(有对手落子的位置编码为 1,其它为 0),将两个平面叠加起来,作为神经网络的训练数据。相应的,每个局面所对应的蒙特卡洛树节点中可以找到每个落子位置的访问次数和当前局面总访问次数,将它们的比值作为落子概率P 的训练目标,再把这局游戏的胜负情况对应到每个玩家的局面上,作为局面估值v 的训练目标。
  因为通过深度神经网络指导下的蒙特卡洛树搜索得到的探索情况算出的各个位置上的落子概率,一般来说比单用深度神经网络得到的对局面各个位置的落子概率要好,所以在经过训练后的神经网络能够输出更好的落子概率,而且大量的局面经验能让神经网络学会判断哪些局面更可能获胜,也就是输出更好的局面估值。更好的落子概率和更好的局面估值加起来就是更强的棋力, 更强的棋力就能够生成更好的自我对弈数据,这些数据又能训练出更好的神经网络,从而 AI 的棋力会在迭代训练的过程中不断增强。
  第 2.7 节 通过并发搜索提高 GPU 利用率
  蒙特卡洛树搜索实际上是一种串行算法,因为在搜索过程中的挑选最优子节点需要依赖前次搜索得到的平均行动价值Q 和探索价值U,每一次对叶节点的展开后的向上更新都会影响之后搜索时对最优子节点的挑选。
  在整个蒙特卡洛树搜索过程中最耗时的步骤就是对局面的评估。为了得到落子概率P 和局面估值v,我们需要将编码后的局面输入到深度神经网络中进行大量的运算。这个运算过程,被称为前向传播,需要消耗大量的时间,是整个算法中最大的性能瓶颈。为了加速这个过程,现 代的深度学习框架通常会把神经网络的计算放在GPU 上进行,一般来说会比使用CPU 进行计算要快得多。
  但这还不够,GPU 最擅长的是并行处理大规模数据,一次仅处理一个局面的输入完全无法充分利用它的并行处理能力。如果每次都要等到当前搜索到的叶节点展开、评估、向上更新之后才能进行下一次搜索,对 CPU 和GPU 的资源都是很大的浪费(搜索过程发生在CPU 上)
  为了解决这个问题,我们考虑对蒙特卡洛树搜索算法做一个并行化改造。我们可以使用线程池或进程池来并发地进行蒙特卡洛树搜索。
  从根节点开始,多个线程/进程同时开始执行选择步骤。为了鼓励每个线程/进程搜索不同的节点,当一个节点的子节点被选中时,我们在这个节点对应该子节点的落子概率P 的上施加一个惩罚,降低该子节点被再次选中的概率。当每个线程/进程都选中了叶子节点之后,我们将这些叶子节点去重、展开,对其中需要进行评估的节点(即非终止节点)编码后一同放入神经网 络求值。这时候,一个优秀的深度学习框架自己知道如何安排好一切,充分利用所有的计算资 源(但它能做到这点的前提是一次性获得所有需要处理的输入,这也是深度学习任务中最常见 的情况)。当神经网络完成评估后,我们再通过线程池/进程池对那些不重复的节点(包括终止节点)进行向上更新,同时将节点中落子概率P 恢复原值。
  这种并行化的蒙特卡洛树搜索在考虑相同多局面的情况下的棋力是比原算法要来得弱的, 并行数越多越明显,因为它在挑选新的子节点的时候无法利用到其它同时进行的搜索得到的信息。但比起并行化以后带来的效率上的提升,这些都是值得的。
  第 2.8 节 使用传统五子棋 AI 算法加速训练
  由于完全从随机策略开始训练起的 AI 需要一段比较长的训练迭代才能理解游戏目标。为了能够更快看到训练效果,我们可以在训练的时候为 AI 添加一个传统的五子棋算法威胁空间搜索(Threat-space search[4])中的威胁(Threat)的概念。
  在五子棋中,威胁是指那些必须进行响应的棋型,常见的威胁类型有这么几种:
  1. 四型(a),一条线上的五个连续的格子中的四个被攻击方占领,剩余的一个格子为空。
  2. 直四型(b),一条线上的六个连续的格子中的中间四个被攻击方占领,剩余的两个格子为空。
  3. 直三型(c),一条线上的七个连续的格子中的中间三个被攻击方占领,剩余的四个格子为空。
  4. 三型(d),一条线上的六个连续的格子中间四个格子中的连续三个被攻击方占领,剩余的三个格子为空。
  5. 间断三型(e),一条直线上的六个连续的格子中间四个格子中的不连续的三个被攻击方占领,剩余三个为空。
  威胁的类型决定了防守方可选的防守位置,这使得在出现威胁的情况下需要搜索的空间范围大幅缩小。不冲突的相互依赖的威胁可以构成威胁序列,寻找到一个可以最终同时创建出两个威胁的威胁序列是五子棋制胜的关键。
  添加了这个概念的AI 在面对敌方威胁和己方威胁的时候能做出正确应对,使得 AI 能够更快地度过训练初期,理解游戏目标。当然威胁作为一个人工设计的规则对于深度增强学习的 AI 不是必要的,因为只要经过一定次数的训练迭代,AI 自然会学会这个概念。是否能正确应对威胁同时也是AI 学习成果的体现,所以在最终测试的过程中不开启这个功能
  第 3 章 通过云计算进行自我对弈训练
  第 3.1 节 自我对弈训练的流程
  AI 使用的深度强化学习算法最终依赖于深度神经网络的训练,深度神经网络的训练方法是标准的监督学习,而监督学习又需要事先标记好的训练数据。强化学习与其它机器学习方法最大的不同就在于强化学习可以自行在环境中探索学习,具体到本文中的算法就是通过自我对弈学习下棋。
  AI 进行自我对弈学习下棋的过程是不断迭代的,每次迭代由以下步骤组成:
  1. 用当前的神经网络参数进行自我对弈生成训练数据。
  2. 用生成的训练数据训练深度神经网络,得到新的神经网络参数。
  3. 用新的神经网络参数进行自我对弈生成新的训练数据。
  在第 2 步中,为了避免深度神经网络出现过拟合现象,我们需要有大量的训练数据,而在第1 步和第 3 步中生成自我对弈数据的过程需要消耗非常多的时间。事实上,在 AlphaGo Zero 和AlphaZero 的训练中绝大多数时间都花在了进行生成自我对弈数据上面。不过这是个可以并行的任务,我们可以通过多台计算机同时生成自我对弈数据来节约时间。为了加速神经网络训练,我们还需要一台GPU 性能强大的计算机。
  第 3.2 节 云服务器的选择和配置
  这两个问题都可以通过租用云服务器来解决。市场上有多种可选的云服务器配置,对于生成自我对弈训练数据的任务,我们最好的选择是那种价格较低又具有基本的低配 GPU 的服务器, 但这个需求比较特殊,常见的云服务器配置要么没有 GPU,要么是专用于深度学习的顶配 GPU。为了平衡成本和效率,决定租用多个无GPU 的低配计算型云服务器用于生成自我对弈训练数据, 在有了足够的训练数据后,再租用专用的深度学习服务器进行神经网络的训练。
  服务器使用的系统是预装了 CUDA 和NVIDIA 驱动的Ubuntu 16.04。每台拥有公网带宽的服务器都会分配一个公网 IP,这个公网 IP 可以被用于远程登陆传输训练数据。为了执行训练代码, 我们还需要为服务器安装Keras 和 Tensorflow。
  当一台服务器配置好了之后,通过创建服务器快照并将快照转为镜像,我们可以直接在其它服务器上使用镜像,而不用重复配置环境的过程。
  第 3.3 节 使用 PuTTY 远程连接服务器
  PuTTY 是一个免费的开源终端模拟器和网络文件传输应用。它支持多种网络协议,其中包括了 SCP,SSH,Telnet,rlogin 和原始套接字连接。PuTTY 经常被用作远程终端提供远程服务器控制。
  在PuTTY 的连接设置中可以使用密钥对进行登陆,此处使用的是 PuTTY Key Generator 生成的密钥。
  第 3.4 节 将自我对弈代码以守护进程的方式执行
  直接在远程终端中执行的代码在与服务器的连接断开后将会停止执行,而 AI 的自我对弈生成训练数据的过程通常要持续一整天。如果要始终保持与服务器的连接的话会非常麻烦,而且在网络不稳定的情况下数据很可能丢失。为了解决这个问题,我们需要一个能够在与服务器断开仍然保持代码正常运行的方法。
  守护进程(Daemon)就是解决这个问题的最佳方法。守护进程是 Linux 上运行在后台的一种特殊进程,它能独立于控制终端周期性的执行一项任务。
  要将 Python 代码以守护进程的方法执行非常简单,我们只要把要执行的 Python 代码头上加上#!/usr/bin/python3,让它能够自动使用Python 执行,然后再通过命令 chmod u+x 指令为代码添加上可执行权限,最后再通过 setsid 命令将代码作为守护进程执行并重定位标准输入输出即可。
  第 3.5 节 查看自我对弈情况
  将训练代码转为守护进程执行后,可以通过 top 指令查看进程执行情况。下图中第一个self_play 进程即为自我对弈进程。
  因为守护进程的执行需要与当前环境分离,所以我们将标准输出重定位到了当前目录下的play.log 文件中,使用vi 指令打开这个文件就可以看到自我对弈数据的生成情况。
  图 9 自我对弈数据生成情况
  第 4 章 AI 性能测试
  第 4.1 节 整体测试情况
  在最终的测试中使用的是一个经过了约 1500 局的自我对弈数据训练的模型,使用八个线程进行搜索,每步考虑216个局面,关闭了训练时使用的威胁指导功能。使用的棋局为 9x9 棋盘上的五子棋,无禁手。测试包含两个项目,分别是与玩家对弈和自我对弈。
  测试的主要目标是检验AI 是否真正理解了游戏目标,即在关闭威胁指导功能后,AI 是否仍然能够正确应对威胁,为己方连成五子,阻止敌方连成五子。更进一步地,还要测试 AI 落子的位置是否合理,是否有进攻和防守意识。
  测试发现,考虑的局面过少的情况下(小于 2000 个局面),AI 仍处于对局面的探索阶段,会漏掉一部分威胁,但仍有防御意识。在考虑的局面数目足够的情况下(大约要20000 个局面以上), AI 有着不错的表现,落子具有进攻性,有提前防守敌方攻击的意识,能够比较好的处理出现的威胁,但在游戏后期存在着漏判的情况,可能会忽略一些比较隐蔽的威胁,有时候有必胜招法却没有发现。在考虑的局面充分的情况下(大约考虑 65536 个局面能达到这个效果),AI 表现出色,落子进攻性强,能发现一些隐秘的好招法,在与玩家对弈有获胜的可能。
  由于花了大量的时间在前期的实验和模型调整中,最终测试的 AI 的经过的迭代训练次数较少,深度神经网络的超参数还没有经过充分的测试挑选,AI 棋力的提升空间还非常大。
  AI 自我对弈及与玩家对弈的具体对局情况放在 4.2 节中,此处展示几个有代表性的局面:
  左图,AI 在(8,4)位置落子,阻挡敌方直三型威胁,并形成己方四型威胁。中图,AI 在(6,3)处落子,同时形成三型和间隔三型两处威胁,如果敌方无法再形成另外其它四型威 胁,则AI 即将取胜。右图,AI 优先阻止敌方四型威胁而不是盲目将己方三型威胁升级到直四型威胁。
  第 4.2 节 AI 对弈棋谱
  总结
  本设计实现了一个基于深度增强学习的五子棋AI,它使用深度神经网络指导下的并发蒙特卡洛树搜索算法,并在云服务器上进行自我对弈训练,最终达到了一个不错的表现。
  整个设计的实现和实验的过程中遇到了很多困难。进行深度学习测试所要花费的成本比期一般的代码测试要高很多,生成自我对弈数据需要时间,训练深度神经网络也需要时间。最早版本的AI 的蒙特卡洛树搜索没有实现并发,进行自我对弈需要更多的时间,AI 在经过了大量数据的训练后仍然无法理解游戏目标,下出来的棋与随机落子无异,令人非常沮丧。
  后来蒙特卡洛树的并发搜索大大提升了搜索的效率,原本单线程下考虑 65536 个局面的棋力测试AI 每下一步需要将近 11 分钟,在八线程并发搜索中仅要 2 分钟就能完成,极大地方便了模型考虑充分局面时棋力的测试。但这个功能的实现并不容易,因为深度学习框架底层的实现上的微妙原因,多线程同时进行预测会导致程序崩溃,必须在找到了所有需要评估的叶子节点进行同步,然后一次性提交所有输入,得到输出后再并发更新各个节点的信息。原先单线程代码实现方式并不适合用于这种情况,这种改动需要对代码进行大幅度的重构,而重构动态类型语言的代码是件痛苦的事情,非常容易遗漏一些细节。庆幸Python 还有着简洁优雅的优点, 虽然在重构过程中遇到了一些困难,最终还是解决了。
  训练中遇到的最大问题还是在于模型的过拟合。最初模型的实验过程中没有足够多的数 据,而且没有意识到即使大幅削减了神经网络的深度,它仍然是一个容量非常大的模型,所以
  在训练过程中发生了严重的过拟合现象。具体表现在AI 上就是对局面的评估过度自信,输出的局面估值v 常常是一个接近 1 或者-1 的值,这掩盖了真实胜负局面给出的正确反馈;输出的落子概率P 常常是在某几个位置的落子概率较高,其它位置几乎可以忽略不计,但有较高落子概率的这几个位置的判断又不正确。
  在后来的实验中,用于训练的自我对弈数据慢慢多了起来,模型的容量也作了进一步的缩减,效果有所改善。但对AI 性能提升最为明显的还是后来在神经网络里添加的L2 正则项,L2 正则项加入之后AI 的性能一下子就好了起来,泛化能力强了很多,对局面的评估变得合理,输出的落子概率也能比较好的指导搜索。而且这种超越之前所有模型的效果还仅仅只是使用了之前实验中得到的自我对弈数据进行训练,如果能够用这个模型多进行几次迭代训练,相信一定能够得到更好的效果。
  在整个设计的制作过程中,看着 AI 从一开始的完全不会下,慢慢提升到了后来的能与人类玩家一较高下,这中间的进步还是非常让人感动的。毕竟它和那些在制作出来后水平就固定死的 AI 不同,它的自我学习能力让它充满了无数可能,正是这种从不会到会慢慢学习的过程才让这个人工产物真正有了一种智能的感觉。
  致谢
  在毕业设计实现的过程中,我要特别感谢我的导师刘枫对我的帮助和鼓励,使我能够在实验不断失败的沮丧中重拾希望并最终克服困难,同时也要感谢他的包容和谅解,让我能够在紧迫的毕业设计时间中充分实验自己的想法。
  感谢 DeepMind 团队带来的阿尔法围棋系列,让世界感受到人工智能的强大魅力。阿尔法围棋那简洁强大的算法给我留下了深刻的印象,这也是我毕业设计选择这个题目的原因。如果没有这些人工智能领域前辈的工作和努力,我也不可能完成这份毕业设计。
  感谢开源社区在我学习过程中的提供的帮助,这让我受益良多。开源精神使我敬佩,之后我也将把我的AI 代码开源,以供他人学习。
  感谢我的母校苏州大学,感谢那些教导我的老师们。
  最后,我要特别感谢我的母亲在背后对我的默默支持和鼓励,这是我无论何时想起都会感到幸福的事。
咨询论文发表及论文撰写
论文空间专注于毕业论文硕士论文论文发表网站地图服务
Copyright © 2002-2019 论文空间 版权所有
联系手机:17343344559 微信:lunwenpass QQ:论文客服 论文客服