人工智能博弈樹(shù)的搜索(45張)課件

《人工智能博弈樹(shù)的搜索(45張)課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《人工智能博弈樹(shù)的搜索(45張)課件（46頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、2.3博弈樹(shù)搜索博弈樹(shù)搜索第1頁(yè)，共46頁(yè)。n20世紀(jì)60年代，研制出的西洋跳棋和國(guó)際象棋的博弈程序達(dá)到了大師級(jí)的水平。n1958約翰麥卡錫提出博弈樹(shù)搜索算法n1997年，IBM公司研制的“深藍(lán)”國(guó)際象棋 程序，采用博弈樹(shù)搜索算法，該程序戰(zhàn)勝了國(guó)際象棋世界冠軍卡斯帕羅夫。1.1.概述概述第2頁(yè)，共46頁(yè)。正在與深藍(lán)下棋的卡斯帕羅夫第3頁(yè)，共46頁(yè)。n博弈問(wèn)題特點(diǎn)：博弈問(wèn)題特點(diǎn)：n雙人對(duì)弈，輪流走步。雙人對(duì)弈，輪流走步。n信息完備，雙方所得到的信息是一樣的。信息完備，雙方所得到的信息是一樣的。n零和，即對(duì)一方有利的棋，對(duì)另一方肯定零和，即對(duì)一方有利的棋，對(duì)另一方肯定是不利的，不存在對(duì)雙方均有利或

2、無(wú)利的是不利的，不存在對(duì)雙方均有利或無(wú)利的棋。棋。1.1.概述概述第4頁(yè)，共46頁(yè)。n博弈的特性博弈的特性兩個(gè)棋手交替地走棋兩個(gè)棋手交替地走棋 ；比賽的最終結(jié)果，是贏、輸和平局中的比賽的最終結(jié)果，是贏、輸和平局中的一種；一種；可用圖搜索技術(shù)進(jìn)行，但效率很低；可用圖搜索技術(shù)進(jìn)行，但效率很低；博弈的過(guò)程，是尋找置對(duì)手于必?cái)B(tài)的博弈的過(guò)程，是尋找置對(duì)手于必?cái)B(tài)的過(guò)程；過(guò)程；雙方都無(wú)法干預(yù)對(duì)方的選擇。雙方都無(wú)法干預(yù)對(duì)方的選擇。1.1.概述概述第5頁(yè)，共46頁(yè)。2.Grundy 2.Grundy 博弈博弈n下下棋棋的的雙雙方方是是對(duì)對(duì)立立的的，命命名名博博弈弈的的雙雙方方，一一方方為為“正正方方”，這這

3、類類節(jié)節(jié)點(diǎn)點(diǎn)稱稱為為“MAX”節(jié)節(jié)點(diǎn)點(diǎn)；另另一一方方為為“反反方方”，這這類類節(jié)節(jié)點(diǎn)點(diǎn)稱稱為為“MIN”節(jié)節(jié)點(diǎn)點(diǎn)。正正方方和和反反方方是是交交替替走走步步的的，因因此此MAX節(jié)節(jié)點(diǎn)點(diǎn)和和MIN節(jié)節(jié)點(diǎn)點(diǎn)會(huì)會(huì)交交替替出出現(xiàn)現(xiàn)。第6頁(yè)，共46頁(yè)。2.Grundy 2.Grundy 博弈博弈nGrundy博弈是一個(gè)分錢(qián)幣的游戲。有博弈是一個(gè)分錢(qián)幣的游戲。有 一堆數(shù)目為一堆數(shù)目為N的錢(qián)幣，由兩位選手輪流進(jìn)的錢(qián)幣，由兩位選手輪流進(jìn)行分堆，要求每個(gè)選手每次只把其中某行分堆，要求每個(gè)選手每次只把其中某一堆分成數(shù)目不等的兩小堆。例如，選一堆分成數(shù)目不等的兩小堆。例如，選手甲把手甲把N分成兩堆后，輪到選手乙就可以

