游戏的好处就在于，其规则都有明确的定义，玩家对棋盘十分熟悉，决策也不像现实世界中那样复杂，但又不失挑战性。1959 年，在商业数字计算机发展的早期，IBM 的机器学习先驱亚瑟·塞缪尔（Arthur Samuel）编写了一个擅长玩国际跳棋的程序，在宣布其诞生的当天，IBM 的股票就获得了巨大的收益。西洋跳棋则相对容易。塞缪尔的程序利用了代价函数来评估对局中不同布阵的优劣情况，这一点跟以前的游戏程序很相似。该程序是在IBM 第一款真空管商用计算机IBM 701 上运行的，它在一个方面的创新令人印象深刻：通过跟自己对弈，学会了下棋。

在转到位于纽约约克敦海茨的IBM 托马斯·J.沃森研究中心之前，杰拉德·特索罗在位于伊利诺伊大学香槟分校的复杂系统研究中心，与我一起训练神经网络玩西洋双陆棋（见图10-1）。2 我们的方法是，使用专家监督来训练反向传播网络，以评估当前的布局和可能的摆法。这种方法的缺陷在于，该程序永远比不过专家，而专家的水平并未达到世界冠军的级别。然而通过自我对局，网络可能会有更出色的表现。当时自我对局面临的问题是，在比赛结束时，唯一的学习信号就是赢或输。但是当一方获胜时，应该归功于之前若干步骤中的哪些步骤呢？这被称为“时域贡献度分配问题”（temporal credit assignment problem）。

图10-1　西洋双陆棋棋板。西洋双陆棋是一种通过朝着终点按步走棋来分出胜负的游戏，红色棋子和黑色棋子的移动方向相反（如箭头所示）。图中标注了游戏的起始位置。同时掷出两个骰子，得到的两个数字表示两个棋子可以向前移动的距离。

有一种可以解决这种时域贡献度分配问题的学习算法，是由理查德·萨顿（Richard Sutton）于1988年发明的。3他当时正在与他的博士生导师、马萨诸塞大学阿姆赫斯特分校的安德鲁·巴托（Andrew Barto），共同解决强化学习领域中的问题。强化学习（reinforcement learning）是受动物实验中的关联学习（associative learning）所启发衍生出的一个机器学习研究分支领域（见图10-2）。深度学习的唯一工作是将输入转换为输出。强化网络与之不同，它会与环境进行闭环交互，接收传感器输入，做出决定并采取行动。强化学习的基础，是观察动物怎样通过探索环境中的各种选择并从结果中学习，从而在不确定的条件中解决难题。随着学习能力的提高，探索过程逐渐减少，最终会直接利用学习过程中发现的最佳策略。

图10-2　强化学习场景。智能体（agent）通过采取行动（actions）和进行观察（observation）来积极探索环境。如果行动成功，执行器将得到奖励（rewards）。该过程的目标，是通过学习怎样采取行动来最大化可能获得的奖励。

假设你必须做出一系列决定才能达成目标。如果你已经知道所有潜在的选择和它们各自可能带来的奖励，你就可以使用搜索算法——具体来说，也就是理查德·贝尔曼（Richard Bellman）的动态规划算法（algorithm for dynamic programming），4即找出能最大化未来奖励的选择集。但是随着可能的选择越来越多，问题的规模也呈指数级增长，这被称为“维数灾难”（curse of dimensionality），本章的开头已经对其进行了说明。但是，如果在选择前没有获得关于选择结果的所有信息，你就要学会即时做出最好的选择。这就是所谓的“在线学习”（online learning）。

理查德·萨顿（见图10-3）的在线学习算法依赖于期望奖励和实际奖励之间的差异（见方框10.1）。在时间差分学习（temporal difference learning）中，你需要估计出在当前状态下做出行动有可能带来的长期奖励（基于已得到的奖励而得出的较好估计），以及下一个状态中潜在的长期奖励，并将二者相比较。当前状态得到了实际奖励，因此估计会更准确。通过让之前的估计更接近改进后的估计，你做出的决定也会越来越好。存在一个价值网络，能够估算出棋盘每个位置上的未来奖励，对该网络进行的更新则被用于决定下一步的行动。在你有足够的时间来探索不同的可能性后，时间差分算法会收敛于最佳规则，指导如何在给定状态下做出决策。维数灾难是可以避免的，因为事实上，在棋盘所有可能的位置中有一小部分会被访问，但这足以为新对局中类似的棋盘位置制定出好的策略。

图10-3　2006 年在加拿大埃德蒙顿阿尔伯塔大学的理查德·萨顿。他教会了我们获取未来奖励的学习方法。理查德是一位癌症幸存者，他在强化学习方面一直是领军人物，并在持续不断地开发创新型的算法。他总是很慷慨地和别人交流，分享自己的见解，同领域的每个人对此都非常赞赏。他和安德鲁·巴托合著的书《强化学习导论》（Reinforcement Learning：An Introduction）是该领域的经典著作之一。此书的第二版在互联网上可以免费获取。图片来源：理查德·萨顿。

