• 精选
  • 会员

权重改变引起的涌现结果

2024年12月25日  来源:涌现 作者:约翰·霍兰德 提供人:It8933......

即使我们已经充分理解了塞缪尔的权重改变技术,但该技术带来的一些重要影响仍可能被忽略。这大致可包括以下五个方面:

· 子目标。尽管评估函数似乎并未直接提及子目标,但事实上,当没有明显的克敌制胜或领先对手的走法时,评估函数确实提供了对子目标做出预测的巧妙思考方向。

· 预测对手。如果机器棋手要预测对手的走法,它必须为对手确定一种策略。评估函数能为对手可能的反应提供指导。

· 通往最大最小策略。尽管评估函数V只能间接地使对手可能造成的最大破坏最小化(最大最小策略),但是它确实已经领悟了这个理念的核心思想。

· 自举程序。机器棋手可以通过与自己博弈来提升棋艺。

· 展望。在了解博弈规则的前提下,机器棋手可以利用对手行为的模型预测几步以后的情况,并根据预测结果改变权重。

下面我将详细讨论上述每一个问题,分别说明它们是如何从改变权重的基本技术中涌现出来的。

子目标

我们现在知道,塞缪尔的国际跳棋程序是通过从博弈过程中获得的信息来进行学习的,它无须等待最终的奖赏,也无须专家的指导。乍一看,子目标的概念在此并无用武之地。事实上,如果不存在通往终极目标的明显路径,子目标的确是关键的过渡步骤,那么它是如何成为这一关键步骤的呢?

和我们猜测的一样,答案是塞缪尔的国际跳棋程序扩展了子目标的作用,只是没有明确说明而已。进一步的研究揭示了国际跳棋程序精妙所在,也揭示出子目标的深刻本质。

我们还是从“领先棋子数”这一特征开始。由于该特征与博弈的胜利紧密相关,因此它在学习程序中获得了较高的权重。此外,在一场势均力敌的博弈中,“领先棋子数”的值接近0,因为如果其中任何一方在棋子数上领先的话,博弈结果就不可能是平局。倘若棋局s处的所有走法都通向平局,那领先棋子数对于棋手在棋局s处的选择影响将会很小。在这种情况下应该如何应对呢?

此时,就轮到那些与胜局没有紧密关系的特征发挥作用了。一些怪异的特征,如前面提到的棋子的“中心力矩”,可能具有非零值。在一场几乎势均力敌的博弈中,尽管这个特征的权重比较小,但是它终究比那些具有接近零值的重要特征对V值的影响要大。当博弈接近平局时,由V所决定的策略,会根据那些具有非零值的怪异特征来选定相应的棋局。也就是说,当机器棋手无法根据那些值接近零的特征做出选择时,则需要根据这些具有非零值的特征来决定(刻画)相应的选择。这样一来,当通往胜局的路径不是很明晰时,就要由那些怪异的特征来确定子目标,决定该怎么走。

当无法根据一些重要特征做出选择时,机器棋手必须能够识别哪些怪异特征更有效。那些同样具有平均和弥补作用的特征在这里也会发挥作用,因为它们是当下较为明显的特征。由于这些怪异特征和胜局的关系不太紧密,所以被赋予的权重较小。其中有些特征是完全不可靠的,这些特征最终的权重会接近零,并且它们对博弈过程影响甚微。而其他特征则可能含有重要的信息,在接近平局时,有助于刻画正确的行动。后一种特征会被赋予非零的权重,在没有更显著的特征来确定行动的前提下,它们正是V寻找的对象。

预测对手

现在,我们开始解决为机器棋手的对手建模的问题。因为机器棋手会遇到不同的对手,它即便采取同样的行动也会导致不同的结局。然而,通过关注那些不够理想的结果——最大最小策略,国际跳棋程序能够在一定程度上克服这个困难。

不理想的结果可能是以下两个原因所致:机器棋手的表现比较糟糕,或者对手的表现非常出色。无论是哪种情况,我们都会很好地修正国际跳棋程序,即为通往这个结果的棋局赋予较小的值,有可能是负值。此外,理想的结果也会带来不明朗的情况。理想结果的获得可能是因为机器棋手表现出色,也可能是因为对手的表现太糟糕。如果是对手太差而使得结果较为理想,那么就不必做出任何调整。由于对手也在不断地学习提高,或者其他不同对手的棋艺比较出色,所以同样的博弈序列往往不会重复出现。

鉴于以上原因,跳棋程序应该把重点放在避免不利的结果上,而不是直接寻求理想的结果。当无法保持理想结果时,无论是哪种情况所致,不利的结果都应当竭力避免。当V的预测值和随后的预测值相比偏高时,只需调整V中的权重就能实现上述目标。如同人工智能国际象棋专家汉斯·伯利纳(Hans Berliner)于1978年所说的那样,理想博弈的秘诀在于避免重大失误。

