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

1、2.3博弈樹搜索第1頁，共46頁。20世紀60年代，研制出的西洋跳棋和國際象棋的博弈程序達到了大師級的水平。1958約翰麥卡錫提出博弈樹搜索算法1997年，IBM公司研制的“深藍”國際象棋 程序，采用博弈樹搜索算法，該程序戰(zhàn)勝了國際象棋世界冠軍卡斯帕羅夫。1.概述第2頁，共46頁。正在與深藍下棋的卡斯帕羅夫第3頁，共46頁。博弈問題特點：雙人對弈，輪流走步。信息完備，雙方所得到的信息是一樣的。零和，即對一方有利的棋，對另一方肯定是不利的，不存在對雙方均有利或無利的棋。1.概述第4頁，共46頁。博弈的特性兩個棋手交替地走棋 ；比賽的最終結(jié)果，是贏、輸和平局中的一種；可用圖搜索技術(shù)進行，但效率很低

2、；博弈的過程，是尋找置對手于必敗態(tài)的過程；雙方都無法干預(yù)對方的選擇。1.概述第5頁，共46頁。2.Grundy 博弈下棋的雙方是對立的，命名博弈的雙方，一方為“正方”，這類節(jié)點稱為“MAX”節(jié)點；另一方為“反方”，這類節(jié)點稱為“MIN”節(jié)點。正方和反方是交替走步的，因此MAX節(jié)點和MIN節(jié)點會交替出現(xiàn)。第6頁，共46頁。2.Grundy 博弈Grundy博弈是一個分錢幣的游戲。有 一堆數(shù)目為N的錢幣，由兩位選手輪流進行分堆，要求每個選手每次只把其中某一堆分成數(shù)目不等的兩小堆。例如，選手甲把N分成兩堆后，輪到選手乙就可以挑其中一堆來分，如此進行下去，直到有一位選手先無法把錢幣再分成不相等的兩堆時

3、就得認輸。第7頁，共46頁。2.Grundy 博弈設(shè)初始狀態(tài)為(7，MIN)，建立問題的狀態(tài)空間圖，圖中所有終結(jié)點均表示該選手必輸?shù)那闆r，取勝方的目標是設(shè)法使棋局發(fā)展為結(jié)束在對方走步時的終結(jié)點上。第8頁，共46頁。MIN先走MAX必勝2.Grundy 博弈第9頁，共46頁。結(jié)點A是MAX的搜索目標，而結(jié)點B，C則為MIN的搜索目標。2.Grundy 博弈第10頁，共46頁。搜索策略要考慮的問題是：對MIN走步后的每一個MAX結(jié)點，必須證明MAX對MIN可能走的每一個棋局對弈后能獲勝，即MAX必須考慮應(yīng)付MIN的所有招法，這是一個與的含意，因此含有MAX符號的結(jié)點可看成與結(jié)點。 2.Grundy

4、 博弈第11頁，共46頁。對MAX走步后的每一個MIN結(jié)點，只須證明MAX有一步能走贏就可以，即MAX只要考慮能走出一步棋使MIN無法招架就成，因此含有MIN符號的結(jié)點可看成或結(jié)點。2.Grundy 博弈第12頁，共46頁。對弈過程的搜索圖呈現(xiàn)出與或圖表示的形式。實現(xiàn)一種取勝的策略就是搜索一個解圖的問題，解圖就代表一種完整的博弈策略。 2.Grundy 博弈第13頁，共46頁。中國象棋一盤棋平均走50步，總狀態(tài)數(shù)約為10的161次方。假設(shè)1毫微秒走一步，約需10的145次方年。結(jié)論：不可能窮舉。3.極小極大搜索過程第14頁，共46頁。對各個局面進行評估評估的目的：對后面的狀態(tài)提前進行考慮，并且

