1700540990
1700540991
现在，定义游戏的边界不再清晰。周末聚一帮好友吃着串玩狼人杀，是一种游戏；深夜与千里之外素不相识的网友，组织一小队去做任务，也是一种游戏。然而游戏不只有娱乐功能，还可以教孩子学英文、帮新兵熟悉战场环境，游戏营造出的奖励机制和现场体验，让学习过程事半功倍。心理学家认为，人们玩游戏时的娱乐体验，构建在智力活动之上。游戏中层层关卡设计，代表不同级别的智力难度，玩家在过关之前，需要投入一定的脑力，观察、思考、实验、学习并动用过去积累的常识知识。这种对智力逐级考察并及时奖励的过程，是我们产生愉悦感的来源，也是游戏和智能密不可分的联系。
1700540992
1700540993
■ 游戏AI的历史
1700540994
1700540995
早在人工智能处于萌芽期，先驱们就产生用计算机解决一些智力任务的想法。人工智能之父——阿兰·图灵很早就从理论上提出用MiniMax算法来下国际象棋的思路[53]。
1700540996
1700540997
第一款成功下棋的软件诞生于1952年，记录在道格拉斯的博士论文中，玩的是最简单的Tic-Tac-Toe游戏（见图14.10（a））。几年后，约瑟夫塞·缪尔开发出下西洋跳棋（见图14.10（b））的软件，是第一款应用机器学习算法的程序，现在这个算法被人们称为强化学习。在早期的游戏中，AI都集中在解决经典棋类游戏的问题上，人们相信人类挑战了几百年甚至上千年的游戏，必定是人类智能的精华所在。然后，三十年的努力，人们在树搜索技术上取得突破。1994年，乔纳森·斯卡费尔的西洋跳棋程序Chinook打败了人类冠军马里恩·汀斯雷[54]；2007年，他在《科学》杂志宣布“Checkers is solved”（西洋跳棋已被攻克）[55]。
1700540998
1700540999
1700541000
1700541001
1700541002
（a）Tic-Tac-Toe游戏
1700541003
1700541004
1700541005
1700541006
1700541007
（b）西洋跳棋
1700541008
1700541009
1700541010
1700541011
1700541012
（c）西洋双陆棋
1700541013
1700541014
图14.10 各种棋类游戏
1700541015
1700541016
长时间以来，国际象棋被公认为AI领域的实验用“果蝇”，大量的AI新方法被测试于此。直到1997年，IBM的深蓝击败世界级国际象棋大师加里·卡斯帕罗夫（见图14.11），展现出超人般的国际象棋水平，这只“果蝇”终于退休了[56]。当时深蓝运行在一个超级计算机上，现在一台普通的笔记本就能运行深蓝程序。
1700541017
1700541018
1700541019
1700541020
1700541021
图14.11 深蓝击败象棋大师加里·卡斯帕罗夫
1700541022
1700541023
游戏AI的另一个里程碑事件发生在西洋双陆棋上（见图14.10（c））。1992年，杰拉尔德·特索罗开发的名叫TD-Gammon的程序，运用了神经网络和时间差分学习方法，达到了顶尖人类玩家的水准[57]。随着AI技术的发展，经历了从高潮到低谷、从低谷到高潮的起起伏伏，时间转移到2010年前后，DeepMind、OpenAI等一批AI研究公司的出现，将游戏AI推向一个新纪元，下面我们开始一一详述。
1700541024
1700541025
■ 从AlphaGo到AlphaGo Zero
1700541026
1700541027
面对古老的中国游戏——围棋，AI研究者们一度认为这一天远未到来。2016年1月，谷歌DeepMind的一篇论文《通过深度神经网络与搜索树掌握围棋》（Mastering the game of go with deep neural networks and tree search）发表在《自然》杂志上，提到AI算法成功运用有监督学习、强化学习、深度学习与蒙特卡洛树搜索算法解决下围棋的难题[58]。2016年3月，谷歌围棋程序AlphaGo与世界冠军李世石展开5局对战，最终以4∶1获胜（见图14.12）。2016年年底，一个名为Master的神秘围棋大师在网络围棋对战平台上，通过在线超快棋的方式，以60胜0负的战绩震惊天下，在第59盘和第60盘的局间宣布自己就是AlphaGo。2017年5月，AlphaGo又与被认为世界第一的中国天才棋手柯洁举行三局较量，结果三局全胜。
1700541028
1700541029
1700541030
1700541031
1700541032
图14.12 AlphaGo击败围棋冠军李世石
1700541033
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的训练