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

高級(jí)搜索算法之

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

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

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

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

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

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

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

minimax(node,

depth)

//

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

//

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

if

node

is

a

terminal

node

or

depth

=

0

return

the

heuristic

value

of

node

//

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

if

the

adversary

is

to

play

at

node

let

α

:=

+∞

foreach

child

of

node

α

:=

min(α,

minimax(child,

depth-1))

//

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

else

{we

are

to

play

at

node}

let

α

:=

-∞

foreach

child

of

node

α

:=

max(α,

minimax(child,

depth-1))

return

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

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)。

不同的是，前面的評(píng)估函數(shù)是針對(duì)白方即，指定的一方來(lái)給出分?jǐn)?shù)的，這里的評(píng)估函數(shù)是根據(jù)當(dāng)前搜索節(jié)點(diǎn)來(lái)給出分?jǐn)?shù)的。每個(gè)人都會(huì)選取最大的分?jǐn)?shù)，然后，返回到上一層節(jié)點(diǎn)時(shí)，會(huì)給出分?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);

//

注意這里有個(gè)負(fù)號(hào)

UnmakeMove();

if

(val

>

best)

{

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

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à)值,可能還沒(méi)有算出來(lái)）那么在對(duì)x的子節(jié)點(diǎn)進(jìn)行考查的過(guò)程中，如果一旦發(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à)值,可能還沒(méi)有算出來(lái)）那么在對(duì)x的子節(jié)點(diǎn)進(jìn)行考查的過(guò)程中，如果一旦發(fā)現(xiàn)某子節(jié)點(diǎn)的估價(jià)值<=b,則不必再考查后面的x的子節(jié)點(diǎn)了。MAXMINMAXXY3.Alpha–beta剪枝當(dāng)搜索節(jié)點(diǎn)X時(shí)，若已求得某子節(jié)點(diǎn)Y的值為2，因?yàn)閄是一個(gè)極小節(jié)點(diǎn)，那么X節(jié)點(diǎn)得到的值肯定不大于2。因此X節(jié)點(diǎn)的子節(jié)點(diǎn)即使都搜索了，X節(jié)點(diǎn)值也不會(huì)超過(guò)2。而節(jié)點(diǎn)K的值為7，由于R是一個(gè)Max節(jié)點(diǎn)，那么R的取值已經(jīng)可以肯定不會(huì)選X的取值了。因此X節(jié)點(diǎn)的Y后面子節(jié)點(diǎn)可以忽略，即圖中第三層沒(méi)有數(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ù)無(wú)窮大

foreachchildofnode

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

break(*Betacut-off*)returnα

else

β:=INF;//無(wú)窮大foreachchildofnode

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

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

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

#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){//判斷一個(gè)局面是否是棋局結(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; //正對(duì)角線判斷

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; //反對(duì)角線判斷

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走法，對(duì)每種走法用MaxSearch求其估價(jià)值，返回估價(jià)值最小的那個(gè)走法(B的選擇）的估價(jià)值。參數(shù)alpha，表示本步（本節(jié)點(diǎn)）的兄弟節(jié)點(diǎn)里面，已經(jīng)算出來(lái)的最大估價(jià)值。如果枚舉走法的過(guò)程中，發(fā)現(xiàn)有MaxSearch的值如ans已經(jīng)小于等于alpha,那么立即停止枚舉，返回ans,表示本節(jié)點(diǎn)的估價(jià)值就是ans如果ans<alpha，那么本節(jié)點(diǎn)就不會(huì)被自己選擇*/ 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)的各個(gè)子節(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à)值。具體辦法，枚舉本步所有走法，對(duì)每種走法用MinSearch求其估價(jià)值，返回估價(jià)值最大的那個(gè)走法的估價(jià)值。beta表示本步的兄弟節(jié)點(diǎn)中，已經(jīng)算出來(lái)的最小的估價(jià)值。如果枚舉走法的過(guò)程中，發(fā)現(xiàn)有MinSearch的值如ans已經(jīng)大于等于beta,那么立即停止枚舉，返回ans,表示本節(jié)點(diǎn)的估價(jià)值就是ans如果ans>beta，那么本節(jié)點(diǎn)就不會(huì)被B選擇*/ intans=-inf;//本節(jié)點(diǎn)展開(kāi)的各子節(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)的各個(gè)子節(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”);//無(wú)必勝走法 } return0;}