第2章-与或图搜索(新母版)-课件.ppt（54页）

1、王庆江中国海洋大学计算机科学系qjwangouc.edu22008-2009学年第1学期2章 与或图搜索n一般图的搜索一般图的搜索q当前结点可解，则父结点可解；当前结点可解，则父结点可解；q解为一条起始结点到目标结点的解为一条起始结点到目标结点的路径路径！崂山校区李村朱家洼中韩鱼山校区32008-2009学年第1学期2章 与或图搜索n与或图的搜索与或图的搜索q某个某个（或某组或某组）子结点都可解，父结点才可解；）子结点都可解，父结点才可解；q解是什么解是什么形式形式的？的？写信计算机纸笔秘书写打印机42008-2009学年第1学期2章 与或图搜索q父结点与子结点的关系用父结点与子结点的关系用超

2、弧线超弧线（又称（又称连接符连接符）标识。）标识。父结点父结点子结点子结点 1-1-连接符连接符2-2-连接符连接符3-3-连接符连接符k-k-连接符连接符52008-2009学年第1学期2章 与或图搜索q根根结点结点n起始结点（起始结点（n0）q端端（叶叶）结点）结点n没有后继没有后继的结点（的结点（n7和和n8）q或或结点结点n对对n1而言而言，n2和和n3是或结点。是或结点。q与与结点结点n对对n0而言而言，n4和和n5是与结点。是与结点。q终终结点结点n直接可解直接可解的结点。的结点。n0n1n4n5n2n3n6n7n862008-2009学年第1学期2章 与或图搜索q从从n出发，正确

3、选择出发，正确选择一个一个外向连接符（外向连接符（k-连接符连接符）；）；q从连接符指向的从连接符指向的每个每个结点出发，继续选择外向连接符；结点出发，继续选择外向连接符；q如此进行下去，直到连接符指向的结点如此进行下去，直到连接符指向的结点都属于都属于N为止。为止。共共k k个结点个结点72008-2009学年第1学期2章 与或图搜索n0n1n3n5n6n7n8n0n1n4n5n2n3n6n7n882008-2009学年第1学期2章 与或图搜索n0n1n4n5n2n3n6n7n8n0n4n5n7n892008-2009学年第1学期2章 与或图搜索n0n1n4n5n2n3n6n7n8n0n4n

4、5n7n8102008-2009学年第1学期2章 与或图搜索n一个与或图一个与或图G中，从结点中，从结点n到结点集到结点集N的解图的解图G是是G的的子图子图。q当当nN时，时，Gn；q若若n有一个有一个k-连接符，指向连接符，指向n1,n2,nk，使得从，使得从ni到到N都存在解图，都存在解图，i1,k，则则Gn,k-连接符连接符,各各ni到到N的解图的解图；q否则，否则，n到到N不存在解图。不存在解图。112008-2009学年第1学期2章 与或图搜索q单一结点是局部图；单一结点是局部图；q选择局部图的任一叶结点，选择其任选择局部图的任一叶结点，选择其任一个外向连接符，则一个外向连接符，则局

5、部图局部图、该外向该外向连接符连接符及及其所指的后继结点其所指的后继结点仍然组成仍然组成一个局部图。一个局部图。n7n8n0n4n5122008-2009学年第1学期2章 与或图搜索q记为记为k(n,N)；q若若nN，k(n,N)=0；q若若n有一个外向连接符指向有一个外向连接符指向n1,n2,ni，并设该连接，并设该连接符的耗散为符的耗散为Cn，则，则 k(n,N)=Cn+k(n1,N)+k(n2,N)+k(ni,N)N=n7,n8k(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)=7

6、n0n4n5n7n8最佳解图，最佳解图，h*(n)=mink(n,N)132008-2009学年第1学期2章 与或图搜索q若若n叶结点叶结点，则，则k(n,N)=h(n)；q若若n有一个外向连接符指向有一个外向连接符指向n1,n2,ni，并设该连接，并设该连接符的耗散为符的耗散为Cn，则，则 k(n,N)=Cn+k(n1,N)+k(n2,N)+k(ni,N)k(n0,N)=2+k(n4,N)+k(n5,N)=2+h(n4)+h(n5)n0n4n5局部图局部图142008-2009学年第1学期2章 与或图搜索q终结点是已解结点；终结点是已解结点；q非终结点已解，当且仅当至少一个非终结点已解，当且

