人工智能-博弈樹的搜索-在線瀏覽
2025-03-23 00:32本頁面
【正文】 的雙方是對立的，只能選擇其中一方為評估的標準方。例如，贏 2個，輸 1個等，都是指正方的。例如，贏 2個，輸一個，其實是指自己輸 2個，贏 1個的。 ? 由于正方和反方是交替走步的，因此MAX節(jié)點和 MIN節(jié)點會交替出現(xiàn)。 ? 反方（ MIN節(jié)點）從其所有子節(jié)點中，選取具有最小評估值的節(jié)點。這種確定棋步的方法，稱為 極小極大搜索法 。 設(shè)程序方 MAX的棋子用 ( )表示， MAX先走。 例如： MIN取勝 估計函數(shù) f(p)=(所有空格都放上 MAX的棋子之后， MAX的三子成線數(shù) )－ (所有空格都放上 MIN的棋子之后， MIN的三子成線的總數(shù) ) 若 P是 MAX獲勝的格局，則 f(p)=+∞ ； 若 P是 MIN獲勝的格局，則 f(p)＝ ∞ 。 這時存在著三個空格 A， B， C， 用博弈樹搜索算法判斷應(yīng)該把棋子放到哪一格內(nèi) 。 ? ??剪支法的 引入 在極小極大法中 ， 必須求出所有終端節(jié)點的評估值 ， 當預(yù)先考慮的棋步比較多時 ， 計算量會大大增加 。 4. ??搜索過程 作為正方出現(xiàn)的 MAX節(jié)點 ， 假設(shè)它的 MIN子節(jié)點有 N個 ， 那么當它的第一個 MIN子節(jié)點的評估值為 ?時 ， 則對于其它的子節(jié)點 ， 如果有高過 ?的 ，就取那最高的值作為該 MAX節(jié)點的評估值；如果沒有 ， 則該 MAX節(jié)點的評估值為 ?。 4. ??搜索過程 ? MAX節(jié)點的評估下限值 ? ? MIN節(jié)點的評估上限值 ? 作為反方出現(xiàn)的 MIN節(jié)點 ， 假設(shè)它的 MAX子節(jié)點有 N個 ， 那么當它的第一個 MAX子節(jié)點的評估值為 ?時 ， 則對于其它子節(jié)點 ， 如果有低于 ?的 ，就取那個低于 ?的值作為該 MIN節(jié)點的評估值；如果沒有 ， 則該 MIN節(jié)點的評估值取 ?。 4. ??搜索過程 ? ?剪支法 MAX節(jié)點 ?? MIN節(jié)點 ?=? ??? ??? ?剪支 A B C D 4. ??搜索過程 設(shè) MAX節(jié)點的下限為 ?，則其 所有的 MIN子節(jié)點中，其評估值的 ?上限小于等于 ?的節(jié)點，其以下部分的搜索都可以停止了，即對這部分節(jié)點進行了 ?剪支。 MAX節(jié)點 ?? MIN節(jié)點 ?=? ??
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1