大多数成功的博弈程序都使用全广度搜索（full-width search），这种搜索在终端节点[1, 7, 11, 14]应用一个启发评价函数。典型评价函数的形式为：

　　Eval = C1 x F1 + C2 x F2 +-...+ CnxFn, (1)

　　其中Eval 是对棋盘局面的静态评价，它是若干特征（F1，F2 . . . . . Fn）经系数（C1, C2 . . . . . Cn）加权后的线性组合。每个特征都是对棋盘局势“优势”的明确估量。在国际象棋中，合理的特征可能为棋子数优势、中心控制以及兵形。在黑白棋游戏中，合理的特征可能为机动性、边位置和棋子中间位置。

　　上文公式揭示了改进全广度搜索博弈程序的三种方法：

　　(1) 寻找更好的搜索策略

　　(2) 选择更好的特征

　　(3) 更好地组合特征

　　我们认为前两种方法本身就很好理解。研究人员提出了几种新的全广度搜索策略，例如SCOUT [10]和零窗口搜索[1]。不幸的是，这些方法只有在指数搜索空间中才能恒定的性能提升[7]。选择好的特征至关重要。但是，从专业知识中导出好的特征通常并不是很难[1]。

　　现在，最厉害的博弈程序依赖于高速的硬件而不是新搜索算法[1,3]，依赖于高效的特征分析而不是发现新的特征[1, 7]。因此我们建议，对全广度搜索和特征选择的研究已经达到饱和点，未来博弈程序的成果将在很大程度上依赖于特征组合的好坏。在本文中，我们将介绍一种基于贝叶斯学习的算法，这种算法自动组合特征。

　　和特征选择不同，特征组合是个非常不直观的过程。一方面，研究人员必须在多种策略之间建立一种不稳定的平衡（例如选择国际象棋中位置优势和棋子优势的权重）。另一方面，必须注意相关特征间的相互作用（例如国际象棋中的兵形和国王安全）。而且，研究人员总是会面临窘境，不是特征太少，就是特征太多（这其中包含相关特征和多余特征）。

　　可以自动组合特征的算法是由Samuel [12]首先提出的。他引入了一种线性评价函数学习算法，之后又设计了一种基于特征表（signature table）的非线性学习算法[13]。但是，他的算法遇到了一些问题。线性评价函数对特征间关系的理解不够充分。特征表出现由过度量化产生的平滑性问题。

　　这两种算法最大的问题是：虽然它们去除了调校系数的负担，但是却增加了新的负担，例如选择特征表结果、确定量化的范围和程度以及在学习期间选择函数调整的量和频率。调试程序所需的工作量远远超过了在专家帮助下对系数进行常规的试误法（trial-and-error）调校所需的工作量。最后，由于所需的工作量太过庞大，Samuel的算法高度领域相关。

　　在本研究中，我们报告一种新的学习算法。和一样，我们的算法学习将特征整合到评价中。但是，不像Samuel的算法那样，我们的算法没有平滑性问题，而且是全自动的，并且不需要进行任何调试。我们的算法基于贝叶斯学习[4]。

　　(1) 我们积累了大量的游戏作为训练数据。每个游戏由有两位专业玩家进行试玩。

　　(2) 我们根据某种标准将每个位置标记（手动或自动）为获胜或失败位置。本研究所使用的标准为游戏的实际结果。

　　(3) 训练程序从标记的训练数据中计算出一个贝叶斯判别函数。该函数试图识别出代表获胜或者失败位置的特征模式。已知某个位置的一组特征值，这个函数给出该位置是获胜位置的概率。

　　(4) 我们为游戏的不同阶段构建不同的分类器。

　　我们的算法有五个重要的优势：

　　(1) 学习过程是完全自动的。不需要调试任何系数或参数，也不需要对特征进行归一化。

　　(2) 假设多变量正态分布，事实证明，平方组合在训练数据上效果最佳[4]。

　　(3) 算法不仅考虑特征本身，还考虑他们互相之间如何共变。例如，如果使用的是两个相关特征，将不会同时把它们完全整合到评价中。

　　(4) 算法在评价中能够从错误信息中恢复。例如，加入一个随机特征并不会降低它的性能。