与或图搜索问题

4 极小极大过程
模拟的就是人的这样一种思维过程。当轮到我方走棋 时，首先按照一定的搜索深度生成出给定深度d以内 的所有状态，计算所有叶节点的评价函数值。然后从 d-1层节点开始逆向计算：对于我方要走的节点（用 MAX标记，称为极大节点）取其子节点中的最大值为 该节点的值（因为我方总是选择对我方有利的棋）； 对于对方要走的节点（用MIN标记，称为极小节点） 取其子节点中的最小值为该节点的值（对方总是选择 对我方不利的棋）。一直到计算出根节点的值为止。 获得根节点取值的那一分枝，即为所选择的最佳走步
目标
n7
目标
n0 n1 n2
初始节点
n1(2) n4
n0
初始节点
n4(1)
n3
n5
n5(1)
n6
n8
目标
n7
红Leabharlann Baidu：4 黄色：3
目标
n0 n1 n2
初始节点
n1 n4 5
n0
初始节点
n4(1) n2(4)
n3
n5 n3(4)
n5(1)
n6
n8
目标
n7
红色：4 黄色：6
目标
n0 n1 n2
初始节点
…... n1 n2 i个 ni
• 解图： 初始节点
目标 目标
在与或图是无环（即不存在这样的节点---其后 继节后同时又是它的祖先）的假定下，解图可 递归定义如下： 定义：一个与或图G中，从节点n到节点集N的 解图记为 ， 是G的子图。 ①若n是N的一个元素，则 由单一节点组成； ②若n有一个指向节点{n1，…，nk}的外向连 接符K，使得从每一个ni到N有一个解图 （i=1，…，k），则 由节点n，连接符K，及 {n1，…，nk}中的每一个节点到N的解图所组 成； ③否则n到N不存在解图。
分钱币问题
对方先走 （6,1） （7） （5,2） （3,2,2） （4,3）
（5,1,1） （4,2,1）
（3,3,1）
（4,1,1,1） （3,1,1,1,1） （2,1,1,1,1,1）
（3,2,1,1）
（2,2,2,1） 我方必胜
（2,2,1,1,1）
中国象棋
一盘棋平均走50步，总状态数约为10的161次 方。 假设1毫微秒走一步，约需10的145次方年。 结论：不可能穷举。
能解节点
终节点是能解节点 若非终节点有“或”子节点时，当且仅当其子 节点至少有一能解时，该非终节点才能解。 若非终节点有“与”子节点时，当且仅当其子 节点均能解时，该非终节点才能解。
不能解节点
没有后裔的非终节点是不能解节点。 若非终节点有“或”子节点，当且仅当所有子 节点均不能解时，该非终节点才不能解。 若非终节点有“与”子节点时，当至少有一个 子节点不能解时，该非终节点才不能解。
α-β剪枝的其他应用
故障诊断
A 风险投资
B
C
D
n1 n4 5
n0
初始节点
n4(1) n2(4)
n3
n5 n3(4) n6(2)
n5(1)
2
n6
n8
n8(0)
目标
n7
目标
n7(0)
红色：5 黄色：6
n0 n1 n2
初始节点
n1 n4 5
n0
初始节点
1 n4(1)
n2(4) n3 n5 n3(4) n6(2) n6 n8 n8(0) n5(1) 2
普通图搜索的情况
s
n
f(n) = g(n) + h(n) 对n的评价实际是对从s到n这条路径的 评价
与或图: 对局部图的评价
初始节点
c
a
b 目标 目标
AO*算法举例
n0 n1 n2 n4
初始节点
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
与或图搜索
一个问题可以有几种求解方法，只要其中一种 方法可以求解问题，则该问题被求解。也就是 说，对求解该问题来说，方法之间是"或"的关 系。但在用每一种方法求解时，又可能需要求 解几个子问题，这些子问题必须全部求解，才 可能用该方法求解原始问题。也就是说，这些 子问题之间是"与"的关系。此类问题可以用与 或图来表示。
f
0
0 1
d b
0 3
m h
1
1
n e
k i
-3 1
6
a
0
c
-3
3
g
5 4
6
j
0
5
-3
3 3
-3
0
2
2
-3
0
-2
3 5 4
1
-3
0 6
8 9
-3
α-β剪枝
极大节点的下界为α。 极小节点的上界为β。 剪枝的条件：
后辈节点的β值≤祖先节点的α值时， α剪枝 后辈节点的α 值≥祖先节点的β值时， β剪枝
简记为：
极小≤极大，剪枝 极大≥极小，剪枝
α-β剪枝（续）
f
0 0 1
d b
0 3
m h
1
1
n e
k i
-3 1
6
a
0
c
-3
3
g
5 4
6
j
0
5
-3
3 3
-3
0
2
2
-3
0
-2
3 5 4
1
-3
0 6
8 9
-3
改进方法
若β值比α值大不了多少或极相近，这时也可以进行剪枝，以便有 条件把搜索集中到会带来更大效果的其他路径上 不严格限制搜索的深度，当到达深度限制时，如出现博弈格局有 可能发生较大变化时（如出现兑子格局），则应多搜索几层，使 格局进入较稳定状态后再中止，这样可使倒推值计算的结果比较 合理，避免考虑不充分产生的影响，这是等候状态平稳后中止搜 索的方法。 当算法给出所选的走步后，不马上停止搜索，而是在原先估计可 能的路径上再往前搜索几步，再次检验会不会出现意外，这是一 种增添辅助搜索的方法。 对某些博弈的开局阶段和残局阶段，往往总结有一些固定的对弈 模式，因此可以利用这些知识编好走步表，以便在开局和结局时 使用查表法。只是在进入中盘阶段后，再调用其他有效的搜索算 法，来选择最优的走步。
与或图搜索
初始节点s a c b
目标 目标
在普通图中，目标用一个节点表达，而在与或 图中，目标则表现为一个节点的集合，该集合 中由一些子目标节点组成。值得指出的是，解 图不一定要求到达目标集中的每一个子目标节 点，而只要求解图的端节点是目标集中的节点 即可。也就是说，解图中的端节点是目标集的 子集即可
1
极大
1
b
0
极小
6
a
0
3
1
0
-3
3
-3
-3
-2
1
-3
6
-3
0
5
-3
3 3
-3
0
2
2
-3
0
-2
3 5 4
1
-3
0 6
8 9
-3
5 α-β剪枝
设某博弈问题如下图所示，应用极小极大方法进行搜索。假设搜索的 顺序为从下到上，从左到右。当计算完a的值为0后，由于b是极大节 点，马上就可以知道b的值大于等于0。接下来求c的值。由于c是极小 节点，由d的值为-3，知道c的值小于等于-3。而a和c都是b的子节点， 所以即便不扩展节点e，也可以知道b的值一定为0了。所以在这种情 况下，没有生成节点e的必要。同样，在知道b的值为0后，由于k是极 小节点，所以立即知道k的值要小于等于0。而通过节点f、g，知道h 的值至少为3。这样即便不扩展A所包围的那些节点，也能知道k的值 一定为0。所以A包围的那些节点也没有生成的必要，不管这些节点取 值如何，都不影响k的值。如果在搜索的过程中，充分利用这些信息， 不就可以少生成很多节点，从而提高搜索的空间利用率吗？α-β过程 正是这样一种搜索方法。
1 基本概念
与或图是一个超图，节点间通过连接符连接。 K-连接符：
…...
K个
耗散值的计算
若解图的耗散值记为k（n，N），则可递归计算 如下： ①若n是N的一个元素，则k（n，N）＝0； ②若n是一个外向连接符指向后继节点{n1，…， ni}，并设该连接符的耗散值为Cn，则 n k(n, N) = Cn+k(n1, N)+…+k(ni, N) 其中：N为终节点集
目标
n7
目标
n7(0)
红色：5 黄色：6
AO*算法与A算法区别
AO*算法不能像A算法那样，单纯靠评价某一个节点来 评价局部图。 由于k-连接符连接的有关子节点，对父节点能解与否以 及耗散值都有影响，因而显然不能象A算法那样优先扩 展其中具有最小耗散值的节点。 AO*算法仅适用于无环图的假设，否则耗散值递归计算 不能收敛，因而在算法中还必须检查新生成的节点已在 图中时，是否是正被扩展节点的先辈节点。 AO*算法没有OPEN和CLOSED表，而AO*算法只用一 个结构G，它代表到目前为止已明显生成的部分搜索图， 图中每一个节点的h（n）值是估计最佳解图，而不是估 计解路径。
2 AO*算法
第一阶段：图生成过程，即扩展节点。 对于每一个已经扩展了的节点， 算法都有一个指针，指向该节点的后 继节点中，耗散值小的那个连接符。图生成过程，就是从初始节点出 发，按照该指针向下搜索，一直到找到一个未扩展的节点为止。然后 扩展该节点。从下面的讨论可以知道，这实际上扩展的是一个耗散值 最小的局部图。 第二阶段：耗散值计算过程。 这是一个逆向的计算过程。设n为最新被扩展的节点，该节点有m个 外向连接符连接n的所有后继节点。则根据耗散值的计算公式，可以 计算出节点n相对于每一个外向连接符的耗散值。从中选择一个最小 值作为n的耗散值。并标记一个指针指向产生最小耗散值的外向连接 符。对于n的父节点，进行同样的计算。重复这一过程，直到初始节 点s为止。这时，从s出发，选择那些指针所指向的连接符得到的局部 图，为当前耗散值最小的局部图。 当连接符全部为1－连接符时，局部图就是一个路径，选择一个耗散 值最小的局部图扩展
3 博弈树搜索
博弈问题
双人 一人一步 双方信息完备 零和
博弈问题为什么可以用与或图表示
当轮到我方走棋时，只需从若干个可以走的棋 中，选择一个棋走就可以了。从这个意义上说， 若干个可以走的棋是“或”的关系。 轮到对方走棋时，对于我方来说，必须能够应 付对手的每一种走棋。这就相当于这些棋“与 "的关系。