ch2与或图搜索问题

1、第第2章章 与或图搜索问题与或图搜索问题目标目标目标目标初始节点初始节点sabc2.1 基本概念基本概念v与或图是一个超图，节点间通过连接符连接。与或图是一个超图，节点间通过连接符连接。vK-连接符：连接符：.K个个耗散值的计算耗散值的计算k(n, N) = Cn+k(n1, N)+k(ni, N)其中：其中：N为终节点集为终节点集 Cn为连接符的耗散值为连接符的耗散值.i个个nn1n2ni目标目标目标目标初始节点初始节点 解图：解图：能解节点能解节点v终节点是能解节点终节点是能解节点v若非终节点有若非终节点有“或或”子节点时，当且仅当其子子节点时，当且仅当其子节点至少有一能解时，该非终节点才

2、能解。节点至少有一能解时，该非终节点才能解。v若非终节点有若非终节点有“与与”子节点时，当且仅当其子子节点时，当且仅当其子节点均能解时，该非终节点才能解。节点均能解时，该非终节点才能解。不能解节点不能解节点v没有后裔的非终节点是不能解节点。没有后裔的非终节点是不能解节点。v若非终节点有若非终节点有“或或”子节点，当且仅当所有子子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。节点均不能解时，该非终节点才不能解。v若非终节点有若非终节点有“与与”子节点时，当至少有一个子节点时，当至少有一个子节点不能解时，该非终节点才不能解。子节点不能解时，该非终节点才不能解。普通图搜索的情况普通图搜索的

3、情况f(n) = g(n) + h(n)对对n的评价实际是对通过的评价实际是对通过n的这条路径的评价的这条路径的评价ns与或图与或图: 对局部图的评价对局部图的评价目标目标目标目标初始节点初始节点abc两个过程两个过程v图生成过程，即扩展节点图生成过程，即扩展节点 从最优的局部途中选择一个节点扩展从最优的局部途中选择一个节点扩展v计算耗散值的过程计算耗散值的过程 对当前的局部图重新计算耗散值对当前的局部图重新计算耗散值AO*算法举例算法举例其中：其中： 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

4、设：设：K连接符连接符的耗散值为的耗散值为K目标目标目标目标初始节点初始节点n0n1n2n3n4n5n6n7n8目标目标目标目标初始节点初始节点n0n1n2n3n4n5n6n7n8初始节点初始节点n0n1(2)n4(1)n5(1)红色：红色：4黄色：黄色：3目标目标目标目标初始节点初始节点n0n1n2n3n4n5n6n7n8初始节点初始节点n0n4(1)n5(1)红色：红色：4黄色：黄色：6n1n2(4)n3(4)5目标目标目标目标初始节点初始节点n0n1n2n3n4n5n6n7n8红色：红色：5黄色：黄色：6初始节点初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0

5、)n8(0)2目标目标目标目标初始节点初始节点n0n1n2n3n4n5n6n7n8红色：红色：5黄色：黄色：6初始节点初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)212.3 博弈树搜索博弈树搜索v博弈问题博弈问题 双人双人 一人一步一人一步 双方信息完备双方信息完备 零和零和分钱币问题分钱币问题（7）（6,1）（5,2）（4,3）（5,1,1）（4,2,1）（3,2,2）（3,3,1）（4,1,1,1）（3,2,1,1） （2,2,2,1）（3,1,1,1,1）（2,2,1,1,1）（2,1,1,1,1,1）对方先走对方先走我方必胜我方必胜中国象棋中

6、国象棋v一盘棋平均走一盘棋平均走50步，总状态数约为步，总状态数约为10的的161次次方。方。v假设假设1毫微秒走一步，约需毫微秒走一步，约需10的的145次方年。次方年。v结论：不可能穷举。结论：不可能穷举。vOthello 奥塞罗奥塞罗vCheckers 西洋跳棋西洋跳棋vChess 国际象棋国际象棋vChinese chess 中国象棋中国象棋vConnectSix 六子棋六子棋vShogi 日本将棋日本将棋vGo 围棋围棋v研究领研究领域域v博弈复杂度：包括状态空间复杂度、博弈博弈复杂度：包括状态空间复杂度、博弈树复杂度（以树复杂度（以10为底）为底）棋类状态空间复杂度博弈树的复杂度C