4、分成兩堆后，輪到選手乙就可以挑其中一堆來(lái)分，如此進(jìn)行下去，直到挑其中一堆來(lái)分，如此進(jìn)行下去，直到有一位選手先無(wú)法把錢(qián)幣再分成不相等有一位選手先無(wú)法把錢(qián)幣再分成不相等的兩堆時(shí)就得認(rèn)輸。的兩堆時(shí)就得認(rèn)輸。第7頁(yè)，共46頁(yè)。2.Grundy 2.Grundy 博弈博弈n設(shè)初始狀態(tài)為設(shè)初始狀態(tài)為(7，MIN)，建立問(wèn)題的狀，建立問(wèn)題的狀態(tài)空間圖，圖中所有終結(jié)點(diǎn)均表示該選態(tài)空間圖，圖中所有終結(jié)點(diǎn)均表示該選手必輸?shù)那闆r，取勝方的目標(biāo)是設(shè)法使手必輸?shù)那闆r，取勝方的目標(biāo)是設(shè)法使棋局發(fā)展為結(jié)束在對(duì)方走步時(shí)的終結(jié)點(diǎn)棋局發(fā)展為結(jié)束在對(duì)方走步時(shí)的終結(jié)點(diǎn)上。上。第8頁(yè)，共46頁(yè)。MIN先走先走M(jìn)AX必勝必勝2.Grun

5、dy 2.Grundy 博弈博弈第9頁(yè)，共46頁(yè)。n結(jié)點(diǎn)結(jié)點(diǎn)A是是MAX的搜索目標(biāo)，而結(jié)點(diǎn)的搜索目標(biāo)，而結(jié)點(diǎn)B，C則為則為MIN的搜索目標(biāo)。的搜索目標(biāo)。2.Grundy 2.Grundy 博弈博弈第10頁(yè)，共46頁(yè)。搜索策略要考慮的問(wèn)題是：搜索策略要考慮的問(wèn)題是：n對(duì)對(duì)MIN走步后的每一個(gè)走步后的每一個(gè)MAX結(jié)點(diǎn)，必須證結(jié)點(diǎn)，必須證明明MAX對(duì)對(duì)MIN可能走的每一個(gè)棋局對(duì)弈后可能走的每一個(gè)棋局對(duì)弈后能獲勝，即能獲勝，即MAX必須考慮應(yīng)付必須考慮應(yīng)付MIN的所有的所有招法，這是一個(gè)與的含意，因此含有招法，這是一個(gè)與的含意，因此含有MAX符符號(hào)的結(jié)點(diǎn)可看成與結(jié)點(diǎn)。號(hào)的結(jié)點(diǎn)可看成與結(jié)點(diǎn)。2.Grun

6、dy 2.Grundy 博弈博弈第11頁(yè)，共46頁(yè)。n對(duì)對(duì)MAX走步后的每一個(gè)走步后的每一個(gè)MIN結(jié)點(diǎn)，只須證結(jié)點(diǎn)，只須證明明MAX有一步能走贏就可以，即有一步能走贏就可以，即MAX只要只要考慮能走出一步棋使考慮能走出一步棋使MIN無(wú)法招架就成，無(wú)法招架就成，因此含有因此含有MIN符號(hào)的結(jié)點(diǎn)可看成或結(jié)點(diǎn)。符號(hào)的結(jié)點(diǎn)可看成或結(jié)點(diǎn)。2.Grundy 2.Grundy 博弈博弈第12頁(yè)，共46頁(yè)。n對(duì)弈過(guò)程的搜索圖呈現(xiàn)出與或圖表示的形式。對(duì)弈過(guò)程的搜索圖呈現(xiàn)出與或圖表示的形式。n實(shí)現(xiàn)一種取勝的策略就是搜索一個(gè)解圖的問(wèn)題，實(shí)現(xiàn)一種取勝的策略就是搜索一個(gè)解圖的問(wèn)題，解圖就代表一種完整的博弈策略。解圖就代

7、表一種完整的博弈策略。2.Grundy 2.Grundy 博弈博弈第13頁(yè)，共46頁(yè)。中國(guó)象棋中國(guó)象棋n一盤(pán)棋平均走50步，總狀態(tài)數(shù)約為10的161次方。n假設(shè)1毫微秒走一步，約需10的145次方年。n結(jié)論：不可能窮舉。3.極小極大搜索過(guò)程極小極大搜索過(guò)程第14頁(yè)，共46頁(yè)。n對(duì)各個(gè)局面進(jìn)行評(píng)估對(duì)各個(gè)局面進(jìn)行評(píng)估n評(píng)估的目的：對(duì)后面的狀態(tài)提前進(jìn)行考慮，并評(píng)估的目的：對(duì)后面的狀態(tài)提前進(jìn)行考慮，并且以各種狀態(tài)的評(píng)估值為基礎(chǔ)作出最好的走棋且以各種狀態(tài)的評(píng)估值為基礎(chǔ)作出最好的走棋選擇。選擇。n評(píng)估的方法：用評(píng)價(jià)函數(shù)對(duì)棋局進(jìn)行評(píng)估。贏評(píng)估的方法：用評(píng)價(jià)函數(shù)對(duì)棋局進(jìn)行評(píng)估。贏的評(píng)估值設(shè)為的評(píng)估值設(shè)為+，輸

