人工智能第2章与或图搜索

第2章与或图搜索王庆江中国海洋大学计算机科学系《人工智能》2.1

与或图的搜索现实中，一个问题可有几种解法。崂山校区李村海尔路中韩鱼山校区…李村、海尔路、中

韩等中，只要一个

地点可到鱼山校区，则崂山校区可到鱼

山校区。问题被拆解为若干子问题，只要一个子问题可解，则问题可解!这种问题的解是一条路径，可用上一章的搜索算法求得。2.1

与或图的搜索现实中的另外一类问题–一个问题被拆成若干子问题，只有所有子问题可解，问题才可解！去鱼山校区班车零钱 公交车自驾车问题被拆解为若干子问题，只有子问题都可解，问题才可解!这时的搜索图怎么表示呢？2.1

与或图的搜索与或图又称超图。父结点与子结点的关系用超弧线（又称k-连接符）标识。父结点子结点…

…1-连接符2-连接符3-连接符k-连接符2.1

与或图的搜索与或图的示例根结点n0端（叶）结点n7和n8或结点n0n1n4n5n2n3对n1而言，n2和n3为或结点。n6与结点对n0而言，n4和n5为与结点。n7终结点直接可解的结点。n82.1

与或图的搜索结点n到终结点集N的解图从n出发，选择一个外向连接符；从连接符指向的每个结点出发，继续选择外向连接符；重复上一步，直到连接符指向的结点都属于N为止。2.1

与或图的搜索解图1n0n1n4n5n2n3n6n7n8n0n1n3n5n6n7n82.1

与或图的搜索解图2n0n1n4n5n2n3n6n7n8n0n4n5n7n82.1

与或图的搜索解图3n0n1n4n5n2n3n6n7n8n0n4n5n7n82.1

与或图的搜索一个与或图G中，从结点n到结点集N的解图G‘是G的子图，它是这样的：–当n∈N时，G’＝{n}；若n有一个k-连接符，指向{n1,n2,…,nk}，使得从ni到N都存在解图，则G’＝{n,

k-连接符,各ni到N的解图}；否则，G’＝Φ。2.1

与或图的搜索局部图单一结点是局部图；选择局部图的任一叶结点，选择其任一个外向连接符，则局部图、该外向连接符及其所指的后继结点组成新

的局部图。搜索n到N解图的过程，就是以n为根的局部图不断“生长”的过程。2.1

与或图的搜索解图的耗散记为k(n,N)。若n∈N，k(n,

N)=0；–若n有一个外向连接符指向{n1,n2,…,ni}，并设该连接符的耗散为Cn，则k(n,

N)

=

Cn

+

k(n1,

N)

+

k(n2,

N)

+

…

+

k(ni,

N)n0n4n5n7n8N

=

{n7,

n8}k(n0,

N)

=

2

+

k(n4,

N)

+

k(n5,

N)=

2

+

(1

+

k(n5,

N))

+

k(n5,

N)=

3

+

2×(2

+

k(n7,

N)

+

k(n8,

N))=

3

+

2×(2

+

0

+

0)=7h*(n)是n-N最佳解图的耗散。h*(n)

＝

min{k(n,

N)}2.1

与或图的搜索n为根的局部图的耗散估计（含义：通过“生长”这个局部图找到n-N解图的耗散估计）记为k(n,N)，表示n经一个k-连接符向N搜索。若n∈{叶结点}，则k(n,N)=h(n)；h(n)是n到N最佳解图的耗散估计。若n有一个外向连接符指向{n1,n2,…,ni}，并设该连接符的耗散为Cn，则k(n,

N)

=

Cn

+

k(n1,

N)

+

k(n2,

N)

+

…

+

k(ni,

N)n0n4n5N

=

{n7,

n8}k(n0,

N)

=

2

+

k(n4,

N)

+

k(n5,

N)=

2

+

h(n4)

+

h(n5)2.1

与或图的搜索已解结点（solved）终结点是已解结点；非终结点已解，当且仅当至少一个“或”结点已解；非终结点已解，当且仅当所有“与”结点已解。未解结点（unsolved）没有后继结点的非终结点是未解结点；非终结点未解，当且仅当所有“或”结点未解；非终结点未解，当且仅当至少一个“与”结点未解。2.2与或图的启发式搜索算法在未找到解图之前，根结点存在一个或多个局部图。n0n1n4n5n2n3n6n7n8n0n1n5n2n3n6n0n4n5n8局部图1 局部图2某一个局部图最终“生长”为解图。那么，每次先“生长”哪个局部图？2.2与或图的启发式搜索算法AO*算法的应用举例

