AI的棋局，其实也是一部热血成长史

导读：不知你有没有看过最近的两部影视剧：《后翼弃兵》与《棋魂》，或者是出版更久远些的《棋魂》原作动漫呢？方正的盘格上，一招一式中暗藏玄机，沉稳缜密的执棋者共同营造着奥妙无穷的哲学空间，而棋局背后，最让人触动的或许更是棋手们那股在胜败之间全力坚守...

不知你有没有看过最近的两部影视剧：《后翼弃兵》与《棋魂》，或者是出版更久远些的《棋魂》原作动漫呢？方正的盘格上，一招一式中暗藏玄机，沉稳缜密的执棋者共同营造着奥妙无穷的哲学空间，而棋局背后，最让人触动的或许更是棋手们那股在胜败之间全力坚守的劲头。

那么，你想了解一下AI的棋局吗？抛开新闻里充斥的“战胜人类” ********* ，试试以一种只把AI看作一个棋手的方式。你或许会发现，它其实也一样，在长久的光阴里，一步步成长，与对手战斗，也挑战自己。还有点不同的是，它的成长不止属于自己，而是更像一个象征，凝结着近百年间人类科学家探索人工智能技术的智慧与成绩，讲述着人类挑战智能技术更高峰的热血坚持。

第一阶段 初露头角

挑战任务：西洋跳棋

西洋跳棋是一种在8x8格的两色相间的棋盘上进行的技巧游戏，以吃掉或堵住对方所有棋子去路为胜利，棋子每次只能向斜对角方向移动，但如果斜对角有敌方棋子并且可以跳过去，那么就把敌方这个棋子吃掉。

大战回顾：

成功秘诀：自我对弈

在和罗伯特雷尼的比赛之后，尼雷表示，计算机走得极其出色，甚至没有一步失误。这是他自1954年以来8年中遇到的第一个击败他的“对手”。那么，这次跳棋盘上的胜利，秘诀在哪里呢？

通过自我对弈学习评价函数是西洋跳棋AI程序的核心技术，自我对弈学习评价函数的基本原理是利用两个副本进行对弈，学习线性评价函数每个特征的权重，其中一个副本使用固定的评价函数来学习特征的权重，另一个副本则是通过与使用极小极大（minimax search）算法作对比来学习特征的权重。事实上，后来的AlphaGo围棋AI程序以及深度学习领域的生成式对抗网络（GAN）都采用了类似的思想。

第二阶段

一场持续半世纪的挑战

挑战任务：国际象棋

国际象棋起源于亚洲，后由 ********* 人传入欧洲，成为国际通行棋种，也是一项受到广泛喜爱的智力竞技运动。

国际象棋棋盘由横、纵各8格、颜色一深一浅交错排列的64个小方格组成，棋子共32个，分为黑、白两方，每方各16个。和8x8的西洋跳棋相比，国际象棋的状态复杂度（指从初始局面出发，产生的所有合法局面的总和）从1021上升到1046，博弈树复杂度（指从初始局面开始，其最小搜索树的所有叶子节点的总和）也从1031上升到10123。人工智能研究者对国际象棋的挑战持续了半个世纪。

大战回顾：

成功秘诀：

●成功秘诀之一：国际象棋加速芯片

“深蓝”计算机在硬件上将通过计算机处理器与象棋加速芯片相结合，采用混合决策的方法，即在自动处理器上执行运算分解任务，交给国际象棋加速芯片并行处理复杂的棋步自动推理，然后将推理得到的可能行棋方案结果返回通用处理器，最后由通用处理器决策出最终的行棋方案。97型“深蓝”与96型相比，运算速度差不多提高了两倍，国际象棋加速芯片的升级功不可没。升级后的国际象棋加速芯片能够从棋局中抽取更多的特征，并在有限的时间内计算出当前盘面往后12步甚至20步的行棋方案，从而让“深蓝”更准确地评估盘面整体趋势。

●成功秘诀之二：知识规则引擎

“深蓝”在软件设计上采用了超大规模知识库结合优化搜索的方法。一方面，“深蓝”储存了国际象棋100多年来70万份国际特级大师的棋谱，能利用知识库在开局和残局阶段节省处理实践并得出更合理的行棋方案；另一方面，“深蓝”采用Alpha-Beta剪枝搜索算法和基于规则的方法对棋局进行评价，通过缩小搜索空间的上界和下界提高搜索效率，同时可根据旗子的重要程度、旗子的位置、棋子对的关系等特征对棋局进行更有效的评价。

规则引擎是一种迁入在应用程序中的组件，能够实现将业务决策从应用程序代码中分离出来，其核心是获取knowledge（知识）。此外，规则引擎使用产生式规则“IFTHENRULE”表达逻辑将知识应用到特定的数据上。

第三阶段 触摸“棋魂”？

挑战任务：围棋

8x8格国际象棋的状态复杂度为1046，博弈树复杂度为10123。到了19x19格的围棋，其状态复杂度已上升到10172，博弈树复杂度则达到惊人的10360，因此被视为人类在棋类人机对抗中最后的堡垒。

破局出现在2016年，Deep Mind公司开发出的AlphaGo在没有任何让子的情况下，以5：0完胜欧洲围棋冠军、职业二段选手樊麾。并在接下来的一系列博弈中势如破竹。而后，AlphaGo Zero作了更进一步的升级和改进，将策略网络和价值网络整合在一起，使用纯粹的深度强化学习方法进行端到端的自我对弈学习。

