人工智能 吉林大学珠海学院计算机科学与技术系 2.1 与或图 (AND/OR Graph) 的搜索 为严格描述 AND/OR 图，我们先推广弧的概念。在 有向图中的弧是从一个父亲节点指向它的儿子节 点的。 在 AND/OR 图中使用的弧叫做超弧，一个 超弧可以把一个父亲节点和 k 个儿子节点同时连接 起来，这样的弧也叫做 k 连弧，在 AND/OR 图中， k 连弧用弧线连接起来。当 k=1 时， k 连弧退化成 通常的有向图中的弧。
人工智能 吉林大学珠海学院计算机科学与技术系 k 连弧 一般的弧
人工智能 吉林大学珠海学院计算机科学与技术系 n7 n6 n3 n0 n1 n4 n2 n5 n8 与或图
人工智能 吉林大学珠海学院计算机科学与技术系 n5n5 n1n1 n3n3 n6n6 n7n7 n8n8 n5n5 n0n0 n7n7 n8n8 n4n4 n0n0 三个解图 n5n5 n7n7 n8n8 n4n4 n0n0
人工智能 吉林大学珠海学院计算机科学与技术系 在定义中假定 AND/OR 图不含回路，即是说， 图中不存在 一个节点的后裔也是这个节点的祖先的情形。 不含回路保 证了节点间具有部分序关系， 从而保证了下面定义的合理 性。 设 N 是 AND/OR 图 G 的目标节点集合， 从图中任意一个节 点 n 出发到 N 的一个解图是 AND/OR 图 G 的一个子图， 用 G’ 表示， 递归定义如下： 如果 n 是 N 中的一个节点， 则 G’ 只包括 n. 如果 n 有一条从 n 出发的 k 连弧 ai, 这个 k 连弧连接的儿子节 点是 {n1, n2,..., nk}, 则解图 G’ 由节点 n, k 连弧 ai, 和由 n1, n2,..., nk 出发的解图构成。 否则， G 没有从 n 出发到 N 的解图。
人工智能 吉林大学珠海学院计算机科学与技术系 与或图 设从节点 n 到目标节点集合 N 的费用用 c(n, N) 表示， 则 c(n, N) 定义如下： 如果 n 是 N 中的一个节点， 则 c(n, N)=0 ， 如果 n 有一条从 n 出发的 k 连弧 ai, 这个 k 连弧连接的儿子节点 是 {n1, n2,..., nk}, 则解图 G’ 由节点 n, k 连弧 ai, 和由 n1, n2,..., nk 出发的解图构成。这时，解图 G’ 的费用定义为 c(n, N)= c(ai)+ c(n, n1)+…+ c(n, nk), 其中 c(ai) 是 k 连弧 ai 的 费用. 否则， G 没有从 n 出发到 N 的解图。设其费用为无穷大 ∞. 。 例如，如果假定 k 连弧的费用是 k, 则图 3.4 所示的 AND/OR 图的两个解图中，左图的费用是 8 ， 右图的费用是 7 。
人工智能 吉林大学珠海学院计算机科学与技术系 2.2 与或图的启发式搜索 AND/OR 图的启发搜索过程 AO* 1. 建立一个只由根节点 s 构成的搜索图 G, 设从 s 出发的解图的 费用为 q(s)=h(s), 如果 s 是目标节点， 用 SOLVED 标记 s. 2. until s 被标上 SOLVED, do: 3. begin 4. 通过跟踪从 s 出发的有标记的超弧计算候选解图 G’( 这些 标记在后 面的步骤 11 中给出 ) 5. 在 G’ 中选一个不是目标节点的叶节点 n, 6. 扩展节点 n, 产生节点 n 的所有儿子 {n1, n2,..., nk}, 并把这 些儿子连到图 G 上, 对于每一个不曾在 G 中出现的儿子 nj, 设 q(nj)=h(nj), 如果这些儿子节点中的某些节点是目标节点, 则 把这些节点标记为 SOLVED.
人工智能 吉林大学珠海学院计算机科学与技术系 7. 建立一个由 n 构成的单元素集合 S. 8. 直到 S 变空, do: 9. begin 10. 从 S 中删除其儿子节点不在 S 中的节点, 记此节点为 m. 11. 按以下步骤修改 m 的费用 q(m), 对于每一个从 m 出发的 指向节点集合 {ni1, ni2,..., nik} 超弧 ai ，计算 qi(m)= c(ai)+ q(ni1)+…+ q(nik), 这里的 q( nij) 或者是在本循环内部的前面步骤计算出的值，或 者是在步骤 6 中指定的值。 设 q(m) 是所有 qi(m) 的最小者， 标记实现 这个最小值的超弧，如果本次标记与以前的标记不同， 擦去以前的 标记， 如果这些超弧指向的所有儿子节点都标记了 SOLVED, 则把 m 也标上 SOLVED. 12. 如果 m 标记了 SOLVED 或者 m 修改后的费用与以前的费用不同， 则把 m 通过标记的超弧连接的父亲节点加入到 S 中， 13 end 14. end
人工智能 吉林大学珠海学院计算机科学与技术系 算法分为两个阶段 步. 自顶向下的产生候补解图, 并扩展候补 解图的过程 , 自底向上修正费用值, 标记弧及的过程. 例 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,
人工智能 吉林大学珠海学院计算机科学与技术系 n1 n5 n , n0 n1 n5 n4 5 1 n2,4 n7,0 3, n0 4 n8,0 n6,2 5, n0 n1 n5 n4 5 1 n2,4 n7,0 n8,0 n6,2 n3, 4 22 一次循环后 二次循环后 三次循环后 四次循环后 图 3.5 AO* 搜索算法的例子 n1 n5 n , n0 n3 4 n2 4
人工智能 吉林大学珠海学院计算机科学与技术系 5, n0 n5 n4 1 n7,0 n8,0 2 搜索得到的解图
人工智能 吉林大学珠海学院计算机科学与技术系 2.3 博弈树的搜索 穷尽的极大极小过程。 两个游戏者分别为 MAX 和 MIN, MAX 想取得高的分数， 而 MIN 想取得低的分数，把整个棋的状态以及所有可能的移动都 用一个有与或图表示出来， 对于某一游戏者求出他的解图， 就是为游戏者制定的赢的策略。 Nim 游戏，桌子上有 7 枚硬币， 由 MAX 和 MIN 两个人分别 把一堆硬币分成不相等的两堆，谁不能继续做下去，谁就算 输， 为 MAX 制定一个赢的策略。 知识表示， 二元组《 s, p 》, 其中 s 为一集合， 表示桌面上各 堆的硬币数， p 表示对当前状态应该移动的游戏者。例如 （ 2 ， 3 ， 2 ， MAX ） 表示现在桌面上有 3 堆硬币， 分别为 2 ， 3 ， 2 个， 此时应抡 到 MAX 移动。
人工智能 吉林大学珠海学院计算机科学与技术系 1
人工智能 吉林大学珠海学院计算机科学与技术系 固定深度的极大极小过程。 实际的游戏的状态空间是非常大的， 例如国际象棋有 个状态， 要想把所有状态都列出来， 实际上是做不 到的， 改进的处理方法是在当前状态下把游戏扩展到某 一固定的深度， 对这个深度的树的叶节点进行状态估值， 然后分别逐层地以取极大和取极小的方式上传， 最终给 出对游戏者移动的最佳建议 例； 九宫游戏 估值函数： MAX 所能占据的行， 列和对角线数 - MAX 所能占据的行， 列和对角线数 如果 MAX 赢， 为无穷大 如果 MIN 赢， 为 0 5-4=1
人工智能 吉林大学珠海学院计算机科学与技术系 两步棋的例子 S JIHGFED A BC MAX 取极大 值 MIM 取极小 值 MAX (-2) (0) (-6) (9) (-4)(-3) (-4) (-2) (-6) MAX 的移动
人工智能 吉林大学珠海学院计算机科学与技术系 过程 MINMAX: 算法分为两个阶段, 第一阶段用宽度优先产生给定深 度内的所有节点, 然后对所有叶节点进行状态估值. 第二阶 段自低向上倒推估计值, 一层取极小, 一层去极大. 直至求 出初始节点的估值.
人工智能 吉林大学珠海学院计算机科学与技术系 MIN MAX 6-5=1, 5-5=0, 4-5=-1 5-6=-1, 5-5=0, 5-6=-1, 6-6=0, 4-6=-2 5-4=1 6-4=2
人工智能 吉林大学珠海学院计算机科学与技术系
人工智能 吉林大学珠海学院计算机科学与技术系 Alpha-beta 过程 在固定深度的极大极小过程中， 对于一个给定的节点， 需要先扩展到给定的深度， 然后对叶节点进行估值，在 一层一层地向上返回值， 决定最佳移动。 为提高效率， 我们可以按深度优先方式， 从左边开始， 先对最左分支 扩展到给定深度， 定出极大和极小的取值界限，即 alpha 值和 beta 值， 然后一边扩展一边估值， 并把估值同 alpha 值和 beta 值相比较，这样就可以省掉许多节点的估 值， 当然这些节点也不必产生了， 因此提高了算法的效 率， 这就是 Alpha-beta 过程。
人工智能 吉林大学珠海学院计算机科学与技术系
人工智能 吉林大学珠海学院计算机科学与技术系 Alpha-beta 剪枝的原则 1 。 在任一个 MIN 节点， 如果发现了其 beta 值小于或者 等于它的一个 MAX 祖先节点的 alpha 值，则可以剪枝 2 。 在任一个 MAX 节点下， 如果发现了其 alpha 值大于 或者等于它的一个 MIN 祖先节点的 bata 值，则可以剪枝
人工智能 吉林大学珠海学院计算机科学与技术系 MAX MIN MAX 0 2
人工智能 吉林大学珠海学院计算机科学与技术系 MI N 图 3.8 alpha-beta 剪枝过程 MA X 最佳移动 β=0 α=0 β=0 α=0 α=1 β=-3 β=1 α=6 α=1