一、前言

人機(jī)博弈是人工智能的重要分支，人們在這一領(lǐng)域探索的過程中產(chǎn)生了大量的研究成果，而極小化極大算法(minimax)是其中最基礎(chǔ)的算法，它由Shannon在1950年正式提出。Alpha-beta剪枝的本質(zhì)就是一種基于極小化極大算法的改進(jìn)方法。Knuth等人在1975年優(yōu)化了算法，提出了負(fù)極大值(negamax)概念，這一概念的原理本質(zhì)上與極小化極大值算法并無不同，但是卻不需要系統(tǒng)區(qū)分取極大值者和極小值者，使得算法更加統(tǒng)一。此外，Knuth等人也對alpha-beta剪枝算法的搜索效率進(jìn)行了深入的研究，Pearl也在1982年證明了alpha-beta剪枝原理的最優(yōu)性。

二、極大極小值算法（Minimax Search）

1. 極大極小算法

在人機(jī)博弈中，雙方回合制地進(jìn)行走棋，己方考慮當(dāng)自己在所有可行的走法中作出某一特定選擇后，對方可能會(huì)采取的走法，從而選擇最有利于自己的走法。這種對弈過程就構(gòu)成了一顆博弈樹，雙方在博弈樹中不斷搜索，選擇對自己最為有利的子節(jié)點(diǎn)走棋。在搜索的過程中，將取極大值的一方稱為max，取極小值的一方稱為min。max總是會(huì)選擇價(jià)值最大的子節(jié)點(diǎn)走棋，而min則相反。這就是極小化極大算法的核心思想。

1. 如果節(jié)點(diǎn)是終止節(jié)點(diǎn)：應(yīng)用估值函數(shù)求值；

2. 如果節(jié)點(diǎn)是max節(jié)點(diǎn)：找到每個(gè)子節(jié)點(diǎn)的值，將其中最大的子節(jié)點(diǎn)值作為該節(jié)點(diǎn)的值；

3. 如果節(jié)點(diǎn)時(shí)min節(jié)點(diǎn)：找到每個(gè)子節(jié)點(diǎn)的值，將其中最小的子節(jié)點(diǎn)值作為該節(jié)點(diǎn)的值。

2. 估值函數(shù)

估值函數(shù)使用來給每一個(gè)局面給出一個(gè)估值，用判斷博弈樹中當(dāng)前局面的形勢。在傳統(tǒng)的棋類游戲智能系統(tǒng)中，估值函數(shù)一般是人為指定的，對棋類游戲智能的水平有決定性作用。

估值函數(shù)的形式不是固定的，它的輸入一般是一個(gè)局面的信息，輸出是一個(gè)表明相應(yīng)局面好壞程度的數(shù)值。為了說明極小化極大算法，例如規(guī)定井字棋的估值函數(shù)為：玩家X還存在可能性的行、列、斜線數(shù)減去玩家O還存在可能性的行、列、斜線數(shù)。

3. α-β pruning search

3.1. alpha-beta剪枝原理

極小化極大算法最大的缺點(diǎn)就是會(huì)造成數(shù)據(jù)冗余，而這種冗余有兩種情況：①極大值冗余；②極小值冗余。相對應(yīng)地，alpha剪枝用來解決極大值冗余問題，beta剪枝則用來解決極小值冗余問題，這就構(gòu)成了完整的Alpha-beta剪枝算法。接下來對極大極小值冗余和具體剪枝過程作簡要介紹。

• Alpha剪枝：極大值冗余如圖所示，這是一顆博弈樹的某一部分，節(jié)點(diǎn)下的數(shù)據(jù)為該節(jié)點(diǎn)的值，節(jié)點(diǎn)B的值為20，節(jié)點(diǎn)D的值為15，這里，C為取極小值的min節(jié)點(diǎn)，因此節(jié)點(diǎn)C的值將小于等于15；而節(jié)點(diǎn)A為取最大值max的節(jié)點(diǎn)，因此A只可能取到B的值，也是就說不再需要搜索C的其他子節(jié)點(diǎn)E和F的值就可以得出節(jié)點(diǎn)A的值。這樣將節(jié)點(diǎn)D的后繼兄弟節(jié)點(diǎn)減去稱為Alpha剪枝。

• Beta剪枝：極小值冗余如圖所示，這也是一顆博弈樹的某一部分，節(jié)點(diǎn)B的值為10，節(jié)點(diǎn)D的值為19，這里，C節(jié)點(diǎn)為取最大值max節(jié)點(diǎn)。因此，C的值將大于等于19；節(jié)點(diǎn)A為取極小值的min節(jié)點(diǎn)，因此A的值只能取B的值10，也就是說不再需要求節(jié)點(diǎn)C的子節(jié)點(diǎn)E和F的值就可以得出節(jié)點(diǎn)A的值。這樣將節(jié)點(diǎn)D的后繼兄弟節(jié)點(diǎn)減去稱為Beta剪枝。

3.2. α-β剪枝實(shí)現(xiàn)

• alpha: 在MAX輪次會(huì)被更新，用來記錄當(dāng)前節(jié)點(diǎn)的各個(gè)子節(jié)點(diǎn)中的最大值，如果子節(jié)點(diǎn)被剪枝了，那就是拋去被裁剪部分之后的最大值。

• beta: 在MIN輪次會(huì)被更新，用來記錄當(dāng)前節(jié)點(diǎn)的各個(gè)子節(jié)點(diǎn)中的最小值，如果子節(jié)點(diǎn)被剪枝了，那就是拋去被裁剪部分之后的最小值。

• 剪枝條件：α>=β

• 初始化：是遞歸調(diào)用，每一個(gè)節(jié)點(diǎn)的alpha的初始值均是負(fù)無窮，因?yàn)閍lpha要負(fù)責(zé)記錄最大值；每一個(gè)節(jié)點(diǎn)的beta的初始值均是正無窮，因?yàn)閎eta要負(fù)責(zé)記錄最小值。

最清晰易懂的MinMax算法和Alpha-Beta剪枝詳解

3.3 α-β search

• The α-value of a MAX-node is set to the current largest final backed-up value of itssuccessors. That is, you can not back up a node until you have finished looking at itschildren.

• The β-value of a MIN-node is set to the current smallest final backed-up value of itssuccessors.

• α cut-off – search is discontinued below a MIN-node whose β value is less than or equal to the α value of any of its MAX-node ancestors.

• β cut-off – search is discontinued below a MAX-node whose α value is greater than or equal to the β value of any of its MIN-node ancestors.

References

https://www.w3cschoool.com/adversarial-search

Alpha-beta剪枝 -機(jī)器之心

Minimax Search以及alpha-beta剪枝文章來源地址http://www.zghlxwxcb.cn/news/detail-765378.html