大战回顾：

成功秘诀：

●成功秘诀之一：蒙特卡罗树搜索

在机器博弈中，每步行棋方案的运算时间、堆栈空间都是有限的，只能给出局部最优解，因此，2006年提出的蒙特卡罗树搜索就成为随机搜索算法的首眩蒙特卡罗树搜索是一种用于某些决策过程的启发式搜索算法，它被广泛用于科学和工程研究的算法仿真中，是现行围棋程序的核心组件。有专家曾通俗地解释什么是蒙特卡罗树搜索：假如篮子里有1000个苹果，让你每次闭着眼睛找一个最大的，不限制挑选次数。于是，你可以闭着眼随机拿一个，然后下一次再随机拿一个与第一个比，留下大的，循环往复，拿的次数越多，挑出最大苹果的可能性也就越大，但除非你把1000个苹果都挑一遍，否则你无法让肯定最终挑出来的就是最大的一个。这就是蒙特卡罗树搜索。它给予了智能体推理的能力，智能体不仅可以根据过去的经验采取更好的策略，也可以根据对未来的推测帮助自己选择合适的方案。

●成功秘诀之二：策略网络与价值网络

策略网络是一个模型，它使用深度学习、监督学习、增强学习等方法来预测下一步棋“大概”该走哪里。策略网络的输入是当前的棋局，输出的是棋子最可能的步法，棋盘上的每一个空位都对应一个概率。AlphaGo面对一个局面时下一步大概怎么走已经了然于胸，这是因为它已经从KGS围棋服务器上向职业选手学习了3000万个局面的下一步，而且学习成果非常惊人；不仅记住了某个局面的下一步怎么走，还记住了相似局面的下一步步法，所以当AlphaGo学习的局面足够多时，就掌握了所有不同局面的下法。这种学习叫做“监督学习（supervised learning）”对于AlphaGo而言，它所学习的职业棋手的棋谱就是它的老师。

价值网络也是一个监督的强化学习的模型，多次线下自我对弈学习的结果为价值网络提供监督信息。它的模型结构与策略网络类似，但学习目标不同，策略网络的目标是当前局面的下一步棋如何走，而价值网络学习的目标是走这一步后赢的概率，主要用于在线下下棋时得到平均的形势判断。

●成功秘诀之三：强化学习

强化学习是机器学习的一个重要分支。有监督学习的目标是从一个已经标记的训练集中进行学习，无监督学习的目标是从一堆未标记样本中发现隐藏的结构，而强化学习的目标则是在当前行动和未来状态中获得最大回报。在边获得样例边学习的过程中，不断迭代“在当前模型的情况下，如何选择下一步的行动才对完善当前的模型最有利”的过程直到模型收敛。

总体来说，AlphaGo在以下四个方面取得重要突破：

01

自学习能力

AlphaGo的对弈知识是通过深度学习方法自己掌握的，而不是像“深蓝”那样编在程序里，它是通过大量棋谱和自我对弈完成的。这种深度学习能力，使得AlphaGo能不断学习进化，产生了很强的适应性，而适应性造就了复杂性，复杂自适应性又是智能演化最普遍的途径。

02

捕捉经验能力

找到了一种捕捉围棋高手的经验，即“棋感直觉”的方法。所谓棋感，就是通过训练得到的直觉，“只可意会，不可言传”。AlphaGo通过深度学习产生的策略网络（走棋网络），在对抗过程中可以实现局部步法的优化；通过增强学习方法生成的估值网络，实现对全局不间断的评估，用于判定每一步棋对全局棋胜负的影响。此外，还可以通过快速走子算法和蒙特卡罗树搜索机制，加快走棋速度，实现对弈质量和速度保证的合理折中。这些技术使得计算机初步具备了既可以考虑局部得失，又可以考虑全局整体胜负的能力。而这种全局性的“直觉”平衡能力，正是过去人们认为人类独有、计算机难以做到的。

03

发现创新能力

发现了人类没有的围棋步法，初步展示了机器发现“新事物”的“创造性”。从观战的超一流棋手讨论和反应可以看出，AlphaGo的下发有些超出了他们的预料，但事后评估又认为是好棋。这意味着AlphaGo的增强学习算法，甚至可以从大数据中发现人类千百年来还未发现的规律和知识，为人类扩展自己的知识体系开辟了新的认知通道。也难怪会有人感叹AlphaGo难道是《棋魂》中的SAI转世?

04

方法具有通用性

这与很多其他博弈程序非常不同，通用性意味着对解决其他问题极具参考价值，AlphaGo运用的方法，实际上是一种解决复杂决策问题的通用框架，而不仅是围棋领域的独门秘籍。自学习的能力，使得计算机有了进化的可能，通用性则使其不再局限于围棋领域。

//////////

从国际跳棋到堪称是世界上最复杂棋盘游戏的围棋，AI棋手不断突破着技术的上限。棋盘竞赛的喧嚣背后，是机器博弈技术的进步和发展历程。

最后，和你分享我们在2001年的《棋魂》动画版中，发现的这样一段对话：

“神之一手会从这里面（电脑）诞生”

“据说电脑下围棋要超过人类还要花一百年呐”

来源：中国科学院自动化研究所

编辑：C&C