风靡全球的机器学习，70年前诞生于一款跳棋小游戏

今天，人工智能的应用已经渗入我们生活的方方面面，这是一个人工智能的时代。

而人工智能的核心是机器学习，或许你不知道的是，它诞生于一种跳棋游戏。

本文摘录自中信出版集团出版的算法科普书《算法简史：从美索不达米亚到人工智能时代》。

学习能力是人类智能的核心。相比之下，早期的计算机只能存储和提取数据。

学习是完全不同的东西，学习是一种基于经验改进行为的能力。孩子通过模仿大人和反复试错来学习走路。一个婴儿蹒跚学步，刚开始时步态不稳，但随着协调和运动能力逐渐提升，最终能够熟练地走路。

1956年2月24日，第一个用来展示学习能力的计算机程序在公共电视节目上公布。

这个程序是由IBM的亚瑟·塞缪尔（Arthur Samuel）编写的。这是一个玩国际跳棋的程序，电视演示给人留下了深刻的印象，IBM的股价在第二天上涨了15个百分点。

塞缪尔1901年出生在美国堪萨斯州。在获得了加州理工学院的电子工程硕士学位后，他加入了贝尔实验室。第二次世界大战后，他加入伊利诺伊大学担任教授职位。尽管这所学校没有计算机，塞缪尔还是开始研究玩国际跳棋的算法。3年后，他加入了IBM，终于弄到了一台真正的计算机，可以开展更加深入的研究。

机器学习的发明者亚瑟·塞缪尔，1956年

1959年，塞缪尔终于发表了一篇论文，描述他的新国际跳棋程序。这篇论文的低调标题——《利用跳棋游戏进行机器学习的一些研究》——掩盖了其思想的重要性。

塞缪尔的程序使用了一种巧妙的评分算法。算法对各种会用到的特征（feature）进行打分。特征是指任何表明一个棋局的长处或弱点的东西。

两个对手棋盘上棋子数量的差异就是一种特征。

棋子的相对位置也是一种特征。战略层面的元素也被认为是特征，比如移动的自由度或对棋盘中心区的掌控程度。

每个特征都有评分。给定特征的得分要乘以权重（weight）。将各个评分结果值加在一起，就得到了当下棋局的总得分。

权重决定了每个特征的相对重要性。权重可以是正的也可以是负的。正权重意味着该特征对计算机玩家有利。负权重意味着该特征降低了计算机获胜的可能性。

权重越大，说明某一特征对总分的影响力越大。然而，低权重的多个特征可能结合在一起影响总体得分，从而影响最终决策。

综上所述，塞缪尔的棋局评价方法的工作原理如下：

以一个棋局作为输入。

将总分设置为零。

对每个特征重复以下步骤：

测量棋盘上的某个特征。

计算该特征的得分。

乘以特征的权重。

把计算结果加到总分中。

当所有特征都评分完成后，停止重复。

输出总分。

这种评分机制对塞缪尔的算法至关重要。分数越能准确地反映出计算机获胜的概率，程序做出的决策就越好。选择用于分析的最优特征组合很重要。

除此之外，确定最佳权重分配也是必不可少的。然而，为权重找到最佳值是一个很棘手的任务。

塞缪尔设计了一个机器学习（machine learning）算法来确定最优权重。最开始，算法猜测权重是多少。然后，计算机与自己玩很多局游戏。

程序的一个副本下白棋，另一个下黑棋。随着游戏的进行，算法会调整权重，以便计算出的分数能更准确地预测游戏的结局。

如果程序获胜，对决策做出积极贡献的权重会得到一点点提升。类似地，任何起到负面作用的权重都将降低。这强化（reinforce）了获胜行为。

实际上，这是在鼓励程序在未来以更贴近这样的风格下棋。如果输了游戏，就会发生相反的情况。这会阻止程序在接下来的游戏中以相同的方式下棋。在很多次游戏后，学习算法得以对程序的玩法做出精细的调整。

与人工选择权重相比，塞缪尔的算法具有两方面的优势。

第一，计算机永远不会忘记——每一步棋都会影响到权重。

第二，计算机可以与自己进行多次游戏，远远超过人类能玩的次数。因此，在学习过程当中可以获得更多的信息。

塞缪尔对机器学习的开发是颠覆性的。以前，想改变程序的行为需要手动修改指令列表。相比之下，塞缪尔的程序所做的决策是由权重控制的，权重是简单的数值。

因此，程序的行为可以通过改变权重来调整。程序代码不需要修改。更改程序代码很困难，但更改几个权重数值是很容易的，该精妙的概念使学习过程的自动化成为可能。

此外，塞缪尔还加入了一个极小极大步骤（minimax）来选择走法。该算法执行一个前瞻预测来生成一个包含所有可能的未来走法的树。

在前瞻预测的结尾，计算出所有棋局的得分。我们假设双方都能走出好棋。为了实现这一点，算法会回溯包含所有可能走法的树。

程序从前瞻预测树的叶子处开始回溯。轮到自己走棋时，回溯算法会选择能够获得最高得分的走法。轮到对手走棋时，程序会选择得分最低的一着。

在每个决策点上，与所选择走法相关联的分数会返回到上一节点。当这个回溯过程抵达树的根部时，程序会使走法与最高回溯分数相关联。

极小极大步骤的运行如下：

以可能走法的树作为输入。

从倒数第二个层级开始。

对每一层级重复以下步骤：

对该层级的每个节点重复如下操作：

如果轮到计算机走棋，

那么就选择得分最高的走法，

否则选择得分最低的走法。

将极小极大得分值复制到当前节点。

检查完这一层级中的所有节点后，停止重复。

当到达树的根部时停止重复。

输出具有最大回溯分数的走法。

采用极小极大算法获得回溯评分的前瞻预测树

想象一个简单的两层级前瞻预测树。这个树包含计算机的潜在后续走法和其对手的可能应对走法。检查树的叶子（第2步棋层级）处的得分，以找到每个子树上的最小值。

这反映了对手从自己的角度选择的最佳走法。那些最低的分数被复制到上面一层的节点（第1步棋层级）。于是分数1、3、7、5、6被放置在第1步棋层级的各个节点上。

下一步，算法要选择得分最高的走法。这意味着计算机站在自己的立场上选择最好的走法。因此，最大值7被复制回树的根部。如果对手是一名优秀的棋手，那么选择走出7分的棋局是最好的选择。这步走法迫使对手在得分为8、7和10的位置之间进行选择。对手能做的最好的选择就是接受7分的这个位置。

1962年，塞缪尔的国际跳棋程序与盲人跳棋大师罗伯特·尼利（Robert Nealey）进行了一场较量。

人们为计算机的获胜而欢呼，但尼利甚至都不是一名州冠军。30多年后的1994年，计算机程序才终于打败国际跳棋世界冠军。