人工智能-博弈樹的搜索-文庫吧
2025-02-09 00:32 本頁面
【正文】 ? 對 MAX走步后的每一個 MIN結點，只須證明 MAX有一步能走贏就可以，即 MAX只要考慮能走出一步棋使 MIN無法招架就成，因此含有 MIN符號的結點可看成或結點。 博弈 ? 對弈過程的搜索圖呈現(xiàn)出與或圖表示的形式。 ? 實現(xiàn)一種取勝的策略就是搜索一個解圖的問題，解圖就代表一種完整的博弈策略。 博弈 中國象棋 ? 一盤棋平均走 50步，總狀態(tài)數(shù)約為 10的161次方。 ? 假設 1毫微秒走一步，約需 10的 145次方年。 ? 結論：不可能窮舉。 ? 對各個局面進行評估 ? 評估的目的：對后面的狀態(tài)提前進行考慮，并且以各種狀態(tài)的評估值為基礎作出最好的走棋選擇。 ? 評估的方法：用評價函數(shù)對棋局進行評估。贏的評估值設為 +∞ ，輸?shù)脑u估值設為 ∞ ，平局的評估值設為 0。 ? 評估的標準：由于下棋的雙方是對立的，只能選擇其中一方為評估的標準方。 MAX節(jié)點和 MIN節(jié)點 ? 命名博弈的雙方，一方為“正方”，對每個狀態(tài)的評估都是對應于該方的輸贏的。例如，贏 2個，輸 1個等，都是指正方的。正方每走一步，都在選擇使自己贏得更多的節(jié)點，因此這類節(jié)點稱為“ MAX”節(jié)點； ? 另一方為“反方”，對每個狀態(tài)的評估都是對應于對手的輸贏的。例如，贏 2個，輸一個，其實是指自己輸 2個，贏 1個的。反方每走一步，都在選擇使對手輸?shù)酶嗟墓?jié)點，因此這類節(jié)點稱為“ MIN”節(jié)點。 ? 由于正方和反方是交替走步的，因此MAX節(jié)點和 MIN節(jié)點會交替出現(xiàn)。 ? 正方（ MAX節(jié)點）從所有子節(jié)點中，選取具有最大評估值的節(jié)點。 ? 反方（ MIN節(jié)點）從其所有子節(jié)點中，選取具有最小評估值的節(jié)點。 ? 反復進行這種選取，就可以得到雙方各個節(jié)點的評估值。這種確定棋步的方法，稱為 極小極大搜索法 。 5 3 3 3 3 0 2 2 3 0 2 3 5 4 1 3 0 6 8 9 3 MIN MAX 0 MAX MIN 0 1 5 3 3 3 3 0 2 2 3 0 2 3 5 4 1 3 0 6 8 9 3 0 3 3 3 3 2 1 3 6 3 0 3 1 6 0 1 MAX MIN MAX MIN
醫(yī)療健康相關推薦
鄂ICP備17016276號-1