人工智能-博弈樹(shù)的搜索45(專業(yè)版)
【正文】 MAX節(jié)點(diǎn) ?? MIN節(jié)點(diǎn) ?=? ??? ??? ?剪支 A B C D 4. ??搜索過(guò)程 ? ?剪支法 A B C D E F G H I J K L N O M 4. ??搜索過(guò)程 MAX節(jié)點(diǎn) MAX節(jié)點(diǎn) MIN節(jié)點(diǎn) 終端節(jié)點(diǎn) 3 5 6 5 2 1 6 4 MAX節(jié)點(diǎn) (5,?) 3 5 6 5 2 1 6 4 (6,?) (2,?) (?,5) (?,2) (5,?) MIN節(jié)點(diǎn) 終端節(jié)點(diǎn) ?剪支 ?剪支 A B C D E F G H I J K L N O M MAX節(jié)點(diǎn) 4. ??搜索過(guò)程 一字棋第一階段 ??剪支方法 4. ??搜索過(guò)程 4. ??搜索過(guò)程 ? 極大節(jié)點(diǎn)的下界為 ?。這種確定棋步的方法，稱為 極小極大搜索法 。 博弈 中國(guó)象棋 ? 一盤棋平均走 50步，總狀態(tài)數(shù)約為 10的161次方。 ? 1958約翰 ?麥卡錫提出博弈樹(shù)搜索算法 ? 1997年， IBM公司研制的“深藍(lán)”國(guó)際象棋 程序，采用博弈樹(shù)搜索算法，該程序戰(zhàn)勝了國(guó)際象棋世界冠軍卡斯帕羅夫。 博弈 ? 對(duì) MAX走步后的每一個(gè) MIN結(jié)點(diǎn)，只須證明 MAX有一步能走贏就可以，即 MAX只要考慮能走出一步棋使 MIN無(wú)法招架就成，因此含有 MIN符號(hào)的結(jié)點(diǎn)可看成或結(jié)點(diǎn)。 ? 正方（ MAX節(jié)點(diǎn)）從所有子節(jié)點(diǎn)中，選取具有最大評(píng)估值的節(jié)點(diǎn)。 總之 ， 該 MIN節(jié)點(diǎn)的評(píng)估值不會(huì)高過(guò) ?， 這個(gè) ?就稱為該 MIN節(jié)點(diǎn)的評(píng)估上限值 。 4. ??搜索過(guò)程 ? 不嚴(yán)格限制搜索的深度 。 對(duì)手 MIN的棋子用 (o)表示。 ? 對(duì)各個(gè)局面進(jìn)行評(píng)估 ? 評(píng)估的目的：對(duì)后面的狀態(tài)提前進(jìn)行考慮，并且以各種狀態(tài)的評(píng)估值為基礎(chǔ)作出最好的走棋選擇。 ? 零和，即對(duì)一方有利的棋，對(duì)另一方肯定是不利的，不存在對(duì)雙方均有利或無(wú)利的棋。 博弈 ? 設(shè)初始狀態(tài)為 (7， MIN)，建立問(wèn)題的狀態(tài)空間圖，圖中所有終結(jié)點(diǎn)均表示該選手必輸?shù)那闆r，取勝方的目標(biāo)是設(shè)法使棋局發(fā)展為結(jié)束在對(duì)方走步時(shí)的終結(jié)點(diǎn)上。例如，
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1