【正文】 board[y][x]) continue。 int cboard[15][15]。 memcpy(cboard,board,sizeof(cboard))。 cboard[y][x]=BLACK。 int value=generate(cboard,WHITE,depth1,pE,alpha,beta)。 if(valuealpha){ alpha=value。 =x。 =y。 } } }else{ for(int i=0。i15*15。i++){ int y=i/15。int x=i%15。 if(board[y][x]) continue。 int cboard[15][15]。 memcpy(cboard,board,sizeof(cboard))。 cboard[y][x]=WHITE。 int value=generate(cboard,BLACK,depth1,pE,alpha,beta)。 if(valuebeta){ beta=value。 =x。 =y。 } } } return pos。 }167。 Alphabeta算法的窗口效應(yīng)前面描述了對(duì)于取大值的節(jié)點(diǎn)，其任意子點(diǎn)的值不能大于beta,而取極小值的節(jié)點(diǎn)，其任意子節(jié)點(diǎn)的值不能小于alpha,事實(shí)上，alphabeta算法建立了一個(gè)范圍為（alpha,beta）的窗口，對(duì)于搜索到的有意義的子節(jié)點(diǎn)，其值必在落在（alpha,beta）這范圍內(nèi)。故對(duì)于最取節(jié)點(diǎn)，alpha=MAX_VALUE，beta=MAX_VALUE，而alphabeta算法在搜索取極大值節(jié)點(diǎn)的子節(jié)點(diǎn)時(shí)，alpha值不怕增大，在搜索取最小值節(jié)點(diǎn)的子節(jié)點(diǎn)時(shí)，beta值不斷減小，隨著這個(gè)窗口不斷減小，剪枝效率也就越來(lái)越高。因而，改進(jìn)alphabeta效率的關(guān)鍵就在于怎么盡可能地縮小(alpha,beta)這個(gè)窗口的大小而又不失其正確性。這可以從兩個(gè)方面加以考慮，第一種就是人為地減小這個(gè)窗口的大小，比較經(jīng)典的算法有Failsoft AlphaBeta算法、渴望搜索、極小窗口搜索（又稱PVS算法），PVS算法是一種很優(yōu)秀的算法，在實(shí)際應(yīng)用中相當(dāng)普遍，故本文采用PVS搜索來(lái)優(yōu)化。第二種對(duì)Alphabeta優(yōu)化的思路是如果在一開始就能夠搜索到比較好的節(jié)點(diǎn)，那么Alpha很快就能得到比較大的值，Beta很快就能得到比較小的值，從而縮小了窗口的大小，但怎么一開始就得到比較好的搜索節(jié)點(diǎn)這可能與具體的游戲相關(guān)，也可以采用歷史啟發(fā)算法。后面我們一分別實(shí)現(xiàn)。167。 極小窗口搜索/PVS算法一、算法分析顧名思義，極小窗口搜索中的窗口是最小的（0容量），該算法先計(jì)算第一個(gè)子節(jié)點(diǎn)的值作為當(dāng)前最佳節(jié)點(diǎn)值best，如果是取極大值的節(jié)點(diǎn)，對(duì)以后的子節(jié)點(diǎn)搜索中，用(alpha,alpha+1)窗口大小搜索，對(duì)于取極小值的節(jié)點(diǎn)，則用(beta1,beta)對(duì)后繼子節(jié)點(diǎn)進(jìn)行搜索，得到值value，由于不能取邊界，這實(shí)際上是零大小的窗口搜索，所以很快能得到結(jié)果，比如取極大值的節(jié)點(diǎn)，要么value比alpha大，要么比alpha小，比alpha小的節(jié)點(diǎn)直接可以忽略過(guò)了，但如果比alpha大，value也并不準(zhǔn)確，但可以確定，最大的值肯定比value還要大，故必須重新搜索，采用新的窗口大小，取極大值的節(jié)點(diǎn)采用(value,beta)，取極小值的節(jié)點(diǎn)采用(alph,value)進(jìn)行搜索。綜上所述，給出PVS算法與一般的alphaBeta算法僅在外層調(diào)用搜索函數(shù)時(shí)所給出的alpha,beta的參數(shù)的不同，其余一樣。所以，僅需要對(duì)Search函數(shù)中調(diào)用generate處稍稍進(jìn)行修改：將黑方處的代碼：int value=generate(board,WHITE,depth1,pe,alpha,beta)。改為：int value=generate(cboard,WHITE,depth1,pe,alpha,alpha+1)。if(valuealpha) value=generate(cboard,WHITE,depth1,pe,value,beta)。將白方處的代碼：int value=generate(board,BLACK,depth1,pe,alpha,beta)。改為：int value=generate(cboard,BLACK,depth1,pe,beta1,beta)。if(valuealpha) value=generate(cboard,WHITE,depth1,pe,alpha,value)。167。 預(yù)估排序和歷史啟發(fā)下面再來(lái)討論第二種優(yōu)化思路，一開始就搜索較好的節(jié)點(diǎn)，從而引發(fā)更高效的剪枝。這可以采用子節(jié)點(diǎn)預(yù)估值排序和歷史啟發(fā)兩種方式實(shí)現(xiàn)一、 預(yù)估排序?qū)τ谖遄悠?，最粗略的好一判斷?biāo)準(zhǔn)就是看棋盤上同一方的棋子連續(xù)相連的個(gè)數(shù)，在大多數(shù)情況也確實(shí)是這樣，我們的估值函數(shù)就是這樣編寫的，所以，對(duì)于要搜索的子節(jié)點(diǎn)，可以對(duì)這些子節(jié)點(diǎn)先進(jìn)行粗略的估值，將這些子節(jié)點(diǎn)按他們的估值進(jìn)行排序，然后，按排序后的節(jié)點(diǎn)順序進(jìn)行搜索。程序中用CSortedAlphaBeta類實(shí)現(xiàn)了排序的AlphaBeta算法，定義了結(jié)構(gòu)：struct CPointScore{ POINT pos。 int value。 bool operator (const CPointScore amp。b){ return value。 }}。該結(jié)構(gòu)保存子節(jié)點(diǎn)某一走法（記錄在pos中）的粗略估值，用stl::vector psArray保存所有子節(jié)點(diǎn)及其估值，用STL模板庫(kù)中的sort函數(shù)進(jìn)行排序，該排序算法需要向量中的元素有重載的“”操作函數(shù)，用來(lái)比較排序。所以在結(jié)構(gòu)中重載了“”操作符函數(shù)。預(yù)估值排序的AlphaBeta算法實(shí)現(xiàn)在CSortedAlphaBeta類中。也可以將預(yù)估值排序與PVS算法相結(jié)合，與預(yù)估排序的AlphaBeta算法大致相同。預(yù)估值排序的PVS實(shí)現(xiàn)在CSortedPVS類中。二、歷史啟發(fā)歷史啟發(fā)簡(jiǎn)單地說(shuō)就是根據(jù)部分已經(jīng)搜索的結(jié)果來(lái)調(diào)整將要搜索的節(jié)點(diǎn)順序。所要解決的問(wèn)題又有兩個(gè)，一是如何保存已經(jīng)搜索過(guò)的歷史記錄，二是如果快速取得這些保存的記錄。hash表由于五子棋的子節(jié)點(diǎn)很多（每層最多15*15個(gè)），不可能保存所有的搜索節(jié)點(diǎn)，故只能保存部分節(jié)點(diǎn)，當(dāng)節(jié)點(diǎn)很多時(shí)，當(dāng)前搜索的節(jié)點(diǎn)是否被搜索過(guò)，如何快速地取得該節(jié)點(diǎn)，這個(gè)時(shí)間最好是常量。顯而易見，哈稀表很適合完成這項(xiàng)工作。在實(shí)現(xiàn)中，用結(jié)構(gòu)HashItem來(lái)保存棋局信息，定義如下：struct HashItem{ unsigned long long check_sum。//64位hash校驗(yàn)值 int value。//棋局的歷史搜索得分 int depth。//得到得分的搜索深度}。check_sum為校驗(yàn)值，用來(lái)標(biāo)識(shí)不同的棋局狀態(tài)，我們知道每一棋局用二維數(shù)組int board[15][15]表示，check_sum就是用這一個(gè)二維數(shù)組計(jì)算出來(lái)的值。具體原理篇幅所限，不再贅述，請(qǐng)參見hash表的相關(guān)文章。value就是棋局的得分，depth用來(lái)表示搜索得到該得分時(shí)的深度，因?yàn)樵跉v史搜索時(shí)，某些節(jié)點(diǎn)的值可能是比較靠近葉子節(jié)點(diǎn)時(shí)得到的。這里的設(shè)計(jì)思想是，如何歷史得分的深度比當(dāng)前高，證明歷史得分比當(dāng)前所期望的精度還要高（深度越深精度越高），可以直接采用歷史得分，否則，只能像預(yù)估值一樣，作為搜索時(shí)的一個(gè)參考（參與排序）。Hash類的實(shí)現(xiàn)在CBoardHash類中，該類定義如下：class CBoardHash{ int nSize。//hash表大小 HashItem *buf。//hash表__int64 check64[3][15][15]。//64位校驗(yàn)生成隨機(jī)數(shù) unsigned long hash32[3][15][15]。//32位hash值生成隨機(jī)數(shù)public: CBoardHash(int size)。 ~CBoardHash(void)。 unsigned long hashCode(int board[][15])。//根據(jù)棋盤生成32位hash值 unsigned long hashCode(unsigned long parHash,int side,int y,int x)。 __int64 checkSum(int board[][15])。 __int64 checkSum(unsigned long long parCheck,int side,int y,int x)。 HashItem getHashItem(unsigned long key)。 void setHashItem(unsigned long key,HashItem amp。it)。}這里介紹它們的公共接口，hashCode和checkSum有兩個(gè)重載版本，一個(gè)接受棋盤數(shù)組，根據(jù)棋局信息生成hash碼和校驗(yàn)值，hash碼用來(lái)在hash表中定位，校驗(yàn)值用來(lái)檢查根據(jù)hash碼定位于表中的信息是否就是當(dāng)前的棋局信息（通過(guò)當(dāng)前棋局調(diào)用checkSum函數(shù)與表項(xiàng)中的check_sum比較）。為讓hash碼與校驗(yàn)值分布均勻，在實(shí)現(xiàn)中引入了兩個(gè)隨機(jī)數(shù)組，一個(gè)是32位的hash32，一個(gè)64位的check64，它們中的值都是隨機(jī)數(shù)。Hash碼的代碼如下：unsigned long inline hashCode(int board[][15]){//hash值生成函數(shù) unsigned long key=0。 for(int