8、的評(píng)估值設(shè)為，輸?shù)脑u(píng)估值設(shè)為-，平局，平局的評(píng)估值設(shè)為的評(píng)估值設(shè)為0。n評(píng)估的標(biāo)準(zhǔn)：由于下棋的雙方是對(duì)立的，只能評(píng)估的標(biāo)準(zhǔn)：由于下棋的雙方是對(duì)立的，只能選擇其中一方為評(píng)估的標(biāo)準(zhǔn)方。選擇其中一方為評(píng)估的標(biāo)準(zhǔn)方。3.3.極小極大搜索過(guò)程極小極大搜索過(guò)程第15頁(yè)，共46頁(yè)。MAX節(jié)點(diǎn)和節(jié)點(diǎn)和MIN節(jié)點(diǎn)節(jié)點(diǎn)n命名博弈的雙方，一方為命名博弈的雙方，一方為“正方正方”，對(duì)每，對(duì)每個(gè)狀態(tài)的評(píng)估都是對(duì)應(yīng)于該方的輸贏的。個(gè)狀態(tài)的評(píng)估都是對(duì)應(yīng)于該方的輸贏的。例如，贏例如，贏2個(gè)，輸個(gè)，輸1個(gè)等，都是指正方的。個(gè)等，都是指正方的。正方每走一步，都在選擇使自己贏得更多正方每走一步，都在選擇使自己贏得更多的節(jié)點(diǎn)，因此這

9、類節(jié)點(diǎn)稱為的節(jié)點(diǎn)，因此這類節(jié)點(diǎn)稱為“MAX”節(jié)點(diǎn)；節(jié)點(diǎn)；3.極小極大搜索過(guò)程極小極大搜索過(guò)程第16頁(yè)，共46頁(yè)。n另一方為另一方為“反方反方”，對(duì)每個(gè)狀態(tài)的評(píng)估，對(duì)每個(gè)狀態(tài)的評(píng)估都是對(duì)應(yīng)于對(duì)手的輸贏的。例如，贏都是對(duì)應(yīng)于對(duì)手的輸贏的。例如，贏2個(gè)，個(gè)，輸一個(gè)，其實(shí)是指自己輸輸一個(gè)，其實(shí)是指自己輸2個(gè)，贏個(gè)，贏1個(gè)的。個(gè)的。反方每走一步，都在選擇使對(duì)手輸?shù)酶捶矫孔咭徊?，都在選擇使對(duì)手輸?shù)酶嗟墓?jié)點(diǎn)，因此這類節(jié)點(diǎn)稱為多的節(jié)點(diǎn)，因此這類節(jié)點(diǎn)稱為“MIN”節(jié)節(jié)點(diǎn)。點(diǎn)。3.3.極小極大搜索過(guò)程極小極大搜索過(guò)程第17頁(yè)，共46頁(yè)。n由于正方和反方是交替走步的，因此由于正方和反方是交替走步的，因此MAX節(jié)

10、點(diǎn)和節(jié)點(diǎn)和MIN節(jié)點(diǎn)會(huì)交替出現(xiàn)。節(jié)點(diǎn)會(huì)交替出現(xiàn)。3.極小極大搜索過(guò)程極小極大搜索過(guò)程第18頁(yè)，共46頁(yè)。n正方（正方（MAX節(jié)點(diǎn)）從所有子節(jié)點(diǎn)中，選節(jié)點(diǎn)）從所有子節(jié)點(diǎn)中，選取具有最大評(píng)估值的節(jié)點(diǎn)。取具有最大評(píng)估值的節(jié)點(diǎn)。n反方（反方（MIN節(jié)點(diǎn)）從其所有子節(jié)點(diǎn)中，節(jié)點(diǎn)）從其所有子節(jié)點(diǎn)中，選取具有最小評(píng)估值的節(jié)點(diǎn)。選取具有最小評(píng)估值的節(jié)點(diǎn)。n反復(fù)進(jìn)行這種選取，就可以得到雙方各反復(fù)進(jìn)行這種選取，就可以得到雙方各個(gè)節(jié)點(diǎn)的評(píng)估值。這種確定棋步的方法，個(gè)節(jié)點(diǎn)的評(píng)估值。這種確定棋步的方法，稱為稱為極小極大搜索法極小極大搜索法。3.極小極大搜索過(guò)程極小極大搜索過(guò)程第19頁(yè)，共46頁(yè)。3.極小極大搜索過(guò)程極小

