Arthur Samuel 跳棋程序

是什么

Arthur Samuel（亚瑟·塞缪尔）的跳棋程序是一个会下跳棋、并能通过下棋提高水平的程序。它之所以被记住，是因为它可运行地证明了：计算机可以被编程，使它学会下出比写这个程序的人更好的跳棋^[2]。这个程序运行在 IBM 701 上，那是 IBM 的第一台商用计算机^[1]。

由来

1949 年，Samuel 来到位于纽约州波基普西（Poughkeepsie）的 IBM，这项研究就是在这里构思并完成的^[1]。他的机器学习研究从 1949 年开始，而跳棋程序最广为人知的是 1959 年的工作^[1]。他在 IBM 701 上做出了第一个跳棋程序^[1]。

怎么学

论文摘要说，作者借助跳棋比较详细地考察了两种机器学习过程^[2]。

第一种被 Samuel 称为机械学习（rote learning）：程序把已经见过的每一个局面，连同奖励函数的终值一起记下来，这实际上等于在这些局面上加深了搜索^[1]。第二种是自我对弈，程序和自己下几千盘棋，作为另一种学习方式^[1]。他后来的程序还根据职业棋局的输入重新评估奖励函数^[1]。

给局面打分，而不是算到终局

跳棋的棋路很长，把每条路径都搜到终局并不现实。Samuel 没有这样做，而是设计了一个评分函数（scoring function），依据某一时刻棋盘上的局面打分^[1]。这个函数衡量双方获胜的机会，考虑的因素包括棋子的数量、王（king）的数量，以及棋子接近升为王（being kinged）的程度^[1]。有了它，程序只要比较各步走法所导致局面的分值，不必把每条线路都走到底。

结果

程序达到了相当不错的业余水平，是第一个在这一水平上下任何棋类游戏的程序^[1]。Samuel 一直做跳棋，直到 20 世纪 70 年代中期，他的程序已经具备挑战一位不错的业余棋手的能力^[1]。

论文

A. L. Samuel 的《Some studies in machine learning using the game of checkers》于 1959 年 7 月 1 日发表在《IBM Journal of Research and Development》第 3 卷第 3 期，第 210 至 229 页^[2]。摘要说明，文中用跳棋比较详细地考察了两种机器学习方法^[2]；摘要还写道，已经做的工作足以验证：计算机可以被编程，使它学会下出比写程序的人更好的跳棋，而且只给规则、一个方向感和一份冗余且不完整的参数表，程序在 8 到 10 小时的机器对局时间里就能学会^[2]。

为什么被记住

它的几个部件今天看来都不陌生：用一个评估函数给局面打分，而不是一直搜到棋局结束；从程序自己与自己下的棋局中学习；把见过的局面记下来。让这个跳棋程序出名的，是这些部件被拼在一起，并且做了衡量。论文的结论不是程序下得完美，而是它下得比作者本人更好，而且靠的是规则和一份粗略的参数表，而不是为每种情况写好的指令^[2]。