7、仅当至少一个“或或”结点已解；结点已解；q非终结点已解，当且仅当所有非终结点已解，当且仅当所有“与与”结点已解。结点已解。q没有后继结点的非终结点是未解结点；没有后继结点的非终结点是未解结点；q非终结点未解，当且仅当所有非终结点未解，当且仅当所有“或或”结点未解；结点未解；q非终结点未解，当且仅当至少一个非终结点未解，当且仅当至少一个“与与”结点未解。结点未解。152008-2009学年第1学期2章 与或图搜索n根结点有几个局部图。根结点有几个局部图。n0n1n5n2n3n6局部图局部图1 1n0n4n5n8局部图局部图2 2优先优先“生长生长”哪个局部图？哪个局部图？n0n1n4n5n2n3

8、n6n7n8n0n4n5n8局部图局部图2 2162008-2009学年第1学期2章 与或图搜索nN=n7,n8n用用AO*算法搜索算法搜索n0到到N的解图，的解图，即找到即找到n0为为根的一个局部图，其根的一个局部图，其端结点都端结点都N。324411200n0n1n4n5n2n3n6n7n8172008-2009学年第1学期2章 与或图搜索n0n1n4n5n0不是终结点时，扩展不是终结点时，扩展n0；对新的叶结点计算耗散值，检查是否对新的叶结点计算耗散值，检查是否加加能解能解标记；标记；向上向上修改修改父辈父辈结点为根的局部图结点为根的局部图的耗的耗散估计，散估计，标识标识最佳局部图。最佳

9、局部图。2113324411200n0n1n4n5n2n3n6n7n8注：注：红色数字红色数字为为k(n,N)h(n1)mink(n0,N)4182008-2009学年第1学期2章 与或图搜索沿沿n0的最佳局部图，找到一个的最佳局部图，找到一个叶叶结点；结点；扩展扩展此叶结点，对新的叶结点计算耗散值，检查是否加此叶结点，对新的叶结点计算耗散值，检查是否加能解能解标记；标记；向上向上修改修改父辈父辈结点为根的局部图结点为根的局部图的耗散估计，的耗散估计，标识标识最佳局部图。最佳局部图。n0n1n4n521134454n3n26324411200n0n1n4n5n2n3n6n7n8注：注：红色数字

10、红色数字为为k(n,N)192008-2009学年第1学期2章 与或图搜索沿沿n0的最佳局部图，找到一个叶结点；的最佳局部图，找到一个叶结点；扩展扩展此叶结点，对新的叶结点计算耗散值，检查是否加此叶结点，对新的叶结点计算耗散值，检查是否加能解能解标记；标记；向上向上修改修改父辈父辈结点为根的局部图结点为根的局部图的耗散估计，的耗散估计，标识标识最佳局部图。最佳局部图。5n0n1n4n5511444n3n2n6n7n80022324411200n0n1n4n5n2n3n6n7n8注：注：红色数字红色数字为为k(n,N)能解能解能解能解能解能解202008-2009学年第1学期2章 与或图搜索沿沿

11、n0的最佳局部图，找到一个叶结点；的最佳局部图，找到一个叶结点；扩展扩展此叶结点，对此叶结点，对新的新的叶结点计算耗散值，检查是否加叶结点计算耗散值，检查是否加能解能解标记；标记；向上向上修改修改父辈父辈结点为根的局部图结点为根的局部图的耗散估计，的耗散估计，标识标识最佳局部图；最佳局部图；n4耗散未变耗散未变但能解标志改变了但能解标志改变了，继续向上修改。，继续向上修改。1 1324411200n0n1n4n5n2n3n6n7n8注：注：红色数字红色数字为为k(n,N)只对只对新新产生的子结产生的子结点计算耗散值点计算耗散值n0n1n4n5521544n3n2n6n7n8002能解能解能解能

