北大公開課高級搜索之a(chǎn)lpha beta剪枝

高級搜索算法之

alpha-beta剪枝北京大學(xué)信息學(xué)院郭煒編輯、修改自網(wǎng)上講義、源代碼1.極大極小搜索法

在博弈搜索中，比如：圍棋，五子棋，象棋等,結(jié)果有三種可能：勝利、失敗和平局。

理論上可以窮舉所有的走法，這就需要生成整棵博弈樹。實(shí)際上不可行。因此搜索時可以限定博弈樹的深度，到達(dá)該深度則不再往下搜，相當(dāng)于只往前看n步。

1.極大極小搜索法看誰能先連成三點(diǎn)一線的一字棋的三層博弈樹：1.極大極小搜索法

假設(shè)：A和Ｂ對弈，輪到Ａ走棋了，那么我們會遍歷A的每一個可能走棋方法，然后對于前面A的每一個走棋方法，遍歷B的每一個走棋方法，然后接著遍歷A的每一個走棋方法，如此下去，直到分出勝負(fù)或者達(dá)到了搜索深度的限制。當(dāng)達(dá)到了搜索深度限制，此時無法判斷結(jié)局如何，一般都是根據(jù)當(dāng)前局面的形式，給出一個得分，計(jì)算得分的方法被稱為評價(jià)函數(shù)，不同游戲的評價(jià)函數(shù)差別很大，需要很好的設(shè)計(jì)。

在搜索樹中，輪到A走棋的節(jié)點(diǎn)即為極大節(jié)點(diǎn)，輪到B走棋的節(jié)點(diǎn)為極小節(jié)點(diǎn)。1.極大極小搜索法確定估價(jià)值函數(shù)，來計(jì)算每個棋局節(jié)點(diǎn)的估價(jià)值。對MAX方有利，估價(jià)值為正，對MAX方越有利，估價(jià)值越大。對MIN方有利，估價(jià)值為負(fù)，對MIN方越有利，估價(jià)值越小。從當(dāng)前棋局的節(jié)點(diǎn)要決定下一步如何走時，以當(dāng)前棋局節(jié)點(diǎn)為根，生成一棵深度為n的搜索樹。不妨總是假設(shè)當(dāng)前棋局節(jié)點(diǎn)是MAX節(jié)點(diǎn)。3)用局面估價(jià)函數(shù)計(jì)算出每個葉子節(jié)點(diǎn)的估價(jià)值4)若某個非葉子節(jié)點(diǎn)是極大節(jié)點(diǎn)，則其估價(jià)值為其子節(jié)點(diǎn)中估價(jià)值最大的那個節(jié)點(diǎn)的估價(jià)值

若某個非葉子節(jié)點(diǎn)是極小節(jié)點(diǎn)，則其估價(jià)值為其子節(jié)點(diǎn)中估價(jià)值最小的那個節(jié)點(diǎn)的估價(jià)值1.極大極小搜索法5)選擇當(dāng)前棋局節(jié)點(diǎn)的估價(jià)值最大的那個子節(jié)點(diǎn)，作為此步行棋的抉擇。MAXMINMAX偽代碼：function

minimax(node,

depth)

//

指定當(dāng)前節(jié)點(diǎn)和還要搜索的深度

//

如果勝負(fù)已分或者深度為零，使用評估函數(shù)返回局面得分

if

node

is

a

terminal

node

or

depth

=

0

return

the

heuristic

value

of

node

//

如果輪到對手走棋，即node是極小節(jié)點(diǎn)，選擇一個得分最小的走法

if

the

adversary

is

to

play

at

node

let

α

:=

+∞

foreach

child

of

node

α

:=

min(α,

minimax(child,

depth-1))

//

如果輪到自己走棋，是極大節(jié)點(diǎn)，選擇一個得分最大的走法

else

{we

are

to

play

at

node}

let

α

:=

-∞

foreach

child

of

