人工智能的計(jì)算機(jī)模擬課件-資料下載頁(yè)
2025-02-20 15:14本頁(yè)面
【正文】 。一字棋游戲極小極大分析法v都是相同的棋局 (在博弈中，一宇棋的分枝系數(shù)比較小起初是由于對(duì)稱性，而后是由于棋盤上未布子的空格減少所致 )。圖 經(jīng)過(guò)兩層搜索生成的博弈樹，靜態(tài)估值記在端節(jié)點(diǎn)下面，倒推值記在圓圈內(nèi)。 圖 應(yīng)用于一字棋的極小極大搜索過(guò)程 (第一階段 )一字棋游戲極小極大分析法v由于右圖所示位置具有最大的倒推值，它應(yīng)當(dāng)選取為 MAX的第一步（正好是 MAX的最好的優(yōu)先走步）。 一字棋游戲極小極大分析法v現(xiàn)在我們假設(shè) MAX走了這一步，而 MIN的回步是直接在 X上方的空格里放上一個(gè)圓圈 (對(duì)MAX來(lái)說(shuō)這是一步壞棋，他一定沒(méi)有采用好的搜索策略 )。下一步， MAX又在新的格局下搜索兩層，產(chǎn)生如圖 。 圖 應(yīng)用于一字棋的極小極大搜索過(guò)程 (第二階段 )一字棋游戲極小極大分析法v現(xiàn)在圖中 MAX有兩個(gè)可能 “最好的 ”優(yōu)先走步，假設(shè) MAX走了圖上指明的那一步。而 MIN為了避免立即敗北被迫走了另一步，從而產(chǎn)生如下棋局： MAX再次搜索，產(chǎn)生如圖 所示的樹。圖 應(yīng)用于一字棋的極小極大搜索過(guò)程 (第三階段 )一字棋游戲極小極大分析法v在這棵樹中某些端節(jié)點(diǎn) (例如其中一個(gè)標(biāo)記著A)代表 MIN獲勝，因此它們的估值為 —∞ 。當(dāng)這些估值被倒推回去時(shí)，可看到 MAX的最好的也是唯一能使他避免立即失敗的一個(gè)走步?，F(xiàn)在， MIN可以看出 MAX必然在他的下一走步中獲勝，因此， MIN只好認(rèn)輸?！ ?αβ剪枝技術(shù) v 首先分析極小極大分析法效率，上述的極小極大分析法，實(shí)際是先生成一棵博弈樹，然后再計(jì)算其倒推值，至使極小極大分析法效率較低。于是在極小極大分析法的基礎(chǔ)上提出了 αβ剪枝技術(shù)?！ ?αβ剪枝技術(shù)的基本思想或算法是，邊生成博弈樹邊計(jì)算評(píng)估各節(jié)點(diǎn)的倒推值，并且根據(jù)評(píng)估出的倒推值范圍，及時(shí)停止擴(kuò)展那些已無(wú)必要再擴(kuò)展的子節(jié)點(diǎn)，即相當(dāng)于剪去了博弈樹上的一些分枝，從而節(jié)約了機(jī)器開(kāi)銷，提高了搜索效率。具體的剪枝方法如下： αβ剪枝技術(shù) v (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ú)任何影響 了 )。這一過(guò)程稱為 α剪枝。 (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ú)任何影響 了 )。這一過(guò)程稱為 β剪枝?！ ˇ力录糁夹g(shù) v 從算法中看到： (1)MAX節(jié)點(diǎn) (包括起始節(jié)點(diǎn) )的 α值永不減少； (2)MIN節(jié)點(diǎn) (包括起始節(jié)點(diǎn) )的 β值永不增加。v 在搜索期間， α和 β值的計(jì)算如下： (1)一個(gè) MAX節(jié)點(diǎn)的 α值等于其后繼節(jié)點(diǎn)當(dāng)前最大的最終倒推值?！?(2)一個(gè) MIN節(jié)點(diǎn)的 β值等于其后繼節(jié)點(diǎn)當(dāng)前最小的最終倒推值。 圖 3． 18一步棋第一階段部分搜索樹αβ剪枝技術(shù) v 畫出根節(jié)點(diǎn)、節(jié)點(diǎn) A及 5個(gè)兒子，計(jì)算并標(biāo)上這些節(jié)點(diǎn)的靜態(tài)估值， A的 5個(gè)兒子節(jié)點(diǎn)的靜態(tài)估值的最小值是 1，因此節(jié)點(diǎn) A的倒推值為 1，從而起始節(jié)點(diǎn)的倒推值的下界 α定為 1，當(dāng)然有可能比 1更小，因?yàn)樗衅渌膬鹤庸?jié)點(diǎn)?！ ‘嫵龉?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。由于 α值不比 β值小，故可以終止節(jié)點(diǎn) B的搜索?！ ?αβ剪枝技術(shù) v例： αβ剪枝技術(shù)的例子，如下圖所示。圖中所生成的搜索樹共有六層 (我們規(guī)定首先生成最左面的節(jié)點(diǎn)。 MAX節(jié)點(diǎn)用方塊表示， MIN節(jié)點(diǎn)用圓圈表示 )。圖中還給出了端節(jié)點(diǎn)的靜態(tài)估值。現(xiàn)在假設(shè)我們采用 αβ剪枝技術(shù)來(lái)引導(dǎo)深度優(yōu)先搜索。由 αβ剪枝技術(shù)生成的子樹在圖中用粗樹枝表示。發(fā)生修剪的那些節(jié)點(diǎn)用 “”表示?！ ≌f(shuō)明 αβ剪枝技術(shù)的例題 v 我們注意到原先 41個(gè)端節(jié)點(diǎn)只有 18個(gè)必須估值，可見(jiàn)說(shuō)明 αβ方法能夠有效地提高效率。 下面讓我們對(duì) αβ剪枝技術(shù)的搜索效率再作一些分析。要進(jìn)行 αβ修剪，必須至少使某一部分的搜索樹生長(zhǎng)到最大深度，因?yàn)?α和 β值必須以端節(jié)點(diǎn)的靜態(tài)估值為依據(jù)。因此采用 αβ剪枝技術(shù)通常都要使用某種深度優(yōu)先的搜索方法。而且在一次搜索期間修剪的枝數(shù)取決于早期的 α、 β值與最終倒推值之間的近似程度?！ ∑鹗脊?jié)點(diǎn)的最終倒推值等于某個(gè)端節(jié)點(diǎn)的靜態(tài)估值。如果在深度優(yōu)先搜索過(guò)程中第一次就遇到這個(gè)端節(jié)點(diǎn)，則修剪枝數(shù)最大。當(dāng)前修剪枝數(shù)最大時(shí)，需要生成和估計(jì)的端節(jié)點(diǎn)數(shù)就最少?！ ?演講完畢，謝謝觀
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1