12、解能解能解能解能解能解能解212008-2009学年第1学期2章 与或图搜索n根结点加了根结点加了能解能解标记后，算法结束，解图如下：标记后，算法结束，解图如下：n0n4n525n7n8001 1222008-2009学年第1学期2章 与或图搜索G:=s,计算计算q(s)=h(s),如果如果GOAL(s),THEN M(s,SOLVED)Until s已加上已加上SOLVED标记标记,do G=FIND(G)n:=G的任一个叶结点（且非终结点）的任一个叶结点（且非终结点）EXPAND(n)nj,计算计算q(nj)=h(nj),这里这里njGG:=Gnj;IF GOAL(nj),THEN M(n

13、j,SOLVED)S:=nUntil S=,do REMOVE(m,S),要求要求m的子结点的子结点S修改修改q(m)计算计算m为根的每个局部图的耗散，为根的每个局部图的耗散，q(m)=mink(m,N)；将将指针指针放在指向最小耗散局部图的放在指向最小耗散局部图的连接符连接符上；上；若该若该连接符连接符指的指的所有所有子结点都能解，则子结点都能解，则M(m,SOLVED)IF CM(m,SOLVED)q(m)q0(m),THEN ADD(ma,S)AO*算法生长，对新叶结点计算q向上修改父辈结点的q和指针当当CM(m,SOLVED)q(m)=q0(m)时，时，q(ma)不不必修改，只考虑是否

14、必修改，只考虑是否ma能解能解，且，且ma仅指仅指mp。当当EXPAND(n)=时，令时，令q(n)=！232008-2009学年第1学期2章 与或图搜索n与或图（超图）与或图（超图）vs.一般图（普通图）一般图（普通图）n解图解图 vs.解路径解路径n评估局部图评估局部图 vs.评估结点（即经过该结点的路径）评估结点（即经过该结点的路径）n无无OPEN/CLOSED表表 vs.有有OPEN/CLOSED表表n不支持有环图不支持有环图 vs.支持有环图支持有环图n都支持在都支持在h(n)h*(n)情况下寻找最佳解，以及情况下寻找最佳解，以及h(n)单单调限制特性。调限制特性。242008-20

15、09学年第1学期2章 与或图搜索n数字重写变换规则如下：数字重写变换规则如下：63,3 64,2 42,2 43,1 32,1 21,1 怎样将怎样将6变为一个若干变为一个若干1组成的数字串？试用组成的数字串？试用AO*算法求搜索图，设算法求搜索图，设k-连接符的耗散为连接符的耗散为k，h函数为：函数为：h(1)=0，h(n)=n(n1)。252008-2009学年第1学期2章 与或图搜索qn(本义本义:下棋下棋)同本义同本义 play chessn视君不如弈棋。视君不如弈棋。左传左传襄公二十五年襄公二十五年n今夫弈之为数。今夫弈之为数。孟子孟子n又如又如:弈思弈思(下棋的思路下棋的思路)，弈

16、棋，弈棋(下棋下棋)qn弈弈,围棋也。围棋也。说文说文n射者中射者中,弈者胜。弈者胜。宋宋欧阳修欧阳修醉翁亭记醉翁亭记n棋局谓之弈。棋局谓之弈。小尔雅小尔雅n又如又如:弈局弈局(棋局棋局,棋盘棋盘);弈具弈具(指棋盘指棋盘,棋子棋子);弈枰弈枰(棋盘棋盘);弈楸弈楸(棋盘棋盘);弈谱弈谱(棋谱棋谱)qn大大 great。如。如:弈弈弈弈(高大的样子高大的样子);弈业弈业(大业大业);弈赫弈赫(盛大盛大显赫的样子显赫的样子)262008-2009学年第1学期2章 与或图搜索qn赌赌(赌博赌博),博弈博弈 gambleq与闵公博。与闵公博。公羊传公羊传庄公十二年庄公十二年q则博塞以游。则博塞以游。

17、庄子庄子骈拇骈拇q或以游博持掩为事。或以游博持掩为事。后汉书后汉书王符传王符传q不有博奕者乎。不有博奕者乎。论语论语阳货阳货q或饮或博。或饮或博。清清薛福成薛福成观巴黎油画记观巴黎油画记n取得取得 get;winq博个封妻荫子。博个封妻荫子。水浒传水浒传q又如又如:博笑博笑(谦词。换取别人一笑谦词。换取别人一笑);博鬻博鬻(换取换取);博名博名(获取获取好名声好名声)q不有博弈者乎不有博弈者乎?论语论语阳货阳货q孔子说孔子说:不闻夫博弈者乎不闻夫博弈者乎,亦尤贤乎已亦尤贤乎已 272008-2009学年第1学期2章 与或图搜索q从参加人数上从参加人数上n单人博弈棋单人博弈棋n双人对弈棋双人对弈

