本篇將簡要介紹α-β剪枝，這是一種基于剪枝（ α-βcut-off）的深度優(yōu)先搜索（depth-first search）。

一、什么是α剪枝？

（1）將走棋方定為MAX方，因為它選擇著法時總是對其子節(jié)點的評估值取極大值，即選擇對自己最為有利的著法；

（2）將應對方定為MIN方，因為它走棋時需要對其子節(jié)點的評估值取極小值，即選擇對走棋方最為不利的、最有鉗制作用的著法。

（3）在對博弈樹（博弈樹是指由于動態(tài)博弈參與者的行動有先后次序,因此可以依次將參與者的行動展開成一個樹狀圖形。）采取深度優(yōu)先的搜索策略時，從左路分枝的葉節(jié)點倒推得到某一層MAX節(jié)點的值，可表示到此為止得以“落實”的著法最佳值，記為α。

（4）顯然此值可作為MAX方著法指標的下界。

（5）在搜索此MAX節(jié)點的其它子節(jié)點，即探討另一著法時，如果發(fā)現(xiàn)一個回合（2步棋）之后評估值變差，即孫節(jié)點評估值低于下界α值，則便可以剪掉此枝（以該子節(jié)點為根的子樹），即不再考慮此“軟著”的延伸。

此類剪枝稱為α剪枝。

二、什么是β剪枝？

（1）同理，由左路分枝的葉節(jié)點倒推得到某一層MIN節(jié)點的值，可表示到此為止對方著法的鉗制值，記為β。

（2）顯然此β值可作為MAX方無法實現(xiàn)著法指標的上界。

（3）在搜索該MIN節(jié)點的其它子節(jié)點，即探討另外著法時，如果發(fā)現(xiàn)一個回合之后鉗制局面減弱，即孫節(jié)點評估值高于上界β值，則便可以剪掉此枝，即不再考慮此“軟著”的延伸。

此類剪枝稱為β剪枝。

三、什么是α-β剪枝？

α-β剪枝是根據(jù)極大-極小搜索規(guī)則的進行的，雖然它沒有遍歷某些子樹的大量節(jié)點，但它仍不失為窮盡搜索的本性。

α-β剪枝原理中得知：

（1）α值可作為MAX方可實現(xiàn)著法指標的下界

（2）β值可作為MAX方無法實現(xiàn)著法指標的上界

（3）于是由α和β可以形成一個MAX方候選著法的窗口，也便出現(xiàn)了各種各樣的α-β窗口搜索算法。