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

博弈_图文_百度文库

来源:未知 编辑:admin 时间:2019-07-26

  博弈_经济/市场_经管营销_专业资料。博弈搜索 博弈 ? ? 富有智能行为的竞争活动,如下棋、打牌、战 争……. 双人完备信息博弈 两位选手对垒,轮流走步,一方知道另一方已经 走过的棋步,并能够估计对方未来的走步。对弈 的结果是一方

  博弈搜索 博弈 ? ? 富有智能行为的竞争活动,如下棋、打牌、战 争……. 双人完备信息博弈 两位选手对垒,轮流走步,一方知道另一方已经 走过的棋步,并能够估计对方未来的走步。对弈 的结果是一方赢,另一方输;或者双方和局。实 例有象棋、围棋等。 ? 机遇性博弈 存在不可预测性的博弈,例如掷币等。 人工智能原理 博弈搜索 2 双人完备信息博弈 ? 在双人完备信息博弈过程中,假设博弈的一方 为MAX,另一方为MIN。可用博弈树表示双方 博弈过程。在博弈树中,那些下一步该 MAX走步的节点称为MAX节点,而下一步 该MIN走步的节点称为MIN节点。 人工智能原理 博弈搜索 3 博弈树例:分钱币游戏 ? 假设有7枚硬币,选手只能将已分好的一堆钱 币分成两堆个数不等的硬币。两位选手轮流进 行,直到每一堆都只有一个或两个硬币,不能 再分为止。哪位选手遇到不能再分的情况,则 认输。 博弈状态:(K1,K2,….,Kn, 当前各个钱堆中的钱币数 MIN or MAX) 当前走步方 4 人工智能原理 博弈搜索 MAX必胜的策略? (7, MIN) (5,2, MAX) (4,3, MAX) (3,3,1, MIN) (6,1, MAX) (5,1,1, MIN) (4,2,1, MIN) (3,2,2, MIN) (3,2,1,1, MAX) (4,1,1,1, MAX) (2,2,2,1, MAX) (3,1,1,1,1, MIN) (2,2,1,1,1, MIN) (2,1,1,1,1,1, MAX) 人工智能原理 分钱币博弈树 博弈搜索 5 博弈树是与或树 ? 双方都希望自己能够获胜。因此,当任何一方 走步时,都是试图选择对自己最为有利,而对 另一方最为不利的行动方案。 ? 从MAX方的观点看,在博弈过程的每一步,可 供自己选择的行动方案之间是“或”的关系,原 因在于选择哪个方案完全是由自己决定的;而可 供MIN选择的行动方案之间则是“与”的关系, 原因是主动权掌握在MIN手里,任何一个方案都 有可能被MIN选中,MAX必须防止那种对自己最 为不利的情况的发生。 人工智能原理 博弈搜索 6 ? 这样,从选手的角度看,博弈树就是一棵与或树, 其特点是: 结论:盲目搜索不可行,即使采用启发式搜索,也难以把 (l)博弈的初始状态是初始节点; 分枝数减少到可以接受的程度,必须考虑采用实用战略 (2)博弈树中的“或”节点和“与”节点逐层交替出现 ! (3)整个博弈过程始终站在某一方的立场上,所有能使自 寻找一步好棋,待对方回敬后再考虑下一步好棋, 己一方获胜的终局都是本原问题,相应的节点是可解节点; 并根据计算时间和存储空间的限制确定每一步的结 所有使对方获胜的终局都是不可解节点。 束条件,即在有限深度范围内进行搜索。 意味着 可以用与或图搜索技术求解必胜策略 ? ? 解图对应开局到终局阶段的弈法 以中国象棋为例,每个状态有40种走法,一盘棋平均走 50步,则总的状态数约为10的160次方。假设1毫秒搜索 一个状态,约需10的145次方年(最新估计宇宙年龄约10 的10次方年) 人工智能原理 博弈搜索 7 4.6 极大极小搜索 ? 用当前正在考察的节点生成一棵部分博弈树, 利用估价函数f(n)对叶节点进行静态评估,对 MAX有利的节点其估价函数取正值,如为 MAX获胜节点,则取正无穷大;对MIN有利的 节点,其估价函数取负值,如为MAX认输节 点,则取负无穷大;那些使双方势均力敌的节 点,其估价函数取0值。 (假设MAX为程序方,MIN为对手方) 人工智能原理 博弈搜索 8 极大极小过程 ? 从叶节点向上倒推计算非叶节点的值,直到当 前考察节点的过程。 对于MAX节点, MAX方总是选择对自己最好的走步, 即估值最大的走步,因此MAX节点的倒推值应该取其后 继节点估值的极大值。 对于MIN节点,MAX方需做最坏的打算,考虑MIN方 会选择对自己最好,从而对MAX方最坏的走步,即估值 最小的走步,因此MIN节点的倒推值应取其后继节点估值 的极小值。 ? 最终,站在MAX的立场上,显然应选择具有 最大倒推值的走步。 人工智能原理 博弈搜索 9 极大极小搜索例:一字棋游戏 ? 设有一个三行三列的棋盘,两个棋手轮流走步, 每个棋手走步时往空格上摆一个自己的棋子, 谁先使自己的棋手成三子一线为赢。设MAX 方的棋子用×标记,MIN方的棋子用 ○标记, 并规定MAX方先走步。 一字棋棋盘 人工智能原理 博弈搜索 10 确定页节点的静态估价函数e(P) 1. 若 P是 MAX的必胜局, 则 e(P) = +∞ 2. 若 P是 MIN的必胜局, 则 e(P) = -∞ ; 3. 若P对MAX、MIN都是胜负未定局,则 e(P) = e(+P)-e(-P) 其中,e(+P)表示棋局 P上有可能使× 成三子一线的数目; e(-P)表示棋局 P上有可能使 ○成三子一线的数目。 例: e(P) = 6 - 4=2 人工智能原理 博弈搜索 11 ? 在搜索过程中,具有对称性的棋局认为是同一 棋局,以大大减少搜索空间。 对称棋局的例子 人工智能原理 博弈搜索 12 第一阶段搜索树 13 人工智能原理 博弈搜索 第二阶段搜索树 14 人工智能原理 博弈搜索 第三阶段搜索树 此时,无论MIN如 何走,都已无法挽 回败局 人工智能原理 博弈搜索 15 4.7 α-β剪枝 ? ? 极大极小过程是先生成与/或树,然后再计算 各节点的估值,即生成节点和计算估值这两个 过程是分离的。在搜索时,需要生成规定深度 内的所有节点,因此搜索效率较低。 如果能边生成节点边对节点估值,并根据一定 的条件,提前剪去一些没用的分枝,那么就可 以有效提高搜索效率。在这种思想的基础上, 人们提出了α-β剪枝技术。 人工智能原理 博弈搜索 16 α-β剪枝方法 ? ? 采用有界深度优先策略,当生成规定深度的节 点时,计算叶节点的静态估值并倒推非端节点 的估值。根据倒推结果,在非端节点的向下分 枝中,剪掉那些目前未知,但无论如何都不会 改变非端节点倒推值的未扩展分枝。 α-β α值为MAX节点倒推值的下确界; β值为MIN节点倒推值的上确界; 人工智能原理 博弈搜索 17 剪枝规则 ① α剪枝: 任何MIN节点n的β值小于或等于它祖先节点 的α值,则n以下的分枝可停止搜索,并令节 点n的倒推值为β。 ② β剪枝: 任何MAX节点n的α值大于或等于它祖先节点 的β值,则n以下的分枝可停止搜索,并令节 点n的倒推值为 α。 人工智能原理 博弈搜索 18 ① α剪枝: 任何MIN节点n的β值小于或等于它祖先节点的α值,则n以下的 分枝可停止搜索,并令节点n的倒推值为β。 ② β剪枝: 任何MAX节点n的α值大于或等于它祖先节点的β值,则n以下的 分枝可停止搜索,并令节点n的倒推值为 α。 ≥4 =4 S0 ≤4 =4 A ≤0 ≥5 D B ≥4 =4 4 F C ≥0 =0 E * * * ≤1 M N G 5 H ≤0 =0 I ≤-6 J K L * * P Q R S * 4 8 6 1 5 8 0 -6 α-β剪枝例 人工智能原理 博弈搜索 19 极大极小值 MAX B A C 3 MIN 3 2 D2 MAX 3 12 8 2 4 6 14 5 2 人工智能原理 博弈搜索 20 博弈树的剪枝(1) (a) [-∞, +∞] A [-∞,3] B (b) 3 [-∞, +∞] A [-∞,3] B 3 12 人工智能原理 博弈搜索 21 博弈树的剪枝(2) (c) [3,3] B [3, +∞] A 3 12 8 (d) [3, +∞] A [3,3] B [-∞,2] C 3 12 8 2 人工智能原理 博弈搜索 22 博弈树的剪枝(3) (e) [3,3] B [3,14] A [-∞,2] C [-∞,14] D 3 12 8 2 14 (f ) [3,3] A [3,3] B [-∞,2] C [2,2] D 3 12 8 2 14 5 2 23 人工智能原理 博弈搜索 ?-?剪枝算法的说明 ? ?-?剪枝可以应用树的任何深度,许多情况 下可以剪掉整个子树 / 其原则是—如果在节 点n的父节点或者更上层的节点有一个更好 的选择m,则在实际游戏(搜索)中永远不会 到达n ? ? ? ?=到目前为止在路径上任意点发现的MAX最 佳选择 ?=到目前为止在路径上任意点发现的MIN最 佳选择 ?-?搜索不断更新?/?值,当某个节点的值分 别比?/?值更差时剪掉该节点的剩余分支 人工智能原理 博弈搜索 24 ?-?剪枝的效率 ? ? ?-?剪枝的效率很大程度上取决于检查后继 节点的次序—应该先检查那些可能最好的后 继 如果能够先检查那些最好的后继,则?-?剪 枝算法只需检查O(bd/2)个节点以决定最佳招 数 人工智能原理 博弈搜索 25

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

相关推荐:

网友评论:

栏目分类

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

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

Top