人工智能之與或圖搜索問題(編輯修改稿)
2025-03-09 13:05 本頁面
【文章內(nèi)容簡(jiǎn)介】 31 中國象棋 ? 一盤棋平均走 50步 ， 總狀態(tài)數(shù)約為 10的 161次方 。 ? 假設(shè) 1毫微秒走一步 ， 約需 10的 145次方年 。 ? 結(jié)論：不可能窮舉 。 32 在人工智能中可以采用搜索方法來求解博弈問題，下面就來討論博弈中兩中最基本的搜索方法。 33 對(duì)于復(fù)雜的博弈問題，要規(guī)定搜索深度與時(shí)間，以便于博弈搜索能順利進(jìn)行。 假設(shè)由 MAX來選擇走一步棋，問題是： MAX如何來選擇一步好棋 ？ 極大極小過程 34 極大極小過程 ? 極大極小過程是考慮雙方對(duì)弈若干步之后 ，從可能的走法中選一步相對(duì)好的走法來走 ，即在有限的搜索深度范圍內(nèi)進(jìn)行求解 。 ? 需要定義一個(gè)靜態(tài)估價(jià)函數(shù) e,以便對(duì)棋局的態(tài)勢(shì)做出評(píng)估 。 35 ① 對(duì)于每一格局 （ 棋局 ） 給出 （ 定義或者倒推 ）一個(gè)靜態(tài)估價(jià)函數(shù)值 。 值越大對(duì) MAX越有利 ， 反之越不利； 極大極小過程的基本思路 ： 36 ② 對(duì)于給定的格局 ， MAX給出可能的走法 ， 然后MIN對(duì)應(yīng)地給出相應(yīng)的走法 ， 這樣重復(fù)若干次 ， 得到一組端節(jié)點(diǎn) （ 必須由 MIN走后得到的 ， 等待MAX下的棋局 ） 。 這一過程相當(dāng)于節(jié)點(diǎn)擴(kuò)展； 注 ：博弈樹深度或?qū)訑?shù)一定是偶數(shù) 。 37 ③ 對(duì)于每一個(gè)端節(jié)點(diǎn) ， 計(jì)算出它們的靜態(tài)估價(jià)函數(shù) ， 然后自下而上地逐層計(jì)算倒推值 ， 直到 MAX開始的格局 。 在 MIN下的格局中取估值的最小值 ，在 MAX下格局中取估值的最大值； ④ 取估值最大的格局作為 MAX要走的一招棋 。 38 例 ： 向前看一步的兩層博弈樹 39 定義靜態(tài)函數(shù) e(P)的一般原則 ： 0 MA X MI N( ) 0 0 MA X MI NeP????? ?? ??占優(yōu)， 不利勢(shì)均力敵不利， 占優(yōu)40 OPEN：存放待擴(kuò)展的節(jié)點(diǎn) ， 此時(shí)為隊(duì)列 ， 即以寬度優(yōu)先的策略擴(kuò)展節(jié)點(diǎn) 。 CLOSED：存放已擴(kuò)展的節(jié)點(diǎn) ， 此時(shí)為堆棧 ，即后擴(kuò)展的節(jié)點(diǎn)先計(jì)算 。 符號(hào) ： 41 ?極大極小過程的基本思想： (1)當(dāng)輪到 MIN走步的節(jié)點(diǎn)時(shí) ， MAX應(yīng)考慮最壞的情況 （ 即 f(p)取極小值 ） ； (2)當(dāng)輪到 MAX走步的節(jié)點(diǎn)時(shí) ， MAX應(yīng)考慮最好的情況 （ 即 f(p)取極大值 ） ； (3)評(píng)價(jià)往回倒推時(shí) ， 相應(yīng)于兩位棋手的對(duì)抗策略 ， 交替使用 （ 1） 和 （ 2） 兩種方法傳遞倒推值 。 42 將初始節(jié)點(diǎn) S 放入 OPEN 表中 ， 開始時(shí)搜索樹 T 由初始節(jié)點(diǎn) S 構(gòu)成； 若 OPEN 表為空 （ 節(jié)點(diǎn)擴(kuò)展結(jié)束 ） ， 則轉(zhuǎn) 5； 將 O P E N 表中第一個(gè)節(jié)點(diǎn) n 移出放 入CLOSED 表的前端； 極大極小搜索過程 為 ： 43 若 n 可直接判定為贏 、 輸 、 或平局 ， 則令對(duì)應(yīng)的 e(n)=∞， ∞或 0， 并轉(zhuǎn) 2；否則擴(kuò)展 n， 產(chǎn)生 n 的后繼節(jié)點(diǎn)集 { ni }， 將 { ni }放入搜索樹 T 中 。 此時(shí) ，若搜索深度 d{ ni }小于預(yù)先設(shè)定的深度 k， 則將{ ni }放入 OPEN表的末端 ， 轉(zhuǎn) 2；否則 ， ni 達(dá)到深度 k， 計(jì)算 e ( ni )， 并轉(zhuǎn) 2； 44 若 CLOSED表為空 ， 則轉(zhuǎn) 8；否則取出CLOSED表中的第一個(gè)節(jié)點(diǎn) ， 記為 np； Open為空，即已經(jīng)擴(kuò)展完節(jié)點(diǎn) 步 2 45 若 np 屬于 MAX層 ， 且對(duì)于它的屬于 MIN層的子節(jié)點(diǎn) nci 的 e ( nci )有值 ， 則： e ( np ) =max { nci } 46 （ 續(xù) ） 若 np 屬于 MIN層 ， 且對(duì)于它的屬于 MAX層的子節(jié)點(diǎn) nci 的 e ( nci )有值 ， 則： e ( np )=min{ nci } 47 轉(zhuǎn) 5；
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1