18、棋n多人博弈棋多人博弈棋q从对弈规则（即棋子和走法）上从对弈规则（即棋子和走法）上n围棋围棋n中国象棋中国象棋n国际象棋国际象棋n跳棋跳棋n一字棋一字棋n余一棋余一棋这里只研究这里只研究双人对弈双人对弈棋棋282008-2009学年第1学期2章 与或图搜索q“双人对弈双人对弈”n双方轮流走步。双方轮流走步。q“信息完备信息完备”n双方得到的棋局信息是一样的。双方得到的棋局信息是一样的。q“零和零和博弈博弈”n属属“非合作非合作”博弈博弈,指博弈一方的指博弈一方的收益收益必然意味着另一方必然意味着另一方的的损失损失,双方的收益和损失双方的收益和损失相加相加永远为永远为“零零”。292008-20

19、09学年第1学期2章 与或图搜索q令棋局为结点，一种走法会得到一个新棋局（结点）。令棋局为结点，一种走法会得到一个新棋局（结点）。q轮我方走时，可选择任何一种走法。轮我方走时，可选择任何一种走法。n各走法得到的新棋局之间是各走法得到的新棋局之间是“或或”关系。关系。q轮对方走时，我方必须应对对方的各种走法。轮对方走时，我方必须应对对方的各种走法。n对方各走法得到的新棋局之间是对方各走法得到的新棋局之间是“与与”关系。关系。q例：例：Grundy博弈博弈n有有N枚钱币，双方轮流分堆；每位棋手把某一堆分为钱币枚钱币，双方轮流分堆；每位棋手把某一堆分为钱币数不等的两堆；如一方不能完成分堆，即认输。数

20、不等的两堆；如一方不能完成分堆，即认输。302008-2009学年第1学期2章 与或图搜索BCs到到B,C没有没有解图，对方没有解图，对方没有必赢必赢的走法！的走法！s到到A有有解图，解图，按按解图走解图走，我方赢！，我方赢！(7)(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)对方赢对方赢我方赢A对方走对方走s我方走我方走(6,1)(5,2)(4,3)312008-2009学年第1学期2章 与或图搜索(7)(4,2,1)(3,2,1,1)(2,2,1,1,1)A

21、s(6,1)(5,2)(4,3)322008-2009学年第1学期2章 与或图搜索(7)(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)我方赢A对方走对方走s我方走我方走(6,1)(5,2)(4,3)332008-2009学年第1学期2章 与或图搜索(7)(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)我方赢A对方走对方走s我方走我方

22、走(6,1)(5,2)(4,3)342008-2009学年第1学期2章 与或图搜索(7)(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)我方赢A对方走对方走s我方走我方走(6,1)(5,2)(4,3)有解图真好！有解图真好！352008-2009学年第1学期2章 与或图搜索n解图是从开局到终局的解图是从开局到终局的完整完整博弈策略。博弈策略。n只要搜索出解图，就可弈胜！只要搜索出解图，就可弈胜！n但是，以中国象棋为例，搜索开销巨大！但是，以中国象棋为例，搜索开销巨

23、大！q假设平均每步有假设平均每步有40种走法，双方共走种走法，双方共走50步；步；q则棋局总数约则棋局总数约(402)5010160，深度约，深度约100层。层。n搜索解图的想法必须放弃！搜索解图的想法必须放弃！n实际上，从任一方来说，许多棋实际上，从任一方来说，许多棋可能可能没有解图。没有解图。362008-2009学年第1学期2章 与或图搜索n人是怎样下棋的呢？人是怎样下棋的呢？q如果如果我走我走这这一步，对方可能会怎么走？对对手的每种走法，一步，对方可能会怎么走？对对手的每种走法，我该怎么走？我该怎么走？q新手只能看一、二个轮次，高手则看几个、十几个轮次。新手只能看一、二个轮次，高手则看

24、几个、十几个轮次。n“想出想出”的若干轮次可表示为一张的若干轮次可表示为一张局部图局部图。q根结点根结点代表代表当前棋局当前棋局；q想想n轮次的结果可表示为轮次的结果可表示为深度为深度为2n+1的局部图。的局部图。n根结点有多个局部图？根结点有多个局部图？q每个每个外向连接符，引出一个外向连接符，引出一个“根结点为根的局部图根结点为根的局部图”，q最佳局部图最佳局部图，意味着，意味着当前的最佳走步当前的最佳走步。n怎样寻找怎样寻找局部图呢？局部图呢？372008-2009学年第1学期2章 与或图搜索n对结点对结点n(即棋局即棋局)的的评估评估q以以f(n)表示；表示；qf(n)0,对我方有利；

