人工智能之與或圖搜索問(wèn)題-在線瀏覽
2025-03-23 13:05本頁(yè)面
【正文】 對(duì)好的走法來(lái)走 ，即在有限的搜索深度范圍內(nèi)進(jìn)行求解 。 35 ① 對(duì)于每一格局 （ 棋局 ） 給出 （ 定義或者倒推 ）一個(gè)靜態(tài)估價(jià)函數(shù)值 。 這一過(guò)程相當(dāng)于節(jié)點(diǎn)擴(kuò)展； 注 ：博弈樹(shù)深度或?qū)訑?shù)一定是偶數(shù) 。 在 MIN下的格局中取估值的最小值 ，在 MAX下格局中取估值的最大值； ④ 取估值最大的格局作為 MAX要走的一招棋 。 CLOSED：存放已擴(kuò)展的節(jié)點(diǎn) ， 此時(shí)為堆棧 ，即后擴(kuò)展的節(jié)點(diǎn)先計(jì)算 。 42 將初始節(jié)點(diǎn) S 放入 OPEN 表中 ， 開(kāi)始時(shí)搜索樹(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 表的前端； 極大極小搜索過(guò)程 為 ： 43 若 n 可直接判定為贏 、 輸 、 或平局 ， 則令對(duì)應(yīng)的 e(n)=∞， ∞或 0， 并轉(zhuǎn) 2；否則擴(kuò)展 n， 產(chǎn)生 n 的后繼節(jié)點(diǎn)集 { ni }， 將 { ni }放入搜索樹(shù) T 中 。 48 第一階段 為 4步 ， 用寬度優(yōu)先算法生成規(guī)定深度 k 的全部博弈樹(shù) ， 然后對(duì)其所有端節(jié)點(diǎn)計(jì)算 e(P)； 第二階段 為 8步 ， 是自下而上逐級(jí)求節(jié)點(diǎn)的倒推估價(jià)值 ， 直至求出初始節(jié)點(diǎn)的 e(S) 為止 ，再由 e(S) 選得相對(duì)較好的走法 ， 過(guò)程結(jié)束 。 50 極大極小過(guò)程 51 例 ： 一字棋的極大極小搜索過(guò)程 約定 ： ? 每一方只向前看一步 （擴(kuò)展出二層） ? 記 MAX的棋子為“ ”， MIN的棋子為“ O” ? 規(guī)定 MAX先手 52 ① 若格局 P 對(duì)任何一方都不能獲勝 ， 則 e(P) =（ 所有空格上都放上 MAX的棋子后 ， MAX的三個(gè)棋子所組成的行 、 列及對(duì)角線的總數(shù) ） （ 所有空格上都放上 MIN的棋子后 ， MIN的三個(gè)棋子所組成的行 、 列及對(duì)角線的總數(shù) ） 靜態(tài)估計(jì)函數(shù) e(P)定義為 ： 53 ② 若 P 是 MAX獲勝 ， 則 e(P)=+∞ ③ 若 P 是 MIN獲勝 ， 則 e(P)=－ ∞ 54 例： 計(jì)算下列棋局的靜態(tài)估價(jià)函數(shù)值 e(P)=64=2 棋局 O O O O O O O O O O 行 =2 列 =2 對(duì)角 =2 行 =2 列 =2 對(duì)角 =0 55 利用棋盤的對(duì)稱性，有些棋局是等價(jià)的 O O O O 56 O O O O O O O O O O O O 1 0 1 0 1 1 0 1 0 2 1 2 1 2 1 1 MAX MIN MAX MAX的走步 57 第二步 O X X O X O X X O X X O X X X O O X X O O X X O X O X O X O X O X O 2 1 3 2 1 1 O O X X O X X O O X X O O X X O O X X O 1 0 2 0 1 O O X X 1 0 O O X X O O X X O O X X O X O X O X X O O X X O 2 2 3 1 2 2 1 O O X X O X O X O O X X 1 1 0 0 1 58 第三步 O O X X X O O X X O O X X X O O X X X O O X
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1