7、hess50123Chinese chess52150Shogi71226Go160400极小极大搜索法极小极大搜索法 其基本思想是：其基本思想是： (1)设博弈的双方中一方为设博弈的双方中一方为A，另一方为，另一方为B。为。为一方一方(如如A)寻找最优行动方案。寻找最优行动方案。(2)为了找到当前的最优行动方案，需要对各个为了找到当前的最优行动方案，需要对各个可能的方案所产生的后果进行比较。可能的方案所产生的后果进行比较。(3)为计算得分，需要根据问题的特性信息定义为计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树端节点的一个估价函数，用来估算当前博弈树端节点的得分。得分

8、。 (4)当端节点的估值计算出来后，再推算出父节当端节点的估值计算出来后，再推算出父节点的得分，方法是：对点的得分，方法是：对“或或”节点，选其子节节点，选其子节点中一个最大的得分作为父节点的得分，这是点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己为了使自己在可供选择的方案中选一个对自己最有利的方案；对最有利的方案；对“与与”节点，选其子节点中节点，选其子节点中一个最小的得分作为父节点的得分，这是为了一个最小的得分作为父节点的得分，这是为了立足于最坏的情况。立足于最坏的情况。 (5)如果一个行动方案能获得较大的倒推值，则如果一个行动方案能获得较大的倒推值，则它

9、就是当前最好的行动方案。它就是当前最好的行动方案。1，极小极大过程，极小极大过程05-333-3022-30-23541-30689-30-33-3-3-21-36-30316011极大极大极小极小abv例例 一字棋游戏。设有如图所示的九个空格，一字棋游戏。设有如图所示的九个空格，由由A，B二人对弈，轮到谁走棋谁就往空格上二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成放一只自己的棋子，谁先使自己的棋子构成“三子成一线三子成一线”谁就取得了胜利。谁就取得了胜利。ba图图 一字棋一字棋 设设A的棋子用的棋子用“a”表示，表示，B的棋子用的棋子用“b”表示。表示。为了不致于生

10、成太大的博弈树，假设每次仅扩展为了不致于生成太大的博弈树，假设每次仅扩展两层。估价函数定义如下：两层。估价函数定义如下：设棋局为设棋局为P，估价函数为，估价函数为f(P)。 (1)若若P是是A必胜的棋局，则必胜的棋局，则f(P)=+。 (2)若若P是是B必胜的棋局，则必胜的棋局，则f(P)=-。 (3)若若P是胜负未定的棋局，则是胜负未定的棋局，则 f(P)=e(+P)-e(-P) v其中其中e(+P)表示棋局表示棋局P上有可上有可能使能使a成为三子成一线的数目；成为三子成一线的数目；e(-P)表示棋局表示棋局P上有可能使上有可能使b成为三子成一线的数目。例如，成为三子成一线的数目。例如，对于

11、所示棋局对于所示棋局: e(P)=6-4=2v另外，我们假定具有对称性的另外，我们假定具有对称性的两个棋局算作一个棋局。还假两个棋局算作一个棋局。还假定定A先走棋，我们站在先走棋，我们站在A的立场的立场上。上。 baab1ab0ab1ab0ab1aS11aS22ab1ab0ab1ab0a b2a1ab1S4ab2S5S0 3-, +AB-,3(a)-, +12AB3-,3(b)12AB3, +383,3(c)12ABC3, +-,23823,3(d)-,1412ABDC3,14-,2382143,3(e)12ABDC3,3-,22,238214523,3(f ) - 剪枝剪枝v极大节点的下界为极大节点的下界为 。v极小节点的上界为极小节点的上界为 。v剪枝的条件：剪枝的条件： 后辈节点的后辈节点的 值值祖先节点的祖先节点的 值时，值时， 剪枝剪枝 后辈节点的后辈节点的 值值祖先节点的祖先节点的 值时，值时， 剪枝剪枝v简记为：简记为： 极小极小极大，剪枝极大，剪枝 极大极大极小，剪枝极小，剪枝86-31453-350 - 剪枝（续）剪枝（续）3-3022-30-2309-300-303305411-31661abcdefghijkmn - 剪枝的效率剪枝的效率v - 剪