这个修正完善了修改权重的规则。只有沿着V所选择的路径会出现棋局s',而s'被赋予了更低值时,我们才用前面提到的启发式方法来修正Vs)中的权重。也就是说,V中的权重只有在Vs)比Vs')大得多时才会得到修正,反之,当Vs)比Vs')小得多时,则不需要修正。

通往最大最小策略

那么,对于国际跳棋来说,如何使用这个规则来得到最大最小策略呢?假设我们有充裕的时间和一个合适的特征集,如果能够证明该方法可以产生最大最小策略,那最好不过了。可惜,这样的证据并不存在。我们能做的只不过是给出一个似是而非的论断:局部的行动“近似于遵循最大最小策略”。

主要结论已经得出,我们可以通过从博弈结束时与可靠预测对应的走法到更早的走法,逐步“回溯”预测。在这个过程中,不断地调整V,为那些意外获得较小值的棋局之前的棋局赋予较小值。由此,V所定义的策略避免了预测失误带来的损失。而且,由于会导致非常不利的结果,那些被赋予绝对值较大的负值的特征和其他情况下权重也为负值的特征一样,都是我们应该避免使用的。这和伯利纳关于避免严重失误的建议是一致的。

随着经验的积累,在越来越多的情况下,我们将会根据这个办法来确定行动,避免失误。也就是说,具有最高值的选择,目前将不会导致那些不利的结果。筛选后的选择是那些在每一步走法中,由V确定的策略选择的合规棋步。这些走法将通往具有最高预测值的棋局。通过这种方式,国际跳棋程序就达到了最大最小策略中的最大效应,获得了希望的结果:使对手希望对你造成的最大破坏最小化。

自举程序

塞缪尔调整权重的程序能够充分发挥最大最小策略的作用,从而使机器棋手可以通过自举程序逐步提高棋艺。将具有固定权重的版本,作为具有学习能力版本的机器棋手的对手进行练习,这样便可通过自举程序来提高棋艺。经过一段时间之后,具有学习能力的机器棋手和具有固定权重的对手对抗时,将轻松立于不败之地。这时,将具有学习能力的机器棋手的权重赋予它的对手,然后不断地重复这个过程。

通过这种方法,具有学习能力的机器棋手面对的是棋艺会不断提高的对手。新的博弈序列不断被探索,具有学习能力的机器棋手的棋艺也不断提升。因为这样做的目的是发现并避免落入棋艺高超的对手设下的陷阱,因此机器棋手通过自举程序产生的策略,可以避免被对手的开局弃子法、陷阱以及其他看似有利实为陷阱的招数所迷惑。

展望

到目前为止,我们只讨论了一种使用评估函数V的方法:在博弈过程中的每一个决策点,根据V的预测来选择下一步的走法。随着博弈的进行,当V每次所做的预测出现实质性改变——变得更糟时,V的权重将相应发生改变。事实上,还有另一种使用V的方法,其中涉及一项被称作“展望”的技术。

借助展望技术,机器棋手能够使用博弈规则从当前位置生成博弈树的一部分(见图4-4)。它先生成从当前位置能够直接得到的棋局,然后再生成这些棋局通向的各个棋局,以此类推。也就是说,当前位置是展望树的根节点,程序在允许的时间范围内产生尽可能多的合理节点。我们知道,各种走法能迅速生成一棵枝繁叶茂的树,因此,当塞缪尔进行验证时,他的国际跳棋程序在所有可能的走法序列上只能展望到五六层的深度。

 

图4-4 展望和最大最小策略

生成展望树之后,机器棋手把评估函数V应用到生成树的终节点,即展望树的叶节点处。这样,机器棋手无须真正执行走法序列,就能预测未来的种种可能性。特别是,在有限的展望跨度内,程序能够估计出对手所有可能反应的结果。借助这些信息,机器棋手得到的启发是,后面的估计要比前面的更加可信。

从展望树的叶节点开始,机器棋手一层一层地返回当前位置,也就是展望树的根节点。在这些层次中,当轮到对手选择走法时,如同前面提到的那样,机器棋手假定对手将会采取对自己最为不利的走法,并且假定对手拥有和自己完全一样的知识——清楚地了解V以及它的特征和权重。

相应地,机器棋手假定对手总是选择具备最小V值的走法,因为在跳棋程序中,对机器棋手不利的选择正是对对手有利的,反之亦然。简言之,塞缪尔使用评估函数V来为对手的选择建模,和确定机器棋手的策略一样。这样,程序最终的结果正是选出一个走法序列,这个走法序列恰恰是它根据评估函数V做出的局部最大最小化的选择(见图4-4):在展望树的范围内,国际跳棋程序确实最小化了V所能预测的最大破坏。

有了这些,机器棋手就可以通过展望技术比较展望树根节点r的值,以及按照最大最小策略选出的叶节点l的值。利用刚才讨论过的实战技术,改变V的权重从而使Vr)能够越来越准确地预测出Vl)。通过这样的方式,机器棋手就能够在真正执行走法序列之前有效地改变它的权重。

如涉及版权,请著作权人与本网站联系,删除或支付费用事宜。

0000