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