十分钟看懂AlphaGo的核心算法

转载 2017年06月16日 16:39:42

围棋是一个完全信息博弈问题。而完全信息博弈,通常能被简化为寻找最优值的树搜索问题。它含有 b 的 d 次方个可能分支,在国际象棋中 b≈35,d≈80;而在围棋中 b≈250,d≈150。很显然,对于围棋,用穷举法或简单的寻路算法(heuristics)是行不通的。但有效的方法是存在的:

从策略(policy) P(a|s) 中取样 action,降低搜索广度

通过位置评估降低搜索深度

把策略和值用蒙特卡洛树搜索(MCTS)结合起来。

通常的步骤是:

用一个 13 层的 CNN,直接从人类棋步中训练一个监督学习策略网络 Pσ。输入为 48 x 19 x 19 的图像(比方说,它的组成棋子颜色 是 3 x 19 x 19),输出是使用 softmax 层预测的全部落子的概率。精确度是 55.7%。

训练一个能在运行时快速取样 action 的快速策略 Pπ。这会用一个基于小型模式特征的线性 softmax。精确度是 24.2%,但它计算一次落子只用 2 微秒,而不像 Pσ 需要 3 毫秒。

训练一个增强学习策略网络 Pρ ,通过优化博弈结果来进一步提升监督策略网络。这把策略网络向赢棋优化,而不是优化预测精确度。本质上,Pρ 与 Pσ 的结构是一样的。它们的权重使用相同值 ρ=σ 初始化。对弈的两个选手,是当前策略网络 Pρ 和随机(防止过拟合)选择的此前的策略网络迭代。

训练一个价值网络(value network)Vθ,来预测强化学习策略网络自己和自己下棋的赢家。该网络的架构和策略网络类似,但多出一个特征平面(当前玩家的颜色),并且输出变成了单一预测(回归,均方差损失)。根据完整棋局来预测对弈结果,很容易导致过拟合。这是由于连续落子位置之间高度相关,只有一子之差。因此,这里使用了强化学习策略网络自己与自己对弈新生成的数据。该数据从包含 3000 万个不同位置的独立棋局中抽取。

把策略网络、价值网络、快速策略和蒙特卡洛树搜索结合起来。一个标准的蒙特卡洛树搜索过程包含四步:选择、扩展、评估、备份。为了让大家更容易理解,我们只粗略讲了讲它如何在模拟中选择状态的部分(如对数学感兴趣,请到原始论文中找公式)。

状态分数=价值网络输出+快速运行(fast rollout)的策略结果+监督学习策略网络输出

高状态得分(或者说落子)会被选择。价值网络输出和快速运行策略结果是评估函数,在叶子节点进行评估(注意,为了评估快速运行,需要一直到最后一步)。监督学习策略网络输出是一个当前阶段的 action 概率,充作选取分数的奖励分。该分数会随访问次数而退化,以鼓励探索。注意强化学习策略网络只被用于辅助,来生成价值网络,并没有直接在蒙特卡洛树搜索中使用。

到这就结束了,以上就是战胜了人类的 AlphaGo 算法!

原文:One-PageAlphaGo 十分钟看懂AlphaGo的核心算法
英文论文:Mastering the game of Go with deep neural networks and tree search

一文读懂AlphaGo Zero算法

CMU计算机学院暨机器人研究所博士邓侃在本文中,尝试用大白话,通俗地解释 AlphaGo Zero,弄清楚蒙特卡洛树搜索(Monte Carlo Tree Search,MCTS)、深度学习启发函数和...
  • zchang81
  • zchang81
  • 2017年10月26日 09:23
  • 3511

AlphaGo算法框架解读

AlphaGo算法框架解读 Author: L. Chen, UoS 1. Introduction:  如图1,在围棋中,每一步棋,从State K到State K+1都有很多种走法(...
  • L_Chen_Soton
  • L_Chen_Soton
  • 2016年06月07日 22:17
  • 3304

10分钟搞懂git和github(该教程只适合快速入门)

目录 目录 正文 一 git的安装配置只有初次使用需要配置 用户名和邮件 ssh-keygen -t rsa 添加公钥 二最基础本地git操作若这步看不懂请先看四 三 关联远程github的操作 四...
  • u013497977
  • u013497977
  • 2017年01月09日 18:53
  • 1338

十分钟看懂批处理

  • 2014年03月08日 18:14
  • 2.5MB
  • 下载

深入浅出看懂AlphaGo Zero

作者丨刘遥行 学校丨圣何塞州立大学研究生 研究方向丨AI与现实生活的工业结合 AlphaGo Zero = 启发式搜索 + 强化学习 + 深度神经网络,你中有我,我中有你,互相对抗,不断自我...
  • Uwr44UOuQcNsUQb60zk2
  • Uwr44UOuQcNsUQb60zk2
  • 2017年11月04日 06:40
  • 177

十分钟看懂图像语义分割技术

大多数人接触“语义”都是在和文字相关的领域,或语音识别,期望机器能够识别你发出去的消息或简短的语音,然后给予你适当的反馈和回复。嗯,看到这里你应该已经猜到了,图像领域也是存在“语义”的。 今天是AI大...
  • u012150360
  • u012150360
  • 2017年04月26日 11:58
  • 1315

十分钟看懂图像语义分割技术

大多数人接触 “语义” 都是在和文字相关的领域,或语音识别,期望机器能够识别你发出去的消息或简短的语音,然后给予你适当的反馈和回复。嗯,看到这里你应该已经猜到了,图像领域也是存在 “语义” 的。 ...
  • witnessai1
  • witnessai1
  • 2017年12月06日 11:28
  • 28

十分钟让你看懂「共享经济」到底是什么?

共享经济,人人分享的时代
  • wave_1102
  • wave_1102
  • 2015年09月13日 23:32
  • 1656

十分钟看懂数据库——数据库入门级语言总结

从sql入门经典,到sql视频,再到自考的数据库系统原理,不知不觉中我们已经走进了数据库的世界,那么什么叫数据库,他又是干什么用的呢? 咱们先看一下百度给的解释啊。 数据库(Database)是按照...
  • liu1121655792
  • liu1121655792
  • 2016年07月31日 11:25
  • 1246

文章解析整理:《十分钟看懂图像语义分割技术》

本文仅是博主自己学习用来加深印象和留存整理,对该内容有兴趣请去阅读原文 原文地址: https://www.leiphone.com/news/201705/YbRHBVIjhqVBP0X5...
  • jianyuchen23
  • jianyuchen23
  • 2017年07月18日 14:49
  • 341
内容举报
返回顶部
收藏助手
不良信息举报
您举报文章:十分钟看懂AlphaGo的核心算法
举报原因:
原因补充:

(最多只允许输入30个字)