5、以各種狀態(tài)的評估值為基礎(chǔ)作出最好的走棋選擇。 評估的方法：用評價函數(shù)對棋局進行評估。贏的評估值設(shè)為+，輸?shù)脑u估值設(shè)為-，平局的評估值設(shè)為0。 評估的標準：由于下棋的雙方是對立的，只能選擇其中一方為評估的標準方。3.極小極大搜索過程第15頁，共46頁。MAX節(jié)點和MIN節(jié)點命名博弈的雙方，一方為“正方”，對每個狀態(tài)的評估都是對應(yīng)于該方的輸贏的。例如，贏2個，輸1個等，都是指正方的。正方每走一步，都在選擇使自己贏得更多的節(jié)點，因此這類節(jié)點稱為“MAX”節(jié)點；3.極小極大搜索過程第16頁，共46頁。另一方為“反方”，對每個狀態(tài)的評估都是對應(yīng)于對手的輸贏的。例如，贏2個，輸一個，其實是指自己輸2個，贏

6、1個的。反方每走一步，都在選擇使對手輸?shù)酶嗟墓?jié)點，因此這類節(jié)點稱為“MIN”節(jié)點。3.極小極大搜索過程第17頁，共46頁。由于正方和反方是交替走步的，因此MAX節(jié)點和MIN節(jié)點會交替出現(xiàn)。3.極小極大搜索過程第18頁，共46頁。正方（MAX節(jié)點）從所有子節(jié)點中，選取具有最大評估值的節(jié)點。反方（MIN節(jié)點）從其所有子節(jié)點中，選取具有最小評估值的節(jié)點。反復(fù)進行這種選取，就可以得到雙方各個節(jié)點的評估值。這種確定棋步的方法，稱為極小極大搜索法。 3.極小極大搜索過程第19頁，共46頁。3.極小極大搜索過程第20頁，共46頁。5-333-3022-30-23541-30689-3MINMAX0MAXM

7、IN3.極小極大搜索過程第21頁，共46頁。015-333-3022-30-23541-30689-30-33-3-3-21-36-3031601MAXMINMAXMIN3.極小極大搜索過程第22頁，共46頁。 在九宮格棋盤上，兩位選手輪流在棋盤上擺各自的 棋子(每次一枚)，誰先取得三線的結(jié)果就取勝。 設(shè)程序方MAX的棋子用()表示， MAX先走。 對手MIN的棋子用(o)表示。 例如：3.極小極大搜索過程MIN取勝第23頁，共46頁。 估計函數(shù) f(p)=(所有空格都放上MAX的棋子之后，MAX的三子成線數(shù))(所有空格都放上MIN的棋子之后，MIN的三子成線的總數(shù)) 若P是MAX獲勝的格局，

8、則f(p)=+ ； 若P是MIN獲勝的格局，則f(p)- 。3.極小極大搜索過程第24頁，共46頁。3.極小極大搜索過程估計函數(shù)值 f(p)=6-4=2估計函數(shù) f(p)=(所有空格都放上MAX的棋子之后，MAX的三子成線(行、列、對角)數(shù))(所有空格都放上MIN的棋子之后，MIN的三子成線(行、列、對角)的總數(shù))當前棋局f(p)=2第25頁，共46頁。3.極小極大搜索過程一字棋第一階段搜索樹第26頁，共46頁。3.極小極大搜索過程一字棋第二階段搜索樹第27頁，共46頁。3.極小極大搜索過程一字棋第三階段搜索樹第28頁，共46頁。 設(shè)有一個擺放三個子的棋盤殘局，如下圖所示，和在結(jié)束前有三步棋可

9、以走，而且設(shè)走第一步的是 。這時存在著三個空格A，B，C，用博弈樹搜索算法判斷應(yīng)該把棋子放到哪一格內(nèi)。 ABC棋盤殘局舉例：3.極小極大搜索過程第29頁，共46頁。ABCBCCB0ACCAABBA-1-0-10-0MAX節(jié)點MIN節(jié)點終端節(jié)點3.極小極大搜索過程第30頁，共46頁。 對于棋盤殘局中的來說，最好的選擇，是將放在C的位置上，這時可以導(dǎo)致平局局面。 3.極小極大搜索過程第31頁，共46頁。-剪支法的引入 在極小極大法中，必須求出所有終端節(jié)點的評估值，當預(yù)先考慮的棋步比較多時，計算量會大大增加。為了提高搜索的效率，引入了通過對評估值的上下限進行估計，從而減少需進行評估的節(jié)點范圍的-剪支

