人工智能-第四章-資料下載頁
2025-08-04 13:39本頁面
【正文】 ? 圖 井字棋 ? 3） 若 p不是可定勝負(fù)的格局 ， 則 e(p)= e+(p) e(p) ? 其中， e+(p)表示當(dāng)前棋局所有空格都放上甲的棋子后，甲構(gòu)成的行、列和對角線的個(gè)數(shù)。同理，e(p)表示當(dāng)前棋局所有空格都放上乙的棋子后，乙構(gòu)成的行、列和對角線的個(gè)數(shù)。對于圖 ，e(p)=64=2 ? 例： ? (1) (2) (1) ? … … ? … … 65=1 55=0 65=1 55=0 45=1 56=1 54=1 ? ??搜索過程 ? 在極大極小過程中 ， 把生成樹和棋局估值兩個(gè)過程完全分離 ， 使效率大大降低 ， 若同時(shí)進(jìn)行 ，再根據(jù)一定的條件判斷 ， 有可能盡早剪掉一些無用的分支 ， 則可能減少搜索工作量 ， 這是 ??搜索過程的基本思想 。 下面我們用井字棋說明??剪枝方法 。 ? 假設(shè)以深度優(yōu)先方法生成了部分搜索樹 ， 則可使用終止搜索規(guī)則 ??剪枝： ? 1． ?剪枝：若任何極小節(jié)點(diǎn)的 ?值小于或等于任何它的極大父節(jié)點(diǎn)的 ?值 ， 則可以終止該極小節(jié)點(diǎn)以下的搜索 ， 并設(shè)置這個(gè)極小節(jié)點(diǎn)的最終倒推值為 ?。 ? 2． ?剪枝：若任何極大節(jié)點(diǎn)的 ?值大于或等于它的極小父節(jié)點(diǎn)的 ?值 ， 則可以終止該極大節(jié)點(diǎn)以下的搜索 ， 并設(shè)置這個(gè)極大節(jié)點(diǎn)的最終倒推值為 ?。 ? ??過程：保存 ?和 ?值 ， 并且當(dāng)可能時(shí)便進(jìn)行剪枝的整個(gè)過程 ， 當(dāng)初始節(jié)點(diǎn)的全部后繼節(jié)點(diǎn)的最終倒推值都給出時(shí) ， 過程即結(jié)束 ， 而最好的優(yōu)先走步就是走向具有最高倒推值的那個(gè)后繼節(jié)點(diǎn) 。 ? 例： MAX ?=1 ? MIN (?= 1) (?=1) (? =1) 65=1 55=0 65=1 55=0 45=1 56=1 54=1 64=2 ? 例 : A ? ? B C D ? ? E F G H I J K ? ? L M N O P Q R S T U V W X Y 2 3 8 5 7 6 0 1 5 2 8 4 10 2
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1