node

α

:=

max(α,

minimax(child,

depth-1))

return

α;更具體的做法：intMinMax(intdepth){//函數(shù)的評估都是以白方的角度來評估的

if(SideToMove()==WHITE){

//白方是“最大”者

returnMax(depth);

}else{

//黑方是“最小”者

returnMin(depth);

}}

intMax(intdepth){

intbest=-INFINITY;

if(depth<=0){

returnEvaluate();

}

GenerateLegalMoves();

while(MovesLeft()){

MakeNextMove();

val=Min(depth-1);

UnmakeMove();

if(val>best){

best=val;

}

}

returnbest;}

intMin(intdepth){

intbest=INFINITY;

//注意這里不同于“最大”算法

if(depth<=0){

returnEvaluate();

}

GenerateLegalMoves();

while(MovesLeft()){

MakeNextMove();

val=Max(depth-1);

UnmakeMove();

if(val<best){

//注意這里不同于“最大”算法

best=val;

}

}

returnbest;}

前面的兩段代碼都是分別用兩部分代碼處理了極大節(jié)點(diǎn)和極小節(jié)點(diǎn)兩種情況，其實(shí)，可以只用一部分代碼，既處理極大節(jié)點(diǎn)也處理極小節(jié)點(diǎn)。

不同的是，前面的評估函數(shù)是針對白方即，指定的一方來給出分?jǐn)?shù)的，這里的評估函數(shù)是根據(jù)當(dāng)前搜索節(jié)點(diǎn)來給出分?jǐn)?shù)的。每個人都會選取最大的分?jǐn)?shù)，然后，返回到上一層節(jié)點(diǎn)時，會給出分?jǐn)?shù)的相反數(shù)。

2.負(fù)值最大算法int

NegaMax(int

depth)

