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