【文章內(nèi)容簡介】 點表示當(dāng)前棋盤局勢，此時該電腦下子，它試著產(chǎn)生每一種可能走法，對于五子棋，最多15*15種，每一種走法都用估值引擎估值，如果此時電腦執(zhí)黑子，它會選擇估值最大的一種走法（估值引擎中棋局的值是黑方的價值減去白方的價值），因為這種走法對自己最有利，如果執(zhí)白子，則選擇估值最小的走法。其算法表示如下：POINT Search(int board[][15],int side,CEvaluation *pe){ POINT pos,best。 if(side==BLACK) best=MAX_VALUE。 else best=MAX_VALUE。 for(int y=0。y15。y++)for(int x=0。x15。x++){ board[y][x]=side。 value=pevalue(board,side==BLACK?WHITE:BLACK)。 board[y][x]=NONE。 if(valuebest){ best=value。 =。=y。 }}return pos。}有了這個算法，計算機(jī)勉強(qiáng)有點智能，可以下一下棋了，但它還是比較笨，只管眼前這一步，而不能看到兩步，三步，或者以后更多步的結(jié)果。要讓計算機(jī)足夠聰明，必須采用某種搜索算法。與估值引擎一樣，為了以后方便擴(kuò)展，單獨設(shè)計了一個CSearch的純虛類來作為公共接口。class CSearch{public: virtual POINT Search(int board[][15],int side,int depth,CEvaluation *pE)=0。// }。在上面深度為1的算法中，我們看到，每一個結(jié)點產(chǎn)生子結(jié)點，要在這子結(jié)點中選擇一個對自己最有利的子結(jié)點，所以，對于黑方來說，總是選擇子結(jié)點值為最大的結(jié)點來走，而不會選擇其它結(jié)點，所以，該最大值的子結(jié)點值就是該結(jié)點的值。白方也一樣，如下圖所示：……n1n2nknn11n1m…………n1k 深度為3的對弈樹根結(jié)點n為當(dāng)前棋局狀態(tài)，它產(chǎn)生了子結(jié)點n1……nk，并且要在子結(jié)點中選擇一個對自己最有利的一個節(jié)點來下子，如果此時n節(jié)點該黑方走，就會選擇其中最大值的節(jié)點。但是此時n1……nk的節(jié)點值此時還不知，比如說n1的值必須要通過計算n1的子結(jié)點n11……n1k，一直到達(dá)葉子結(jié)點為止，n結(jié)點為黑方，則n1為白方，它會選擇所有子結(jié)點值為最小的作為自己的結(jié)點值，n2,n3,……,nk結(jié)點的值計算也一樣，最后，n2,n3,……,nk當(dāng)中最大的一個結(jié)點就作為n的結(jié)點值，也就是需要確定的走法。程序中極大極小搜索引擎的類為CMaxMinSearch，它繼承至CSearch，按指定的深度，搜索產(chǎn)生一個走法：其搜索引擎?zhèn)未a表示如下：int generate(board,int side,int depth){ int best。 游戲結(jié)束返回估值 深度為0估值返回 Best=極大極小值 for(each possible pos){ board[y][x]=side。 int value=generate(board,anotherside,depth1)。 board[y][x]=NONE。 if(side==BLACK) best=max(value,best)。 else best=min(value,best)。 } return best。}CmaxMinSearch類在其公共接口中調(diào)用這個函數(shù)，選擇最佳的一個走法，其Search函數(shù)如下：POINT CMaxMinSearch::Search(int board[][15],int side,int depth,CEvaluation *pe)。它調(diào)用generate函數(shù)計算得出子節(jié)點的值，然后選擇一個最佳子節(jié)點的坐標(biāo)返回，作為下子的位置。167。 Alphabeta算法極大極小值算法的效率不高，如下圖（81）所示:……n1n2nknn21n2m…………n2kn為極大值節(jié)點（黑方）n1到nk為極小值節(jié)點（白方）n1=50n11=43 Alpha截枝n節(jié)點此代表黑方該下子的節(jié)點，它要在它的子節(jié)點中找一個值最大的子節(jié)點max(n1,n2,……,nk)作為自己的值（或下子），此時它得到其子節(jié)點n1的值為50，然后計算n2節(jié)點的值，此時n2為白方下子的節(jié)點，它要搜索一個值最小的子節(jié)點作為自己的值，這時它搜索計算得出其子節(jié)點n21的值為43，此時，我們就可以得出結(jié)論，因為n2要取最小子節(jié)點值作為自己的值，所以n2的值不會大于43，所以n2更不會大于前面的兄弟節(jié)點n1，所以n2一定不會被n選作為最佳子節(jié)點，故，在搜索n2的子結(jié)點n21——n2k的過程中，只要n2有子節(jié)點的值小于50，則n2就不必再搜索了，后面n3，n4……nk也一樣，只要它們的某子結(jié)點值小于前面兄弟結(jié)點的最大值，則不必須再搜索了。我們將取極大值節(jié)點（上圖中n）所產(chǎn)生子節(jié)點的最大值用變量alpha表示，如果子節(jié)點（極小值節(jié)點）在搜索過程中，產(chǎn)生的孫子節(jié)點值小于alpha，則子節(jié)點不需要搜索了，這叫做alpha截枝?！璶1n2nknn21n2m…………n2kn為極大值節(jié)點（黑方）n1到nk為極小值節(jié)點（白方）n1=50……nxnx1…………nxknxmnx極小值節(jié)點（白方）極大值節(jié)點再推廣到搜索深度很深的情況，如上圖（圖82）所示，取極大的值節(jié)點n的不知道哪一代孫子節(jié)點nx，它的祖先為n2m，n2，n，它為取極小值節(jié)點，假設(shè)它的某子節(jié)點的值小于n1=50，假如是nx1=40，那么nx是否應(yīng)該放棄其子節(jié)點的搜索而截枝呢？我們可以這樣推論：n的子節(jié)點現(xiàn)在搜索得到的最大值是50，alpha=50,對于n的子節(jié)點n2……nk，它們在搜索過程中，所產(chǎn)生的不被截枝的任一子節(jié)點必須大于50（否則必被截枝），故n2m未被截枝大于50,n2m是取極大值的節(jié)點，所以其子節(jié)點中必有大于50的節(jié)點，故可得到在n2m這一層所得到的最大節(jié)點值alpha≥50，由此可以再推而廣之，n2m的子孫中，凡是取極大值的節(jié)點，它們的子孫節(jié)點的最大值都應(yīng)該≥50，到了nx這一層，nx是取極小值的節(jié)點，它的父親是取極大值的節(jié)點，所以alpha也應(yīng)該≥50，故nx1=40應(yīng)該被截枝。……n1n2nknn21n2m…………n2kn為極小值節(jié)點（白方）n1到nk為極大值節(jié)點（黑方）n1=20n11=33 Beta 截枝再來看另一方的情況，如上圖（圖83）情況與圖81相反，n為取極小值節(jié)點，它的某子節(jié)點的值為20(n1)，搜索其后繼子節(jié)點，如圖中的n2，n2的子節(jié)點中某子節(jié)點n21的值為33，而n2取極大值，n2的值至少為33，故n2的父節(jié)點不可能選擇n2，所以n2中一旦搜索發(fā)現(xiàn)其子節(jié)點值大于兄弟節(jié)點中的最小值，就沒有搜索必要了。我們將取極小值節(jié)點的子節(jié)點中最小值用變量beta表示，某子節(jié)點在搜索孫子節(jié)點的過程中，如果孫子節(jié)點的值大于beta，則該子節(jié)點不需要再進(jìn)行搜索，這叫beta截枝。再推而廣之，任何一層取最小值的節(jié)點，它的子節(jié)點值大于beta，則應(yīng)該截枝。綜合兩種情況，由此而得到alphabeta算法，下面用偽碼表示:int generate(board,int side,int depth,int alpha,int beta){ 游戲結(jié)束估值返回。 到葉子節(jié)點估值返回。 if(side==BLACK){//此節(jié)點該黑方，取極大值 for(Each Possible Move){ if(alpha=beta) return alpha。 board[y][x]=side。 int value=alphbeta(board,anotherside,depth1,alpha,beta)。 board[y][x]=NONE。 if(valuealpha) alpha=value。//子節(jié)點的最大值記錄到alpha中 } return alpha。//返回最大值 }else{ for(each possible move){ if(alpha=beta) return beta。 board[y][x]=side。 int value=generate(board,anotherside,depth1,alpha,beta)。 board[y][x]=NONE。 if(valuebeta) beta=value。//最小子節(jié)點的最 } return beta。 }其外層調(diào)用函數(shù)search代碼如下，不同的是search返回坐標(biāo)值：POINT CAlphaBeta::Search(int board[][15],int side,int depth,CEvaluation *pE){ POINT pos={1,1}。 int alpha=MAX_VALUE,beta=MAX_VALUE。 if(side==BLACK){ for(int i=0。i15*15。i++){ int y=i/15。int x=i%15。 if(