5.5　学会改进

知识和搜索的混合是一个很好的折中——尽可能多地学习（知识），然后通过各种选项（搜索）将其应用于计划。我们知道国际象棋大师是这样做的：他们识别特定的场景，然后进行小型搜索来测试选项。但是基本的电脑游戏方法有一个严重的局限性——它们不包括学习。如果你第二次和它们玩同样的游戏，它们会以完全相同的方式输掉或获胜。因此，接下来的开发是实现某种形式的学习，使性能能够随着经验而提高。这一领域的一个重要先驱是Arthur Samuel，他写了两篇开创性论文，是关于电脑学习下跳棋方面的（Samuel，1959，1967）。西洋跳棋，在英国被称为国际象棋（draughts），是一种在棋盘上玩的棋类游戏，有12个黑色棋子和12个白色棋子。这不是一种容易的游戏，但它比国际象棋容易得多。

跳棋游戏的完整的搜索树现在已经完全探索。在数百台计算机上进行了大量的计算，结果证明，只要双方都尽可能地发挥出水平，游戏总是以平局告终。这一结果在2007年遵循了所有完美的走法，处理了1014个棋盘位置（Schaeffer et al.，2007）。那就是10万亿个棋盘位置。注意，他们只涵盖了最佳的走法，没有为所有其他走法生成搜索树——那将需要检查5000亿亿个可能的位置（5×1020）。但是，即使我们可以用今天的超级计算机来处理这一问题，也几乎不可能枚举出所有象棋的树，因为它大约有1045个位置（也就是说，1后面有45个0！）。

Samuel意识到评估函数中的混合特征可能会发生变化。例如，一个给定的函数可以计算如下位置的值：60%的物质优势，加上30%的中心控制，加上10%的捕获可能性。但是这个由数字60、30、10决定的混合体是由设计者设定的，它只是对可能是重要的东西的估计：没有人知道最佳混合体应该是什么！Samuel没有将混合体的比例固定，而是将其设为参数x，y，z，这样就可以根据游戏性能进行调整。

他的创新之处在于让两个程序相互对抗，进行更多的跳棋比赛。一个程序的参数在游戏中是固定的，而另一个程序可以在学习过程中调整参数。当学习程序比固定版本表现得更好时，它们都将被赋予新的参数，然后再进行比赛。其想法是，评估函数只会得到改进，因此它们会互相引导，得到越来越好的评估，从而提高游戏水平。

有一个虚构的故事，Samuel曾在IBM当过一段时间的夜班警卫，看守一个装满IBM 360计算机的巨大仓库，他让这些计算机通宵彼此下跳棋。（一台计算机可以在两个对手之间切换来进行完整的对局。有趣的是，这是人类很难甚至不可能做到的事情——都在一个大脑内进行！）

Samuel还开创了许多小的编程技巧和技术，它们被广泛应用于进行棋盘游戏的系统中，他的论文对于学习计算机游戏的学生来说仍然非常具有可读性和相关性。但经过10年的工作，他仍然担心自己可能没有找到最佳特征，也无法找到一种方法来“让程序产生它自己的特征”（Samuel，1967，617）。他已经自动化了几乎所有他能做的事情，包括学习特征参数，但他仍然需要自己设计实际的特征。他发现，使用正确的特征对良好的性能至关重要，而真正需要的是一种让计算机自己发现最佳和最合适特征的方法。

在他的第二篇论文中，Samuel说自动生成特征“在未来仍将像1959年那样遥远”（Samuel，1967，617）。他处理这个问题的方法是考虑尽可能多的特征，实现它们，并希望最有效的特征也包括在内。他通常会尝试大约25个特征，但经常会尝试多达40个。在学习过程中，当特征参数接近于零时，一些特征会消失；它们都是不好的特征，没有任何贡献。但是你怎么知道是否错过了一个好的特征呢？那么什么是好的特征呢？