由于黑白棋在距离游戏结束还有很多棋步可走时可以达成终局,我们可以根据某一程序选择(无需搜索到最终节点)得出最佳结果的棋步的频率,来推断出该程序的性能。这个方法存在一个问题:当达到终局时,已知的黑白棋策略会变得不再那么适用,而且有时还需走出违反直觉的棋步。为了尽可能减小这个问题,我们获取了一个有63个获胜位置并且剩余20-24步可走的棋局数据库,剩下的每个棋步都可以得出领先最多分数的获胜结果。这个数据库是由Clarence Hewlett建立的硬件终局搜索器生成的[6]。 BILL的线性版本个贝叶斯学习版本都设定了这些问题,每个版本都使用3-8层的搜索得出最佳棋步。它们同意选择最佳棋步的频率如表3所示。在进行比赛的情况下,BILL可以在游戏的这个阶段大概搜索8层。因此如果问题出现在实际比赛中,那么BILL 2.0和BILL 3.0将分别解决55%和64%的问题。 表3:两个版本的BILL同意最佳棋步的概率以及确保得出最大胜出差距的棋步 为了评价这些数字,我们应知道某些最佳棋步可能仍然是违反直觉的。更为重要的是,很多棋步通常仍保留一个获胜位置,这些位置的胜出差距可能相同。不幸的是,我们没有足够的信息来估计差棋步导致失败的频率。但是上述统计数据表明,贝叶斯学习毫无疑问更好。 4.3. BILL对弈人类专家 将BILL与人类专家作对比的一种方法是在最后比较他们解决终局问题的性能。这些位置中有19个取自世界顶级高手间的六场比赛。我们发现,人类专家的棋步中正确的有九步,错误的有十步,准确率为47.36%。借助8层搜索,BILL 2.0和BILL 3.0分别破解了63%和68%的位置。这表明,两个版本的BILL的水平都高出人类专家很多。 由于上述样本太小,无法得出BILL与人类专家比较游戏水平的结论,因此我们邀请了美国排名最高的黑白棋玩家Brian Rose与BILL 3.0进行一场比赛。结果,BILL 3.0以56比8的成绩大胜Rose。 Jonathan Cerf曾在1982年表示,IAGO即使比不过最优秀的人类玩家,也与他们不相上下。由于BILL的性能要比IAGO高出很多,因此我们对BILL战胜Rose并不感到意外。 5.讨论 5.1.贝叶斯学习的优点 在本部分中,我们将通过对比贝叶斯学习和Samuel的算法来讨论贝叶斯学习的优点。表4显示了Samuel的两种算法与贝叶斯学习算法的对比情况。 表4:Samuel的算法与贝叶斯学习算法的对比
尽管这三种算法都用来解决相同问题,但是它们之间存在许多较大的差异。 第一个较大的差异就是线性。Samuel的多项式学习算法学习的是线性函数。这种算法假设所有的特征都是相互独立的,我们已经证明这种假设是不成立的。如果将两个完全相同的特征输入到他的算法中,这个算法会向这两个特征分配相同的权重,这样就会导致效用在总体上被高估。特征表表学习是一种合理的非线性近似法。 但是,正如第2.2.2小节所述,只有在对特征表的结构进行仔细安排后,特征表学习中的非线性才会发挥作用。即使这样,不同特征表的特征之间的相互关系也会丢失。如果没有为两个完全相同的特征正确安排位置,那么它们的效用仍会被高估。正因为如此,需要通过人为干预来估计冗余度和确定特征表结构。 在最糟糕的情况下,所有的特征都将在很大程度上相互关联,并且必须放在相同的特征表中。显然,这种算法并不理想,因为这个特征表将会扩大到不合理的程度。但是,贝叶斯学习方法可以通过考虑特征对之间的协变来理解非线性关系。这种算法总是能够发现冗余特征并解释特征间的所有交叠。 在上一部分中,我们在非线性评价函数的使用中看到了巨大的性能提升。为了说明线性评价函数不够理想的原因,图5显示了每对特征间的相互关系。尽管这四个特征分别取自于棋盘的不同特性,但是我们发现它们高度相关,尤其是机动性、潜在机动性和加权格子。如果对这些高度相关的特征进行线性组合,后果将会不堪设想。 (责任编辑:本港台直播) |