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