上節(jié)提到強(qiáng)化學(xué)習(xí)算法解決的井字棋游戲并不適合用Minimax算法解決惹盼，理由是Minimax假設(shè)游戲雙方都不會(huì)犯錯(cuò)妄辩，這種情況比較特殊惑灵。
1.Minimax算法
別稱(chēng)：Minmax算法（MM）算法，極小化極大算法眼耀，為了找出失敗的最大可能性中的最小值的算法英支。
常用于棋類(lèi)等由兩方較量的游戲和程序。是一個(gè)零總和算法哮伟，即乙方要在可選的選項(xiàng)中選擇將其優(yōu)勢(shì)最大化的選擇性干花，另一方選擇令對(duì)手又是最小化的方法，而開(kāi)始總和為0楞黄。很多棋類(lèi)游戲可以采取此算法池凄，例如井字棋（tic-tac-toe）。
在對(duì)弈過(guò)程中鬼廓，為了實(shí)現(xiàn)自己獲勝概率最大化肿仑，在盡可能多的預(yù)測(cè)對(duì)手后面行動(dòng)的情況下走出使自己接下來(lái)贏面估價(jià)最大的行動(dòng)。
先手與后手的目的一樣碎税，行動(dòng)指南也都是以最大化自己估價(jià)而最小化對(duì)手估價(jià)尤慰。
在這里以正方形代表先手（選擇估價(jià)最大的局面），圓形代表后手（選擇估價(jià)最小的局面）雷蹂。只有葉子節(jié)點(diǎn)才可以直接計(jì)算估價(jià)值伟端。則我們假設(shè)棋局的博弈樹(shù)如下（預(yù)測(cè)后面的四步），每步策略匪煌？
該游戲中所有策略的集合可以由一棵巨大的根樹(shù)來(lái)表示荔泳，樹(shù)中的每個(gè)頂點(diǎn)都對(duì)應(yīng)于棋盤(pán)的一個(gè)布局（configuration）蕉饼。所謂“棋盤(pán)的一個(gè)布局”，是在游戲過(guò)程中通過(guò)標(biāo)記棋盤(pán)上的小方格得到的玛歌。其中數(shù)字表示達(dá)到此種布局先手可以獲得的分?jǐn)?shù)昧港。
以井字棋為例，令葉子頂點(diǎn)對(duì)應(yīng)于游戲的最終狀態(tài)支子，將其標(biāo)記為1或0创肥，分別對(duì)應(yīng)于游戲者A獲勝或失敗值朋；對(duì)于游戲者B而言叹侄，數(shù)值的含義是相反的。
對(duì)于下圖(a)的局面而言昨登，A只有一個(gè)選擇趾代，且之后將獲勝，因此可以將樹(shù)中對(duì)應(yīng)于下圖(a)的頂點(diǎn)也標(biāo)記為1——表示A將獲勝丰辣。
之后簡(jiǎn)單分析一下下圖(b)就會(huì)發(fā)現(xiàn)無(wú)論B怎樣選擇撒强，最終他都將失利，而由A獲得勝利笙什，因此可以將樹(shù)中對(duì)應(yīng)于下圖(b)的頂點(diǎn)也標(biāo)記為1——表示此時(shí)無(wú)論B如何行棋飘哨，A都一定獲勝。
對(duì)于下圖(c)而言琐凭，B怎樣選擇芽隆，他都可以獲勝，因此可以將樹(shù)中對(duì)應(yīng)于下圖(c)的頂點(diǎn)也標(biāo)記為0——表示B一定可以獲勝统屈。但是對(duì)于下圖(d)胚吁，如果游戲者B做出了正確選擇（左下角），那么他將獲勝愁憔，而如果他做出了錯(cuò)誤選擇（右上角）囤采，那么他將失利。為了分析博弈樹(shù)惩淳，將假定任何一名游戲者都不會(huì)犯錯(cuò)誤蕉毯。在這種假定下，可以將樹(shù)中對(duì)應(yīng)于下圖(d)的頂點(diǎn)也標(biāo)記為0——表示存在著游戲者B的獲勝策略思犁。
如果將分別以下圖(b)~(d)為根的子樹(shù)展開(kāi)的話（見(jiàn)下圖(e)）代虾，會(huì)發(fā)現(xiàn)對(duì)應(yīng)于輪到B行棋的奇數(shù)層頂點(diǎn)根據(jù)其孩子頂點(diǎn)的標(biāo)號(hào)對(duì)自己進(jìn)行標(biāo)號(hào)的行為和邏輯運(yùn)算“與”一致，因此可以用∧表示激蹲。?
回到此問(wèn)題棉磨，分?jǐn)?shù)表示當(dāng)前布局是使先手可以獲得的最好結(jié)果。
首先学辱，先手應(yīng)該計(jì)算后手在第四步的時(shí)候應(yīng)該會(huì)選擇價(jià)值為多大的局面（即從所有子節(jié)點(diǎn)中選擇最小的）乘瓤，如下圖（紅色字體）：所有子節(jié)點(diǎn)代表了第五步所有可能的情況环形，為了使先手得分最低，后手會(huì)在第四步從自己所有走步可能中選擇使第五步估價(jià)最差的一步衙傀；
然后先手在計(jì)算自己在第三步時(shí)應(yīng)該如何選擇（即從所有后手子節(jié)點(diǎn)中選擇最大的）抬吟，如下圖（紅色字體）：先手考慮到后手第四步的選擇，則會(huì)在第三步選擇使自己得分最高的情況统抬；
然后先手在計(jì)算后手在第二步時(shí)應(yīng)該如何選擇（即從所有子節(jié)點(diǎn)中選擇最小的）火本，如下圖（紅色字體）：
最后先手就可以決定下一步應(yīng)該怎么走了（即從所有子節(jié)點(diǎn)中選擇最大的），如下圖（紅色字體）：
所以聪建，如果先后手都進(jìn)行最有決策的話钙畔，棋局的走向則下圖所示（紅線）：
(當(dāng)然，如果后手不是進(jìn)行最優(yōu)決策的話金麸，棋局的走向就不一定是這樣的了擎析，先手也可以嘗試走有風(fēng)險(xiǎn)，但是收益更高的局面挥下，這就不在我們的討論范圍之內(nèi)了揍魂，參考強(qiáng)化學(xué)習(xí)部分)
??可以看到，如果按照MinMax算法來(lái)進(jìn)行決策的話见秽，需要的計(jì)算量是隨著向后看的步數(shù)的增加而呈指數(shù)級(jí)增長(zhǎng)的。但是讨盒，這些狀態(tài)中其實(shí)是包含很多不必要的狀態(tài)的解取，所以我們可以進(jìn)行剪枝。
2 
剪枝
名稱(chēng)來(lái)自于計(jì)算過(guò)程傳遞的兩個(gè)邊界返顺，根據(jù)邊界限制不必要的可能的解決方案集禀苦。其中，表示目前所有可能解中最大下界遂鹊，
是目前所有可能解中最小上界振乏。
因此，如果搜索樹(shù)上的一個(gè)節(jié)點(diǎn)被考慮作為最優(yōu)解路上的節(jié)點(diǎn)（或者說(shuō)是這個(gè)節(jié)點(diǎn)被認(rèn)為是有必要進(jìn)行搜索的節(jié)點(diǎn)）秉扑，那么它一定滿足以下條件（N是當(dāng)前節(jié)點(diǎn)的估價(jià)值）：
在求解過(guò)程中會(huì)逐漸逼近
慧邮。如果對(duì)于某一個(gè)節(jié)點(diǎn)，出現(xiàn)了
的情況舟陆，那么此節(jié)點(diǎn)必不會(huì)產(chǎn)生最優(yōu)解误澳，也就不必繼續(xù)擴(kuò)展（或生成子節(jié)點(diǎn)），從而完成剪枝秦躯。
以上圖的情況進(jìn)行說(shuō)明：
（1）從根節(jié)點(diǎn)開(kāi)始向下搜索忆谓，到第四步，紅色序號(hào)代表順序踱承。
當(dāng)搜索到了第一個(gè)葉子節(jié)點(diǎn)的時(shí)候倡缠，發(fā)現(xiàn)它的權(quán)值是3哨免，且父節(jié)點(diǎn)是Min節(jié)點(diǎn)，又因?yàn)楦腹?jié)點(diǎn)的最小上界β > 3昙沦，所以更新父節(jié)點(diǎn)琢唾，令β = 3 。（因?yàn)楦腹?jié)點(diǎn)要取最小值桅滋，這個(gè)最小值不會(huì)比3更大慧耍，所以我們更新其上界）然后繼續(xù)向下搜索。
因?yàn)?7比3大丐谋，所以這個(gè)節(jié)點(diǎn)我們可以無(wú)視掉（沒(méi)啥用）芍碧。我們已經(jīng)搜索完了當(dāng)前這個(gè)Min節(jié)點(diǎn)的所有孩子，所以我們返回它的節(jié)點(diǎn)值給它的父節(jié)點(diǎn)（Max節(jié)點(diǎn)）号俐，嘗試更新父節(jié)點(diǎn)的α 值泌豆。（因?yàn)檫@是一個(gè)Max節(jié)點(diǎn)，他的孩子的估價(jià)值和α 吏饿、 β 值已經(jīng)確定了踪危，所以父節(jié)點(diǎn)取值范圍的下界也需要被更新），此處更新父節(jié)點(diǎn)猪落，令α = 3 贞远。然后繼續(xù)進(jìn)行搜索，注意新生成的子節(jié)點(diǎn)的 α 笨忌、 β 值繼承自父節(jié)點(diǎn)蓝仲。
繼續(xù)搜索，至葉子節(jié)點(diǎn)：
我們發(fā)現(xiàn)它的權(quán)值是2官疲，并且它的父節(jié)點(diǎn)是Min節(jié)點(diǎn)袱结，又因?yàn)楦腹?jié)點(diǎn)的最小上界β > 2 ，所以我們更新父節(jié)點(diǎn)途凫，令β = 2垢夹。（因?yàn)楦腹?jié)點(diǎn)要取最小值，這個(gè)最小值不會(huì)比2更大维费，所以我們更新其上界）果元。然后此時(shí)我們發(fā)現(xiàn)父節(jié)點(diǎn)出現(xiàn)了α > β 的情況，說(shuō)明最優(yōu)解不可能從這個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)中產(chǎn)生犀盟，所以我們不再繼續(xù)搜索它的其他子節(jié)點(diǎn)噪漾。（這就是β 剪枝）并繼續(xù)返回其節(jié)點(diǎn)值，嘗試更新父節(jié)點(diǎn)且蓬。因?yàn)楦腹?jié)點(diǎn)的α = 3 > 2 欣硼，所以更新失敗。
然后我們已經(jīng)搜索完了當(dāng)前這個(gè)Max節(jié)點(diǎn)的所有子節(jié)點(diǎn)，所以我們返回它的節(jié)點(diǎn)值诈胜，并嘗試更新他的父節(jié)點(diǎn)的β 值豹障。因?yàn)楦腹?jié)點(diǎn)的β > 3 ，所以我們令β = 3 焦匈。并繼續(xù)向下搜索至葉子節(jié)點(diǎn)血公，注意新生成的子節(jié)點(diǎn)的 α 、β值繼承自父節(jié)點(diǎn)缓熟。
然后累魔，我們發(fā)現(xiàn)15并不能更新當(dāng)前節(jié)點(diǎn)的β值，所以令當(dāng)前節(jié)點(diǎn)權(quán)值為15够滑，并返回其權(quán)值垦写，嘗試更新其父節(jié)點(diǎn)(Max節(jié)點(diǎn))的α 值。因?yàn)槠涓腹?jié)點(diǎn)的α < 15彰触，所以我們令α = 15 梯投。此時(shí)，該節(jié)點(diǎn)α = 15 , β = 3 况毅，α > β 分蓖，則說(shuō)明其子節(jié)點(diǎn)并不包含最優(yōu)解，不需要在進(jìn)行搜索尔许。所以返回其節(jié)點(diǎn)權(quán)值給父節(jié)點(diǎn)（Min節(jié)點(diǎn)）么鹤，嘗試對(duì)父節(jié)點(diǎn)的β值進(jìn)行更新。父節(jié)點(diǎn)的β < 15 味廊，則不需要進(jìn)行更新蒸甜。同時(shí)可確定父節(jié)點(diǎn)的權(quán)值為3。
繼續(xù)返回權(quán)值給父節(jié)點(diǎn)毡们，嘗試更新父節(jié)點(diǎn)的α 迅皇，發(fā)現(xiàn)父節(jié)點(diǎn)α < 3 昧辽，則令α = 3衙熔，并繼續(xù)向下搜索直至葉子節(jié)點(diǎn)。注意新生成的子節(jié)點(diǎn)的 α 搅荞、 β? 值繼承自父節(jié)點(diǎn)红氯。
從葉子節(jié)點(diǎn)返回權(quán)值給父節(jié)點(diǎn)（Min節(jié)點(diǎn)），并嘗試更新其父節(jié)點(diǎn)的β值咕痛，因?yàn)楦腹?jié)點(diǎn)β > 2痢甘，所以，令β = 2茉贡，此時(shí)有α > β塞栅，說(shuō)明其子節(jié)點(diǎn)并不包含最優(yōu)解，不需要再進(jìn)行搜索腔丧。所以返回其節(jié)點(diǎn)權(quán)值給父節(jié)點(diǎn)（Max節(jié)點(diǎn)）放椰，嘗試對(duì)父節(jié)點(diǎn)的α值進(jìn)行更新作烟。因?yàn)楦腹?jié)點(diǎn)α > 2 ，無(wú)需進(jìn)行更新砾医，繼續(xù)搜索其子節(jié)點(diǎn)至葉子節(jié)點(diǎn)拿撩。
從葉子節(jié)點(diǎn)返回權(quán)值給父節(jié)點(diǎn)（Min節(jié)點(diǎn)），并嘗試更新其父節(jié)點(diǎn)的β值如蚜，因?yàn)楦腹?jié)點(diǎn)β > 3 压恒，所以，令β = 3 错邦，同時(shí)確認(rèn)父節(jié)點(diǎn)權(quán)值為3探赫。繼續(xù)返回權(quán)值給父節(jié)點(diǎn)，并嘗試更新其父節(jié)點(diǎn)的α 值兴猩，因?yàn)楦腹?jié)點(diǎn)α = 3期吓，所以無(wú)需進(jìn)行更新，同時(shí)確定該節(jié)點(diǎn)權(quán)值為3倾芝。
因?yàn)樵摴?jié)點(diǎn)的所有子節(jié)點(diǎn)全部搜索完畢讨勤，所以返回該點(diǎn)權(quán)值給父節(jié)點(diǎn)，并嘗試更新其父節(jié)點(diǎn)的β值晨另，因?yàn)楦腹?jié)點(diǎn)β > 3 潭千，所以，令β = 3 借尿，同時(shí)確認(rèn)父節(jié)點(diǎn)權(quán)值為3刨晴。因?yàn)榇藭r(shí)有α = β = 3，所以無(wú)需再搜索其子節(jié)點(diǎn)路翻，直接返回權(quán)值給根節(jié)點(diǎn)狈癞，并嘗試更新根節(jié)點(diǎn)的α 值，因?yàn)楦?jié)點(diǎn)α = 3 茂契，所以無(wú)需進(jìn)行更新蝶桶。
根節(jié)點(diǎn)的所有子節(jié)點(diǎn)搜索完畢，則得出最優(yōu)解為3掉冶。
可以對(duì)比一下不加剪枝與加了剪枝之后的搜索過(guò)程真竖，可以發(fā)現(xiàn)Alpha-Beta剪枝對(duì)算法的性能有了很大的提升。
