2020/3/5
17
华北电力大学
AO及AO*搜索算法
▪ 利用结点的可解/不可解性质，能从搜索图中删去可解 结点的任何不可解结点的子结点；同样地，能删去不可 解结点的所有的子结点
▪ 搜索这些被删除的结点是没有意义的，而只会降低搜索效率
与普通图搜索算法相类似，与/或图搜索算法有盲目 搜索，如广度优先搜索法、深度优先搜索法等；也有启发 式搜索，如AO及AO*搜索法
2020/3/5
18
华北电力大学
AO*算法——两个过程1
▪ 图生成过程，即扩展节点
▪ 对于每一个已经扩展了的节点，AO*算法都有一个 指针，指向该节点的后继节点中，耗散值小的那个 连接符
▪ 从最优的局部图中选择一个节点扩展
▪ 图生成过程，就是从初始节点出发，按照该指针向 下搜索，一直到找到一个未扩展的节点为止。然后 扩展该节点。并对其后继节点赋估计耗散值和加能 解标记
n8
目标
23
红色：4 黄色：6
华北电力大学
n1
n3 n6
n7目标
2020/3/5
AO*算法举例
n0
初始节点
n0
n2 n5
n1 5
n4 n2(4) n5(1)
n3(4) n6(2) n8
目标
n7(0)
24
初始节点
n4(1) 2
n8(0)
红色：5 黄色：6
华北电力大学
n1
n3 n6
n7目标
2020/3/5
AO*算法举例
n0
初始节点
n0
n2 n5
n1 5
n4 n2(4) n5(1)
n3(4) n6(2) n8
目标
n7(0)
25
初始节点
1 n4(1)
2
n8(0)
红色：5 黄色：6
华北电力大学
AO*与A的区别
▪ AO*算法不能像A算法那样，单纯靠评价某一个节点来评 价局部图
▪ 由于k-连接符连接的有关子节点，对父节点能解与否以及耗散值 都有影响，因而显然不能象A算法那样优先扩展其中具有最小耗散 值的节点
▪ 若f（p）＝＋∞，则MAX赢，若f（p）＝－∞，则MIN赢 ▪ 顶节点深度d＝0，MAX代表程序方，MIN代表对手方，
② 若n是一个外向连接符指向后继节点{n1，…，ni}，并设 该连接符的耗散值为Cn，则
k(n, N) = Cn+k(n1, N)+…+k(ni, N)
其中：N为目标节点集
n
2020/3/5
…...
n1 n2
ni
i个
10
华北电力大学
例:k-连接符的耗散为k
K(n0,{n7,n8})=8
K(n0,{n7,n8})=7
•根节点：没有任何父节点的节点 •端（叶）节点：没有任何后继节点
的节点
•S •两个连接符 •1-连接符指向a（或节点） •2-连接符指向{b、c}（与节点）
目标2•目标2
•b的与节点（2-连接符） •c的或节点（1-连接符）
5
华北电力大学
2.1 基本概念
▪ 与或图是一个超图，节点间通过连接符连接 ▪ K-连接符：从一个父节点指向一组k个后继节点
2020/3/5
26
华北电力大学
2.3 博弈树搜索
▪ 博弈问题
▪ 双人，一人一步 ▪ 双方信息完备 ▪ 零和：即对一方有利的棋，对另一方肯定是不利的，不存在对双
方均有利、或均无利的棋。对弈的结果是一方赢，而另一方输， 或者双方和棋
▪ 用与或图表示
▪ 在决定自己走步时只需考虑对自己有利的一步——“或” ▪ 考察对方时,则应考虑对方所有可能的走步——“与” ▪ 两人严格地轮流走步，使博弈状态图呈现出严格的与和或的交替
极小极大搜索过程(2)
▪ 假设：
▪ 双方都是对弈高手 ▪ 在只看一步棋的情况下，我方一定走评价函数值最
大的一步棋 ▪ 对方一定走评价函数值最小的一步棋 ▪ 在只看一步的情况下最好的棋，从全局来说不一定
就好，还可能很不好 ▪ 为了走出好棋，必须多看几步，从多种可能状态中
选择一步好棋
2020/3/5
32
第二章 与或图搜索问题
华北电力大学 计算机系 刘丽
学习目标
▪ 了解一般的与或图搜索问题 ▪ 掌握与或图的启发式搜索算法AO* ▪ 了解博弈树搜索问题 ▪ 掌握博弈树搜索中的
▪ 极小极大方法 ▪ α-β剪枝搜索方法
2020/3/5
2
华北电力大学
知识点
2020/3/5
3
华北电力大学
与或图搜索问题
▪ 状态空间搜索问题
▪ 评价函数值大于0，表示棋局对我方有利，对对方不 利
▪ 评价函数小于0时，表示棋局对我方不利，对对方有 利
▪ 评价函数值越大，表示对我方越有利。当评价函数 值等于正无穷大时，表示我方必胜
▪ 评价函数值越小，表示对我方越不利。当评价函数 值等于负无穷大时，表示对方必胜
2020/3/5
31
华北电力大学
▪ 每一步结束条件可根据时间限制、存储空间限制或 深度限制等因素加以确定
▪ 搜索策略可采用宽度、深度或启发式方法，一个阶 段搜索结束后，要从搜索树中提取一个优先考虑的 “最好的”走步，这就是实用策略的基本点
▪ 极小极大搜索策略就是其中的一种
2020/3/5
30
华北电力大学
极小极大搜索过程(1)
▪ 假定有一个评价函数可以对所有棋局评估：
▪ 图2.2给出n0→{n7，n8}的三个解图
2020/3/5
7
华北电力大学
基本概念
解图：
2020/3/5
8
华北电力大学
基本概念
▪ 解图的递归定义 ▪ 一个与或图G中，从节点n到节点集N的解图记为G’，
G’是G的子图
①若n是N的一个元素，则由单一节点组成 ②若n有一个指向节点{n1，…，nk}的外向连接符K，使得
▪ 一个节点的后继节点之间是“或”的关系
▪ 与或图搜索问题
▪ 一个节点其部分或全部后继节点是“与”的 关系
▪ 博弈树的搜索
2020/3/5
4
华北电力大学
a
目标1
2020/3/5
简单的与或图例子
初始节点s b
•超图 •超弧线（连接符） •K-连接符：从父节点指向一组
K个后继节点的节点集（K>1
c 时注意小圆弧）
华北电力大学
n1 n3
AO*算法举例
n0
初始节点
n0
初始节点
n1(2)
n2
n4
n4(1)
n5
n5(1)
n6
n7目标
2020/3/5
n8
目标
22
红色：4 黄色：3
华北电力大学
n1 n3
AO*算法举例
n0
初始节点
n0
初始节点
n1 5
n2
n4
n2(4)
n4(1)
n5
n5(1)
n3(4)
n6
n7目标
2020/3/5
层次 ▪ 可设计特殊的与/或图搜索算法，即博弈树搜索算法
2020/3/5
27
华北电力大学
分钱币问题（Grundy博弈）
对方先走
（7）
对方扩展的节点1,1） （4,2,1）
（3,2,2）
（3,3,1）
对方扩展的节点
（4,1,1,1） （3,2,1,1） （2,2,2,1）
• 中国象棋：一盘棋平均走50步，总状态数约为10的161 次方。假设1毫微秒走一步，约需10的145次方年→→不 可能穷举
• 即使用了强有力的启发式搜索技术，也不可能使分枝压 到很少
2020/3/5
29
华北电力大学
与或图搜索技术
▪ 解决：
▪ 实用策略：把目标确定为寻找一步好棋，等对手回 敬后再考虑寻找另一步好棋
▪ 局部图的耗散值k(n，N)，则：
① 若n是局部图的一个叶节点，则k(n，N)＝h(n) ② 若n是一个外向连接符指向后继节点{n1，…，ni},并设
该连接符的耗散值为Cn，则 k(n，N)＝Cn+ k(n1，N) + … + k(ni，N)
2020/3/5
12
华北电力大学
能解节点(Solved)
▪ 一直到计算出根节点的值为止。获得根节点取值的那一分枝，即 为所选择的最佳走步
2020/3/5
33
华北电力大学
极小极大搜索过程——叶节点的评价函数
▪ 是一个静态估计函数f
▪ 对棋局的势态（节点）作出优劣估值 ▪ 可根据势态优劣特征来定义（主要用于对端节点的“价值”
进行度量）
▪ 一般规定：
▪ 有利于MAX的势态，f（p）取正值；有利于MIN的势态，f （p）取负值；势均力敌的势态，f（p）取0值
的节点集
2020/3/5
…... K个
6
华北电力大学
基本概念
▪ 解图
▪ 与或图中某一个节点n到节点集N的一个解图类似于 普通图中的一条解路径
▪ 解图的求法：
▪ 从节点n开始，正确选择一个外向连接符，再从该连 接符所指的每一个后继节点出发，继续选一个外向 连接符，如此进行下去直到由此产生的每一个后继 节点成为集合N中的一个元素为止
我方扩展的节点
（3,1,1,1,1）
（2,2,1,1,1） 我方必胜
对方扩展的节点
（2,1,1,1,1,1）
2020/3/5
28
华北电力大学
与或图搜索技术
▪ 问题
▪ 对简单的博弈或复杂博弈的残局，可以用类似于与或 图的搜索技术求出解图，解图代表了从开局到终局任 何阶段上的弈法