–h(n)结点n到N的最佳解图耗散估计–怎样寻找n0到{n7,n8}的解图呢？n0n5n2n7n83n1244

n3n4112

n6002.2与或图的启发式搜索算法第一次生长n0n1n4n5n2n3n6n7n8n1n4n51）扩展n0；2）计算以n0根的局部图的耗散；3）标识耗散最小的n0为根的局部图。211n032.2与或图的启发式搜索算法第二次生长n0n1n4n5n2n3n6n81）沿n0的最佳局部图，找到一个叶结点；n72）扩展此叶结点，计算以叶结点为根的局部图的耗散；3）向上修改非终结点为根的局部图的耗散估计，表示最佳局部图；4）修改n0最佳局部图的标识。n1n4n511n03445

24n3n262.2与或图的启发式搜索算法第三次生长n0n1n4n5n2n3n81）沿n0的最佳局部图，找到一个叶结点；n72）扩展此叶结点，计算以叶结点为根的局部图的耗散；3）向上修改非终结点为根的局部图的耗散估计；4）修改n0最佳局部图的标识。5n4n1511n0444n3n2n6n7n8002

n62n52.2与或图的启发式搜索算法第四次生长n0n1n4n5n2n3n81）沿n0的最佳局部图，找到一个叶结点；n72）扩展此叶结点，计算以叶结点为根的局部图的耗散；3）向上修改非终结点为根的局部图的耗散估计；4）修改n0最佳局部图的标识。5n5n1521n0544n3n2n6n7n8002

n6n412.2与或图的启发式搜索算法以结点n为尾的红色箭头，标识结点n为根的最佳局部图。在第4步得到的n0局部图中，叶结点都属于{n7,n8}。解图：n05n70n412n5n802.2与或图的启发式搜索算法①

G:={s},计算q(s)=h(s),如果GOAL(s),THEN

M(s,SOLVED)②

While(s还没加上SOLVED标记）do{G’

=

FIND(G)n:=G’的任一个非终结点EXPAND(n)

→{nj},

计算q(nj)=h(nj),这里nj∈GG:=G∪{nj};

IF

GOAL(nj),

THEN

M(nj,

SOLVED)S

:=

{n}While

(S≠Φ)

do

{REMOVE(m,

S),

要求m的子结点∈S修改q(m)对m为根的每个局部图，计算qi(m)将指针标记指向最小耗散局部图的k-连接符上如果最小耗散局部图能解，则M(m,SOLVED)c) IF

(m,

SOLVED)∨

q(m)

≠q0(m),

THEN

ADD(ma,

S)g)

}③

}AO*算法生长，对新结点计算q向上修改父辈结点的q当(m,SOLVED)∧q(m)=q0(m)时,q(ma)不必修改,只考虑是否能解当EXPAND(n)={}时,令q(n)=∞2.2与或图的启发式搜索算法AO*算法和A*算法的比较与或图vs

一般图解图vs

解路径评估局部图vs

评估结点无OPEN/CLOSED表vs

有OPEN/CLOSED表都有h(n)≤h*(n)和h(n)满足单调限制的特点2.3

博弈树的搜索弈yì–

<动>(本义:下棋)同本义[play

chess]视君不如弈棋。——《左传·襄公二十五年》今夫弈之为数。——《孟子》又如:弈思(下棋的思路)，弈棋(下棋)–

<名>弈,围棋也。——《说文》射者中,弈者胜。——宋·欧阳修《醉翁亭记》棋局谓之弈。——《小尔雅》又如:弈局(棋局,棋盘);弈具(指棋盘,棋子);弈枰(棋盘);弈楸(棋盘);弈谱(棋谱)–

<形>大[great]。如:弈弈(高大的样子);弈业(大业);弈赫(盛大显赫的样子)2.3

博弈树的搜索博bó–

<动>赌(赌博),博弈[gamble]与闵公博。――《公羊传·庄公十二年》则博塞以游。――《庄子·骈拇》或以游博持掩为事。――《后汉书·王符传》不有博奕者乎。――《论语·阳货》或饮或博。――清·薛福成《观巴黎油画记》取得[get;win]博个封妻荫子。――《水浒传》又如:博笑(谦词。换取别人一笑);博鬻(换取);博名(获取好名声)博弈不有博弈者乎?——《论语·阳货》孔子说:"不闻夫博弈者乎,亦尤贤乎已"2.3

