2013第三章_与或图的搜索

第10次课 10月07日
上次课程回顾




与或图搜索:搜索从初始节点到一组终节点集N的一个 解图。 对于与或图搜索，是通过对局部图的评价来选择待扩 展的节点。 解图的求法是：从节点n开始，正确选择一个外向连接 符，再从该连接符所指的每一个后继结点出发，继续 选一个外向连接符，如此进行下去直到由此产生的每 一个后继节点成为集合N中的一个元素为止。 具有最小耗散值的解图称为最佳解图。 能解节点 不能解节点
算法

极大极小过程MINIMAX：
1. T:=(s, MAX)，OPEN:=(s)，CLOSED:=( );开始时树由初始节点 构成，OPEN表只含有S. 2. LOOP1: IF OPEN =( ) THEN GO LOOP2; 3. n:=FIRST(OPEN)，REMOVE(n,OPEN)，ADD(n,CLOSED);将n放到 CLOSED表的前面， 4. IF n可直接判定为赢, 输或平局 THEN f(n):= -0，GO LOOP1 ELSE EXPAND(n){ni}， ADD ({ni} ，T) IF d{ni} k THEN ADD({ni}, OPEN) ,GO LOOP1 ELSE 计算f(ni); ni达到深度k,计算各端节点f值.
n5(1)
2
n6
n8
n8(0)
目标
n7
目标
n7(0)
红色：5 蓝色：6
3次循环之后
n0 n1 n2
初始节点
n1 n4 5
n0
初始ห้องสมุดไป่ตู้点
1 n4(1)
n2(4)
n3
n5 n3(4) n6(2)
n5(1)
2
n6
n8
n8(0)
目标
n7
目标
n7(0)
红色：5 蓝色：6
4次循环之后
两个过程

图生成过程，即扩展节点
第9次课 09月28日
上次课程回顾

盲目搜索策略
启发式搜索策略

第三章 与或图的搜索
1
2 3 1 8 4 7 6 5
2
或
或
c
或
2 3 1 8 4 7 6 5
d
2 8 3 1 4 7 6 5
3
6
2 3 1 8 4 7 6 5
9
2 8 3 1 6 4 7 5
4
5
2 8 3 1 4 7 6 5
7 8
1，极小极大搜索过程（1）


是博弈树搜索的基本方法，目前常用的 -剪枝搜索方法，也从极小极大搜索过 程发展而来。 假定一个评价函数可以对所有的棋局进 行评价：


当评价函数>0时,表示对我方有利，越大越 有利； 当评价函数<0时,表示对对方有利，越小越 有利。
极小极大搜索过程（2）


假定双方都是对弈高手，在决定走棋时， 会尽可能多看几步，并都选评价函数有 利的走棋。 极小极大搜索过程模拟人下棋的思考过 程
2 8 3 6 4 1 7 5
2 8 3 1 6 7 5 4
8 3 2 1 4 7 6 5
2 8 3 7 1 4 6 5
2 8 1 4 3 7 6 5
2 8 3 1 4 5 7 6
目标
引入

上章介绍了状态空间问题以及搜索算法， 其特点是：


结点的后继结点是或的关系，只要一个后继 节点得以求解，该节点也就被求解。 从初始结点到目标结点，求解的是一条路径， 也就是结点的序列。
目标
n7
红色：4
黄色：3
目标 1次循环之后
n0 n1 n2
初始节点
n1 n4 5
n0
初始节点
n4(1) n2(4)
n3
n5 n3(4)
n5(1)
n6
n8
目标
n7
红色：4
蓝色：6
目标 2次循环之后
n0 n1 n2
初始节点
n1 n4 5
n0
初始节点
n4(1) n2(4)
n3
n5 n3(4) n6(2)
策略



极小极大搜索策略是考虑双方对弈若干步之后， 从可能的走步中选一个相对较好的走法来走， 即在有限的搜索深度范围内进行求解。 定义静态估计函数f, 以便对棋局作出优劣估值， 主要对端结点的“价值”进行度量。 f>0, 表对我方有利，f<0,表对方有利，f=0,表 势均力敌；f=,表我方胜，f=- 表对方胜
初始节点
n3
n5
n6
n8
其中： h(n0)=3 h(n1)=2 h(n2)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=2 h(n7)=0 h(n8)=0 设：K连接符 的耗散值为K
目标
n7
目标
n0 n1 n2
初始节点
n1(2)
n4
n0
初始节点
n4(1)
n3
n5
n5(1)
n6
n8
• 解图：
初始节点s
目标 目标
能解节点（SOLVED)


