人工智能-博弈樹(shù)的搜索-文庫(kù)吧在線文庫(kù)
【正文】 ○ ?? ● ○ ● ?? ○ ● ?? ○ ● ?? ○ ● ?? ○ 博弈樹(shù)搜索 ? 20世紀(jì) 60年代，研制出的西洋跳棋和國(guó)際象棋的博弈程序達(dá)到了大師級(jí)的水平。 正方和反方是交替走步的 ， 因此 MAX節(jié)點(diǎn)和 MIN節(jié)點(diǎn)會(huì)交替出現(xiàn) 。 博弈 ? 對(duì)弈過(guò)程的搜索圖呈現(xiàn)出與或圖表示的形式。 ? 評(píng)估的標(biāo)準(zhǔn)：由于下棋的雙方是對(duì)立的，只能選擇其中一方為評(píng)估的標(biāo)準(zhǔn)方。 ? 反方（ MIN節(jié)點(diǎn)）從其所有子節(jié)點(diǎn)中，選取具有最小評(píng)估值的節(jié)點(diǎn)。 這時(shí)存在著三個(gè)空格 A， B， C， 用博弈樹(shù)搜索算法判斷應(yīng)該把棋子放到哪一格內(nèi) 。 4. ??搜索過(guò)程 ? ?剪支法 MAX節(jié)點(diǎn) ?? MIN節(jié)點(diǎn) ?=? ??? ??? ?剪支 A B C D 4. ??搜索過(guò)程 設(shè) MAX節(jié)點(diǎn)的下限為 ?，則其 所有的 MIN子節(jié)點(diǎn)中，其評(píng)估值的 ?上限小于等于 ?的節(jié)點(diǎn)，其以下部分的搜索都可以停止了，即對(duì)這部分節(jié)點(diǎn)進(jìn)行了 ?剪支。 4. ??搜索過(guò)程 ? 對(duì)某些博弈的開(kāi)局階段和殘局階段，往往總結(jié)了一些固定的對(duì)弈模式，因此可以利用這些知識(shí)編好走步表，以便在開(kāi)局和結(jié)局時(shí)使用查表法。 ? 剪支的條件： ? 后輩節(jié)點(diǎn)的 ?值 ≤祖先節(jié)點(diǎn)的 ?值時(shí)， ?剪支 ? 后輩節(jié)點(diǎn)的 ? 值 ≥祖先節(jié)點(diǎn)的 ?值時(shí)， ?剪支 ? 簡(jiǎn)記為： ? 極小 ≤極大， ?剪支 ? 極大 ≥極小， ?剪支 4. ??搜索過(guò)程 8 6 3 1 4 5 3 3 5 0 3 3 0 2 2 3 0 2 3 0 9 3 0 0 3 0 3 3 0 5 4 1 1 3 1 6 6 1 a b c d e f g h i j k m n MAX MIN MAX MIN 改進(jìn)方法 ? 使用 ??剪支技術(shù) ， 當(dāng)不滿足剪支條件(即 ???)時(shí)或 ?值比 ?值大不了多少或極相近時(shí) ， 這時(shí)也可以進(jìn)行剪支 ， 以便有條件把搜索集中到會(huì)帶來(lái)更大效果的其他路徑上 ， 這就是中止對(duì)效益不大的一些子樹(shù)的搜索 ， 以提高搜索效率 。 4. ??搜索過(guò)程 作為正方出現(xiàn)
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1