博弈树的搜索弈（即棋）有许多种从参加人数上单人博弈棋双人对弈棋多人博弈棋从对弈规则（即棋子和走法）上围棋中国象棋国际象棋跳棋一字棋余一棋这里只研究双人对弈棋2.3

博弈树的搜索“博弈论”术语

–“双人对弈”双方轮流走步。“信息完备”双方得到的棋局信息是一样的。“零和博弈”属“非合作”博弈,指博弈一方的收益必然意味着另一方的损失,双方的收益和损失相加永远为“零”。2.3

博弈树的搜索博弈可用“特殊的”与或图表达令棋局为结点，一种走法会得到一个新棋局。轮我方走时，可选择任何一种走法。各走法得到的新棋局之间是“或”关系。轮对方走时，我方必须应对对方的各种走法。对方各走法得到的新棋局之间是“与”关系。例：Grundy博弈有N枚钱币，双方轮流分堆；每位棋手把某一堆分为钱币数不等的两堆；如一方不能完成分堆，即认输。2.3

博弈树的搜索76,15,24,35,1,14,2,13,2,23,3,14,1,1,13,2,1,12,2,2,13,1,1,1,12,2,1,1,12,1,1,1,1,1根结点：初始棋局叶结点：终棋局黄方赢橙方赢对于橙方，{A}是终结点集，如有解图，按解图走必赢！ABC

黄方赢对于黄方，{B,C}是终结点集，如有解图，按解图走必赢！与结点或结点或结点与结点或结点我方为黄方由黄方分Grundy博弈的与或图表达2.3

博弈树的搜索从橙方角度理解的与或图76,15,24,35,1,14,2,13,2,23,3,14,1,1,13,2,1,12,2,2,13,1,1,1,12,2,1,1,12,1,1,1,1,1黄方赢橙方赢ABC

黄方赢或结点与结点与结点或结点与结点2.3

博弈树的搜索橙方需要的解图76,15,1,14,2,13,2,1,12,2,1,1,1橙方赢解图176,14,2,13,2,1,12,2,1,1,1橙方赢解图274,34,2,13,3,13,2,1,12,2,1,1,1橙方赢解图3对于橙方，无论黄方第一步怎么走，都能找到解图！而黄方无解图，为什么？2.3

博弈树的搜索解图是从开局到终局的完整博弈策略。只要搜索出解图，就可弈胜！但是，以中国象棋为例，搜索开销巨大！–

假设每步平均有40种走法，则双方共走50步，–

则棋局总数约，深度约100层。∴搜索解图的想法必须放弃！实际上，从任一方来说，许多棋没有解图。(402

)50

»101602.3

博弈树的搜索人是怎样下棋的？如果我走这一步，对方会有多少走法？然后，我再怎么走？…新手只能看一、二个轮次，高手则看几个，甚至十几个轮次。“想出”的若干轮次可表示为一张局部图。根结点代表当前棋局；想n轮次的结果可表示为深度为2n+1的局部图。根结点有多个局部图每个外向连接符，引出一个“根结点为根的局部图”，最佳局部图，意味着当前的最佳走步。怎样寻找最佳局部图呢？2.3

博弈树的搜索对结点n(即棋局)的评估以f(n)表示。f(n)>0,

对我方有利；f(n)<0,

对对方有利；f(n)越大，对我方越有利；反之，越不利。f(n)=∞,我方胜；f(n)=－∞,对方胜；不失一般性，假设轮我方走，当前棋局为s。2.3

博弈树的搜索f(s)的求法sABCDEFGHIJ9-60

0 -2 -4 -3-6-2-4-2极小结点极大结点端结点对方肯定选择对自己最有利的走法！我方肯定也选择对我最有利的走法！极小极大算法2.3

博弈树的搜索T:=(s),

OPEN:=(s),

CLOSED:=()LOOP1:

IF

OPEN=(),

THENGO

LOOP2n:=FIRST(OPEN),

REMOVE(n,

OPEN),

ADD(n,

CLOSED)IF

n为终棋局,THEN

f(n):=∞∨－∞∨0,GO

LOOP1 ELSE{EXPAND(n)→{ni},ADD({ni},T)IF

d(ni)<k,

THEN

ADD({ni},OPEN),

ELSE计算f(ni)GO

LOOP1}

LOOP2:IF

CLOSED=(),

THEN

GO

LOOP3np:=FIRST(CLOSED)IF(np∈MAX)

∧f(nci)有值,THENf(np):=max{f(nci)},REMOVE(np,CLOSED)IF

