对抗搜索.pptx

-——比如说象棋——搜索是在博弈者双方之间进行的。任何一方在搜索时,都必须要考虑对方可能要采用的走步。对于一个优秀的博弈者来说,应考虑的不只是对方一步的走法,而是若干步的走法。这一过程一般来说是动态进行的。在考虑若干步走法以后,下了一步棋;而在对方走棋之后,还要再次考虑若干步走法,决定下一步的走法,而不是一劳永逸,搜索一次就决定了所有的走法。概述本章所讲的博弈:主要指的是类似于象棋这样的游戏问题。这类问题有以下一些特点:双人对弈,对垒的双方轮流走步。信息完备,对垒双方所得到的信息是一样的,不存在一方能看到,而另一方看不到的情况。零和。即对一方有利的棋,对另一方肯定是不利的,不存在对双方均有利、或均无利的棋。对弈的结果是一方赢,而另一方输,或者双方和棋。概述双人完备信息博弈:指两位选手对垒,轮流走步,这时每一方不仅都知道对方过去已经走过的棋步,而且还能估计出对方未来可能的走步。对弈的结果是一方赢(另一方则输),或者双方和局。这类博弈的实例有:一字棋、余一棋、西洋跳棋、国际象棋、中国象棋、围棋等。机遇性博弈:存在不可预测性的博弈,例如掷币等。例如:西洋双陆棋。Grundy博弈Grundy博弈是一个分钱币的游戏。有一堆数目为N的钱币,由两位选手轮流进行分堆,要求每个选手每次只把其中某一堆分成数目不等的两小堆。例如,选手甲把N分成两堆后,轮到选手乙就可以挑其中一堆来分。如此进行下去,直到有一位选手先无法把钱币再分成不相等的两堆时就得认输。对于这样的简单博弈问题,可以生成出它的状态空间图。这样就有可能从状态空间图中找出取胜的策略。Grundy博弈当初始钱币数为7时的状态空间图MIN代表对方走MAX代表我方走MAX存在完全取胜的策略Grundy博弈搜索策略要考虑的问题:对MIN走步后的每一个MAX节点,必须证明MAX对MIN可能走的每一个棋局对弈后能获胜,即MAX必须考虑应付MIN的所有招法,这是一个与的含意。因此含有MAX符号的节点可看成与节点。对MAX走步后的每一个MIN节点,只须证明MAX有一步能走赢就可以,即MAX只要考虑能走出一步棋使MIN无法招架就成。因此含有MIN符号的节点可看成或节点。因此,对弈过程的搜索图就呈现出与或图表示的形式。Grundy博弈寻找MAX的取胜策略和求与或图的解图相对应。MAX要取胜,必须对所有与节点取胜,但只需对一个或节点取胜,这就是一个解图。因此,寻找一种取胜的策略就是搜索一个解图的问题,解图就代表一种完整的博弈策略。对于Grundy这种较简单的博弈,或者复杂博弈的残局,可以用类似于与或图的搜索技术求出解图,解图代表了从开局到终局任何阶段上的弈法。显然这对许多博弈问题是不可能实现的。例如,中国象棋,国际象棋和围棋等。Grundy博弈对于复杂的博弈问题,因此即使用了强有力的启发式搜索技术,也不可能使分枝压到很少。因此,这种完全取胜策略(或和局)必须丢弃。应当把目标确定为寻找一步好棋,等对手回敬后再考虑寻找另一步好棋这种实际可行的实用策略。这种情况下每一步的结束条件可根据时间限制、存储空间限制或深度限制等因素加以确定。搜索策略可采用宽度、深度或启发式方法。一个阶段搜索结束后,要从搜索树中提取一个优先考虑的"最好的"走步,这就是实用策略的基本点。