设为首页 - 加入收藏
广告 1000x90
您的当前位置:二四六天天好彩308K文字资料 > 博弈树搜索 > 正文

管理博弈树ppt

来源:未知 编辑:admin 时间:2019-06-10

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  树的应用 博弈树 搜索 假定你的房间里铺有 100 块地板,其中一块底下有一块金砖,一块底下有一颗地雷。如果你翻开有金砖的那块地板,你就可以成为百万富翁;如果你翻开有地雷的那块地板,你就可以到地狱旅行。在经历了长期煎熬之后,你决定将这些地板逐一翻开,以找寻百万富翁的生活。这个寻找命运答案的过程,就是搜索(Search)。 而将地板逐一翻开的搜索方法,叫作盲目搜索( Blind Search)。在这个盲目搜索的过程中,随着未翻开地板数目的减少,终将会找到一个答案。 博弈(对抗性搜索) 又假定你还有一位朝夕相伴的室友,同你一样起了这个念头。于是,你们商定每人每天可以交替翻开一块地板。这样当一个人碰到地雷时,他最亲密的朋友就可以得到剩下的金砖。所以你们各自在心中祝愿对方黄泉路上一帆风顺。最多50天,命运的答案就会完全揭晓。你们翻开了98块地板后仍一无所获,在最后的时刻,你犹豫了,到底要不要翻开这一块决定命运的地板?你感到同你竞争的并非你的室友,而是魔鬼的化身。这个同魔鬼的化身交战的过程就叫作博弈。而敌对双方交替动作的搜索叫做对抗性搜索(Adversarial Search)。 博弈树 诸如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。博弈有很多种,我们讨论最简单的二人零和、全信息、非偶然博弈,其特征如下: (1) 对垒的MAX、MIN双方轮流采取行动,博弈的结果只有三种情况:MAX方胜,MIN方败;MIN方胜,MAX方败;和局。 (2) 在对垒过程中,任何一方都了解当前的格局及过去的历史。 (3) 任何一方在采取行动前都要根据当前的实际情况,进行得失分析,选取对自已为最有利而对对方最为不利的对策,不存在掷骰子之类的碰运气因素。即双方都是很理智地决定自己的行动。 在博弈过程中,任何一方都希望自己取得胜利。因此,当某一方当前有多个行动方案可供选择时,他总是挑选对自己最为有利而对对方最为不利的那个行动方案。此时,如果我们站在MAX方的立场上,则可供MAX方选择的若干行动方案之间是或关系,因为主动权操在MAX方手里,他或者选择这个行动方案,或者选择另一个行动方案,完全由MAX方自已决定。当MAX方选取任一方案走了一步后,MIN方也有若干个可供选择的行动方案,此时这些行动方案对MAX方来说它们之间则是与关系,因为这时主动权操在MIN方手里,这些可供选择的行动方案中的任何一个都可能被MIN方选中,MAX方必须应付每一种情况的发生。 这样,如果站在某一方(如MAX方,即MAX要取胜),把上述博弈过程用图表示出来,则得到的是一棵与或树。描述博弈过程的与或树称为博弈树,它有如下特点: (1) 博弈的初始格局是初始节点。 (2) 在博弈树中,或节点和与节点是逐层交替出现的。自己一方扩展的节点之间是或关系,对方扩展的节点之间是与关系。双方轮流地扩展节点。 (3) 所有自己一方获胜的终局相应的节点是可解节点;所有使对方获胜的终局都认为是不可解节点。 我们假定MAX先走,处于奇数深度级的节点都对应下一步由MAX走,这些节点称为MAX节点,相应地偶数级为MIN节点。 极大极小搜索 在二人博弈问题中,为了从众多可供选择的行动方案中选出一个对自己最为有利的行动方案,就需要对当前的情况以及将要发生的情况进行分析,通过某搜索算法从中选出最优的走步。在博弈问题中,每一个格局可供选择的行动方案都有很多,因此会生成十分庞大的博弈树,如果试图通过直到终局的与或树搜索而得到最好的一步棋是不可能的,比如曾有人估计,西洋跳棋完整的博弈树约有10的40次方个节点。 最常使用的分析方法是极小极大分析法。其基本思想或算法是: (1) 设博弈的双方中一方为MAX,另一方为MIN。然后为其中的一方(例如MAX)寻找一个最优行动方案。 (2) 为了找到当前的最优行动方案,需要对各个可能的方案所产生的后果进行比较,具体地说,就是要考虑每一方案实施后对方可能采取的所有行动,并计算可能的得分。 (3) 为计算得分,需要根据问题的特性信息定义一个估价函数,用来估算当前博弈树叶节点的得分。此时估算出来的得分称为静态估值。 (4) 当叶节点的估值计算出来后,再推算出父节点的得分,推算的方法是:对“或”节点,选其子节点中一个最大的得分作为父节点的得分,这是为了使自己在可供选择的方案中选一个对自己最有利的方案;对“与”节点,选其子节点中一个最小的得分作为父节点的得分,这是为了立足于最坏的情况。这样计算出的父节点的得分称为倒推值。 (5) 如果一个行动方案能获得较大的倒推值,则它就是当前最好的行动方案。 在博弈问题中,每一个格局可供选择的行动方案都有很多,因此会生成十分庞大的博弈树。试图利用完整的博弈树来进行极小极大分析是困难的。可行的办法是只生成一定深度的博弈树,然后进行极小极大分析,找出当前最好的行动方案。在此之后,再在已选定的分支上扩展一定深度,再选最好的行动方案。如此进行下去,直到取得胜败的结果为止,至于每次生成博弈树的深度,当然是越大越好,但由于受到计算机存储空间的限制,只好根据实际情况而定。 0 5 -3 3 3 -3 0 2 2 -3 0 -2 3 5 4 1 -3 0 6 8 9 -3 极小极大过程 0 -3 3 -3 -3 -2 1 -3 6 -3 0 3 1 6 0 1 1 极大 极小 b 极大 极小 三子棋极大极小搜索分析 设有九个空格,由MAX,MIN二人对弈,轮到谁走棋谁就往空格上放一只自己的棋子,谁先使自己的棋子构成“三子成一线”(同一行或列或对角线全是某人的棋子),谁就取得了胜利。 用叉号表示MAX,用圆圈代表MIN。 比如下图中就是MIN取胜的棋局。 为了不致于生成太大的博弈树,假设每次仅扩展两层。估价函数定义如下: 设棋局为P,估价函数为e(P)。 (1) 若P对任何一方来说都不是获胜的位置,则e(P)=e(那些仍为MAX空着的完全的行、列或对角线的总数)-e(那些仍为MIN空着的完全的行、列或对角线) 若P是MAX必胜的棋局,则e(P)=+∞。 (3) 若P是MIN必胜的棋局,则e(P)=-∞。 比如P如下图示,则e(P)=6-4=2 下图画出了经过两层搜索生成的博弈树,静态估值记在端节点下面,倒推值记在圆圈内。 由于下图所示位置具有最大的倒推值,它应当选取为MAX的第一步(正好是MAX的最好的优先走步)。 现在我们假设MAX走了这一步,而MIN的回步是直接在X上方的空格里放上一个圆圈(对MAX来说这是一步坏棋,他一定没有采用好的搜索策略)。下一步,MAX又在新的格局下搜索两层,产生如下所示的搜索图 现在图中MAX有两个可能“最好的”优先走步,假设MAX走了图上指明的那一步。而MIN为了避免立即败北被迫走了另一步,从而产生如下棋局:MAX再次搜索,产生如下所示的树。 在这棵树中某些叶节点代表MIN获胜,因此它们的估值为—∞。当这些估值被倒推回去时,可看到MAX的最好的也是唯一能使他避免立即失败的一个走步。现在,MIN可以看出MAX必然在他的下一走步中获胜,因此,MIN只好认输。 下面给出极大极小搜索算法的伪代码 int MiniMax(position p,int d) { int bestValue,value; if (d == nSearchDepth) { return evaluation(p); } if(IsMaxTurn) { bestValue = -INFINITY; } else { bestValue = INFINITY; } for(each possibly m in moves) { MakeMove(m); value = MiniMax(p,d+1); UnMakeMove(m); if (IsMaxTurn) bestValue = max(value,bestValue); else bestValue = min (value,bestValue); } return bestValue; }

本文链接:http://mzi-ads.com/boyishusousuo/581.html

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top