终节点是能解节点 若非终节点有“或”子节点时，当且仅 当其子节点至少有一个能解时，该非终 节点才能解。 若非终节点有“与”子节点时，当且仅 当其子节点均能解时，该非终节点才能 解。
不能解节点(UNSOLVED)


没有后裔的非终节点是不能解节点。 若非终节点有“或”子节点，当且仅当 所有子节点均不能解时，该非终节点才 不能解。 若非终节点有“与”子节点时，当至少 有一个子节点不能解时，该非终节点才 不能解。
与或图的启发式搜索算法AO*



启发式与或图搜索过程和普通图类似， 也是通过评价函数f(n)来引导搜索过程。 对于与或图，由于局部图有多个叶结点， 不能象普通图那样，通过对某一个结点 的评价来实现对整个局部图的评价。 对于与或图搜索，是通过对局部图的评 价来选择待扩展的节点。
普通图的情况
s
n
f(n) = g(n) + h(n) 表面上是对结点n的评价，实际上是对从s 到目标结点（通过n）的这条路径的评价。
图 生 成 过 程
⑦
⑧
耗 散 值 修 正
⑨ ⑩ 11
12
13 14
S:={n};建立含n的单一节点集合S.（待修正的节点集合） Until S为空, do: Begin REMOVE(m, S),mc(S);这个m的子结点mc应不在S中。 修改m的耗散值q(m): 对m指向节点集(n1i,n2i,„nki)的每个连接符i分别计算qi, qi (m)=Ci+q(n1i)+„+q(nki), q(m):= minqi(m); 加指针到minqi(m)的连接符上,或把指针修改到minqi(m) 对m的i个连接符，取计 的连接符上,即原来指针与新确定的不一致时应删去 . IF M(nji,SOLVED) THEN算结果最小的哪个耗散 M(m, SOLVED),(j=1,„,k） 值为q（m） IF M(m, SOLVED)(q(m) q0(m)) THEN ADD(ma, S); end (与9匹配) 若该连接符的所有子节点都是 m 能解或修正的耗散值与 end (,与 3也标上能解 匹配) . 能解的 则m
与或图: 对局部图的评价
初始节点
有与的关系，有或的关 系，评价起来复杂一些
c
a b 目标
把普通图的思想应用到与或图中，对解图进行评 目标 价，解图相当于解路径。红色和蓝色都是局部图， 具体选择那条路径，选择f值最小的。
AO*算法
过程AO*: ① 建立一个搜索图G，G:=s，计算q(s)=h(s)，IF GOAL(s) THEN M(s, SOLVED)； 对G中未出现的子结点添加到G ② Until s已标记为SOLVED, do: 开始时图G只包括s，耗散 中, 并计算其耗散值，若有终节 值估计为h(s)，若s是终节 ③ Begin 点则加能解标记。 点,则标记上能解。 ④ G:=FIND(G)； ⑤ n:=G中的任一非终节点（选一个非终节点作为 根据连接符标记（指 当前节点）。 针）找出一个待扩展 ⑥ EXPAND(n),生成子节点集 {ni}，其中niG， 的局部解图G G:=ADD({ni},G),计算q(ni)=h(ni)，IF GOAL(ni) THEN M(ni, SOLVED);

从最优的局部图中选择一个节点扩展 对当前的局部图重新计算耗散值

计算耗散值的过程


对于2次循环中，先扩展结点n4还是n5好 呢？ 一般选择一个最可能导致该局部图耗散值 发生较大变化的结点先扩展（因为选择 这个结点先扩展，会促使及时修改局部 解图的标志。
3.3 博弈树搜索

博弈问题



双人 一人一步 双方信息完备 (对垒双方看到的信息是一样 的，不存在一方看到另一方看不到的情况） 零和（对一方有利的走棋，对另一方是不利 的，不存在对双方均有利或者均无利的棋）
算法(续）
5. LOOP2：IF CLOSED=NIL,THEN GO LOOP3 ELSE nd=FIRST(CLOSED); 6.IF(nd MAX) (f(nci MIN)有值) THEN f(nd):=max{f(nci)},REMOVE(nd，CLOSED), GO LOOP2; 若MAX所有子节点均有值,则该MAX取其极大值. ELSE IF(nd MIN) (f(nci MAX)有值) THEN f(nd):=min{f(nci)},REMOVE(nd，CLOSED), GO LOOP2; 若MIN所有子节点均有值，则该MIN取其极小值. 7. GO LOOP2; 8.LOOP3:IF f(s)≠NIL THEN EXIT(END M(Move,T)) ; s有值,或 则结束或标记走步。