转载

深蓝与AlphaGo的对比

20年前,深蓝与卡斯帕罗夫的对弈使人工智能进入大众视野;20年后,AlphaGo对李世乭的压倒性胜利再次使人工智能成为热议焦点。同样是战胜了棋类世界冠军,两代人工智能最重要的差别在于:深蓝仍然是专注于国际象棋的、以暴力穷举为基础的特定用途人工智能,而AlphaGo是几乎没有特定领域知识的、基于机器学习的、高度通用的人工智能。这一区别决定了深蓝只是一个象征性的里程碑,而AlphaGo则更具实用意义。

深蓝与AlphaGo的对比

深蓝的算法

整体而言,深蓝是一套专用于国际象棋的硬件,大部分逻辑是以“象棋芯片”(Chess Chip)的形式用电路实现的。在象棋芯片之上,有较少量的软件负责调度与一些高阶功能。

深蓝算法的核心是基于暴力穷举:生成所有可能的走法,然后执行尽可能深的搜索,并不断对局面进行评估,尝试找出最佳走法。深蓝的象棋芯片包含三个主要的组件:走棋模块(Move Generator),评估模块(Evaluation Function),以及搜索控制器(Search Controller)。各个组件的设计都服务于“优化搜索速度”这一目标。

走棋模块负责生成可能的走法。走棋模块的核心是一个8*8的组合逻辑电路阵列,代表棋盘的64个格子。国际象棋的走棋规则以硬件电路的方式嵌入到阵列之中,因此走棋模块可以给出合法的走法。在核心之外还有附加的逻辑电路用于探测和生成特殊走法(例如“吃过路兵”和“王车易位”)。

评估模块是整个芯片中最主体的部分,占据了芯片上2/3的面积、超过半数的逻辑三极管和80%以上的存储三极管。评估模块又分为三个部分:棋子位置评估;残局评估;以及慢速评估。棋子位置评估对盘面上所有棋子当前所处的位置计分,不同棋子处于不同位置的分值由软件预先计算好后写入硬件。芯片中输入了大约8000种不同的“模式”,并针对每种模式赋予了一定的分值。残局评估也预存了一系列专门针对残局的估值规则,例如“王在棋盘中央有利”(King centralization bonus)的规则。残局评估子模块还以8*8组合逻辑电路阵列的形式跟踪所有兵所处的位置,并计算兵是否越过了对方的王、是否能一路冲到对方底线晋级。由于逻辑嵌入在硬件中,棋子位置评估和残局评估都只需要一个时钟周期就可以完成计算。

慢速评估子模块是整个芯片上最复杂的元素,占据芯片上约一半的面积,并且完成计算需要10个时钟周期。大量国际象棋特有的逻辑都在慢速评估的过程中计算,包括:

square control, pins, xrays, king safety, pawn structure, passed pawns, ray control, outposts, pawn majority, rook on the 7th, blockade, restraint, color complex, trapped pieces, development and so on

搜索控制器实现了一个最小窗口alpha-beta搜索算法(minimum-window alpha-beta search algorithm),也称为alpha-beta剪枝算法,能快速削减搜索的规模。

深蓝的软件也是专门设计用于与硬件协同工作的。软件部分负责调度最多32个象棋芯片并行搜索,并负责对大范围规划的局面进行软件评估。深蓝的软件还连接了“仅剩5子”的残局数据库,一旦出现仅剩5子的残局,就会直接从这个数据库中搜索最佳走法。软件中还包含了从30万局棋中抽取出来的开局书,并且工程师还不断优化其中记录的开局走法。

AlphaGo的算法

AlphaGo是一个能够运行在通用硬件之上的纯软件程序。据称其中 部分程序使用了TensorFlow 。

AlphaGo的核心算法基于机器学习。在训练的第一阶段,AlphaGo仅仅根据彼此无关的盘面信息模仿专家棋手的走法。通过3000万个盘面数据训练一个13层的监督式策略网络,这个神经网络随后就能以超过50%的精度预测人类专家的落子。值得注意的是,在这一阶段,AlphaGo对于围棋规则一无所知,只是毫无目的地模仿而已。尽管如此,由于违反规则的走法(例如“自杀”)专家棋手不会走出,所以AlphaGo也相当于学会了遵守围棋规则。

在训练的第二阶段,AlphaGo开始与自己下棋:将过往训练迭代中的策略网络与当前的策略网络对弈,并将对弈过程用于自我强化训练。在这一阶段,引入了唯一的围棋规则:对获胜的棋局加以奖励。经过这一阶段的训练,AlphaGo已经超过所有围棋软件,对弈当时最强的开源围棋软件Pachi可以达到85%胜率。

在训练的第三阶段,AlphaGo在自我对弈中,从不同棋局中采样不同位置生成3000万个新的训练数据,用以训练局面评估函数。经过三阶段训练的策略网络被混和进蒙特卡洛树搜索算法,从而在比赛进行过程中预测棋局未来可能的发展方式、并对各种可能的未来局面进行评估。

在整个算法中,只有“获胜”这个概念作为围棋规则被输入训练过程,除此之外AlphaGo对于围棋规则一无所知,更没有高级围棋专门概念(例如“定式”)。尤其是第一阶段的训练,完全基于简单的盘面信息训练达到相当可观的预测效果,这一过程在很多需要“预测”这一功能的领域具有显著的意义。

规模与复用

深蓝的一枚象棋芯片包含大约1百万个三极管,其中逻辑三极管45万个、存储三极管55万个。该芯片采用0.6微米CMOS技术,主频30~40兆赫。1997年与卡斯帕罗夫对弈并获胜的深蓝II是一台30个节点的RS/6000超级计算机,每个节点上部署16枚象棋芯片,共计480枚象棋芯片并发。由于内嵌大量国际象棋专用逻辑、且采用硬件方式实现,深蓝对于IBM后续的人工智能(例如Watson)并无太多可复用性。

AlphaGo使用的硬件则要强大得多。与李世乭对弈的分布式版本使用了1920颗CPU和280颗GPU,并且据称该版本的AlphaGo 已经使用了Google自制的“张量处理单元” (TPU)。Google宣称这种芯片专门针对TensorFlow优化,其计算效率比GPU高出一个数量级。由于几乎不包含领域特定知识、且运行于通用硬件基础上,AlphaGo的软件据信非常简单( 一个开源项目 仅用约1200行代码就实现了AlphaGo的核心算法),且其中大部分算法可以解决用于其它领域的机器学习问题。

参考资料

  • Campbell, M., Hoane Jr., a. J., & Hsu, F. (2002). Deep Blue. Artificial Intelligence , 134(1-2), 57–83.
  • Ferrucci, D., Brown, E., Chu-Carroll, J., Fan, J., Gondek, D., Kalyanpur, A. a., … Welty, C. (2010). Building Watson: An Overview of the DeepQA Project. AI Magazine , 31(3), 59–79.
  • Hsu, F., Campbell, M., & Hoane, J. (1995). Deep Blue system overview. In ICS ’95: Proceedings of the 9th international conference on Supercomputing (pp. 240–244).
  • Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche, G., … Hassabis, D. (2016). Mastering the game of Go with deep neural networks and tree search. Nature , 529(7587), 484–489.
原文  http://gigix.thoughtworkers.org/2016/7/21/comparing-deep-blue-alphago/
正文到此结束
Loading...