打字猴:1.700541e+09
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的训练
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
[ 上一页 ]  [ :1.700541e+09 ]  [ 下一页 ]