計(jì)算機(jī)科學(xué)中最有趣的事情之一就是編寫一個(gè)人機(jī)博弈的程序。有大量的例子，最出名的是編寫一個(gè)國(guó)際象棋的博弈機(jī)器。但不管是什么游戲，程序趨向于遵循一個(gè)被稱為Minimax算法，伴隨著各種各樣的子算法在一塊。本篇將簡(jiǎn)要介紹 minimax 算法，并通過實(shí)例分析幫助大家更好的理解。

一、概念

Minimax算法又名極小化極大算法，是一種找出失敗的最大可能性中的最小值的算法。Minimax算法常用于棋類等由兩方較量的游戲和程序，這類程序由兩個(gè)游戲者輪流，每次執(zhí)行一個(gè)步驟。我們眾所周知的五子棋、象棋等都屬于這類程序，所以說(shuō)Minimax算法是基于搜索的博弈算法的基礎(chǔ)。該算法是一種零總和算法，即一方要在可選的選項(xiàng)中選擇將其優(yōu)勢(shì)最大化的選擇，而另一方則選擇令對(duì)手優(yōu)勢(shì)最小化的方法。

（1）Minimax是一種悲觀算法，即假設(shè)對(duì)手每一步都會(huì)將我方引入從當(dāng)前看理論上價(jià)值最小的格局方向，即對(duì)手具有完美決策能力。因此我方的策略應(yīng)該是選擇那些對(duì)方所能達(dá)到的讓我方最差情況中最好的，也就是讓對(duì)方在完美決策下所對(duì)我造成的損失最小。

（2）Minimax不找理論最優(yōu)解，因?yàn)槔碚撟顑?yōu)解往往依賴于對(duì)手是否足夠愚蠢，Minimax中我方完全掌握主動(dòng)，如果對(duì)方每一步?jīng)Q策都是完美的，則我方可以達(dá)到預(yù)計(jì)的最小損失格局，如果對(duì)方?jīng)]有走出完美決策，則我方可能達(dá)到比預(yù)計(jì)的最悲觀情況更好的結(jié)局。總之我方就是要在最壞情況中選擇最好的。

二、實(shí)例分析：

題目：現(xiàn)在考慮這樣一個(gè)游戲：有三個(gè)盤子A、B和C，每個(gè)盤子分別放有三張紙幣。A放的是1、20、50；B放的是5、10、100；C放的是1、5、20。單位均為“元”。有甲、乙兩人，兩人均對(duì)三個(gè)盤子和上面放置的紙幣有可以任意查看。

游戲分三步：

（1）甲從三個(gè)盤子中選取一個(gè)。

（2）乙從甲選取的盤子中拿出兩張紙幣交給甲。

（3）甲從乙所給的兩張紙幣中選取一張，拿走。

其中甲的目標(biāo)是最后拿到的紙幣面值盡量大，乙的目標(biāo)是讓甲最后拿到的紙幣面值盡量小。

基本思路：一般解決博弈類問題的自然想法是將格局組織成一棵樹，樹的每一個(gè)節(jié)點(diǎn)表示一種格局，而父子關(guān)系表示由父格局經(jīng)過一步可以到達(dá)子格局。Minimax也不例外，它通過對(duì)以當(dāng)前格局為根的格局樹搜索來(lái)確定下一步的選擇。而一切格局樹搜索算法的核心都是對(duì)每個(gè)格局價(jià)值的評(píng)價(jià)。

解題：下圖是上述示例問題的格局樹：

注意，由于示例問題格局?jǐn)?shù)非常少，我們可以給出完整的格局樹。這種情況下我可以找到Minimax算法的全局最優(yōu)解。而真實(shí)情況中，格局樹非常龐大，即使是計(jì)算機(jī)也不可能給出完整的樹，因此我們往往只搜索一定深度，這時(shí)只能找到局部最優(yōu)解。

我們從甲的角度考慮。其中正方形節(jié)點(diǎn)表示輪到我方（甲），而三角形表示輪到對(duì)方（乙）。經(jīng)過三輪對(duì)弈后（我方-對(duì)方-我方），將進(jìn)入終局。黃色葉結(jié)點(diǎn)表示所有可能的結(jié)局。從甲方看，由于最終的收益可以通過紙幣的面值評(píng)價(jià)，我們自然可以用結(jié)局中甲方拿到的紙幣面值表示終格局的價(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)的最大值。最終完整賦值的格局樹如下：

總結(jié)一下Minimax算法的步驟：

（1）首先確定最大搜索深度D，D可能達(dá)到終局，也可能是一個(gè)中間格局。

（2）在最大深度為D的格局樹葉子節(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)最大值，min節(jié)點(diǎn)取子節(jié)點(diǎn)最小值。

（4）每次輪到我方時(shí)（此時(shí)必處在格局樹的某個(gè)max節(jié)點(diǎn)），選擇價(jià)值等于此max節(jié)點(diǎn)價(jià)值的那個(gè)子節(jié)點(diǎn)路徑。

在上面的例子中，根節(jié)點(diǎn)的價(jià)值為20，表示如果對(duì)方每一步都完美決策，則我方按照上述算法可最終拿到20元，這是我方在Minimax算法下最好的決策。格局轉(zhuǎn)換路徑如下圖紅色路徑所示：

強(qiáng)調(diào)幾點(diǎn)：

（1）真實(shí)問題一般無(wú)法構(gòu)造出完整的格局樹，所以需要確定一個(gè)最大深度D，每次最多從當(dāng)前格局向下計(jì)算D層。

（2）因?yàn)樯鲜鲈?，Minimax一般是尋找一個(gè)局部最優(yōu)解而不是全局最優(yōu)解，搜索深度越大越可能找到更好的解，但計(jì)算耗時(shí)會(huì)呈指數(shù)級(jí)膨脹。

（3）也是因?yàn)闊o(wú)法一次構(gòu)造出完整的格局樹，所以真實(shí)問題中Minimax一般是邊對(duì)弈邊計(jì)算局部格局樹，而不是只計(jì)算一次，但已計(jì)算的中間結(jié)果可以緩存。