11、極大搜索過(guò)程第20頁(yè)，共46頁(yè)。5-333-3022-30-23541-30689-3MINMAX0MAXMIN3.極小極大搜索過(guò)程極小極大搜索過(guò)程第21頁(yè)，共46頁(yè)。015-333-3022-30-23541-30689-30-33-3-3-21-36-3031601MAXMINMAXMIN3.極小極大搜索過(guò)程極小極大搜索過(guò)程第22頁(yè)，共46頁(yè)。n 在九宮格棋盤(pán)上，兩位選手輪流在棋盤(pán)上擺各自的在九宮格棋盤(pán)上，兩位選手輪流在棋盤(pán)上擺各自的 棋子棋子(每次一枚每次一枚)，誰(shuí)先取得三線的結(jié)果就取勝。，誰(shuí)先取得三線的結(jié)果就取勝。設(shè)程序方設(shè)程序方MAXMAX的棋子用的棋子用()()表示，表示，MAXM

12、AX先走。先走。對(duì)手對(duì)手MINMIN的棋子用的棋子用(o o)表示。表示。例如：例如：3.極小極大搜索過(guò)程極小極大搜索過(guò)程MIN取勝取勝第23頁(yè)，共46頁(yè)。估計(jì)函數(shù)估計(jì)函數(shù) f(p)=(f(p)=(所有空格都放上所有空格都放上MAXMAX的的棋子之后，棋子之后，MAXMAX的三子成線數(shù)的三子成線數(shù))(所有空所有空格都放上格都放上MINMIN的棋子之后，的棋子之后，MINMIN的三子成的三子成線的總數(shù)線的總數(shù))若若P P是是MAXMAX獲勝的格局，則獲勝的格局，則f(p)=+f(p)=+；若若P P是是MINMIN獲勝的格局，則獲勝的格局，則f(p)f(p)-。3.極小極大搜索過(guò)程極小極大搜索過(guò)

13、程第24頁(yè)，共46頁(yè)。3.極小極大搜索過(guò)程極小極大搜索過(guò)程估計(jì)函數(shù)值估計(jì)函數(shù)值 f(p)=6-4=2估計(jì)函數(shù)估計(jì)函數(shù) f(p)=(f(p)=(所有空格都放上所有空格都放上MAXMAX的棋子之后，的棋子之后，MAXMAX的三子成線的三子成線(行、列、對(duì)角行、列、對(duì)角)數(shù)數(shù))(所有空格都放上所有空格都放上MINMIN的棋子之后，的棋子之后，MINMIN的三子的三子成線成線(行、列、對(duì)角行、列、對(duì)角)的總數(shù)的總數(shù))當(dāng)前棋局當(dāng)前棋局f(p)=2第25頁(yè)，共46頁(yè)。3.極小極大搜索過(guò)程極小極大搜索過(guò)程一字棋第一階段搜索樹(shù)一字棋第一階段搜索樹(shù)第26頁(yè)，共46頁(yè)。3.極小極大搜索過(guò)程極小極大搜索過(guò)程一字棋第

14、二階段搜索樹(shù)一字棋第二階段搜索樹(shù)第27頁(yè)，共46頁(yè)。3.極小極大搜索過(guò)程極小極大搜索過(guò)程一字棋第三階段搜索樹(shù)一字棋第三階段搜索樹(shù)第28頁(yè)，共46頁(yè)。設(shè)設(shè)有有一一個(gè)個(gè)擺擺放放三三個(gè)個(gè)子子的的棋棋盤(pán)盤(pán)殘殘局局，如如下下圖圖所所示示，和和 在在結(jié)結(jié)束束前前有有三三步步棋棋可可以以走走，而而且且設(shè)設(shè)走走第第一一步步的的是是 。這這時(shí)時(shí)存存在在著著三三個(gè)個(gè)空空格格A，B，C，用用博博弈弈樹(shù)樹(shù)搜搜索索算算法法判判斷斷應(yīng)應(yīng)該把棋子放到哪一格內(nèi)。該把棋子放到哪一格內(nèi)。A AB BC C棋盤(pán)殘局舉例：棋盤(pán)殘局舉例：3.極小極大搜索過(guò)程極小極大搜索過(guò)程第29頁(yè)，共46頁(yè)。A AB BC CB BC CC CB B

15、0A AC CC CA AA A B BB BA A-1-0-10-0MAX節(jié)點(diǎn)節(jié)點(diǎn)MIN節(jié)點(diǎn)節(jié)點(diǎn)終端節(jié)點(diǎn)終端節(jié)點(diǎn)3.極小極大搜索過(guò)程極小極大搜索過(guò)程第30頁(yè)，共46頁(yè)。對(duì)對(duì)于于棋棋盤(pán)盤(pán)殘殘局局中中的的來(lái)來(lái)說(shuō)說(shuō)，最最好好的的選選擇擇，是是將將放放在在C C的位置上，這時(shí)可以導(dǎo)致平局局面。的位置上，這時(shí)可以導(dǎo)致平局局面。3.極小極大搜索過(guò)程極小極大搜索過(guò)程第31頁(yè)，共46頁(yè)。n-剪支法的剪支法的引入引入 在在極極小小極極大大法法中中，必必須須求求出出所所有有終終端端節(jié)節(jié)點(diǎn)點(diǎn)的的評(píng)評(píng)估估值值，當(dāng)當(dāng)預(yù)預(yù)先先考考慮慮的的棋棋步步比比較較多多時(shí)時(shí)，計(jì)計(jì)算算量量會(huì)會(huì)大大大大增增加加。為為了了提提高高搜搜索

16、索的的效效率率，引引入入了了通通過(guò)過(guò)對(duì)對(duì)評(píng)評(píng)估估值值的的上上下下限限進(jìn)進(jìn)行行估估計(jì)計(jì)，從從而而減少需進(jìn)行評(píng)估的節(jié)點(diǎn)范圍的減少需進(jìn)行評(píng)估的節(jié)點(diǎn)范圍的-剪支法。剪支法。4.4.-搜索過(guò)程搜索過(guò)程第32頁(yè)，共46頁(yè)。作作為為正正方方出出現(xiàn)現(xiàn)的的MAX節(jié)節(jié)點(diǎn)點(diǎn)，假假設(shè)設(shè)它它的的MIN子子節(jié)節(jié)點(diǎn)點(diǎn)有有N個(gè)個(gè)，那那么么當(dāng)當(dāng)它它的的第第一一個(gè)個(gè)MIN子子節(jié)節(jié)點(diǎn)點(diǎn)的的評(píng)評(píng)估估值值為為 時(shí)時(shí)，則則對(duì)對(duì)于于其其它它的的子子節(jié)節(jié)點(diǎn)點(diǎn)，如如果果有有高高過(guò)過(guò) 的的，就就取取那那最最高高的的值值作作為為該該MAX節(jié)節(jié)點(diǎn)點(diǎn)的的評(píng)評(píng)估估值值；如如果果沒(méi)沒(méi)有有，則則該該MAX節(jié)節(jié)點(diǎn)點(diǎn)的的評(píng)評(píng)估值為估值為?？偪傊?，該該MAX節(jié)

17、節(jié)點(diǎn)點(diǎn)的的評(píng)評(píng)估估值值不不會(huì)會(huì)低低于于，這這個(gè)個(gè) 就就稱為該稱為該MAX節(jié)點(diǎn)的評(píng)估下限值。節(jié)點(diǎn)的評(píng)估下限值。4.-搜索過(guò)程搜索過(guò)程n MAX節(jié)點(diǎn)的評(píng)估下限值節(jié)點(diǎn)的評(píng)估下限值 第33頁(yè)，共46頁(yè)。n MIN節(jié)點(diǎn)的評(píng)估上限值節(jié)點(diǎn)的評(píng)估上限值 作作為為反反方方出出現(xiàn)現(xiàn)的的MIN節(jié)節(jié)點(diǎn)點(diǎn)，假假設(shè)設(shè)它它的的MAX子子節(jié)節(jié)點(diǎn)點(diǎn)有有N個(gè)個(gè)，那那么么當(dāng)當(dāng)它它的的第第一一個(gè)個(gè)MAX子子節(jié)節(jié)點(diǎn)點(diǎn)的的評(píng)評(píng)估估值值為為 時(shí)時(shí)，則則對(duì)對(duì)于于其其它它子子節(jié)節(jié)點(diǎn)點(diǎn)，如如果果有有低低于于 的的，就就取取那那個(gè)個(gè)低低于于 的的值值作作為為該該MIN節(jié)節(jié)點(diǎn)點(diǎn)的的評(píng)評(píng)估估值值；如如果果沒(méi)沒(méi)有有，則則該該MIN節(jié)點(diǎn)的評(píng)估值取節(jié)點(diǎn)的評(píng)

18、估值取。總總之之，該該MIN節(jié)節(jié)點(diǎn)點(diǎn)的的評(píng)評(píng)估估值值不不會(huì)會(huì)高高過(guò)過(guò)，這這個(gè)個(gè) 就就稱為該稱為該MIN節(jié)點(diǎn)的評(píng)估上限值。節(jié)點(diǎn)的評(píng)估上限值。4.-搜索過(guò)程搜索過(guò)程第34頁(yè)，共46頁(yè)。n 剪支法剪支法 MAX節(jié)點(diǎn)節(jié)點(diǎn)MIN節(jié)點(diǎn)節(jié)點(diǎn)=剪支剪支ABCD4.-搜索過(guò)程搜索過(guò)程 設(shè)設(shè)MAX節(jié)點(diǎn)的下限為節(jié)點(diǎn)的下限為，則其，則其所有的所有的MIN子節(jié)點(diǎn)中，其子節(jié)點(diǎn)中，其評(píng)估值的評(píng)估值的 上限小于等于上限小于等于 的節(jié)點(diǎn)，其以下部分的搜索都可以停的節(jié)點(diǎn)，其以下部分的搜索都可以停止了，即對(duì)這部分節(jié)點(diǎn)進(jìn)行了止了，即對(duì)這部分節(jié)點(diǎn)進(jìn)行了 剪支。剪支。第35頁(yè)，共46頁(yè)。設(shè)設(shè)MIN節(jié)點(diǎn)的上限為節(jié)點(diǎn)的上限為，則其，則其所有

19、的所有的MAX子節(jié)點(diǎn)中，子節(jié)點(diǎn)中，其評(píng)估值的其評(píng)估值的 下限大于等于下限大于等于 的節(jié)點(diǎn)，其以下部分的搜索的節(jié)點(diǎn)，其以下部分的搜索都可以停止了，即對(duì)這部分節(jié)點(diǎn)進(jìn)行了都可以停止了，即對(duì)這部分節(jié)點(diǎn)進(jìn)行了 剪支。剪支。MAX節(jié)點(diǎn)節(jié)點(diǎn)MIN節(jié)點(diǎn)節(jié)點(diǎn)=剪支剪支ABCD4.-搜索過(guò)程搜索過(guò)程n 剪支法剪支法 第36頁(yè)，共46頁(yè)。A B CDEFG H I J K L N O M4.-搜索過(guò)程搜索過(guò)程MAX節(jié)點(diǎn)節(jié)點(diǎn)MAX節(jié)點(diǎn)節(jié)點(diǎn)MIN節(jié)點(diǎn)節(jié)點(diǎn)終端節(jié)點(diǎn)終端節(jié)點(diǎn)35652164第37頁(yè)，共46頁(yè)。MAX節(jié)點(diǎn)節(jié)點(diǎn)(5,)35652164(6,)(2,)(-,5,5)(-,2,2)(5,)MIN節(jié)點(diǎn)節(jié)點(diǎn)終端節(jié)點(diǎn)終端

20、節(jié)點(diǎn) 剪支剪支 剪支剪支A B CDEFG H I J K L N O MMAX節(jié)點(diǎn)節(jié)點(diǎn)4.-搜索過(guò)程搜索過(guò)程第38頁(yè)，共46頁(yè)。一字棋第一階段一字棋第一階段-剪支方法剪支方法4.-搜索過(guò)程搜索過(guò)程第39頁(yè)，共46頁(yè)。4.-搜索過(guò)程搜索過(guò)程n極大節(jié)點(diǎn)的下界為極大節(jié)點(diǎn)的下界為。n極小節(jié)點(diǎn)的上界為極小節(jié)點(diǎn)的上界為。n剪支的條件：剪支的條件：n后輩節(jié)點(diǎn)的后輩節(jié)點(diǎn)的 值值祖先節(jié)點(diǎn)的祖先節(jié)點(diǎn)的 值時(shí)，值時(shí)，剪支剪支n后輩節(jié)點(diǎn)的后輩節(jié)點(diǎn)的 值值祖先節(jié)點(diǎn)的祖先節(jié)點(diǎn)的 值時(shí)，值時(shí)，剪支剪支n簡(jiǎn)記為：簡(jiǎn)記為：n極小極小極大，極大，剪支剪支n極大極大極小，極小，剪支剪支第40頁(yè)，共46頁(yè)。4.-搜索過(guò)程搜索過(guò)程8

21、6-31453-3503-3022-30-2309-300-303305411-31661abcdefghijkmnMAXMINMAXMIN第41頁(yè)，共46頁(yè)。改進(jìn)方法改進(jìn)方法n 使使用用-剪剪支支技技術(shù)術(shù)，當(dāng)當(dāng)不不滿滿足足剪剪支支條條件件(即即)時(shí)時(shí)或或 值值比比 值值大大不不了了多多少少或或極極相相近近時(shí)時(shí)，這這時(shí)時(shí)也也可可以以進(jìn)進(jìn)行行剪剪支支，以以便便有有條條件件把把搜搜索索集集中中到到會(huì)會(huì)帶帶來(lái)來(lái)更更大大效效果果的的其其他他路路徑徑上上，這這就就是是中中止止對(duì)對(duì)效效益益不不大大的的一一些些子子樹(shù)樹(shù)的的搜索，以提高搜索效率。搜索，以提高搜索效率。4.-搜索過(guò)程搜索過(guò)程第42頁(yè)，共46頁(yè)。

22、n 不不嚴(yán)嚴(yán)格格限限制制搜搜索索的的深深度度。當(dāng)當(dāng)?shù)降竭_(dá)達(dá)深深度度限限制制時(shí)時(shí)，如如出出現(xiàn)現(xiàn)博博弈弈格格局局有有可可能能發(fā)發(fā)生生較較大大變變化化時(shí)時(shí)，則則應(yīng)應(yīng)多多搜搜索索幾幾層層，使使格格局局進(jìn)進(jìn)入入較較穩(wěn)穩(wěn)定定狀狀態(tài)態(tài)后后再再中中止止，這這樣樣可可使使倒倒推推值值計(jì)計(jì)算算的的結(jié)結(jié)果果比比較較合合理理，避避免免考考慮慮不不充充分分產(chǎn)產(chǎn)生生的的影影響響，這這是是等等候候狀狀態(tài)態(tài)平穩(wěn)后中止搜索的方法。平穩(wěn)后中止搜索的方法。4.-搜索過(guò)程搜索過(guò)程第43頁(yè)，共46頁(yè)。n當(dāng)算法給出所選的走步后，不要馬上停止搜當(dāng)算法給出所選的走步后，不要馬上停止搜索，而是在原先估計(jì)可能的路徑上再往前搜索，而是在原先估計(jì)可

23、能的路徑上再往前搜索幾步，再次檢驗(yàn)會(huì)不會(huì)出現(xiàn)意外，這是一索幾步，再次檢驗(yàn)會(huì)不會(huì)出現(xiàn)意外，這是一種增添輔助搜索的方法。種增添輔助搜索的方法。4.-搜索過(guò)程搜索過(guò)程第44頁(yè)，共46頁(yè)。n對(duì)某些博弈的開(kāi)局階段和殘局階段，往對(duì)某些博弈的開(kāi)局階段和殘局階段，往往總結(jié)了一些固定的對(duì)弈模式，因此可往總結(jié)了一些固定的對(duì)弈模式，因此可以利用這些知識(shí)編好走步表，以便在開(kāi)以利用這些知識(shí)編好走步表，以便在開(kāi)局和結(jié)局時(shí)使用查表法。只是在進(jìn)入中局和結(jié)局時(shí)使用查表法。只是在進(jìn)入中盤(pán)階段后，再調(diào)用其他有效的搜索算法，盤(pán)階段后，再調(diào)用其他有效的搜索算法，來(lái)選擇最優(yōu)的走步。來(lái)選擇最優(yōu)的走步。4.-搜索過(guò)程搜索過(guò)程第45頁(yè)，共46

24、頁(yè)。1、不是井里沒(méi)有水，而是你挖的不夠深。不是成功來(lái)得慢，而是你努力的不夠多。2、孤單一人的時(shí)間使自己變得優(yōu)秀，給來(lái)的人一個(gè)驚喜，也給自己一個(gè)好的交代。3、命運(yùn)給你一個(gè)比別人低的起點(diǎn)是想告訴你，讓你用你的一生去奮斗出一個(gè)絕地反擊的故事，所以有什么理由不努力!4、心中沒(méi)有過(guò)分的貪求，自然苦就少?？诶锊徽f(shuō)多余的話，自然禍就少。腹內(nèi)的食物能減少，自然病就少。思緒中沒(méi)有過(guò)分欲，自然憂就少。大悲是無(wú)淚的，同樣大悟無(wú)言。緣來(lái)盡量要惜，緣盡就放。人生本來(lái)就空，對(duì)人家笑笑，對(duì)自己笑笑，笑著看天下，看日出日落，花謝花開(kāi)，豈不自在，哪里來(lái)的塵埃!5、心情就像衣服，臟了就拿去洗洗，曬曬，陽(yáng)光自然就會(huì)蔓延開(kāi)來(lái)。陽(yáng)光那

25、么好，何必自尋煩惱，過(guò)好每一個(gè)當(dāng)下，一萬(wàn)個(gè)美麗的未來(lái)抵不過(guò)一個(gè)溫暖的現(xiàn)在。6、無(wú)論你正遭遇著什么，你都要從落魄中站起來(lái)重振旗鼓，要繼續(xù)保持熱忱，要繼續(xù)保持微笑，就像從未受傷過(guò)一樣。7、生命的美麗，永遠(yuǎn)展現(xiàn)在她的進(jìn)取之中;就像大樹(shù)的美麗，是展現(xiàn)在它負(fù)勢(shì)向上高聳入云的蓬勃生機(jī)中;像雄鷹的美麗，是展現(xiàn)在它搏風(fēng)擊雨如蒼天之魂的翱翔中;像江河的美麗，是展現(xiàn)在它波濤洶涌一瀉千里的奔流中。8、有些事，不可避免地發(fā)生，陰晴圓缺皆有規(guī)律，我們只能坦然地接受;有些事，只要你愿意努力，矢志不渝地付出，就能慢慢改變它的軌跡。9、與其埋怨世界，不如改變自己。管好自己的心，做好自己的事，比什么都強(qiáng)。人生無(wú)完美，曲折亦風(fēng)景

26、。別把失去看得過(guò)重，放棄是另一種擁有;不要經(jīng)常艷羨他人，人做到了，心悟到了，相信屬于你的風(fēng)景就在下一個(gè)拐彎處。10、有些事想開(kāi)了，你就會(huì)明白，在世上，你就是你，你痛痛你自己，你累累你自己，就算有人同情你，那又怎樣，最后收拾殘局的還是要靠你自己。11、人生的某些障礙，你是逃不掉的。與其費(fèi)盡周折繞過(guò)去，不如勇敢地攀登，或許這會(huì)鑄就你人生的高點(diǎn)。12、有些壓力總是得自己扛過(guò)去，說(shuō)出來(lái)就成了充滿負(fù)能量的抱怨。尋求安慰也無(wú)濟(jì)于事，還徒增了別人的煩惱。13、認(rèn)識(shí)到我們的所見(jiàn)所聞都是假象，認(rèn)識(shí)到此生都是虛幻，我們才能真正認(rèn)識(shí)到佛法的真相。錢(qián)多了會(huì)壓死你，你承受得了嗎?帶，帶不走，放，放不下。時(shí)時(shí)刻刻發(fā)悲心，

27、饒益眾生為他人。14、夢(mèng)想總是跑在我的前面。努力追尋它們，為了那一瞬間的同步，這就是動(dòng)人的生命奇跡。15、懶惰不會(huì)讓你一下子跌倒，但會(huì)在不知不覺(jué)中減少你的收獲;勤奮也不會(huì)讓你一夜成功，但會(huì)在不知不覺(jué)中積累你的成果。人生需要挑戰(zhàn)，更需要堅(jiān)持和勤奮!16、人生在世：可以缺錢(qián)，但不能缺德;可以失言，但不能失信;可以倒下，但不能跪下;可以求名，但不能盜名;可以低落，但不能墮落;可以放松，但不能放縱;可以虛榮，但不能虛偽;可以平凡，但不能平庸;可以浪漫，但不能浪蕩;可以生氣，但不能生事。17、人生沒(méi)有筆直路，當(dāng)你感到迷茫、失落時(shí)，找?guī)撞窟@種充滿正能量的電影，坐下來(lái)靜靜欣賞，去發(fā)現(xiàn)生命中真正重要的東西。18、在人生的舞臺(tái)上，當(dāng)有人愿意在臺(tái)下陪你度過(guò)無(wú)數(shù)個(gè)沒(méi)有未來(lái)的夜時(shí)，你就更想展現(xiàn)精彩絕倫的自己。但愿每個(gè)被努力支撐的靈魂能吸引更多的人同行。第46頁(yè)，共46頁(yè)。