Mitchell [8]进行了另一项研究,他使用回归分析法在黑白棋游戏中创造了一个线性评价函数。得出的程序并未达到预期的游戏水平。我们猜想,这是由于(1)他的程序未使用搜索;(2)他的程序缺乏非线性特性。 这些结果都证明线性评价函数有缺陷。但是,由于平滑性问题和需要进行过多调试,特征表方法也存在缺陷。 3.评价函数的贝叶斯学习 在本部分中,我们将介绍一种自动组合特征的算法。首先,我们先向不熟悉贝叶斯学习的读者介绍这个概念,接下来再简短介绍一下黑白棋游戏和黑白棋程序BILL。最后,我们将介绍基于贝叶斯学习的评价学习算法,这种算法适用于黑白棋游戏。 3.1.贝叶斯学习 判别函数的贝叶斯学习是一种用在模式识别中的标准方法。通常,它被用于识别和分类具体对象,例如字符、图像、语音和震波。假设采用多元正态分布,判别函数定义类别间的判定边界。在双类别问题中,这条边界上的所有点属于每一类别的可能性都相同。这条边界是由训练数据的特征向量自动计算出的, 它考虑特征的方差和协方差。该边界由两个阶段构成,即训练阶段和识别阶段。 3. 1. 1.训练阶段 该训练阶段是一个简单的参数估计阶段。需要一个已标记训练数据的数据集。每个训练样本包含一个特征向量和一个表明特征向量所属类别的标记。训练阶段的任务是估计训练数据的每个标记(或类别)的均值特征向量和协方差矩阵。 类别c的均值向量()就是每个标记为本类别的训练样本的每个特征向量的算数平均值,其计算公式如下所示: (3) 其中,是观察类别c的次数,类别c的第i个特征向量。 类别c的协方差矩阵()衡量两个特征互相协变的程度,其计算公式如下所示: 其中T是矩阵转置操作。 3.1.2.识别阶段 推导均值向量和协方差矩阵的逆矩阵公式,可得出某一分布的一般多元正态密度函数p的计算公式,如图(5)所示: 其中x是N-元特征向量,是协变矩阵的行列式,是协变矩阵的逆矩阵,是类别c的均值向量。 贝叶斯法则表明,使用判别函数可以实现最小误差率分类: 其中P(c)是类别c的先验概率。用(5)替代(6),我们可得出: 为了判别某一新特征向量属于哪一类别,计算每个类别的g,将新的输入特征向量分配给g值最大的类别。另外,如果优先使用概率(P)作出困难的决策,那么可通过归一化 g(x) 得出概率(P): 3.2.黑白棋游戏和BILL 在解释如何将贝叶斯学习应用于评价函数学习前,我们先简要介绍一下我们的试验领域,黑白棋游戏。 黑白棋游戏是一种二人(黑棋和白棋)对弈的游戏,它使用的是8 x 8的棋盘。游戏开始前先按图3布置棋盘。黑棋先在棋盘的任一格子上走一步黑色棋子(黑色面向上的棋子),黑棋可以使白棋翻转。这个黑棋与任何其他黑棋之间的每个被俘获的白棋都要翻转为黑棋。双方交替在棋盘上落子,直到一方无棋步可下。棋盘上棋子最多那一方的就为获胜方。 黑白棋游戏一直都是一种非常适合计算机实现的游戏,因为它相对较小的分支因子,以及游戏规则的编程较为容易。这种容易是由于黑白棋游戏对于人类玩家较为难玩。黑白棋游戏难玩是因为每走一步后棋盘局势会发生非常大的改变,某些策略是违反直觉的。
图3(a)显示了黑白棋棋盘的初始布置以及格子的标准名称;图(b)显示了一个简单的棋局中,移动黑棋到c6、d6、d2、e6和g2的合规走法;图(c)显示了黑棋走到e6后的棋局。 1981年,Rosenbloom [11]证明了编写世界冠军水平的黑白棋游戏程序的可能性。IAGO的评价包含边稳定性、机动性和潜在机动性。在1986年,Lee和Mahajan [7]编写的另一个程序BILL连续战胜了IAGO。BILL在1986年北美锦标赛中获得了第二名的成绩,它是世界上最优秀的黑白棋玩家之一。BILL的游戏水平归功于它使用的评价函数高效且准确,这个评价函数利用预先编辑的知识使用特征表。BILL 2.0使用四组特征表,也就是四个特征。这些特征为: (1) 加权当前机动性衡量玩家每一步棋的数量和质量。所有的棋步都使用特征表,对较差的棋步进行适当的惩罚。 (2) 加权潜在机动性衡量玩家未来棋步的优胜程度。使用考虑各棋子周围棋子的特征表。 (责任编辑:本港台直播) |