與或圖搜索問(wèn)題ppt課件(參考版)
2025-05-08 18:36本頁(yè)面
【正文】 。如果在深度優(yōu)先搜索過(guò)程中第一次就遇到這個(gè)端節(jié)點(diǎn)，則修剪枝數(shù)最大。而且在一次搜索期間修剪的枝數(shù)取決于早期的 α、 β值與最終倒推值之間的近似程度。 65 ? 要進(jìn)行 αβ修剪，必須至少使某一部分的搜索樹(shù)生長(zhǎng)到最大深度，因?yàn)?α和 β值必須以端節(jié)點(diǎn)的靜態(tài)估值為依據(jù)。對(duì)于一個(gè)“或”節(jié)點(diǎn)，如果估值最高的子節(jié)點(diǎn)最先生成，或者對(duì)于一個(gè)“與”節(jié)點(diǎn)，估值最低的子節(jié)點(diǎn)最先生成，則被剪除的節(jié)點(diǎn)數(shù)最多，搜索的效率最高。這種剪枝稱為 ?剪枝。這種剪枝稱為 ?剪枝。發(fā)生修剪的那些節(jié)點(diǎn)用“ ”表示?，F(xiàn)在假設(shè)我們采用 αβ剪枝技術(shù)來(lái)引導(dǎo)深度優(yōu)先搜索。 MAX節(jié)點(diǎn)用方塊表示， MIN節(jié)點(diǎn)用圓圈表示 )。 62 ? 例： αβ剪枝技術(shù)的例子，圖 。 畫(huà)出節(jié)點(diǎn) B及它的第一個(gè)兒子節(jié)點(diǎn) C，算出節(jié)點(diǎn) C的靜態(tài)值為 1，于是節(jié)點(diǎn) B的倒推值不會(huì)比 1大，又注意到節(jié)點(diǎn) B的最終倒推值不會(huì)小于起始節(jié)點(diǎn)的 α值，由此可肯定最終倒推值 β=1。 (2) 一個(gè) MIN節(jié)點(diǎn)的 β值等于其后繼節(jié)點(diǎn)當(dāng)前最小的最終倒推值。 59 ? 從算法中看到： (1) MAX節(jié)點(diǎn) (包括起始節(jié)點(diǎn) )的 α值永不減少； (2) MIN節(jié)點(diǎn) (包括起始節(jié)點(diǎn) )的 β值永不增加。 (2) 對(duì)于一個(gè)或節(jié)點(diǎn) MAX，若能估計(jì)出其倒推值的下確界 α，并且這個(gè) α值不小于 MAX的父節(jié)點(diǎn) (一定是與節(jié)點(diǎn) )的估計(jì)倒推值的上確界 β，即 α≥β，則就不必再擴(kuò)展該 MAX節(jié)點(diǎn)的其余子節(jié)點(diǎn)了 (因?yàn)檫@些節(jié)點(diǎn)的估值對(duì)MAX父節(jié)點(diǎn)的倒推值已無(wú)任何影響 了 )。 58 ? (1) 對(duì)于一個(gè)與節(jié)點(diǎn) MIN，若能估計(jì)出其倒推值的上確界 β，并且這個(gè) β值不大于 MIN的父節(jié)點(diǎn) (一定是或節(jié)點(diǎn) )的估計(jì)倒推值的下確界 α，即 α≥β，則就不必再擴(kuò)展該 MIN節(jié)點(diǎn)的其余子節(jié)點(diǎn)了 (因?yàn)檫@些節(jié)點(diǎn)的估值對(duì) MIN父節(jié)點(diǎn)的倒推值已無(wú)任何影響 了 )。這種剪枝稱為 ?剪枝 ?“或”節(jié)點(diǎn) D的 ?值不能降低其父節(jié)點(diǎn) A的 ?值，則對(duì)節(jié)點(diǎn) D以下的分枝可停止搜索，并使 D的倒推值為 ?。 ? αβ剪枝技術(shù)的基本思想或算法是，邊生成博弈樹(shù)邊計(jì)算評(píng)估各節(jié)點(diǎn)的倒推值，并且根據(jù)評(píng)估出的倒推值范圍，及時(shí)停止擴(kuò)展那些已無(wú)必要再擴(kuò)展的子節(jié)點(diǎn)，即相當(dāng)于剪去了博弈樹(shù)上的一些分枝，從而節(jié)約了機(jī)器開(kāi)銷，提高了搜索效率。 54 55 56 ??剪枝 ? 上述的極小極大分析法，實(shí)際是先生成一棵博弈樹(shù)，然后再計(jì)算其倒推值，致使極小極大分析法效率較低。 53 極大極小分析法：一子棋 A的第一著棋生成的博弈樹(shù)。 51 1，極小極大過(guò)程 0 5 3 3 3 3 0 2 2 3 0 2 3 5 4 1 3 0 6 8 9 3 0 3 3 3 3 2 1 3 6 3 0 3 1 6 0 1 1 極大 極小 a b 52 極大極小分析法：一子棋 ? 一子棋游戲：估價(jià)函數(shù)定義如下 ? 設(shè)棋局為 P，估價(jià)函數(shù)為 e(P)： ? 1. 若 P是 A必勝的棋局，則 e(P)＝＋ ?； ? 2. 若 P是 B必勝的棋局，則 e(P)＝－ ?； ? 3. 若 P是勝負(fù)未定的棋局，則 e(P)=e(+P)e(P)。這樣計(jì)算出的父節(jié)點(diǎn)的得分稱為 倒推值 。 ? 4. 當(dāng)端節(jié)點(diǎn)的估值計(jì)算出來(lái)后，再推算出父節(jié)點(diǎn)的得分。 ? 3. 為計(jì)算得分，需要根據(jù)問(wèn)題的特性信息定義一個(gè)估價(jià)函數(shù)，用來(lái)估算當(dāng)前博弈樹(shù)端節(jié)點(diǎn)的得分。 ? 2. 為了找到當(dāng)前的最優(yōu)行動(dòng)方案，需要對(duì)各個(gè)方案可能產(chǎn)生的后果進(jìn)行比較。 50 極大極小方法 ? 基本思想： ? 1. 設(shè)博弈的一方為 A、一方為 B。 ? 假設(shè) 1毫微秒走一步，約需 10的 145次方年。即雙方都是很理智地決定自己的行動(dòng)。 ? 在對(duì)壘過(guò)程中，任何一方都了解當(dāng)前的格局及過(guò)去的歷史。其中最為簡(jiǎn)單的一種稱為“二人零和、全信息、非偶然”博弈。稱之為 走法產(chǎn)生 。依賴于 具體棋類特征 。 解謎：電腦是怎樣下棋的 —— 人機(jī)博弈程序的一般設(shè)計(jì)方法 以中國(guó) 棋為 例 （ 1）第一步該做什么？ 數(shù)據(jù)結(jié)構(gòu)的選取 —— 棋盤(pán)表示 占用空間 〉 少 操作速度 〉 快 是否方便 〉 方便 在機(jī)器中表示棋局，讓程序知道 博弈狀態(tài)。極大極小算法是所有搜索算法的基礎(chǔ)。 – 沒(méi)有隨機(jī)因素的博弈在兩個(gè)人之間進(jìn)行，在任何一個(gè)時(shí)刻，一方失去的利益即為另一方得到的利益，不會(huì)出現(xiàn) “ 雙贏 ”的局面，而且在任何時(shí)刻，博弈的雙方都明確的知道每一個(gè)棋子是否存在和存在于哪里。這個(gè)博弈樹(shù)的根節(jié)點(diǎn)是當(dāng)前時(shí)刻的棋局，它的兒子節(jié)點(diǎn)是假設(shè)再行棋一步以后的各種棋局，孫子節(jié)點(diǎn)是從兒子節(jié)點(diǎn)的棋局再行棋一步的各種棋局，以此類推，構(gòu)造整棵博弈樹(shù)，直到可以分出勝負(fù)的棋局。 ? 對(duì)圍棋、中國(guó)象棋、橋牌、撲克等許多種其它種類游戲博弈的研究也正在進(jìn)行中。 ? 1997年 IBM的 “ 深藍(lán) ” 戰(zhàn)勝了國(guó)際象棋世界冠軍卡斯帕羅夫，驚動(dòng)了世界。 ? 2022年 1至 2月 “ 更年少者 ” 與卡斯帕羅夫在紐約較量， 3比 3戰(zhàn)平。 電腦棋手：永不停歇的挑戰(zhàn)！ ? 2022年 “ 更弗里茨 ” 擊敗了除了克拉姆尼克之外的所有排名世界前十位的棋手。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1