博弈树的搜索ppt课件.ppt

《博弈树的搜索ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、20世纪60年代，研制出的西洋跳棋和国际象棋达到了大师级的水平。1958约翰•麦卡锡提出博弈树α－β剪枝算法1997年，IBM公司研制的“深蓝”国际象棋程序，采用博弈树搜索算法，该程序战胜了国际象棋世界冠军卡斯帕罗夫。1.概述正在与深蓝下棋的卡斯帕罗夫博弈问题特点：双人对弈，轮流走步。信息完备，双方所得到的信息是一样的。零和，即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利或无利的棋。1.概述博弈的特性两个棋手交替地走棋；比赛的最终结果，是赢、输和平局中的一种；可用图搜索技术进行，但效率很低；博弈

2、的过程，是寻找置对手于必败态的过程；双方都无法干预对方的选择。1.概述2.Grundy博弈下棋的双方是对立的，命名博弈的双方，一方为“正方”，这类节点称为“MAX”节点；另一方为“反方”，这类节点称为“MIN”节点。正方和反方是交替走步的，因此MAX节点和MIN节点会交替出现。2.Grundy博弈Grundy博弈是一个分钱币的游戏。有一堆数目为N的钱币，由两位选手轮流进行分堆，要求每个选手每次只把其中某一堆分成数目不等的两小堆。例如，选手甲把N分成两堆后，轮到选手乙就可以挑其中一堆来分，如此进行下去，直到有

3、一位选手先无法把钱币再分成不相等的两堆时就得认输。2.Grundy博弈设初始状态为(7，MIN)，建立问题的状态空间图，图中所有终结点均表示该选手必输的情况，取胜方的目标是设法使棋局发展为结束在对方走步时的终结点上。MIN先走MAX必胜2.Grundy博弈结点A是MAX的搜索目标，而结点B，C则为MIN的搜索目标。2.Grundy博弈搜索策略要考虑的问题是：对MIN走步后的每一个MAX结点，必须证明MAX对MIN可能走的每一个棋局对弈后能获胜，即MAX必须考虑应付MIN的所有招法，这是一个与的含意，因此含有

4、MAX符号的结点可看成与结点。2.Grundy博弈对MAX走步后的每一个MIN结点，只须证明MAX有一步能走赢就可以，即MAX只要考虑能走出一步棋使MIN无法招架就成，因此含有MIN符号的结点可看成或结点。2.Grundy博弈对弈过程的搜索图呈现出与或图表示的形式。实现一种取胜的策略就是搜索一个解图的问题，解图就代表一种完整的博弈策略。2.Grundy博弈对各个局面进行评估评估的目的：对后面的状态提前进行考虑，并且以各种状态的评估值为基础作出最好的走棋选择。评估的方法：用评价函数对棋局进行评估。赢的评估值设

5、为+∞，输的评估值设为-∞，平局的评估值设为0。评估的标准：由于下棋的双方是对立的，只能选择其中一方为评估的标准方。3.极小极大搜索过程MAX节点和MIN节点命名博弈的双方，一方为“正方”，对每个状态的评估都是对应于该方的输赢的。例如，赢2个，输1个等，都是指正方的。正方每走一步，都在选择使自己赢得更多的节点，因此这类节点称为“MAX”节点；3.极小极大搜索过程另一方为“反方”，对每个状态的评估都是对应于对手的输赢的。例如，赢2个，输一个，其实是指自己输2个，赢1个的。反方每走一步，都在选择使对手输得更多的

6、节点，因此这类节点称为“MIN”节点。3.极小极大搜索过程由于正方和反方是交替走步的，因此MAX节点和MIN节点会交替出现。3.极小极大搜索过程正方（MAX节点）从所有子节点中，选取具有最大评估值的节点。反方（MIN节点）从其所有子节点中，选取具有最小评估值的节点。反复进行这种选取，就可以得到双方各个节点的评估值。这种确定棋步的方法，称为极小极大搜索法。3.极小极大搜索过程3.极小极大搜索过程5-333-3022-30-23541-30689-3MINMAX0MAXMIN3.极小极大搜索过程015-333-

7、3022-30-23541-30689-30-33-3-3-21-36-3031601MAXMINMAXMIN3.极小极大搜索过程在九宫格棋盘上，两位选手轮流在棋盘上摆各自的棋子(每次一枚)，谁先取得三线的结果就取胜。设程序方MAX的棋子用(×)表示，MAX先走。对手MIN的棋子用(o)表示。例如：3.极小极大搜索过程MIN取胜估计函数f(p)=(所有空格都放上MAX的棋子之后，MAX的三子成线数)－(所有空格都放上MIN的棋子之后，MIN的三子成线的总数)若P是MAX获胜的格局，则f(p)=+∞；若P是M

8、IN获胜的格局，则f(p)＝-∞。3.极小极大搜索过程3.极小极大搜索过程估计函数值f(p)=6-4=2估计函数f(p)=(所有空格都放上MAX的棋子之后，MAX的三子成线(行、列、对角)数)－(所有空格都放上MIN的棋子之后，MIN的三子成线(行、列、对角)的总数)当前棋局f(p)=23.极小极大搜索过程一字棋第一阶段搜索树3.极小极大搜索过程一字棋第二阶段搜索树3.极小极大搜索过程一字棋第三阶段搜索树设有一个