25、对我方有利；qf(n)0,对对方有利；对对方有利；qf(n)越大，对我方越有利；反之，越不利。越大，对我方越有利；反之，越不利。qf(n)=,我方胜；我方胜；qf(n)=,对方胜；对方胜；n不失一般性，假设不失一般性，假设轮我方走轮我方走，当前棋局为，当前棋局为s。382008-2009学年第1学期2章 与或图搜索sABCDEFGHIJ9-600-2-4-3-6-2-4-2端结点端结点极小结点极小结点极大结点极大结点轮我方走轮我方走392008-2009学年第1学期2章 与或图搜索T:=(s),OPEN:=(s),CLOSED:=()LOOP1:IF OPEN=(),THEN GO LOOP2

26、 n:=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 LOOP3 np:=FIRST(CLOSED)IF(npMAX)f(nci)有值有值,THEN f(np):=maxf(nci),REMOVE(np,CLOSED)IF(npMIN)f(nci)有值有值,THEN f(np):=mi

27、nf(nci),REMOVE(np,CLOSED)GO LOOP2LOOP3:M(Move,T)生成局部图生成局部图倒推计算倒推计算f值值402008-2009学年第1学期2章 与或图搜索n九宫格中的一字棋九宫格中的一字棋q我方棋子用我方棋子用“”表示，对方棋子用表示，对方棋子用“”表示；表示；q先将本方棋子连成先将本方棋子连成“三子一线三子一线“者，获胜！者，获胜！n轮我方走时，应选择轮我方走时，应选择f最大的走法。最大的走法。q 轮我方走的棋局（结点）称为轮我方走的棋局（结点）称为MAX结点，轮对方走的棋结点，轮对方走的棋局（结点）称为局（结点）称为MIN结点。结点。q假设：计算机程序模拟

28、假设：计算机程序模拟MAX一方，计算机先走。一方，计算机先走。nf(p)计算方法计算方法q若结点若结点p不是终棋局，不是终棋局，f(p)=(所有空格摆放所有空格摆放“”后，三后，三“”一线的数目一线的数目)(所有空格摆放所有空格摆放“”后，三后，三“”一线的数一线的数目目)。q反之，反之，f(p)=。412008-2009学年第1学期2章 与或图搜索65=155=065=1 55=0 45=156=155=0 56=1 66=0 46=264=254=1-1-211OPEN=sA,B,CB,CC sABCCLOSED=ss,As,A,Bs,A,B,Cs,B,Cs,Cs 位置优选次序:中央,角,

29、边中422008-2009学年第1学期2章 与或图搜索42=2 32=1 52=3 31=2 42=2010132=133=0 53=2 33=0 43=143=143=142=2 42=2 52=3 32=1 42=2 42=243=143=133=01432008-2009学年第1学期2章 与或图搜索 121210100112211111442008-2009学年第1学期2章 与或图搜索n极小极大搜索的特点极小极大搜索的特点q先先按规定深度，生成搜索树（即局部图）；按规定深度，生成搜索树（即局部图）；q再再倒推计算结点的估值。倒推计算结点的估值。n能不能将能不能将“向下生成向下生成”和和“

30、倒推计算倒推计算”融合起来？融合起来？q只要能计算估值，就只要能计算估值，就立即立即计算。计算。n这有什么益处？这有什么益处？n可能可能省略省略一些结点之下的搜索！一些结点之下的搜索！q这种搜索称为这种搜索称为-剪支。剪支。n为结合为结合“生成生成”和和“估值估值”过程，按过程，按“有界的深度有界的深度优先优先”策略生成局部图；策略生成局部图；n具体怎么做？具体怎么做？452008-2009学年第1学期2章 与或图搜索65=155=065=1 55=0 45=165=254=11-11-1=-156=1=1=1一字棋一字棋“第一阶段第一阶段”的的-剪支剪支少生成结点少生成结点27深深度度为为3

31、0=-1462008-2009学年第1学期2章 与或图搜索nq极大结点的估值极大结点的估值下界下界；q随着子结点的生成，随着子结点的生成，只可能上升。只可能上升。nq极小结点的估值极小结点的估值上界上界；q随着子结点的生成，随着子结点的生成，只可能下降。只可能下降。n剪支剪支q当某当某极小极小结点的结点的值值 其其先辈先辈的的极大极大结点的结点的值，则值，则终止该终止该极小结点之下极小结点之下的搜索，并的搜索，并令令其估值为其估值为，这种剪支称，这种剪支称剪支。剪支。n剪支剪支q当某当某极大极大结点的值结点的值 其其先辈先辈的的极小极小结点的结点的值，则值，则终止该终止该极大结点之下极大结点之

