人工智能与或图搜索

2.1与或图(AND/ORGraph)搜索为严格描述AND/OR图，我们先推广弧概念。在有向图中弧是从一个父亲节点指向它儿子节点。在AND/OR图中使用弧叫做超弧，一个超弧能够把一个父亲节点和k个儿子节点同时连接起来，这么弧也叫做k连弧，在AND/OR图中，k连弧用弧线连接起来。当k=1

时，k连弧退化成通常有向图中弧。

人工智能与或图搜索第1页k连弧普通弧人工智能与或图搜索第2页n7n6n3n0n1n4n2n5n8与或图人工智能与或图搜索第3页n5n1n3n6n7n8n5n0n7n8n4n0三个解图n5n7n8n4n0人工智能与或图搜索第4页在定义中假定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解图。人工智能与或图搜索第5页与或图设从节点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。人工智能与或图搜索第6页2.2与或图启发式搜索AND/OR图启发搜索过程AO*1.建立一个只由根节点s组成搜索图G,设从s出发解图费用为q(s)=h(s),假如s是目标节点，用SOLVED标识s.2.untils被标上SOLVED,do:3.begin4.经过跟踪从s出发有标识超弧计算候选解图G’(这些标识在后面步骤11中给出)5.在G’中选一个不是目标节点叶节点n,6.扩展节点n,产生节点n全部儿子{n1,n2,...,nk},并把这些儿子连到图G上,对于每一个不曾在G中出现儿子nj,设q(nj)=h(nj),假如这些儿子节点中一些节点是目标节点,则把这些节点标识为SOLVED.人工智能与或图搜索第7页7.建立一个由n组成单元素集合S.8.直到S变空,do:9.begin10.从S中删除其儿子节点不在S中节点,记此节点为m.按以下步骤修改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中，13end14.end人工智能与或图搜索第8页算法分为两个阶段1.4-6步.自顶向下产生候补解图,并扩展候补解图过程.2.7-12,自底向上修正费用值,标识弧及过程.例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,人工智能与或图搜索第9页n1n5n41215,n0n1n5n451n2,4n7,03,n04n8,0n6,25,n0n1n5n451n2,4n7,0n8,0n6,2n3,422一次循环后二次循环后三次循环后四次循环后图3.5AO*搜索算法例子n1n5n41213,n0n34n24人工智能与或图搜索第10页5,n0n5n41n7,0n8,02搜索得到解图人工智能与或图搜索第11页2.3博弈树搜索

穷尽极大极小过程。

两个游戏者分别为MAX和MIN,MAX想取得高分数，而MIN想取得低分数，把整个棋状态以及全部可能移动都用一个有与或图表示出来，对于某一游戏者求出他解图，就是为游戏者制订赢策略。

Nim游戏，桌子上有7枚硬币，由MAX和MIN两个人分别把一堆硬币分成不相等两堆，谁不能继续做下去，谁就算输，为MAX制订一个赢策略。

知识表示，二元组《s,p》,其中s为一集合，表示桌面上各堆硬币数，p表示对当前状态应该移动游戏者。比如

（2，3，2，MAX）

表示现在桌面上有3堆硬币，分别为2，3，2个，此时应抡到MAX移动。人工智能与或图搜索第12页1人工智能与或图搜索第13页固定深度极大极小过程。

实际游戏状态空间是非常大，比如国际象棋有10120个状态，要想把全部状态都列出来，实际上是做不到，改进处理方法是在当前状态下把游戏扩展到某一固定深度，对这个深度树叶节点进行状态估值，然后分别逐层地以取极大和取极小方式上传，最终给出对游戏者移动最正确提议

例；九宫游戏

估值函数：MAX所能占据行，列和对角线数-

MAX所能占据行，列和对角线数

假如MAX赢，为无穷大假如MIN赢，为05-4=1人工智能与或图搜索第14页两步棋例子SJIHGFEDABCMAX取极大值MIM取极小值MAX(-2)(-2)(0)(0)(-6)(9)(-4)(-3)(-4)(-2)(-6)MAX移动人工智能与或图搜索第15页过程MINMAX:算法分为两个阶段,第一阶段用宽度优先产生给定深度内全部节点,然后对全部叶节点进行状态估值.第二阶段自低向上倒推预计值,一层取极小,一层去极大.直至求出初始节点估值.人工智能与或图搜索第16页MINMAX6-5=1,5-5=0,6-5=1,

5-5=0,4-5=-15-6=-1,5-5=0,5-6=-1,6-6=0,4-6=-25-4=16-4=2人工智能与或图搜索第17页人工智能与或图搜索第18页Alpha-beta过程

在固定深度极大极小过程中，对于一个给定节点，需要先扩展到给定深度，然后对叶节点进行估值，在一层一层地向上返回值，决定最正确移动。为提升效率，我们能够按深度优先方式，从左边开始，先对最左分支扩展到给定深度，定出极大和极小取值界限，即alpha值和beta值，然后一边扩展一边估值，并把估值同alpha值和beta值相比较，这么就能够省掉许多节点估值，当然这些节点也无须产生了，所以提升了算法效率，这就是Alpha-beta过程。人工智能与或图搜索第19页人工智能与或图搜索第20页Alpha-beta剪枝标准

1。在任一个MIN节点，假如发觉了其beta值小于或者等于它一个MAX祖先节点alpha值，则能够剪枝

2。在任一个MAX节点下，假如发觉了其alpha值大于或者等于它一个MIN祖先节点bata值，则能够剪枝人工智能与或图搜索第21页253120333MAXMINMAX02人工智能与或图搜索第22页MIN图3.8