今天做SGU 423，WA得我眼淚汪汪。后來發現原來這個問題很早就被何牛提到過：

極大極小過程的alpha-beta剪枝不可與記憶化搜索一起使用。

原因是這樣的：

在一個博弈圖中，可能存在這樣的情況：一個狀態有不止一個前繼。

比如，設狀態u和狀態v都可以轉移到同一個狀態w。

假設極大極小過程先搜索到u，為了得到u的估值f(u)，我們要搜索w并且給本次搜索一個估值上界beta(u)，一旦在w的搜索過程中發現f(w)當前值>=beta(u)，則立刻停止搜索因為f(u)的估值不會用到w這個分支。這就是alpha-beta剪枝。

但是請注意，此時并不保證f(w)的正確性，我們僅僅知道f(w)>=beta(u)而已。這次剪枝僅僅保證u的搜索結果的正確性。

為了得到v的估值f(v)我們會再次搜索到w，注意此時所給的估值上界是beta(v)而不是beta(u)，也就是這兩次搜索對于w的限制是不同的。如果使用記憶化，就相當于默認f(w)為精確值。但是由于之前的剪枝，我們得到的僅僅是f(w)的一個界而已，這里就會出現錯誤。更確切地，當beta(v)>beta(u)時，就會由于u與beta(u)對于w的限制被記憶，導致計算v的估值所需要的w的信息被誤剪。

T_T

順便貼個alpha-beta剪的思路模板吧：

//alpha-beta剪枝 //不可以和記憶化搜索混用 //需要在外部記錄狀態（局面以及當前先手者），通過make_move和unmake_move函數進行改變。 int ab(int alpha, int beta, int depth, bool pass) {// 當前最佳估值，預設為負無窮大int best = -INF;// 如果到達預定的搜索深度if (depth <= 0) {// 計算出估值return eval();}// 嘗試每個后繼狀態foreach (move) {// 試著走后繼狀態if (make_move(move)) {// 如果合法，對所形成的局面進行遞歸搜索int now = -alpha_beta(-beta, -alpha, depth-1, 0);// 恢復原來的局面 unmake_move(move);// 如果這步棋引發剪枝if (now >= beta) {// 停止對當前局面的搜索，立即返回。return now;}// 如果這步更好if (now > best) {// 保存更好的結果best = now;// 更新估值下限if (now > alpha) {alpha = now;}}}}// 如果沒有合法后繼，則此步為棄著if (best == -INF) {// 如果上一步也是棄著，表明對局結束if (pass) {// 計算出精確值return calc();}// 否則這步棋棄著，局面不變先后手互換 make_move(PASS_MOVE);// 遞歸搜索，并標明該步棄著。best = -alpha_beta(-beta, -alpha, depth, 1);// 恢復原來的局面 unmake_move(PASS_MOVE);}// 返回最佳估值return best; }

轉載于:https://www.cnblogs.com/jffifa/archive/2012/08/01/2618960.html

總結

以上是生活随笔為你收集整理的[笔记]极大极小过程的alpha-beta剪枝不可与记忆化搜索一起使用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。