新媒体网站建设费用详单,企业网站 自适应,商家小程序怎么制作,软件著作权怎么写图 1-1: AphaGo 结构概览
1. 前言
AlphaGo 是一个非常经典的模型#xff0c;不论从影响力还是模型设计上。它的技术迭代演进路径#xff1a;AlphaGo#xff0c;AlphaGoZero#xff0c;AlphaZero#xff0c;MuZero 更是十分精彩。相信有很多同学因为听了 AlphaGo 的故事对…
图 1-1: AphaGo 结构概览
1. 前言
AlphaGo 是一个非常经典的模型不论从影响力还是模型设计上。它的技术迭代演进路径AlphaGoAlphaGoZeroAlphaZeroMuZero 更是十分精彩。相信有很多同学因为听了 AlphaGo 的故事对机器学习或者深度学习产生兴趣致力投身于机器学习/深度学习的领域。本文尝试对 AlphaGo即李世石版 进行分析看看当时在全世界范围内引起广泛关注的模型是如何设计的。同时我们也会对封面图进行解读看看这张图里到底放生了什么故事。本文大致可以分为三个模块 对计算机下围棋问题的分析和思考 解释经典的 MCTS 思想 介绍 AlphaGo 的算法内容。
文章比较长祝有个精彩的旅程。
本文将尝试解释以下内容 了解计算机下围棋的问题 MCTS 的基本原理 Policy Network Value Network AlphaGo 中的 MCTS
2. 计算机下围棋的问题描述
围棋是一个两人博弈的游戏每个围棋选手均想战胜对方这是一种两个人的零和游戏即下棋的最后一定有一个胜利者和失败者 和棋情况先不考虑。在计算机诞生的早期作为计算机的先驱比较感兴趣的是在下棋方向计算机何时取代人类。所有的棋类游戏对于人类来说都是一个思维活动的过程然而计算机是一堆电子元器件堆积的产物一个自然的问题在棋类游戏中由电子元器件组成的计算机如何模拟由生物细胞组成的人的思维方式呢
2.1 计算机棋类游戏发展简史
要回答这个问题不得不先看看计算机棋类游戏的发展史。可能在此过程中会遇到不少的熟人可能会惊叹他们在棋类游戏中也做出了如此了不起的工作也许对于他们来说思考这个问题只是平时娱乐的游戏。首先 1950 是 Claude Shannon香农 提出用 Tree search树搜索 方式解决棋类问题这点很重要将棋类问题建模为 Tree 将人类的思维过程建模为 Tree 上搜索的过程在此我们先概略的体会它的重要性在后续 MCTS 中将会看到这一个思想精彩的延展。然后 1953 年 Alan Turing艾伦·图灵 写出第一个国际象棋程序这人同时也是我们的“祖师爷”。然后 Arthur Samuel 在前人的基础上写出第一个跳棋游戏的程序下的比它的开发者还好 与此同时各个棋类的计算机程序在飞速的发展在 1968 年写出第一个击败围棋新手的程序。
因为前人已经将棋类游戏建模为 Tree Search 问题不同棋类规则不同从而树的规模不同计算机擅长快速计算普通的台式机计算能力在 129GFLOPS。所以问题转化为 在棋类游戏中计算机利用它的快速计算能力在 Tree Search 任务上如何战胜人类选手即各种棋类中人类的最强选手。在 1992 年在西洋双陆棋中IBM 开发的程序 TD-Gammon 仅次于人类的最佳选手但它探索了很多人类未走过的策略最终导致双陆器玩法的进步。1996 年在跳棋领域程序 Chinook 赢得了美国的锦标赛冠军。然后就是部分同学知道的 IBM 的 DeepBlue深蓝 击败当时国际象棋的世界冠军 Garry Kasparov。最后是 2016 年就是大家熟知的 AlphaGo 击败人类九段选手李世石因为当年围棋积分排行榜第一是柯洁所以 AlphaGo 不算真正的击败人类最强选手于是在 2017 年 AlphaGo Master 在乌镇击败当时的世界冠军柯洁。相当于宣布在所有的棋类游戏中计算机战胜了人类。 图 2-2: DeepBlue 作者与国际象棋世界冠军握手
2.2 围棋的规则简述
据说在所有的棋类游戏中围棋的规则最简单但却是最难玩的棋类游戏。我们先初步看下围棋的主要规则有助于后续理解围棋的复杂性以及感受当初 Deepmind 面对问题的难度。 围棋由 19 条横线和 19 条竖线组成的网格共有 361 个交点每个交点均是一个落子点最开始时棋盘上空无一子 一个选手执黑色棋子一个选手执白色棋子在棋盘上轮流下且执黑色棋子的选手先行 当一片连续的同色的棋子完全被另外一种颜色的棋子包围时这片连续棋子为“死棋”将会被提走。如图 2-3c 所示黑棋下在粉色区域白色棋子将被提子 当围棋结束时统计黑白双方各自占据的交点占据交点数量多的一 方获胜如图 2-3d 白色棋子占据 9 个交点黑色棋子占据 16 个交点 黑色棋子胜
以上我们介绍这些规则已经可以在盘面上演绎出千变万化的局面。面对这千变万化的局面如果让我们“解决计算机围棋选手战胜人类围棋选手的问题”我们该从何下手 图 2-3围棋的主要规则
2.3 计算机模拟人下围棋问题的难度
2.3.1 遍历围棋 Tree
借用 Claude Shannon香农 Tree search 的思想我们来建模围棋的 Tree。首先 Tree 的每个节点是一个符合围棋规则的棋盘状态。顺此推理Tree 的根节点是一个空的棋盘如图 2-4 所示。一个节点 s 的子节点是 在节点 s 状态下对方棋子所有的落子可能。在图 2-4 的棋盘中根节点的子节点有 16 个即黑棋落在 16 个交点的任意一个点都是根节点的一个子节点只不过其中有些子节点是“送人头”人类选手不下在相应的位置上罢了所以在图 2-4 中只描述节点常出现的子节点一颗实际 列出所有可能的围棋 Tree 要比图 2-4 的 Tree 大很多。Tree 的叶子节点则是一场对弈中的终止状态即在一场对弈中已经分出胜负。 图 2-4: 一颗简单的围棋 Tree
现在我们有了一颗围棋 Tree 每个从根节点到叶子节点的路径都是一盘有胜负的对弈这颗 Tree 枚举了围棋中任何一种状态下所有可能的落子情况。那么计算机在与人类选手对弈时参考这颗围棋 Tree选择对自己有利的位置下棋。这样计算机完全立于不败之地我们似乎解决了“计算机围棋选手战胜人类围棋选手的问题”似乎没有 AlphaGo 什么事了。但我们都知道事实是 AlphaGo 战胜了人类。计算机借助围棋 Tree 下赢人类的推演逻辑是正确的那什么地方没考虑到才导致 Tree search 的思想出现 60 年后计算机围棋选手才战胜人类职业选手呢
2.3.2 围棋 Tree 节点太多
首先第一点这棵围棋 Tree 很庞大。在标准棋盘下19*19361我们简单估算一下枚举所有落子状态的 Tree 的节点个数。假设一场对弈最后棋盘上每个点上都有棋子 在一个空棋盘上黑子的落子可能有 361 种在黑子落下后白子有 360 种落子可能然后黑子有 359 种落子可能白子 358 种落子可能... 以此类推下去 倒数第二手白子有两种落子可能最后一手黑子只有一种落子可能。很明显这是一个阶乘即所有节点个数最多为 361个。阶乘是一个增长速率很恐怖的运算恐怖到阶乘的计算器都不计算 5000 或者 10000 以上的数的阶乘 如图 2-5可能因为计算结果太大对人类已经没有使用价值了吧。 图 2-5: 随机抽取的阶乘计算器
361! 的计算结果如图 2-5d 所示用科学计数法表示1.43∗目前性能稍好些的 CPU 主频在 3GHz 左右我们假设 1hz 查看一个 Tree 的节点遍历完所有节点需要的年数用科学计数法表示在 10 的指数上只是比节点个数少 17 次方而已。我们估计节点个数的方法比较粗暴在引入围棋规则后节点个数大约 比我们粗暴的估计方法减少很多。但这个值依然大的无法遍历 Tree。
2.3.3 很难判断一个节点的好坏
第二点我们忽略的难点在围棋下完前的某个节点状态很难判断谁赢谁输。这点也是导致“遍历围棋 Tree 的思想”不能实现的关键因素之一。也许在看完章节 2.3.2 后 有的同学会说围棋只有 361 个落子点所以我们不需要查看围棋 Tree 所有的节点我们只需要遍历每个选中节点的子节点就行这样最多只需要查看 个节点这个数值计算机可以很快算完。这个想法也是对的在下棋时我们确实按照这个逻辑在 Tree 上搜索只不过这个想法忽略的是Tree search 过程需要比较节点 s 的所有子节点然后在所有子节点中选择最有利于自己的子节点作为下一步的落子方案。因为针对围棋 Tree 上除叶子节点外任何一个单独的节点我们不能判断输赢即针对黑子 或者白子 判断不了当前局面的好坏。所以在落子前必须先遍历围棋 Tree由叶子节点向上一层层计算出每个节点的值这个节点值表示对黑子的有利程度用于子节点比较时找出最有利于自己的子节点。也许大家会好奇一个问题 遍历围棋 Tree 时如何计算每个节点的值
2.3.4 计算围棋 Tree 中每个节点的值
在“遍历围棋 Tree 的思想”下既然每个节点 s 有一个值 用于节点之间比较那么借助图 2-6 我们来理解如何精确计算围棋 Tree 各个节点的值。如图 2-6a 假设我们有一颗 5 层的简化的围棋 Tree 只有叶子节点能判断胜负如果黑子胜标记为 1如果白字胜标记为 −1。黑白棋子交替行棋最开始由黑子先行。黑白棋子均会参考这颗围棋 Tree 行棋而且每步行棋对自己来说都是最优策略在此情况下我们计算每个节点的值 。根据我们的定义 越大表示对黑子越有利 越小表示对白子越有利。 的定义如式 2.1 可以从以下 3 个方面理解式 2.1 对于叶子节点 s如果黑子胜 1如果白子胜 −1 对于非叶子节点 s 若此轮到黑子行棋为了让自己赢 是所有子 节点中的最大值行棋方案是最大值的子节点对应的动作 a 对于非叶子节点 s 若此轮到白子行棋为了让自己赢 是所有子 节点中的最小值行棋方案是最小值的子节点对应的动作 a
因为围棋中不是黑子赢就是白子赢所以黑子和白子计算 的策略是相 反的。 根据公式 2.1 对 的定义 现在我们再来看看图 2-6a 中这颗 5 层的围 棋 Tree 由下到上如何一层层计算节点的值 。围棋 Tree 的第五层叶子 节点的值由黑子和白子的胜负自然得到围棋 Tree 的第四层由白子行棋 第四层中每个节点的值 为子节点中的最小值于是便得到图 2-6b 的结 果围棋 Tree 的第三层由黑子行棋第三层中每个节点的值 为子节点中最大值于是得到图 2-6c 的结果。第二层和第一层的节点依次类推计算 便得到图 2-6d 的结果。这样我们便得到图 2-6 这颗 5 层的围棋 Tree 的所有 节点的值 。参照这种计算方法我们可以计算任何一颗围棋 Tree 的节 点值 有了一颗围棋 Tree 完整的节点值我们就可以在这颗 Tree 上 search 了。只可惜真正棋盘的围棋 Tree 的 我们是计算不出来的。 图 2-6: 一颗围棋 Tree 节点值 v(s) 的计算过程
2.3.5 用近似求解代替精确求解
现在我们知道“遍历一颗围棋 Tree 的思想”为什么行不通了。那我们 是放弃还是继续攻克这个难题针对个人讲绝大多数人选择了放弃只有 少部分人选择继续。针对全人类来讲只要还有一个人在坚持探索计算机下 围棋那么就等于没有放弃这个问题。AlphaGo 和 AlphaGo Zero 的出现 也证明人类没有放弃这个问题并且还解决了这个难题让计算机围棋选手 战胜了人类围棋选手。继续回到我们的故事在面临“遍历一颗围棋 Tree” 不现实的情况下该如何继续我们的探索 前辈们给出的答案 我们不再追 求遍历一颗完整的围棋 Tree 而是通过近似估计的方法降低对围棋 Tree 深度和宽度的依赖。这种思想下最精彩的算法是 MCTS我们在下一节将 详细介绍 MCTS大家一起欣赏有关它的故事看看这个算法是如何将“近 似解替代精确解的思想”发挥的淋漓尽致。 图 3-7: MCTS 概览
3. 团队介绍
「三翼鸟数字化技术平台-智慧设计团队」依托实体建模技术与人工智能技术打造面向家电的智能设计平台为海尔特色的成套家电和智慧场景提供可视可触的虚拟现实体验。智慧设计团队提供全链路设计涵盖概念化设计、深化设计、智能仿真、快速报价、模拟施工、快速出图、交易交付、设备检修等关键环节为全屋家电设计提供一站式解决方案。