{

int

best

=

-INFINITY;

if

(depth

<=

0)

{

return

Evaluate();

//估價(jià)函數(shù)

}

GenerateLegalMoves();

while

(MovesLeft())

{

MakeNextMove();

val

=

-NegaMax(depth

-

1);

//

注意這里有個負(fù)號

UnmakeMove();

if

(val

>

best)

{

//都是選擇最大的分?jǐn)?shù)，因?yàn)樵u估分?jǐn)?shù)的對象變化了

best

=

val;

}

}

return

best;

}3.Alpha–beta剪枝若結(jié)點(diǎn)x是Max節(jié)點(diǎn)，其兄弟節(jié)點(diǎn)(父節(jié)點(diǎn)相同的節(jié)點(diǎn)）中，已經(jīng)求到的最小估價(jià)值是a（有些兄弟節(jié)點(diǎn)的估價(jià)值,可能還沒有算出來）那么在對x的子節(jié)點(diǎn)進(jìn)行考查的過程中，如果一旦發(fā)現(xiàn)某子節(jié)點(diǎn)的估價(jià)值>=a,則不必再考查后面的x的子節(jié)點(diǎn)了。若結(jié)點(diǎn)x是Min節(jié)點(diǎn)，其兄弟節(jié)點(diǎn)(父節(jié)點(diǎn)相同的節(jié)點(diǎn)）中，已經(jīng)求到的最大估價(jià)值是b（有些兄弟節(jié)點(diǎn)的估價(jià)值,可能還沒有算出來）那么在對x的子節(jié)點(diǎn)進(jìn)行考查的過程中，如果一旦發(fā)現(xiàn)某子節(jié)點(diǎn)的估價(jià)值<=b,則不必再考查后面的x的子節(jié)點(diǎn)了。MAXMINMAXXY3.Alpha–beta剪枝當(dāng)搜索節(jié)點(diǎn)X時，若已求得某子節(jié)點(diǎn)Y的值為2，因?yàn)閄是一個極小節(jié)點(diǎn)，那么X節(jié)點(diǎn)得到的值肯定不大于2。因此X節(jié)點(diǎn)的子節(jié)點(diǎn)即使都搜索了，X節(jié)點(diǎn)值也不會超過2。而節(jié)點(diǎn)K的值為7，由于R是一個Max節(jié)點(diǎn)，那么R的取值已經(jīng)可以肯定不會選X的取值了。因此X節(jié)點(diǎn)的Y后面子節(jié)點(diǎn)可以忽略，即圖中第三層沒有數(shù)字的節(jié)點(diǎn)可被忽略。此即為Alpha剪枝----因被剪掉的節(jié)點(diǎn)是極大節(jié)點(diǎn)。相應(yīng)的也有Beta剪枝，即被剪掉的節(jié)點(diǎn)是極小節(jié)點(diǎn)。

MAXMINMAXXYKRfunctionalphabeta(node,depth,α,β,maximizingPlayer)ifdepth=0ornodeisaterminalnodereturntheheuristicvalueofnodeifmaximizingPlayer

α:=-INF;//負(fù)無窮大

foreachchildofnode

α:=max(α,alphabeta(child,depth-1,α,β,not(maximizingPlayer)))ifβ≤α

break(*Betacut-off*)returnα

else

β:=INF;//無窮大foreachchildofnode

β:=min(β,alphabeta(child,depth-1,α,β,not(maximizingPlayer)))ifβ≤α

break(*Alphacut-off*)returnβ(*Initialcall*)alphabeta(origin,depth,-infinity,+infinity,TRUE)紅色字母處，隨便寫什么值都可以在搜到底的情況下，infinity不一定是無窮大infinity應(yīng)該是主角贏的那個狀態(tài)(勝負(fù)已分的狀態(tài)）的估價(jià)值，而-infinity應(yīng)該是主角輸?shù)哪莻€狀態(tài)(勝負(fù)已分的狀態(tài)）的估價(jià)值。Alpha–beta剪枝例題POJ1568給定一個4*4的四子連珠棋棋盤的局面，現(xiàn)在輪到x先走，問x下在哪里可以必勝.....xo..ox.....Alpha–beta剪枝例題POJ1568在窮盡搜索，而非搜幾層就停止的情況下，估價(jià)函數(shù)只有三種取值，正(inf)，0,負(fù)(-inf)。分別代表己方勝，平，負(fù)。必勝：

無論對手(B)怎么走，己方(A)最后都能找到獲勝辦法。不是自己無論怎么走，都能獲勝。此步行棋，若能找到一個走法，其對應(yīng)的節(jié)點(diǎn)估價(jià)值為inf,則此為一個必勝的走法。

#include<iostream>#include<cstdio>#include<map>#include<cstring>#include<cmath>#include<vector>#include<queue>#include<algorithm>#include<set>usingnamespacestd;//程序改編自網(wǎng)上博客源代碼#defineinf1<<30//inf取1也可以charstr[5][5];intX,Y,chess;boolcheck(intx,inty){//判斷一個局面是否是棋局結(jié)束的局面 inttot=0; //橫向判斷

for(inti=0;i<4;i++) if(str[x][i]=='o')tot++; elseif(str[x][i]=='x')tot--; if(tot==4||tot==-4)returntrue; tot=0; //縱向判斷

for(inti=0;i<4;i++) if(str[i][y]=='o')tot++; elseif(str[i][y]=='x')tot--; if(tot==4||tot==-4) returntrue; tot=0; //正對角線判斷

for(inti=0;i<4;i++) if(str[i][i]=='o')tot++; elseif(str[i][i]=='x')tot--; if(tot==4||tot==-4)returntrue; tot=0; //反對角線判斷

for(inti=0;i<4;i++) if(str[i][3-i]=='o')tot++; elseif(str[i][3-i]=='x')tot--; if(tot==4||tot==-4)returntrue; returnfalse;}intMinSearch(intx,inty,intalpha);intMaxSearch(intx,inty,intbeta);intMinSearch(intx,inty,intalpha){/*本節(jié)點(diǎn)是A剛下完,剛剛下在了(x,y)該輪到B下的節(jié)點(diǎn)MinSearch的返回值是B最佳走法的估價(jià)值。具體辦法，枚舉本步所有B走法，對每種走法用MaxSearch求其估價(jià)值，返回估價(jià)值最小的那個走法(B的選擇）的估價(jià)值。參數(shù)alpha，表示本步（本節(jié)點(diǎn)）的兄弟節(jié)點(diǎn)里面，已經(jīng)算出來的最大估價(jià)值。如果枚舉走法的過程中，發(fā)現(xiàn)有MaxSearch的值如ans已經(jīng)小于等于alpha,那么立即停止枚舉，返回ans,表示本節(jié)點(diǎn)的估價(jià)值就是ans如果ans<alpha，那么本節(jié)點(diǎn)就不會被自己選擇*/ intans=inf; if(check(x,y))//自己剛走了一步，如果棋局分出勝負(fù)，那么定是自己勝利

returninf; if(chess==16) return0;//平局

for(inti=0;i<4;++i) for(intj=0;j<4;++j){ if(str[i][j]=='.'){ str[i][j]='o';++chess; inttmp=MaxSearch(i,j,ans);//此處的ans是beta值，即在本節(jié)點(diǎn)的各個子節(jié)點(diǎn)中，目前已經(jīng)找到的最小的估價(jià)值

str[i][j]='.';--chess; ans=min(ans,tmp); if(ans<=alpha){ returnans; } } } returnans; }intMaxSearch(intx,inty,intbeta){/*本節(jié)點(diǎn)是B剛下完,下在(x,y),該輪到A下的節(jié)點(diǎn)在MaxSearch中，要返回本步A最佳走法的估價(jià)值。具體辦法，枚舉本步所有走法，對每種走法用MinSearch求其估價(jià)值，返回估價(jià)值最大的那個走法的估價(jià)值。beta表示本步的兄弟節(jié)點(diǎn)中，已經(jīng)算出來的最小的估價(jià)值。如果枚舉走法的過程中，發(fā)現(xiàn)有MinSearch的值如ans已經(jīng)大于等于beta,那么立即停止枚舉，返回ans,表示本節(jié)點(diǎn)的估價(jià)值就是ans如果ans>beta，那么本節(jié)點(diǎn)就不會被B選擇*/ intans=-inf;//本節(jié)點(diǎn)展開的各子節(jié)點(diǎn)中，最大的估價(jià)函數(shù)值

if(check(x,y)) return–inf; if(chess==16) return0; for(inti=0;i<4;++i) for(intj=0;j<4;++j){ if(str[i][j]=='.'){ str[i][j]='x';++chess; inttmp=MinSearch(i,j,ans);//ans是beta值，即在本節(jié)點(diǎn)的各個子節(jié)點(diǎn)中，目前找到的最大的估價(jià)值

str[i][j]='.';--chess; ans=max(tmp,ans); if(ans>=beta) returnans;

} } returnans;}boolSolve(){ intalpha=-inf; for(inti=0;i<4;++i) for(intj=0;j<4;++j){ if(str[i][j]=='.'){ str[i][j]='x';++chess; inttmp=MinSearch(i,j,alpha); str[i][j]='.';--chess; if(tmp==inf){ X=i; Y=j; returntrue; } } } returnfalse;}intmain(){ charch[5]; while(scanf("%s",ch)!=EOF&&ch[0]!='$'){ chess=0; for(inti=0;i<4;i++){ scanf("%s",str[i]); for(intj=0;j<4;j++) chess+=str[i][j]!='.'; } //這一步直接從2S+到0ms if(chess<=4){ printf("#####\n"); continue; } if(Solve())printf("(%d,%d)\n",X,Y); elseprintf(“#####\n”);//無必勝走法 } return0;}