Minimax算法及實(shí)例分析

1、Minimax 算法及實(shí)例分析發(fā)表于2015/5/11 15:20:322419 人閱讀分類： AI 算法計(jì)算機(jī)科學(xué)中最有趣的事情之一就是編寫一個(gè)人機(jī)博弈的程序。有大量的例子，最出名的是編寫一個(gè)國(guó)際象棋的博弈機(jī)器。但不管是什么游戲，程序趨向于遵循一個(gè)被稱為Minimax 算法，伴隨著各種各樣的子算法在一塊。Minimax 算法又名極小化極大算法，是一種找出失敗的最大可能性中的最小值的算法。Minimax 算法常用于棋類等由兩方較量的游戲和程序，這類程序由兩個(gè)游戲者輪流，每次執(zhí)行一個(gè)步驟。我們眾所周知的五子棋、象棋等都屬于這類程序，所以說(shuō)Minimax 算法是基于搜索的博弈算法的基礎(chǔ)。該算法是一

2、種零總和算法，即一方要在可選的選項(xiàng)中選擇將其優(yōu)勢(shì)最大化的選擇，而另一方則選擇令對(duì)手優(yōu)勢(shì)最小化的方法。1. Minimax 是一種悲觀算法，即假設(shè)對(duì)手每一步都會(huì)將我方引入從當(dāng)前看理論上價(jià)值最小的我方最差情況中最好的，也就是讓對(duì)方在完美決策下所對(duì)我造成的損失最小。1. Minimax 不找理論最優(yōu)解，因?yàn)槔碚撟顑?yōu)解往往依賴于對(duì)手是否足夠愚蠢，Minimax 中我實(shí)例分析：甲從三個(gè)盤子中選取一個(gè)。乙從甲選取的盤子中拿出兩張紙幣交給甲?，F(xiàn)在考慮這樣一個(gè)游戲：有三個(gè)盤子A、B 和CA12050；B5、10、100；C1、520甲從三個(gè)盤子中選取一個(gè)。乙從甲選取的盤子中拿出兩張紙幣交給甲。3. 甲從乙所給

3、的兩張紙幣中選取一張，拿走。3. 甲從乙所給的兩張紙幣中選取一張，拿走。其中甲的目標(biāo)是最后拿到的紙幣面值盡量大，乙的目標(biāo)是讓甲最后拿到的紙幣面值盡量小?；舅悸芬话憬鉀Q博弈類問(wèn)題的自然想法是將格局組織成一棵樹(shù)，樹(shù)的每一個(gè)節(jié)點(diǎn)表示一種格局，而父子關(guān)系表示由父格局經(jīng)過(guò)一步可以到達(dá)子格局。Minimax 也不例外，它通過(guò)對(duì)以當(dāng)前格局為根的格局樹(shù)搜索來(lái)確定下一步的選擇。而一切格局樹(shù)搜索算法的核心都是對(duì)每個(gè)格局價(jià)值的評(píng)價(jià)。解題下圖是上述示例問(wèn)題的格局樹(shù)：注意，由于示例問(wèn)題格局?jǐn)?shù)非常少，我們可以給出完整的格局樹(shù)。這種情況下我可 以找到Minimax可能給出完整的樹(shù)，因此我們往往只搜索一定深度，這時(shí)只能找到

4、局部最優(yōu)解。我們從甲的角度考慮。其中正方形節(jié)點(diǎn)表示輪到我方（甲），而三角形表示輪到對(duì) 方（乙）。經(jīng)過(guò)三輪對(duì)弈后（），將進(jìn)入終局。黃色葉結(jié)點(diǎn)表示所有可能方拿到的紙幣面值表示終格局的價(jià)值。下面考慮倒數(shù)第二層節(jié)點(diǎn)，在這些節(jié)點(diǎn)上，輪到我方選擇，所以我們應(yīng)該引入可選擇的最大價(jià)值格局，因此每個(gè)節(jié)點(diǎn)的價(jià)值為其子節(jié)點(diǎn)的最大值：這些輪到我方的節(jié)點(diǎn)叫做max 節(jié)點(diǎn)，max 節(jié)點(diǎn)的值是其子節(jié)點(diǎn)最大值。倒數(shù)第三層輪到對(duì)方選擇，假設(shè)對(duì)方會(huì)盡力將局勢(shì)引入讓我方價(jià)值最小的格局，此這些節(jié)點(diǎn)的價(jià)值取決于子節(jié)點(diǎn)的最小值。這些輪到對(duì)方的節(jié)點(diǎn)叫做min節(jié)點(diǎn)。最后，根節(jié)點(diǎn)是max 節(jié)點(diǎn)，因此價(jià)值取決于葉子節(jié)點(diǎn)的最大值。最終完整賦值的格

5、局樹(shù)如下：1.首先確定最大搜索深度D，1.首先確定最大搜索深度D，D可能達(dá)到終局，也可能是一個(gè)中間格局。在上面的例子中，根節(jié)點(diǎn)的價(jià)值為 20在上面的例子中，根節(jié)點(diǎn)的價(jià)值為 20，表示如果對(duì)方每一步都完美決策，則我方按照上述算法可最終拿到 20 元，這是我方在Minimax 算法下最好的決策。格局轉(zhuǎn)換路徑如下圖紅色路徑所示：強(qiáng)調(diào)幾點(diǎn)：2.在最大深度為D 的格局樹(shù)葉子節(jié)點(diǎn)上，使用預(yù)定義的價(jià)值評(píng)價(jià)函數(shù)對(duì)葉子節(jié)點(diǎn)價(jià)值進(jìn)行評(píng)價(jià)。3.自底向上為非葉子節(jié)點(diǎn)賦值。其中max 節(jié)點(diǎn)取子節(jié)點(diǎn)最小值。4.每次輪到我方時(shí)（此時(shí)必處在格局樹(shù)的某個(gè)max 節(jié)點(diǎn)），選擇價(jià)值等于此max 節(jié)點(diǎn)價(jià)值的那個(gè)子節(jié)點(diǎn)路徑。真實(shí)問(wèn)題一般無(wú)法構(gòu)造出完整的格局樹(shù)，所以需要確定一個(gè)最大深度真實(shí)問(wèn)題一般無(wú)