(np∈MIN)

∧f(nci)有值,THENf(np):=min{f(nci)},REMOVE(np,CLOSED)GO

LOOP2LOOP3:

M(Move,

T))MINIMAX算法生成局部图倒推计算f值2.3

博弈树的搜索九宫格中的一字棋我方棋子用“×”表示，对方棋子用“○”表示；先将本方棋子连成“三子一线“者，获胜！轮我方走时，应选择f最大的走法。∴轮我方走的棋局（结点）称为MAX结点，轮对方走的棋局（结点）称为MIN结点。假设：计算机程序模拟MAX一方，计算机先走。f(p)计算方法若结点p不是终棋局，f(p)=(所有空格摆放“×”后，三“×”一线的数目)－(所有空格摆放“○”后，三“○”一线的数目)。反之，f(p)=∞∨－∞。×○×○×○×○×○6–5=15–5=06–5=15–5=04–5=–1○×○×○××○×○5–6=–1

5–5=0

5–6=–1

6–6=04–6=–2×××6–4=25–4=1○×○×-1-21OPEN={s}{A,B,C}{B,C}{C}{

}2.3

博弈树的搜索s

1ABCCLOSED={

}{s}{s,A}{s,A,B}{s,A,B,C}{s,B,C}{s,C}{s}{

}×××○××××××○○○○○○○○位置优选次序:中央,角,边中2.3

博弈树的搜索○×4–2=23–2=15–2=33–1=2

4–2=20101×○××○○××○×○×○×○×○×○×○×○×○○×3–2=13–3=05–3=23–3=0

4–3=1○××○○××○××○○××○○××○○××○○○××4–3=14–3=14–2=24–2=25–2=33–2=1

4–2=2○××○○××○○××○××○○××○○×○×○○××4–2=2○××○○××○○××○×○×4–3=14–3=13–3=01×○×○××××××○○○×○○○○2.3

博弈树的搜索○○×××○○××○○×××○○×××○○×××○○××××○○○×××○○××○×○○××○×○○×○×○○○×××○○×××○○○×××○○○××○×○○○×××○○○×××○○×××○○○×○××○○○×××○○○×××○○××○×○○×○××○○○×××○○○×××○○×××○○○×××○1212－∞－∞－∞－∞1010011221111－∞－∞－∞－∞12.3

博弈树的搜索极小极大搜索的特点先按规定深度，生成搜索树（即局部图）；再倒推计算结点的估值。能不能将“向下生成”和“倒推计算”融合起来？只要能计算估值，就立即计算。这有什么益处？可能省略一些结点之下的搜索！这种搜索称为α-β剪支。为结合“生成”和“估值”过程，按“有界的”深度优先策略生成局部图；具体怎么做？2.3

博弈树的搜索×○×○×○×○×○6–5=15–5=06–5=15–5=04–5=–1×××6–5=25–4=1×○○×≤-1≤1○×5–6=–11≥-11以一字棋“第一阶段”为例少生成4个端结点(33％)深度为3≤1≤0-12.3

博弈树的搜索α极大结点的估值下界。随着子结点的生成，α只可能上升。β极小结点的估值上界。随着子结点的生成，β只可能下降。α剪支当某极小结点的β值≤其先辈的极大结点的α值，则终止该极小结点之下的搜索，并令其估值为β，这种剪支称α剪支。β剪支当某极大结点的值α

≥其先辈的极小结点的β值，则终止该极大结点之下的搜索，令其估值为α，这种剪支称β剪支。2.3

博弈树的搜索注意：仅在极小和极大结点之间比较；不只和父结点比较，还和其他“直系”先辈结点比较；仅当估值被“固定”后，才向上传递；α-β剪支的搜索结果，与极小极大法一致。2.3

博弈树的搜索β1α

5

≥02

≤04

=03

60

5

－3

3

3

－3

07

≤-

38

=0β

9

≤01011

=312

≥3α14

≥015

172 2

－3

0

－2

3

5

420

=118

≤416

≤521

≥124

=123

≤-

319

22

26

281

－3

0

6

8 9

－327≤629

=630

≥625

≤131

=132

=113

=0与极小极大法相比，

α-β剪支少生成16个结点(16

÷37

＝

43％)潜在的2轮次搜索图2.3

博弈树的搜索α-β剪支的效率问题–设搜索树深度为4，分支数均为2；–最理想情况下，即MAX结点按f值由大到小扩展出子结点，MIN结点按f值由小到大扩展出子结点；–