32、下的搜索，令的搜索，令其其估值为估值为，这种剪支称，这种剪支称剪支。剪支。472008-2009学年第1学期2章 与或图搜索n注意：注意：q仅在极小和极大结点之间比较；仅在极小和极大结点之间比较；n之间不能比较，之间不能比较，之间也不能比较。之间也不能比较。q不只和父结点比较，还和其他不只和父结点比较，还和其他“直系直系”先辈结点比较；先辈结点比较；q仅当估值被仅当估值被“固定固定”后，才向上传递；后，才向上传递；q-剪支的搜索结果，与极小极大法一致剪支的搜索结果，与极小极大法一致。482008-2009学年第1学期2章 与或图搜索 0 5 3 3 3 3 0 2 2 3 0 2 3 5 4

33、1 3 0 6 8 9 312 034=05 067-38=09 01011=312 313=114 01516 51718 41920=12112223-324=125 1262762829=630631=132=0与极小极大法相比，与极小极大法相比，-剪支少生剪支少生成成16个结点个结点(16 37 43)倒推值等于某端结倒推值等于某端结点的静态估值。点的静态估值。492008-2009学年第1学期2章 与或图搜索q设搜索树深度为设搜索树深度为4，分支数均为，分支数均为2；q理想情况下，理想情况下，MAX结点按结点按f值由大到小扩展出子结点，值由大到小扩展出子结点，MIN结点按结点按f值由

34、小到大扩展出子结点；值由小到大扩展出子结点；q则可能的剪支则可能的剪支:少生成端结点少生成端结点5656，少生成结点少生成结点4242502008-2009学年第1学期2章 与或图搜索q设搜索树深度为设搜索树深度为D，分支数均为，分支数均为B；q不采用剪支时，端结点数为不采用剪支时，端结点数为BD；q最理想情况下，最理想情况下，n使用剪支时，只扩展出使用剪支时，只扩展出n在资源限制在资源限制(限制生成结点数）时，采用剪支可搜索得更深。限制生成结点数）时，采用剪支可搜索得更深。为奇数）为奇数）（为偶数）或为偶数）或（D1 D122/)1(2/)1(2/DDDBBB2048102451225612

35、8643216842N(极小极大极小极大)956347312315117532N(剪支法剪支法)1110987654321DB=2时，端结点数N与深度D的关系512008-2009学年第1学期2章 与或图搜索q若不满足若不满足，但，但和和已很接近，考虑剪支；已很接近，考虑剪支；q不严格限制搜索深度；不严格限制搜索深度；n棋局势态较不稳定时，适当增大棋局势态较不稳定时，适当增大D。q在选择最佳走法（即最佳局部图）后，继续在选择最佳走法（即最佳局部图）后，继续“生长生长”该局部图，检验是否有意外；该局部图，检验是否有意外；q利用定式，减少不必要的搜索；利用定式，减少不必要的搜索；q怎么处理对手的失

36、误怎么处理对手的失误?怎么利用对手的棋风怎么利用对手的棋风?.522008-2009学年第1学期2章 与或图搜索q博弈问题可以按与或图理解；博弈问题可以按与或图理解；q如果能求出解图，则博弈必胜！如果能求出解图，则博弈必胜！q但实际中搜索当前最佳走步；但实际中搜索当前最佳走步；q极小极大法可用于双人对弈时搜索最佳走步；极小极大法可用于双人对弈时搜索最佳走步；q-剪支可及时省略不必要的搜索，且搜索结果与极剪支可及时省略不必要的搜索，且搜索结果与极小极大法一致；小极大法一致；q重点：重点：-剪支法。剪支法。n思考题思考题q2.5和和2.8n作业作业q2.6532008-2009学年第1学期2章 与或图搜索n一字棋的向量表示，以右图为例一字棋的向量表示，以右图为例n评价函数示例评价函数示例+1110+10+100按按68页计算页计算:41=3+2+1+2+1+4+1+2+1+25+10+10+20+10+13支持的三子一线数目：中央位置：4 角位置：3 边中位置：2+3+2+3+2+4+2+3+2+35按按68页计算页计算:23=123 20+10010+101有没有更准确的评估函数？4-3-24-2-12-1-0 Thank you