机器学习系列(8)_读《Nature》论文,看AlphaGo养成

作者:longxinchen_ml

作者: 龙心尘 && 寒小阳
时间:2016年3月。
出处:http://blog.csdn.net/longxinchen_ml/article/details/50900070
http://blog.csdn.net/han_xiaoyang/article/details/50903562
声明:版权所有,转载请联系作者并注明出处

1.文章声明

  • 博主是围棋小白,下棋规则都记不清楚,也没有设计过棋类AI程序。这篇文章主要是阅读《Nature》论文及关于AlphaGo的相关文章的学习心得。
  • 本文的主要目的是增进分享,交流学习,方便初学者了解AlphaGo中的算法,以及一些机器学习中的常见思路。真正的工程实现过程远比本文介绍得复杂。
  • 本文更多是启发式地进行阐述与分析,包括一些作者结合自己的理解进行的简化处理。
  • 文章中不严谨和理解不当之处,欢迎大家批评指出,我们努力修改完善。

2.围棋的业务特点

机器学习的第一步都是先了解业务。围棋的业务特点包括其基本规则、对弈特性和下棋的典型思路。根据这些业务特点,我们可以分阶段实现我们的围棋算法。

2.1 围棋的基本规则

  • 使用方形格状棋盘及黑白二色圆形棋子进行对弈,
  • 棋盘上有纵横各19条直线将棋盘分成361个交叉点,棋子走在交叉点上,
  • 双方交替行棋,落子后不能移动,
  • 以围地多者为胜。
  • 并且双方可以相互吃子(提子),只要我方棋子将对方某一片紧邻的棋子周围围住,就可以将对方这片棋子吃掉。

2.2 对弈特性

基于以上规则,围棋对弈过程中有以下特性:

  • 不像象棋、军棋那样盘面上的棋子越走越少,而是越走越多。所以一局棋从开始到结束,用一张标记好走棋顺序的棋谱就能保存绝大部分下棋的信息,是一个时间序列。如下图就是《Nature》论文中的樊麾与AlphaGo对弈的一个棋谱:


    棋谱

  • 对弈从开局到中局变化都很大,尤其是中局,往往是一着不慎,满盘皆输。用数学的描述叫做估值函数(得分函数)非常不平滑

  • 到收尾阶段,由于棋盘上总体的棋子是越来越多的,其变化就越来越少。可以看成是一个动态收敛的过程。
  • 状态空间非常大,约为2×10170,超过目前的计算机的计算能力,无法通过暴力穷举解决。

2.3 下围棋的基本思路

而人类不需要搜索这么多状态空间也能够下好围棋,说明还是有规律的,只是这些规律比较抽象。我们机器学习算法就是要尽量找出人类下围棋的一些规律。我们可以简单总结一些人类下围棋典型思路如下:

  • 首先是明确基本规则,这个方便。
  • 其次是掌握一些基本“定式”,也就是在一个给定的局面下人类一般会怎么走,这个过程不涉及优劣的判断,也比较难以用确定性的规则描述。
  • 基于对棋局未来演化情况的评估,决定当今当下的下棋策略。所谓“手下一着子,心想三步棋”。这是围棋最复杂的情况。

2.4 分阶段实现下棋算法

基于以上这些初步了解,我们可以分阶段实现我们的下棋算法:

  • 第一步是学会人类下棋的一般定式,形成一些优