人工智能第二章與或圖搜索問題68(文件)
【正文】 =2 h(n7)=0 h(n8)=0 設： K連接符 的耗散值為 K 目標 目標 初始節(jié)點 n0 n1 n2 n3 n4 n5 n6 n7 n8 10 目標 目標 初始節(jié)點 n0 n1 n2 n3 n4 n5 n6 n7 n8 初始節(jié)點 n0 n1(2) n4(1) n5(1) 紅色： 4 黃色： 3 11 初始節(jié)點 n0 n4(1) n5(1) 紅色： 4 黃色： 6 n1 n2(4) n3(4) 5 目標 目標 初始節(jié)點 n0 n1 n2 n3 n4 n5 n6 n7 n8 12 紅色： 5 黃色： 6 初始節(jié)點 n0 n4(1) n5(1) n1 n2(4) n3(4) 5 n6(2) n7(0) n8(0) 2 目標 目標 初始節(jié)點 n0 n1 n2 n3 n4 n5 n6 n7 n8 13 紅色： 5 黃色： 6 2 1 初始節(jié)點 n0 n4(1) n5(1) n1 n2(4) n3(4) 5 n6(2) n7(0) n8(0) 目標 目標 初始節(jié)點 n0 n1 n2 n3 n4 n5 n6 n7 n8 14 博弈 是一類具有競爭性的智能活動 雙人博弈 ：即兩位選手對壘 ， 輪流依次走步 ，其中任何一方都完全知道對方過去已經(jīng)走過的棋步和今后可能的走步 ， 其結(jié)果是一方贏 (而另一方則輸 )， 或雙方和局 博弈樹搜索 15 博弈的例子 ： ? 一字棋 ? 跳棋 ? 中國象棋 ? 圍棋 ? 五子棋 16 博弈樹搜索 ? 博弈問題 ? 雙人對弈 ， 對壘的雙方輪流走步； ? 信息完備 ， 對壘雙方所得到的信息是一樣的 ，不存在一方能看到 ， 而另外一方看不到的情況； ? 零和 ， 即對一方有利的棋 ， 對另一方肯定是不利的 ， 不存在對雙方均有利或均無利的棋 ， 對弈的結(jié)果是一方贏 ， 而另一方輸 ， 或者雙方和棋 。 博弈問題（求解過程）的表示 ： 20 假設博弈雙方為： MAX和 MIN 在博弈過程中 ， 規(guī)則是雙方輪流走步 。 MAX 好招 23 總之： 從 MAX方來說，與節(jié)點、或節(jié)點交替出現(xiàn)；反之，從 MIN方的角度來看，情況正好相反。 26 例 Grundy博弈：分配物品的問題 如果有一堆數(shù)目為 N的錢幣 ， 由兩位選手輪流進行分配 ， 要求每個選手每次把其中某一堆分成數(shù)目 不等 的兩小堆 ， 直至有一選手不能將錢幣分成不等的兩堆為止 ， 則判定這位選手為輸家 。 31 中國象棋 ? 一盤棋平均走 50步 ， 總狀態(tài)數(shù)約為 10的 161次方 。 33 對于復雜的博弈問題，要規(guī)定搜索深度與時間，以便于博弈搜索能順利進行。 值越大對 MAX越有利 ， 反之越不利； 極大極小過程的基本思路 ： 36 ② 對于給定的格局 ， MAX給出可能的走法 ， 然后MIN對應地給出相應的走法 ， 這樣重復若干次 ， 得到一組端節(jié)點 （ 必須由 MIN走后得到的 ， 等待MAX下的棋局 ） 。 38 例 ： 向前看一步的兩層博弈樹 39 定義靜態(tài)函數(shù) e(P)的一般原則 ： 0 MA X MI N( ) 0 0 MA X MI NeP????? ?? ??占優(yōu)， 不利勢均力敵不利， 占優(yōu)40 OPEN：存放待擴展的節(jié)點 ， 此時為隊列 ， 即以寬度優(yōu)先的策略擴展節(jié)點 。 此時 ，若搜索深度 d{ ni }小于預先設定的深度 k， 則將{ ni }放入 OPEN表的末端 ， 轉(zhuǎn) 2；否則 ， ni 達到深度 k， 計算 e ( ni )， 并轉(zhuǎn) 2； 44
職業(yè)教育相關推薦
鄂ICP備17016276號-1