AlphaGo小白的人工智能之路

小白的人工智能之路2018-6AlphaGo&AlphaGoZero在接下来的一个小时中，你将会……•认识“谁”是可爱的AlphaGo还有它的兄弟AlphaGoZero……•探知AlphaGo和AlphaGoZero的实现原理深度神经网络……蒙特卡洛树搜索……有监督学习•做自己的井字棋AI/人机对弈程序易于实现的极大极小树算法AlphaGoHumanorAI？AlphaGo战绩2016年1月27日AlphaGo以5:0完胜欧洲围棋冠军樊麾2016年3月9日到15日挑战世界围棋冠军李世石的AlphaGo以4:1取得胜利2017年5月23日到27日乌镇围棋峰会，AlphaGo以3:0战胜世界围棋冠军柯洁AlphaGo家族AlphaGo→AlphaGoZero→AlphaZero•AlphaGo:于2014年开始由GoogleDeepMind开发的人工智能围棋软件。它以人类围棋高手的棋谱作为参考数据。•AlphaGoZero:AlphaGo的团队于2017年10月19日在《自然》杂志上发表了一篇文章，介绍了AlphaGoZero，这是一个没有用到人类数据的版本（围棋棋盘大小与规则除外），比以前任何击败人类的版本都要强大。通过跟自己对战，AlphaGoZero经过3天的学习，以100:0的成绩超越了AlphaGoLee的实力，21天后达到了AlphaGoMaster的水平，并在40天内超过了所有之前的版本。•AlphaZero:AlphaZero使用与AlphaGoZero类似但更一般性的算法，在不做太多改变的前提下，并将算法从围棋延伸到将棋与国际象棋上。AlphaGo家族有多可怕？！训练第0天的AlphaGoZero什么都不懂，训练第3天打败AlphaGoLee，训练第21天打败AlphaGoMaster，训练第40天超越了此前AlphaGo系列的所有成员。AlphaGo家族有多可怕？！AlphaZero在短时间训练后能达到其他算法的同等或更高水平版本使用规则硬件Elo等级分的理论峰值战绩AlphaGo樊(v13)中国规则176个GPU，分布式3,1445比0战胜[???]AlphaGo李(v18)48个TPU，分布式3,7394比1战胜[???]AlphaGoMaster4个TPUv2，单机4,858网棋60比0战胜职业棋手；3比0战胜柯洁；1比0战胜人类团队AlphaGoZero川普-泰勒规则4个TPUv2，单机5185100:0战胜AlphaGo李;与AlphaGoMaster对战胜率达90%AlphaZero4个TPUv2，单机N/A60:40战胜AlphaGoZero（3天版本）AlphaGo走下神坛AlphaGo的胜利意味着AI技术有了突破性的进展？AlphaGo的胜利意味着机器打败人脑？答案是否定的。其实，AlphaGo在算法层面上并没有太多新意，而是通过Google强大的团队和计算平台，把已有的技术整合在一起，利用大量的训练数据和计算资源来提高准确性。AlphaGo=蒙特卡洛树搜索算法(MCTS)+深度神经网络博弈树把游戏看作一棵树每个结点是一种游戏状态。名称棋盘大小(位置数)状态空间复杂度(状态数)状态树复杂度(叶子结点数)平均游戏长度井字棋(Tic-Tac-Toe)91031059四子棋(Connect4)421013102121翻转棋(Reversi/Othello)641028105858跳棋(Internationaldraughts/Checkers)501030105490中国象棋9010401015095国际象棋(Chess)6410471012370五子棋(Gomoku)22510105107030围棋(Go)3611017010360150六子棋(Connect6)361101721014030常见对弈游戏的状态复杂度对比围棋的状态复杂度为10170那么10的170次方意味着什么呢？21个百亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿亿这个规模十分可怕！由于不能将所有状态都遍历一次，于是AlphaGo使用“蒙特卡罗树搜索”算法(MCTS)先从蒙特卡罗方法开始：假设我们要计算一个不规则图形的面积。蒙特卡罗方法基于这样的思想：假想你有一袋豆子，把豆子均匀地朝这个图形上撒，然后数这个图形之中有多少颗豆子，这个豆子的数目就是图形的面积。当你的豆子越小，撒的越多的时候，结果就越精确。AlphaGo——什么是蒙特卡罗树搜索(MCTS)？图：计算机蒙特卡罗方法模拟借助计算机程序可以生成大量随机的、均匀分布坐标点，统计出图形内的点数，通过它们占总点数的比例和坐标点生成范围的面积就可以求出图形面积。AlphaGo——什么是蒙特卡罗树搜索(MCTS)？如何让计算机“看懂棋局”：AlphaGo中一个游戏状态的大小是19*19*17。不仅要考虑当前棋盘状态，还要考虑前几次下棋的位置。其中19*19是围棋棋盘的大小,17=8+8+1：1、过去8步的黑棋位置2、过去8步的白棋位置3、当前走棋方(黑棋/白棋)AlphaGo——什么是蒙特卡罗树搜索(MCTS)？蒙特卡罗树的一个结点：对应一个游戏盘面树节点的子结点：从该状态出发可以产生的后续状态父结点到子结点的边：落子动作每个结点还具有信息N和W：N=结点(动作)被选择的次数W=所有子结点的价值总和价值：获胜的期望值,-1为负,0为平,1为胜。图：一棵蒙特卡罗树AlphaGo——什么是蒙特卡罗树搜索(MCTS)？蒙特卡罗树搜索的一次迭代包括四个阶段：选择、扩展、模拟、反向传播（回溯）蒙特卡罗树搜索的一次迭代选择(Selection)：从当前结点的子结点的中选择U值最大的一个。U=f(N,W)扩展(Expansion)：扩展结点，列出所有可能的动作及其游戏状态。模拟(Simulation)：对于一个节点，多次随机模拟博弈直到决出胜负。用频率代替概率，估算这个子节点的价值W。胜:W:=W+1平:W:=W+0负:W:=W-1蒙特卡罗树搜索的一次迭代蒙特卡罗树搜索的一次迭代进行多次模拟后，可以近似认为W/N就是获胜的期望值。反向传播(Backpropagation)：回溯更新父节点到子节点的路径上所有结点的(N,W)值。蒙特卡罗树搜索的一次迭代•AlphaGo等算法中，不同于传统MCTS方法的随机模拟博弈，W/N的值由深度神经网络(后述)估算。•选择子结点时，除了N,W以外还需要考虑落子概率P。•AlphaGo中使用人类专业棋手的棋谱数据训练深度神经网络，落子更接近于人的思维。•而AlphaGoZero和AlphaZero算法中，在进行多次MCTS迭代后，以(子结点N/父结点N)估算落子概率，再以此训练深度神经网络。AlphaGo等算法中MCTS的创新•注:图中Q=W/N,U正相关于P/(N+1)(不同于前述传统MCTS的U）深度神经网络可以用函数f(s)表示,s表示当前游戏状态。函数f(s)有两个输出:P(落子概率)和W(价值)，按下图的方式应用到MCTS的计算中。根据N,W,P的值，进一步选择子结点并迭代。最初使用传统MCTS随机模拟的估算结果来训练深度神经网络。迭代的次数足够后，用深度神经网络的输出代替随机模拟。用深度神经网络预测落子概率和价值的方法比传统MCTS的随机模拟速度更快，效果更好。AlphaGoAlphaGo=深度神经网络+蒙特卡罗树搜索算法||估值网络+走棋网络使得电脑像人类的大脑一样自发学习使得电脑可以结合树状图进行长远推断AlphaGo——什么是深度神经网络？图：一个三层结构的简单神经网络神经网络三要素：输入层隐藏层输出层走棋网络(PolicyNetwork)的输出是19*19+1维向量，表示在19*19的棋盘上每个位置落子的概率，以及当前走棋方(黑棋/白棋)。估值网络(ValueNetwork)的输出是范围在[-1,1]的标量。AlphaGo的估值网络和走棋网络是独立的，并且没有用到残差层。AlphaGoZero、AlphaZero的估值网络与走棋网络共享前面的网络层。AlphaGo等算法的强化学习流程(ReinforcementLearning)•（1）自对弈(Self-Play)当前网络自对弈25000局，保存每一步的游戏状态、MCTS中的结点概率以及最终的获胜者。AlphaGo等算法的强化学习流程(ReinforcementLearning)•（2）训练(RetrainNetwork)从500000局游戏中抽取2048个样本。样本包括上述的游戏状态、MCTS的结点概率以及最终获胜者。将游戏状态作为深度神经网络的输入。然后将预测输出与实际结果对比，得到损失函数的值。最后，反向传播调整深度神经网络中的参数。AlphaGo等算法的强化学习流程(ReinforcementLearning)•（3）评价网络(EvaluateNetwork)调整后的网络与原网络对弈400局。若调整后的网络能赢下至少55%的对局，则接受调整后的网络，并替代原网络。实战环节：做自己的井字棋AI/人机对弈程序19×19的围棋AlphaGo能hold住，哈哈，我的电脑可不行！一口吃不成胖子，谁叫我们是人工智能小白呢！不如来看看轻量级的人工智能应用——井字棋人机对弈实战：自己动手做井字棋AI/人机对弈程序1、安装python3python3-V2、安装pygame模块python3-mpipinstall-i实战：自己动手做井字棋AI/人机对弈程序3、分析极大极小树算法的实现函数实战：自己动手做井字棋AI/人机对弈程序4、将文件“ticky.py”放进D盘根目录在cmd中输入①D:回车；②python3ticky.py，回车；程序效果实战：自己动手做井字棋AI/人机对弈程序5、点击绿色按键“vsAI”；点击蓝色框内的棋盘；重新开始请再次点击“vsAI”。THANKS