IBM 开发 TD-Gammon

背景

双陆棋（backgammon）是一种由掷骰子决定可选走法的棋盘游戏，运气和长期策略同时起作用，一次掷骰就可能改变胜负。程序要下好它，就得在眼前得失和局面的长远价值之间做权衡。TD-Gammon 是 Gerald Tesauro 于 1990 年代在 IBM 托马斯·J·沃森研究中心（Thomas J. Watson Research Center）开发的双陆棋程序^[1]。它的名字来自它的构造：它是一个用时间差分学习（temporal-difference learning）训练的人工神经网络，具体算法是 TD-Lambda^[1]。

怎么做的

TD-Gammon 的核心是一个三层神经网络：198 个输入神经元编码棋盘局面，4 个输出神经元估计每种可能对局结果的概率^[1]。它并不是被人告知「什么样的局面是好局面」，而是通过和自己对弈、从对局结果中学习，把自己训练成双陆棋的评估函数^[3][4]。

Tesauro 在文章中描述了这类学习的一般框架：学习主体观察到一个输入状态，产生一个输出，然后得到一个标量回报；当回报延迟给出时，就出现了时间信用分配问题（temporal credit assignment problem）——要判断此前一系列决策中哪一步该记功、哪一步该记过^[3][4]。文章举出两项让这种做法变得有希望的进展：一是非线性函数逼近方法，例如决策树、样条拟合和多层感知机（multilayer perceptron）；二是 Sutton 的时间差分方法^[3][4]。

用时间差分学习的话说，网络对某个局面价值的估计，会朝着它对后续局面的估计更新，因此它学的是前后两次预测之间的差，而不是等人类为每一步标好答案。

版本与战绩

1992 年，程序发展到 2.0 版，有 80 个隐藏单元，训练了 80 万局，并带有 2 层搜索（2-ply search）^[1]。1993 年的 2.1 版用 150 万局自我对弈训练，棋力略低于当时最顶尖的人类棋手^[1]。1998 年，在一场 100 局的系列对局中，它被世界冠军击败，但分差只有 8 分^[1]。

为什么重要

TD-Gammon 的棋力大幅超过了此前所有双陆棋程序；但 Tesauro 写明，开发它的目的是探索强化学习的新想法和新途径，而不是为了赢棋^[3][4]。这个程序被设计用来检验以 TD(lambda) 训练的多层神经网络，并比较时间差分学习与「在专家标注样本上做监督训练」这两条路线^[3][4]。它还探索出了一些人类棋手没有采用的策略，推动了正确的双陆棋下法理论的发展^[1]。

1995 年 3 月 1 日，Tesauro 在《Communications of the ACM》第 38 卷第 3 期第 58–68 页发表文章介绍这项工作，当时他在位于纽约州约克敦海茨（Yorktown Heights）的 IBM 托马斯·J·沃森研究中心^[2]；该刊 1995 年 3 月号把文章排在第 38 卷第 3 期第 58 页起^[4]。

后来回看，TD-Gammon 常被举为强化学习与神经网络的早期成功案例，有关深度 Q 学习（deep Q-learning）和 AlphaGo 的论文都引用过它^[1]。对后续研究来说，它提供了一个参照点：一个几乎没有被灌输双陆棋知识的系统，靠自我对弈学习，最终下到了接近当时人类最高水平的地步^[1]。