10、法。4. -搜索過程第32頁，共46頁。 作為正方出現(xiàn)的MAX節(jié)點，假設(shè)它的MIN子節(jié)點有N個，那么當它的第一個MIN子節(jié)點的評估值為時，則對于其它的子節(jié)點，如果有高過的，就取那最高的值作為該MAX節(jié)點的評估值；如果沒有，則該MAX節(jié)點的評估值為。 總之，該MAX節(jié)點的評估值不會低于，這個就稱為該MAX節(jié)點的評估下限值。4. -搜索過程 MAX節(jié)點的評估下限值 第33頁，共46頁。 MIN節(jié)點的評估上限值 作為反方出現(xiàn)的MIN節(jié)點，假設(shè)它的MAX子節(jié)點有N個，那么當它的第一個MAX子節(jié)點的評估值為時，則對于其它子節(jié)點，如果有低于的，就取那個低于的值作為該MIN節(jié)點的評估值；如果沒有，則該MIN

11、節(jié)點的評估值取。 總之，該MIN節(jié)點的評估值不會高過，這個就稱為該MIN節(jié)點的評估上限值。4. -搜索過程第34頁，共46頁。剪支法 MAX節(jié)點MIN節(jié)點=剪支ABCD4. -搜索過程 設(shè)MAX節(jié)點的下限為，則其所有的MIN子節(jié)點中，其評估值的上限小于等于的節(jié)點，其以下部分的搜索都可以停止了，即對這部分節(jié)點進行了剪支。第35頁，共46頁。 設(shè)MIN節(jié)點的上限為，則其所有的MAX子節(jié)點中，其評估值的下限大于等于的節(jié)點，其以下部分的搜索都可以停止了，即對這部分節(jié)點進行了剪支。MAX節(jié)點MIN節(jié)點=剪支ABCD4. -搜索過程剪支法 第36頁，共46頁。A B CDEFG H I J K L N O

12、 M4. -搜索過程MAX節(jié)點MAX節(jié)點MIN節(jié)點終端節(jié)點35652164第37頁，共46頁。MAX節(jié)點(5,)35652164(6,)(2,)(-,5)(-,2)(5,)MIN節(jié)點終端節(jié)點剪支剪支A B CDEFG H I J K L N O MMAX節(jié)點4. -搜索過程第38頁，共46頁。一字棋第一階段-剪支方法4. -搜索過程第39頁，共46頁。4. -搜索過程極大節(jié)點的下界為。極小節(jié)點的上界為。剪支的條件：后輩節(jié)點的值祖先節(jié)點的值時， 剪支后輩節(jié)點的 值祖先節(jié)點的值時， 剪支簡記為：極小極大， 剪支極大極小， 剪支第40頁，共46頁。4. -搜索過程86-31453-3503-3022

13、-30-2309-300-303305411-31661abcdefghijkmnMAXMINMAXMIN第41頁，共46頁。改進方法 使用-剪支技術(shù)，當不滿足剪支條件(即)時或值比值大不了多少或極相近時，這時也可以進行剪支，以便有條件把搜索集中到會帶來更大效果的其他路徑上，這就是中止對效益不大的一些子樹的搜索，以提高搜索效率。 4. -搜索過程第42頁，共46頁。 不嚴格限制搜索的深度。當?shù)竭_深度限制時，如出現(xiàn)博弈格局有可能發(fā)生較大變化時，則應(yīng)多搜索幾層，使格局進入較穩(wěn)定狀態(tài)后再中止，這樣可使倒推值計算的結(jié)果比較合理，避免考慮不充分產(chǎn)生的影響，這是等候狀態(tài)平穩(wěn)后中止搜索的方法。 4. -搜索

