Minimax算法及實例分析

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

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

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

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

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