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

第5章状态空间搜索

来源:未知 编辑:admin 时间:2019-05-09

  第五章 状态空间搜索 状态空间搜索 问题归约法 博弈树搜索 1 2 3 17:12 1页 1997年5月11日超级电脑深蓝战胜卡斯帕罗夫 17:12 卡斯帕罗夫在与“深蓝”对弈(右为“深蓝”现场操作者) 2页 搜索的含义 适用情况: 不良结构或非结构化问题;难以获得求解所需 的全部信息;更没有现成的算法可供求解使用。 概念: 依靠经验,利用已有知识,根据问题的实际情 况,不断寻找可利用知识,从而构造一条代价最小 的推理路线,使问题得以解决的过程称为搜索 17:12 3页 搜索的类型 按是否使用启发式信息 盲目搜索:按预定的控制策略进行搜索,在搜索过 程中获得的中间信息并不改变控制策略。 启发式搜索:在搜索中加入了与问题有关的启发性 信息,用于指导搜索朝着最有希望的方向前进,加速 问题的求解过程并找到最优解。 按问题的表示方式 状态空间搜索:状态空间法求解问题所进行的搜索 与或树搜索:问题归约法求解问题时所进行的搜索 17:12 4页 状态空间表示方法 状态(State)是表示问题求解过程中每一步问题状 况的数据结构,它可形式地表示为: Sk ={ Sk0, Sk1, … } 当对每一个分量都给以确定的值时,就得到了一个 具体的状态。 操作(Operator)也称为算符,它是把问题从一种状 态变换为另一种状态的手段。 操作可以是一个机械步骤,一个运算,一条规则或 一个过程。操作可理解为状态集合上的一个函数,它 描述了状态之间的关系。 17:12 5页 罪犯躲到一幢5层楼房,共2个楼门,每楼门每层2户 17:12 6页 状态、操作 ? Sk ={ Sk0, Sk1, … } Ski =(A, P, C) %罪犯位置,警察位置,抓住否 Sk0=(2101, 1101, 0) %罪犯2-101,警察1-101,在逃 Sk1=(2201, 1102, 0) %罪犯2-201,警察1-102,在逃 Sk2=(2301, 1201, 0) %罪犯2-301,警察1-201,在逃 …… Sk20=(2502, 2502, 1) %罪犯2-502,警察2-502,抓住 17:12 7页 5.2 状态空间搜索 5.2.1 问题的状态空间表示 状态空间(State space)用来描述一个问题的全 部状态以及这些状态之间的相互关系。常用一 个三元组表示:(S,O,G) S:状态集合,状态是某种事实的符号或数据, 问题的初始状态是S的非空子集 G:目标状态集,S的非空子集。可以是若干具 体的状态,也可以是对某些状态性质的描述 O:操作算子集,利用它将一个状态转化为另一 个状态 17:12 8页 状态空间法求解问题的基本过程 ① 首先为问题选择适当的“状态”及“操作”的形式 化描述方法; ② 然后从某个初始状态出发,每次使用一个“操 作”,递增地建立起操作序列,直到达到目标状 态为止; 此时,由初始状态到目标状态所使用的算符序 列就是该问题的一个解。 状态空间也可用一个赋值的有向图来表示,称 为状态空间图。图中,节点表示问题的状态, 有向边表示操作。 17:12 9页 例 传教士(Missionaries)和野人(Cannibals)问题 设在河的一岸有三个野人、三个传教士(修道 士)和一条船,修道士想用这条船把所有的人运 到河对岸(演示) 一是修道士和野人都会划船,但每次船上至多 可载两个人; 二是在河的任一岸,如果野人数目超过修道士 数,修道士会被野人吃掉。 如果野人会服从任何一次过河安排,请规划一 个确保修道士和野人都能过河,且没有修道士被 野人吃掉的安全过河计划。 17:12 10页 状态 需考虑两岸的传教士人数和野人数、船在左岸还 是在右岸。问题状态可用三元组(m, c, b)表示 ? m为传教士在左岸或船上人数,c为野人在左岸或 船上人数,b左岸船数 右岸的状态可由下式确定: 右岸传教士数 m=3-m 右岸野人数 c=3-c 右岸船数 b=1-b m和c都可取0、1、2、3中之一, b可取0和1中之一。 共有4×4×2=32种状态。 17:12 11页 状态 这32种状态并非全有意义,除去不合法状态和修 道士被野人吃掉的状态,有意义的16种: S0=(3, 3, 1) S1=(3, 2, 1) S2=(3, 1, 1) S3=(2, 2, 1) S4=(1, 1, 1) S5=(0, 3, 1) S6=(0, 2, 1) S7=(0, 1, 1) S8=(3, 2, 0) S9=(3, 1, 0) S10=(3, 0, 0) S11=(2, 2, 0) S12=(1, 1,0) S13=(0, 2, 0) S14=(0, 1, 0) S15=(0, 0, 0) 有了这些状态,还需要考虑可进行的操作。 17:12 12页 操作 操作是指用船把修道士或野人从河的左岸运到右 岸,或从河的右岸运到左岸。满足如下条件: 一是船至少有一个人(m或c)操作,离开岸边 的m和c的减少数目应该等于到达岸边的m和c的 增加数目; 二是每次操作船上人数不得超过2个; 三是操作应保证不产生非法状态。 因此,操作应由条件部分和动作部分: 条件:只有当其条件具备时才能使用 动作:刻划了应用此操作所产生的结果。 17:12 13页 操作 操作的表示 用符号Pij表示从左岸到右岸的运人操作 用符号Qij表示从右岸到左岸的操作 i表示船上的修道士人数,j表示船上的野人数 操作集:10种操作可供选择 F={P01, P10, P11, P02, P20, Q01, Q10, Q11, Q02, Q20} 以P01和Q01为例(野人来回过河) 操作符号 条件 动作 P01 b=1, m=0或3, c≥1 b=0, c=c-1 Q01 b=0, m=0或3, c≤2 b=1, c=c+1 17:12 14页 问题解决 初始状态(3, 3, 1)→ 目标状态(0, 0, 0) (传教士-野人-左岸) 17:12 15页 5.2.2 状态空间的穷搜索法 广度优先搜索算法 深度优先搜索算法 17:12 16页 罪犯躲到一幢5层楼房,共2个楼门,每楼门每层2户 17:12 17页 搜索策略 S0 1层 1-1-1 1-1-2 2-1-1 2-1-2 2层 1-2-1 1-2-2 2-2-1 2-2-2 楼门1- 1层- 1室 17:12 18页 1. 广度优先搜索 基本思想 从初始节点S0开始逐层向下扩展,在第n层节点还没 有全部搜索完之前,不进入第n+1层的节点进行搜索。 Open表(先进先出队列) 中的节点总是按进入的 先后排序,先进入的节 点排在前面,后进入的 节点排在后面。 S0 1 3 6 17:12 2 4 7 8 19页 5 搜索算法 (1) 把初始节点S0放入Open表(先进先出队列,存放 待扩展节点)中 (2) 如果Open表为空,则问题无解,失败退出; (3) 把Open表的第一个节点取出放入Closed表(存 放已被扩展的节点),并记该节点为n(n=n+1); (4) 考察节点n是否为目标节点。若是,则得到问题 的解,成功退出; Open表 Closed表 17:12 S0 S0 入队列 20页 搜索算法 (5) 若节点n不可扩展(无后续节点),转第(2)步; (6) 扩展节点n(产生其所有后续节点),将其子节点 依次放入Open表的尾部,并为每一个子节点设置 指向父节点的指针,然后转第(2)步。 Open表 Closed表 17:12 S1 S2 ··· ··· S0 入队列 21页 例 八数码难题。 3×3的方格棋盘上,分别放置了表有数字1、2、3、 4、5、6、7、8的八张牌,初始状态S0,目标状态Sg 可以使用的操作 空格左移,空格上移,空格右移,空格下移 只允许位于空格左、上、右、下方的牌移入空格 要求应用广度优先搜索策略寻找从初始状态到目标 状态的解路径。 S0 Sg 2 1 7 17:12 8 3 4 1 8 7 2 3 4 6 5 6 5 22页 S0 2 8 3 1 4 7 6 5 1 2 2 8 3 1 4 7 6 5 3 2 3 1 8 4 7 6 5 4 2 8 3 1 4 7 6 5 5 2 8 3 1 6 4 7 5 6 8 3 2 1 4 7 6 5 7 2 8 3 7 1 4 6 5 8 2 3 1 8 4 7 6 5 9 2 3 1 8 4 7 6 5 10 2 8 1 4 3 7 6 5 11 2 8 3 1 4 5 7 6 12 2 8 3 1 6 4 7 5 13 2 8 3 1 6 4 7 5 14 8 3 2 1 4 7 6 5 15 2 8 3 7 1 4 6 5 16 1 2 3 8 4 7 6 5 17 2 3 4 1 8 7 6 5 18 2 8 1 4 3 7 6 5 19 2 8 3 1 4 5 7 6 20 2 8 3 6 4 1 7 5 21 2 8 3 1 6 7 5 4 22 8 3 2 1 4 7 6 5 23 8 1 3 2 4 7 6 5 24 2 8 3 7 4 6 1 5 25 2 8 3 7 1 4 6 5 26 1 2 3 8 4 7 6 5 27 Sg 1 2 7 8 6 3 4 5 17:12 23页 罪犯躲到一幢5层楼房,共2个单元,每单元每层2户 17:12 24页 搜索策略 S0 1层 1-1-1 1-1-2 2-1-1 2-1-2 2层 1-2-1 1-2-2 2-2-1 2-2-2 1单元- 1层- 1室 17:12 25页 2. 深度优先搜索 基本思想 从初始节点S0开始,在其子节点中选择一个最新生 成的节点进行考察, 如果该子节点不是目标节点且可以扩展,则扩展该 子节点, S0 然后再在此子节点的子节 点中选择一个最新生成的 5 1 节点进行考察, 依此向下搜索,直到某个 8 2 6 子节点既不是目标节点, 又不能继续扩展时,才选 4 7 3 择其兄弟节点进行考察。 17:12 26页 搜索算法 (1) 把初始节点S0放入Open表(先进后出的堆栈) (2) 如果Open表为空,则问题无解 ,失败退出; (3) 把Open表的第一个节点取出放入Closed表,并 记该节点为n; . (4) 考察节点n是否为目标节点。 若是,则得到问题的解,成功退出; (5) 若节点n不可扩展,则转第(2)步; (6) 扩展节点n,将其子节点依次压入 Closed表 Open堆栈,并为每一个子节点设置指 向父节点的指针,然后转第(2)步。 6 17:12 27页 例 八数码难题 八数码难 题的深度 优先搜索 2 8 3 1 4 7 6 5 S0 2 8 3 1 4 7 6 5 1 2 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 1 6 7 5 4 3 4 5 6 28页 一种改进的深度优先算 法是有界深度优先搜索 算法,深度限制为dm 17:12 2 8 3 1 6 7 5 4 2 8 1 6 3 7 5 4 2 8 1 6 3 7 5 4 5.2.3 启发式搜索 1. 启发性信息的概念 启发性信息是指那种与具体问题求解过程有关 的,并可指导搜索过程朝着最有希望方向前进的 控制信息。 启发性信息的种类 ① 有效地帮助确定扩展节点的信息; ② 有效的帮助决定哪些后继节点应被生成的信息; ③ 能决定在扩展一个节点时哪些节点应从搜索树上 删除的信息。 启发性信息的作用 启发信息的启发能力越强,扩展的无用结点越少。 17:12 29页 评价/估价函数 估价函数用来估计节点重要性的函数。 目的是评估从初始节点S0出发,经过节点n到达 目标节点Sg的所有路径中最小路径代价的估计值。 估价函数一般形式为: f(n) = g(n) + h(n) g(n)是从初始节点S0到节点n的实际代价(已经 付出) h(n)是从节点n到目标节点Sg的最优路径的估计 代价。(将要付出) 希望实现选f(n)最小的节点先进行扩展。 17:12 30页 例 八数码难题 设问题的初始状态S0和目标状态Sg如下图 所示,且估价函数为 f(n)=d(n)+W(n) 其中d(n)表示节点n在搜索树中的深度 W(n)表示节点n中“不在位”的数码个数。 请计算初始状态S0的估价函数值f(S0) S0 2 1 7 17:12 8 3 4 Sg 1 8 7 2 3 4 6 5 6 5 31页 解:取g(n)=d(n),h(n)=W(n)。 它说明是用从S0到n的路径上的单位代价表 示实际代价,用结点n中“不在位”的数码个 数作为启发信息。 一般来说,某节点中的“不在位”的数码个 数越多,说明它离目标节点越远。 对初始节点S0,d(S0)=0,W(S0)=3,有 f(S0)=0+3=3 17:12 32页 2. A算法 概念 在图搜索算法中,如果能在搜索的每一步 都利用估价函数f(n)=g(n)+h(n)对Open表 中的节点进行排序,则该搜索算法为A算法。 由于估价函数中带有问题自身的启发性信 息,因此,A算法也被称为启发式搜索算法。 17:12 33页 类型: 可根据搜索过程中选择扩展节点的范围, 将启发式搜索算法分为全局择优搜索算法 和局部择优搜索算法。 全局择优: 从Open表的所有节点中选择一 个估价函数值最小的一个进行扩展。 局部择优:仅从刚生成的子节点中选择一 个估价函数值最小的一个进行扩展。 17:12 34页 全局择优搜索A算法描述 (1) 把初始节点S0放入Open表中,f(S0)=g(S0)+h(S0); (2) 如果Open表为空,则问题无解 ,失败退出; (3) 把Open表的第一个节点取出放入Closed表,并记该节点 为n; (4) 考察节点n是否为目标节点。若是,则找到了问题的解, 成功退出; (5) 若节点n不可扩展,则转第(2)步; (6) 扩展节点n,生成其子节点ni(i=1, 2, …),计算每一个子 节点的估价值f(ni)(i=1, 2, …),并为每一个子节点设置指 向父节点的指针,然后将这些子节点放入Open表中; (7) 根据各节点的估价函数值,对Open表中的全部节点按从 小到大的顺序重新进行排序;(课本更细,其意思均是走 代价更小的路线,发现更小代价的路线页 例 八数码难题 设问题的初始状态S0和目标状态Sg如图所示,估 价函数与前例相同。用全局择优搜索解决该问题 解:该问题的全局择优搜索树如下图所示。在该图 中,每个节点旁边的数字是该节点的估价函数值。 ? 例如,对节点S2,其估价函数值的计算为: f(S2)=d(S2)+W(S2) =2+2=4 初始S0 2 1 7 17:12 目标Sg 3 4 1 8 7 6 2 3 4 5 1 7 S2 2 8 6 3 4 5 36页 8 6 5 全局择优搜索树 2 8 3 S0 1 4 7 6 5 3 1 8 4 7 6 5 与前面搜索不同? 4 2 8 3 1 4 7 6 5 4 2 S1 5 2 8 3 5 2 8 3 1 4 7 6 5 1 6 4 7 5 5 8 3 2 1 4 7 6 5 6 2 8 3 7 1 4 6 5 4 S2 2 3 1 8 4 7 6 5 6 2 3 1 8 4 7 6 5 S3 4 1 2 3 8 4 7 6 5 4 1 2 3 6 1 2 3 8 4 7 6 5 7 8 6 4 5 Sg 该问题的解为: S0→S1→S2→S3→Sg 17:12 37页 3. A*算法(启发式搜索算法) A算法不能保证找到从起点到目标结点的最短路径 A*算法保证一定能找到一条最短路径 怎么做到? 对A算法的评估函数f(n)=g(n)+h(n)加上限制! (1) 设f*(n)是从初始节点出发、经过(约束必走)节点n 到达目标节点的最小代价,广义评估函数 f*(n) = g*(n) + h*(n) ? g*(n)为起点到节点n的最短路径值(启发信息) ? h*(n)为节点n到目标节点的最短路径值 按最小代价f*(n)走的路径是我们的理想! 17:12 38页 评估函数f(n) = g(n) + h(n) 是对f*(n)的估计值 (2) A*算法对A算法(全局择优的启发式搜索算法) 中的g(n)和h(n)分别提出如下限制(满足): g(n)是对最小代价g*(n)的估计,且g(n)≥g*(n) 搜索时边搜边扩展结点,很可能没找到最短路 径;若刚好走了最短路径时g(n)=g*(n) h(n)是最小代价h*(n)的下界,即对任意结点n均 有h(n)≤h*(n)。(g大了没走最短路径,h需要小 即启发信息少以扩大搜索范围) A*算法保证能找到一条最短路径(王永庆课本有证明) 17:12 39页 启发函数h(n)---约束条件 h(n)是对h*(n)的近似估计,要满足h(n) ≤ h*(n) h(n)=0≤h*(n)情况,搜索的节点多,搜索范围 大,故总能找到最优解。 例如广度优先搜索,将要走的路线没有任何启发 信息h(n)=0,所有节点都搜索; 随着启发信息h(n)增多,搜索时扩展的节点变 少,即排除了一些节点不用搜索,搜索效率变高。 h(n)>h*(n)情况,搜索的节点少,搜索范围小, 效率高,但不能保证得到最优解。 拼出租车最合算?搜索1人、2人、3人、4人、5人 h说5人以上更合算,漏掉搜索4人,5人被罚款 17:12 40页 例 修道士和野人问题 解:用m表示左岸的修道士人数,c表示左岸的野人 数,b表示左岸的船数,用三元组(m, c, b)表示问 题的状态。(需要设计h(n),没有通用的) 对A*算法,首先需要确定估价函数。设 g(n)=d(n) ,d(n)为节点的深度; h(n)=m+c-2b,左岸剩余的修道士和野人数,通 过分析可知h(n)≤h*(n),满足A*算法的限制条件。 h*(n)左岸最合适人数 则有 f(n)=g(n)+h(n)=d(n)+m+c-2b M-C问题的搜索过程如下图所示。 17:12 41页 (3,3,1) h=5 f=6 h=4 f=4 h=4 f=5 g=0层 (2,2,0) g=1层 g=2 (3,2,0) h=4 f=5 (3,1,0) h=3 f=5 (3,2,1) h=3 f=6 h=2 f=6 h=2 f=7 h=1 f=7 h=1 f=8 h=0 f=8 (2,1,0) (3,0,0) h=3 f=6 (3,1,1) (1,1,0) h=2 f=6 g=3 g=4 g=5 g=6 (2,2,1) (0,2,0) (0,3,1) (0,1,0) (0,2,1) (0,0,0) h=2 f=7 h(n)=m+c-2b 左岸剩 余的修道士和野人数 g=7 g=8 传教士和野人问题的搜索图 g=9 42页 17:12 5.3 问题归约法 基本思想:当一问题较复杂时,可通过分解或变换, 将其转化为一系列较简单的子问题,然后通过对这些 子问题的求解来实现对原问题的求解。 分解 思想 ?如果一个问题P可以归约为一组子问题P1,P2,…,Pn, ?并且只有当所有子问题Pi都有解时原问题P才有解, ?任何一个子问题Pi无解都会导致原问题P无解, 则称此种归约为问题的分解。分解所得到的子问题 的“与”与原问题P等价。 17:12 43页 5.3 问题归约法 等价变换 ?如果一个问题P可以归约为一组子问题P1,P2,…,Pn, ?并且子问题Pi中只要有一个有解则原问题P就有解, ?只有当所有子问题Pi都无解时原问题P才无解, 思想 称此种归约为问题的等价变换,简称变换。变换所得 到的子问题的“或”与原问题P等价。 17:12 44页 (1)与树 分解 P P (2) 或树 等价变换 P1 P2 与树 P3 P1 P2 或树 P3 (3) 与/或树 P P2 P12 P3 P31 P32 P33 45页 P1 P12 17:12 与/或树 5.3.1 问题归约描述 用一个三元组(S0,O,P)来描述 S0:初始问题,即要求解的问题。 P:本原问题集,其中的每一个问题是不证明 的,自然成立的,如公理、已知事实等,或已 证明过的。 O:操作算子集,通过一个操作算子把一个问 题化成若干个子问题。 目的是产生本原问题,问题得解 17:12 46页 5.3.2 与或图表示 用与或图可方便地把问题归约为子问题替换集合 例:假设问题A既可通过问题C1与C2,也可通过 问题C3,C4和C5,或者由单独求解问题C6来解决, 图5-10中节点表示要求解的问题或子问题。 图5-10 子问题替换集合 17:12 图5-11 各结点后继只 含一个K连接弧 47页 与/或树的搜索 搜索过程是一个不断寻找解树的过程,搜索过程 将形成一颗与/或树,这种由搜索过程所形成的与/ 或树称为搜索树。 (1) 把原始问题作为初始节点S0,并把它作为当前 节点; (2) 应用分解或等价变换操作对当前节点进行扩展; (3) 为每个子节点设置指向父节点的指针; (4) 选择合适的子节点作为当前节点,反复执行第(2) 步和第(3)步,在此期间需要多次调用可解标记过 程或不可解标记过程,直到初始节点被标记为可 解节点或不可解节点为止。 17:12 48页 与/或树的搜索 与/或树的盲目搜索 与/或树的广度优先搜索 与/或树的深度优先搜索 与/或树的启发式搜索 17:12 49页 5.4 博弈树搜索 博弈的概念 :博弈是一类具有智能行为的竞争 活动,如下棋、战争等。 博弈的类型 双人完备信息博弈:两位选手(例如MAX和 MIN )对垒,轮流走步,每一方不仅知道对方已 经走过的棋步,而且还能估计出对方未来的走步。 机遇性博弈:存在不可预测性的博弈,例如掷 币等。 17:12 50页 5.4 博弈树搜索 这里讲的博弈是二人博弈,即由人对垒,轮流依 次走步,每一方都知道对方已经走过的棋步和以 后可能走的棋步,双方最终将有胜负之分或者为 和局,这类博弈如一字棋、象棋、围棋等。 要考虑如何表示博弈问题的状态、博弈过程、 博弈知识等。 17:12 51页 具体例子:分钱币的博弈 假设有七个钱币,任一选手只能将已分好的一 堆钱币分成两堆个数不等的钱币,两位选手轮流 进行,直到每一堆都只有一个或两个钱币,不再 能分为止。哪个遇到不能再分的情况,则就为输。 用数字序列加上一个说明表示一个状态,其 中数字表示不同堆中钱币的个数,说明表示 下一步由谁来分。 如(7,MIN)表示只有一个由七个钱币组成 的堆,由MIN进行分堆。 17:12 52页 立场? 无论MIN怎么走,MAX总可以获胜? MIN胜 MAX胜 MIN胜 17:12 53页 博弈树:若把双人完备信息博弈过程用图表示出 来,就得到一棵与/或树,这种与/或树被称为博弈 树。在博弈树中,那些下一步该MAX走步的节点 称为MAX节点,下一步该MIN走步的节点称为 MIN 节点。 博弈树的特点 (1) 博弈的初始状态是初始节点; (2) 博弈树中“或”节点和“与”节点是逐层交替出现的 (3) 整个博弈过程始终站在某一方的立场上,例如 MAX方。所有能使自己一方获胜的终局都是本原 问题,相应的节点是可解节点;所有使对方获胜 的终局都是不可解节点。 17:12 54页 5.4.1 极大极小过程 假定由MAX选择走一步棋,如何来选择一步好棋? 下图表示向前看两步,共四层的博弈树,用□表示 MAX,用○表示MIN,端结点上的数字表示估价函数的值。 17:12 55页 极大极小分析法的思想 为了找到最优行动方案,需对各方案可能 产生的后果进行比较。怎么比? 根据问题设计一个估价函数,估算当前节 点的得分。 再推算父节点的得分(称为倒推值)。对 或节点,选最大分;对与节点,选最小分。 若一个方案获得最大的倒推值,就是最好 的方案。 17:12 56页 己方立场:(获利)最大的倒推值就是最好的方案 17:12 57页 5.4.1 极大极小过程 对简单的博弈问题,可生成整个博弈树,找到必 胜的策略。 对于复杂的博弈问题,不可能生成整个搜索树, 如国际象棋,大约有10120个节点。 怎么办? 一种可行的方法是用当前正在考察的节点生成一 棵部分博弈树(比如一定的深度),并利用估价函 数f(n)对叶节点进行静态估值。 对叶节点的估值方法是:那些对MAX有利的节 点,其估价函数取正值;那些对MIN有利的节点, 其估价函数取负值;那些使双方均等的节点,其估 价函数取接近于0的值。(站在谁的立场上?) 17:12 58页 5.4.1 极大极小过程 对非叶节点的值,必须从叶节点开始向上倒退。 其倒退方法是: ? 对于MAX节点,由于MAX 方总是选择估值最 大的走步,因此,MAX节点的倒退值应该取其后 继节点估值的最大值。 ? 对于MIN节点,由于MIN方总是选择使估值最 小的走步,因此MIN节点的倒推值应取其后继节 点估值的最小值。 立场? 这样一步一步的计算倒推值,直至求出初始节点 的倒推值为止。这一过程称为极大极小过程。 17:12 59页 用一字棋来具体说明一下极大极小过程。 评价函数e(p)规定如下: 1.若格局P对任何一方都不是获胜的,则 e(p)=(所有空格都放上MAX的棋子之后,MAX的 三个棋子所组成的行、列及对角线的总数)— (所有空格都放上MIN的棋子后,MIN三个棋子所 组成的行、列及对角线.若p是MAX 必胜, e(P)为正无穷大 3.若p是MIN 必胜, e(P)为负无穷大 17:12 60页 一子棋游戏 设有一个三行三列的棋盘,如下图所示,两个棋手 轮流走步,每个棋手走步时往空格上摆一个自己的棋 子,谁先使自己的棋子成三子一线为赢。设MAX方 的棋子用×标记,MIN方的棋子用○标记,并规定 MAX方先走步。 估价函数 e(P)=e(+P)-e(-P) 一子棋棋盘 棋局1 解:e(+P):P上有可能使×成三子为一线的数目; e(-P):P上有可能使○成三子为一线页 不失一般,设只进行两层,即每方只走一步 棋局即估价函数 e(P)=e(+P)-e(-P)=? 具有对称性的棋盘可认为是同一棋盘。如下图: 其e(P)=e(+P)-e(-P)=5-4=1 17:12 62页 ×最佳走棋(立场) S0 S3 S1 1 S0 ○最佳走棋 S3 S4 1 (倒推值) -1 -2 S2 S3 S4 S5 6-4=2 6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1 5-4=1 5-6=-1 5-5=0 5-6=-1 6-6=0 4-6=-2 P145漏‘与’关系 17:12 一子棋的极大极小搜索 63页 5.4.2 α ? β 过程 极大极小过程先生成一棵博弈搜索树, 然后再进行估值的倒推计算。 这种生成节点和计算估值相分离的搜索 方式,需要生成规定深度内的所有节点, 因此搜索效率较低。 如果能边生成节点边对节点估值,并剪去 一些没用的分枝,以减少搜索的次数,这 种技术被称为α-β过程/剪枝。 17:12 64页 中止搜索---剪技的规则 1. 任何MIN节点n的α值小于或等于它先辈MAX 节点的α值,则n 以下的分枝可停止搜索,并令 节点n的倒推值为β。 这种剪枝称为α剪枝。 β =α 2.任何MAX节点n的α值大于或等于它先辈MIN 节点的β值,则n 以下的分枝可停止搜索,并令 节点n的倒推值为α。 这种剪枝称为β剪枝。 α = β 17:12 65页 值,取最大倒推值 值,取最小倒推值 发现S5=23,S6就不用搜索了 17:12 66页 17:12 67页

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

相关推荐:

网友评论:

栏目分类

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

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

Top