杰拉德·特索罗的程序名为“TD-Gammon”，内建了西洋双陆棋棋盘和规则的重要特征，但它并不知道怎么下好每一步棋。在学习的初始阶段，这些棋步是随机的，但最终某一方会赢，并得到最终奖励。西洋双陆棋的赢家是第一个将其所有棋子从棋盘上“剔除”出来的玩家。

10.1

时间差分学习(www.daowen.com)

这个蜜蜂大脑的模型能够选择行动（比如落在一朵花上），以最大化未来所有的折扣奖励（discounted rewards）：

R（t）=rt+1+γrt+2+γ2 rt+3+…

rt+1 是在时间t+1 时的奖励，0＜γ＜1 是折扣系数。基于当前感官输入s（t）的预测的未来奖励是通过神经元P计算出来的：

Pt（s）=wy sy+wb sb

来自黄色（Y）花朵和蓝色（B）花朵的传感器输入被分别以wy 和wb 加权。位于时间t 的奖励预测误差δ（t）计算方法如下：

δt = rt +γPt（st）- Pt（st - 1）

rt 代表当前的奖励。每个权重的改变如下：

δwt =αδt st - 1

α代表学习速率。如果当前奖励大于预测奖励，且δt 是正值，奖励出现之前的感官输入的权重就会增加，但是如果当前奖励小于预测奖励，且δt是负值，感官输入的权重就会减少。

图片改编自：Montague，P.R.and Sejnowski，T.J.，The Predictive Brain：Temporal Coincidence and Tempo al Order in Synaptic Learning Mechanisms，figure 6 A。

由于唯一的实际奖励发生在游戏结束时，你可能会合理地推测TD-Gammon 将首先学习游戏结局，然后是游戏的中间部分，最后是开局。这些实际上是发生在“表格强化学习”（tabular reinforcement learning）的过程，其状态空间中的每个状态都对应着一个数值表。但它与神经网络完全不同——神经网络快速锁定输入特征中的简单可靠信号，接着锁定后期较复杂、不太可靠的输入信号。TD-Gammon 学习的第一个概念是“拿走棋子”，可以通过对表示拿走棋子数目的输入特征添加正的权重来实现。第二个概念是“击中对手棋子”——这是一个在所有阶段效果都相当不错的启发式做法，一部分输入单元对被击中的对手棋子的数目进行了编码，可以通过为这些单元加上正权重进行学习。第三个概念“避免被击中”，是对第二个概念的一种自然反应，可以通过对可能被击中的单个棋子施加负权重来学习。第四个概念是通过“积累积分”来阻止对手前进，通过对积分输入赋予正权重来学习。理解这些基本概念需要完成几千场的训练棋局。通过一万场棋局，TD-Gammon 会学习到中级概念；通过10 万场棋局，它开始学习高级概念；经历了100 万场棋局后，它已经学会了冠军级的概念，或者超越了20 世纪90 年代初人类玩家的水平。

杰拉德·特索罗于1992 年向全世界展示了TD-Gammon，它的表现让我和其他同行都感到非常惊讶。5 这个程序的价值函数（value function）是一个具有80 个隐藏单元的反向传播网络。在30 万场比赛之后，该程序击败了杰拉德，于是他联系了著名的西洋双陆棋世界冠军选手兼作家比尔·罗伯特（Bill Robertie），并邀请他来约克敦海茨的IBM 跟TD-Gammon 对局。罗伯特赢得了大部分的棋局，但是对在一些胜算较高的对局中落败不免感到惊讶，随后他宣布这是他对决过的最好的西洋双陆棋程序。TD-Gammon 展现了一些他从未见过的棋路；经过一番仔细研究，这些棋路被证明可以在总体上提升人类玩家的水平。当该程序与自己对局达到150 万次时，罗伯特回来了，而且非常惊讶于自己居然只跟TD-Gammon 打了个平手。它的水平突飞猛进，罗伯特觉得它已经达到了人类冠军的水平。西洋双陆棋专家基特·伍尔西（Kit Woolsey）发现，当时TD-Gammon 对于应该打安全牌（低风险/低奖励）还是走险着（高风险/高奖励）的判断，比他见过的任何人都要准确。虽然150 万局的训练可能看起来已经很多了，但它只代表了所有1020个可能的西洋双陆棋板位置的无限小部分；这要求TD-Gammon的几乎每一步棋都能推广到新的棋板位置。

TD-Gammon 并没有像IBM 的“深蓝”那样受到公众的关注，后者在1997 年的国际象棋比赛中击败了加里·卡斯帕罗夫（Gary Kasparov）。国际象棋比西洋双陆棋要困难得多，卡斯帕罗夫当时是国际象棋的世界冠军。但在某些方面，TD-Gammon 是一个令人印象更加深刻的成就。首先，TD-Gammon 使用模式识别技术来教会自己如何下棋，这与人类学习的风格十分相似，而“深蓝”则通过暴力算法（brute force）获得胜利，使用特制硬件，比任何人类棋手都能预见到更多可能的棋路。其次，TD-Gammon 也很有创意，使用了人类从未见过的微妙策略和位置决策。这样一来，TD-Gammon 也提高了人类的竞技水平。这一成就是人工智能历史上的一道分水岭，因为我们从一个人工智能程序中学习到了新东西。该程序教会了自己如何在一个人类熟稔的领域中掌握一种复杂的策略，这种新策略值得人们关注和思考。