1700541034
从算法上讲，AlphaGo的成功之处在于完美集成了深度神经网络、有监督学习技术、强化学习技术和蒙特卡洛树搜索算法。虽然人们很早就尝试使用蒙特卡洛树搜索算法来解决棋类AI问题，但是AlphaGo首先采用强化学习加深度神经网络来指导蒙特卡洛树搜索算法。强化学习提供整个学习框架，设计策略网络和价值网络来引导蒙特卡洛树搜索过程；深度神经网络提供学习两个网络的函数近似工具，而策略网络的初始化权重则通过对人类棋谱的有监督学习获得。与传统蒙特卡洛树搜索算法不同，AlphaGo提出“异步策略与估值的蒙特卡洛树搜索算法”，也称APV-MCTS。在扩充搜索树方面，APV-MCTS根据有监督训练的策略网络来增加新的边；在树节点评估方面，APV-MCTS结合简单的rollout结果与当前值网络的评估结果，得到一个新的评估值。训练AlphaGo可分成两个阶段：第一阶段，基于有监督学习的策略网络参数，使用强化学习中的策略梯度方法，进一步优化策略网络；第二阶段，基于大量的自我对弈棋局，使用蒙特卡洛策略评估方法得到新的价值网络。需要指出的是，为了训练有监督版的策略网络，在50核的分布式计算平台上要花大约3周时间，如图14.13所示。
1700541035
1700541036
1700541037
1700541038
1700541039
图14.13 AlphaGo的训练
1700541040
1700541041
就在众人尚未回过神来之际，AlphaGo的后继者AlphaGo Zero横空出世，后者根本不需要人类棋谱做预先训练，完全是自己和自己下[59]。算法上，AlphaGo Zero只凭借一个神经网络，进行千万盘的自我对弈。初始时，由于没有人类知识做铺垫，AlphaGo Zero不知围棋为何物；36小时后，AlphaGo Zero达到2016年与李世石对战期AlphaGo的水平；72小时后，AlphaGo Zero以100∶0的战绩绝对碾压李世石版的AlphaGo；40天后，AlphaGo Zero超越所有版本的AlphaGo，如图14.14所示。研究者们评价AlphaGo Zero的意义，认为它揭示出一个长期以来被人们忽视的真相——数据也许并非必要，有游戏规则足够。这恰和人们这几年的观点相左，认为深度学习技术是数据驱动型的人工智能技术，算法的有效性离不开海量规模的训练数据。事实上，深层次探究个中原因，有了游戏的模拟系统，千万盘对弈、千万次试错不也是基于千万个样本数据吗，只是有效数据的定义不一定指人类的知识。
1700541042
1700541043
1700541044
1700541045
1700541046
图14.14 AlphaGo Zero 超越所有围棋选手的进步过程
1700541047
1700541048
纵观其他经典的棋类游戏，如国际象棋、中国象棋等，无一不是基于确定性规则建立的游戏。这类游戏不仅规则明晰，而且博弈的双方均持有对称的信息，即所谓的“完美信息 ”。游戏AI面对的问题，通常是一个搜索问题，而且是一对一的MiniMax游戏。原理上，记住当前局面并向下进行搜索式推演，可以找到较好的策略。当搜索空间不大时，可以把各种分支情况都遍历到，然后选出最佳方案；当搜索空间太大时，可以用一些剪枝的或概率的办法，减少要搜索的状态数。国际象棋和中国象棋的棋子较少，且不同棋子走子方式固定，用今天的超级计算机穷举不是问题。但是围棋不同，棋盘是19×19，有361个落子点，一盘围棋约有10的170次方个决策点，是所有棋类游戏中最多的，需要的计算量巨大，所以穷举方式是不可能的，这也导致围棋成为最后被计算机攻克的棋类游戏。数学上，中国象棋和国际象棋的空间复杂程度大约是10的48次幂，而围棋是10的172次幂，还有打劫的手段可以反复提子，事实上要更复杂。值得一提的是，可观测宇宙的质子数量为10的80次幂。
1700541049
1700541050
■ 德州扑克中的“唬人”AI
1700541051
1700541052
德州扑克在欧美十分盛行，大概的规则是每人发两张暗牌，只有自己看到，然后按3-1-1的节奏发5张明牌，七张牌组成最大的牌型，按照同花顺>四条>葫芦>同花>顺子>三条>两对>对子>高牌的顺序比大小。这期间，玩家只能看到自己的两张底牌和桌面的公共牌，因此得到的信息不完全。高手可以通过各种策略来干扰对方，比如诈唬、加注骚扰等，无限注德州扑克可以随时全下。
1700541053
1700541054
2017年1月，在美国宾夕法尼亚州匹兹堡的河流赌场，一个名为Libratus的AI程序，在共计12万手的一对一无限注德州扑克比赛中，轮流击败四名顶尖人类高手，斩获20万美元奖金和约177万美元的筹码（见图14.15）。它的设计者卡耐基梅隆大学博士诺阿·布朗透露，他自己只是一个德州扑克的爱好者，并不十分精通，平时只与朋友打打五美元一盘的小牌，所以从未通过自己或其他人类的经验教Libratus怎么玩牌，仅仅给了它德扑的玩法规则，让它通过“左右互搏”来自己摸索这个游戏该怎么玩，如何能更大概率地获胜。也许正因为布朗未传授人类经验给Libratus，使它玩德扑的风格如此迥异于人类，让人捉摸不透，而这对获胜十分关键，因为在玩德扑的过程中，下注要具备足够的随机性，才会让对手摸不清底细，同时也是成功诈唬住对手的关键。与Libratus交手的四位人类职业玩家证实了Libratus下注十分大胆，不拘一格。它动不动就押下全部筹码，多次诈唬住人类对手，这让人类玩家在20天内只有4天是赢钱的，其他日子都输了。
1700541055
1700541056
据称，Libratus自我学习能力非常强，人类头一天发现它的弱点，第二天它就不会再犯。布朗所用的方法称为反事实遗憾最小化算法（Counterfactual Regret Minimization，CFR），可得到一个近似纳什均衡的解，基本原理是：先挑选一个行为A予以实施，当隐状态揭开时，计算假设选择其他非A行为可获得的奖励，类似计算机会成本，并将非A行为中的最佳收益与事实行为A的收益之差称为“遗憾”，如果遗憾大于零，意味着当前挑选的行为非最优，整个过程就是在最小化这个遗憾[60]。
1700541057
1700541058
DeepStack是另一个同样达到世界级水准的德扑AI程序[61]。与Libratus相同，DeepStack采用自我对战和递归推理的方法学习策略；不同的是，它不是计算一个显式的策略，而是类似AlphaGo，采用树搜索结合近似值函数的强化学习方法来决定每轮的行为，可看成一个带不完美信息的启发式搜索AlphaGo。
1700541059
1700541060
1700541061
1700541062
1700541063
图14.15 德州扑克AI Libratus的决策过程
1700541064
1700541065
牌类游戏与棋类游戏不同。国际象棋、中国象棋和围棋等都是“完美信息”游戏，也就是说，所有玩家在游戏中获得的信息是确定的、公开的和对称的。AI攻克这些游戏的难度，主要取决于游戏过程的决策点数量，这决定了需要的计算量。然而，扑克是一种包含很多隐藏信息的“不完美信息”游戏。玩家掌握不对称信息，只看得到自己手里的牌，却不知道对手手中的牌，更不知道对手如何猜测自己的手牌。因此，虽然一局德扑的决策点数量要少于一盘围棋，但是不确定性的加入，使得每个决策点上，玩家都要全盘进行推理，计算量难以想象。在非对称信息博弈中，对同样的客观状态，由于每个玩家看到的信息不同，这增加了玩家状态空间的数目以及做决策的难度。如果考虑心理层面的博弈，有别于机器，人类可以“诈唬”来虚张声势，这被人类看作是智商和情商的完美结合。
1700541066
1700541067
非对称博弈中双方的猜测是彼此的，是相互影响的，故而没有单一的最优打法，AI必须让自己的移动随机化，这样在它唬骗对方时对方才无法确定真假。举个石头剪子布的例子，如果别人一直用石头剪刀布各1/3的混合策略，那自己就会发现好像怎么出招收益都是0；于是每次都出石头，但是这样的话，对手就可以利用这个策略的弱点提高自己的收益。所以好的算法就要求，基于别人已有策略得到的新策略要尽可能地少被别人利用。这样的研究有很实际的意义，它将来能够应用在金融谈判、拍卖、互联网安全等领域，需要AI在“不完美信息”的情景中做出决策，这或许正是Libratus擅长的。
1700541068
1700541069
■ AI电子竞技
1700541070
1700541071
2013年，尚未被谷歌收购的DeepMind发表了一篇里程碑式的论文《用深度强化学习玩Atari》（Playing Atari with deep reinforcement learning）[62]。Atari 2600是20世纪80年代一款家庭视频游戏机（见图14.16），相当于以前的小霸王学习机，输出信号接电视机，输入则是一个控制杆。研究者通常在它的模拟器Arcade Learning Environment（ALE）上做实验[63]。这篇论文试图让AI仅凭屏幕上的画面信息及游戏分数，学会打遍所有Atari 2600上的游戏。该文充分吸收了近些年深度学习的研究成果——深度卷积神经网络，结合强化学习的已有框架，运用经验回放的采样思路，设计出深度Q-learning算法，最后结果出奇地好，在很多游戏上都胜过人类高手。传说正是因为这点，让谷歌看上了DeepMind。2015年，谷歌DeepMind在《自然》杂志上发表了著名的文章《通过深度强化学习达到人类水平的控制》（Human-level control through deep reinforcement learning），提出了著名的深度Q网络（DQN），仅训练一个端到端的DQN，便可在49个不同游戏场景下全面超越人类高手[64]。
1700541072
1700541073
1700541074
1700541075
1700541076
1700541077
1700541078
1700541079
图14.16 游戏机Atari上的游戏
1700541080
1700541081
此外，在2016年4月，另一家AI研究公司——OpenAI对外发布了一款用于研发和评比强化学习算法的工具包Gym。Gym包括了各种模拟环境的游戏，如最经典的倒立摆。该平台提供一个通用的交互界面，使开发者可以编写适用不同环境的通用AI算法。开发者通过把自己的AI算法拿出来训练和展示，获得专家和其他爱好者的点评，大家共同探讨和研究。强化学习有各种各样的开源环境集成，与它们相比，Gym更为完善，拥有更多种类且不同难度级别的任务，如图14.17所示。
1700541082
1700541083