14、過程第43頁，共46頁。當算法給出所選的走步后，不要馬上停止搜索，而是在原先估計可能的路徑上再往前搜索幾步，再次檢驗會不會出現(xiàn)意外，這是一種增添輔助搜索的方法。 4. -搜索過程第44頁，共46頁。對某些博弈的開局階段和殘局階段，往往總結(jié)了一些固定的對弈模式，因此可以利用這些知識編好走步表，以便在開局和結(jié)局時使用查表法。只是在進入中盤階段后，再調(diào)用其他有效的搜索算法，來選擇最優(yōu)的走步。4. -搜索過程第45頁，共46頁。1、不是井里沒有水，而是你挖的不夠深。不是成功來得慢，而是你努力的不夠多。2、孤單一人的時間使自己變得優(yōu)秀，給來的人一個驚喜，也給自己一個好的交代。3、命運給你一個比別人低的起

15、點是想告訴你，讓你用你的一生去奮斗出一個絕地反擊的故事，所以有什么理由不努力!4、心中沒有過分的貪求，自然苦就少?？诶锊徽f多余的話，自然禍就少。腹內(nèi)的食物能減少，自然病就少。思緒中沒有過分欲，自然憂就少。大悲是無淚的，同樣大悟無言。緣來盡量要惜，緣盡就放。人生本來就空，對人家笑笑，對自己笑笑，笑著看天下，看日出日落，花謝花開，豈不自在，哪里來的塵埃!5、心情就像衣服，臟了就拿去洗洗，曬曬，陽光自然就會蔓延開來。陽光那么好，何必自尋煩惱，過好每一個當下，一萬個美麗的未來抵不過一個溫暖的現(xiàn)在。6、無論你正遭遇著什么，你都要從落魄中站起來重振旗鼓，要繼續(xù)保持熱忱，要繼續(xù)保持微笑，就像從未受傷過一樣。

16、7、生命的美麗，永遠展現(xiàn)在她的進取之中;就像大樹的美麗，是展現(xiàn)在它負勢向上高聳入云的蓬勃生機中;像雄鷹的美麗，是展現(xiàn)在它搏風擊雨如蒼天之魂的翱翔中;像江河的美麗，是展現(xiàn)在它波濤洶涌一瀉千里的奔流中。8、有些事，不可避免地發(fā)生，陰晴圓缺皆有規(guī)律，我們只能坦然地接受;有些事，只要你愿意努力，矢志不渝地付出，就能慢慢改變它的軌跡。9、與其埋怨世界，不如改變自己。管好自己的心，做好自己的事，比什么都強。人生無完美，曲折亦風景。別把失去看得過重，放棄是另一種擁有;不要經(jīng)常艷羨他人，人做到了，心悟到了，相信屬于你的風景就在下一個拐彎處。10、有些事想開了，你就會明白，在世上，你就是你，你痛痛你自己，你累累

17、你自己，就算有人同情你，那又怎樣，最后收拾殘局的還是要靠你自己。11、人生的某些障礙，你是逃不掉的。與其費盡周折繞過去，不如勇敢地攀登，或許這會鑄就你人生的高點。12、有些壓力總是得自己扛過去，說出來就成了充滿負能量的抱怨。尋求安慰也無濟于事，還徒增了別人的煩惱。13、認識到我們的所見所聞都是假象，認識到此生都是虛幻，我們才能真正認識到佛法的真相。錢多了會壓死你，你承受得了嗎?帶，帶不走，放，放不下。時時刻刻發(fā)悲心，饒益眾生為他人。14、夢想總是跑在我的前面。努力追尋它們，為了那一瞬間的同步，這就是動人的生命奇跡。15、懶惰不會讓你一下子跌倒，但會在不知不覺中減少你的收獲;勤奮也不會讓你一夜成功，但會在不知不覺中積累你的成果。人生需