實驗5：-剪枝實現(xiàn)一字棋一、實驗?zāi)康膶W(xué)習(xí)極大極小找尋及-剪枝算法實現(xiàn)一字棋。二、實驗原理游戲規(guī)則一字棋"游戲（又叫"三子棋"或"井字棋"），是一款十分經(jīng)典的益智小游戲。"井字棋"的棋盤很簡單，是一個3×3的格子，很像中國文字中的"井"字，所以得名"井字棋。"井字棋"游戲的規(guī)則與"五子棋"十分近似，"五子棋"的規(guī)則是一方第一五子連成一線就成功；"井字棋"是一方第一三子連成一線就成功。極小極大解析法設(shè)有九個空格，由MAX，MIN二人棋戰(zhàn)，輪到誰走棋誰就往空格上放一只自己的棋子，誰先使自己的棋子構(gòu)成"三子成一線"(同一行或列或?qū)蔷€所有是某人的棋子)，誰就獲取了成功?！皎w○○○

用圓圈表示MAX，用叉號代表MIN比方左圖中就是MAX取勝的棋局。╳估價函數(shù)定義以下設(shè)棋局為P，估價函數(shù)為╳e(P)。(1)若P對任何一方來說都不是獲勝的地址，則e(P)=e(那些仍為MAX空著的完全的行、列或?qū)蔷€的總數(shù))-e(那些仍為MIN空著的完滿的行、列或?qū)蔷€的總數(shù))若P是MAX必勝的棋局，則e(P)＝+（實質(zhì)上賦了60）。(3)若P是B必勝的棋局，則e(P)＝-（實質(zhì)上賦了-20）。比方P以以下圖示,則e(P)=5-4=1○需要說明的是，+賦60，-賦-20的原因是機器若贏了，則不論玩家下一步可否會贏，都會走這步必贏棋。╳3.-剪枝算法上述的極小極大解析法，實質(zhì)是先生成一棵博弈樹，爾后再計算其倒推值，至使極小極大解析法效率較低。于是在極小極大解析法的基礎(chǔ)上提出了-剪枝技術(shù)。剪枝技術(shù)的基本思想或算法是，邊生成博弈樹邊計算評估各節(jié)點的倒推值，并且依照評估出的倒推值范圍，及時停止擴(kuò)展那些已無必要再擴(kuò)展的子節(jié)點，即相當(dāng)于剪去了博弈樹上的一些分枝，從而節(jié)約了機器開銷，提高了找尋效率。詳盡的剪枝方法以下：對于一個與節(jié)點MIN，若能估計出其倒推值的上確界，并且這個值不大于MIN的父節(jié)點(必然是或節(jié)點)的估計倒推值的下確界，即，則就不用再擴(kuò)展該MIN節(jié)點的其他子節(jié)點了(因為這些節(jié)點的估值對MIN父節(jié)點的倒推值已無任何影響了)。這一過程稱為剪枝。對于一個或節(jié)點MAX，若能估計出其倒推值的下確界，并且這個值不小于MAX的父節(jié)點(必然是與節(jié)點)的估計倒推值的上確界，即，則就不用再擴(kuò)展該MAX節(jié)點的其他子節(jié)點了(因為這些節(jié)點的估值對MAX父節(jié)點的倒推值已無任何影響了)。這一過程稱為剪枝。從算法中看到：MAX節(jié)點(包括初步節(jié)點)的值永不減少；MIN節(jié)點(包括初步節(jié)點)的值永不增加。在找尋時期，和值的計算以下：一個MAX節(jié)點的值等于以后繼節(jié)點目前最大的最后倒推值。一個MIN節(jié)點的值等于以后繼節(jié)點目前最小的最后倒推值。4．勝敗判斷算法設(shè)計因為每次以致勝敗的只會是目前放置的棋子,勝敗算法中只需從目前點開始掃描判斷可否已經(jīng)形成三子。對于這個子的八個方向判斷可否已經(jīng)形成三子。若是有，則說明有一方成功，若是沒有則連續(xù)找尋，直到有一方成功也許找尋完滿個棋盤。三、實驗代碼#include<iostream>usingnamespacestd;intnum=0;

<<endl;return0;}if(val>m){

<<endl;return0;}gotoL5;}else{

<<endl;return0;}for(intx=0;x<3;x++){for(inty=0;y<3;y++){if(now[x][y]==0){now[x][y]=1;cut(val,dep,1);if(Checkwin( )==1){cout<<"電腦將棋子放在:"<<x+1<<y+1<<endl;PrintQP( );cout<<"電腦獲勝!游戲結(jié)束."<<endl;return0;}if(val>m){m=val;x_pos=x;y_pos=y;}val=-10000;now[x][y]=0;}}}now[x_pos][y_pos]=1;val=-10000;m=-10000;dep=1;cout<<"電腦將棋子放在:"<<x_pos+1<<y_pos+1<<endl;PrintQP( );cout<<endl;num++;value( );if(q==0){cout<<"平局!"<<endl;return0;}gotoL4;}return0;}intmain( ){computer( );system("pause");return0;}主要函數(shù)估值函數(shù)估價函數(shù)：intCTic_MFCDlg::evaluate(intboard[])完成功能：依照輸入棋盤，判斷目前棋盤的估值，估價函數(shù)為前面所講：若是MAX的必勝局，則e=+INFINITY，這里為+60若是MIN的必勝局，則e=-INFINITY，這里為-20，這樣賦值的原因是機器若贏了，則不考慮其他因素。其他情況，棋盤上能使CUMPUTER成三子一線的數(shù)目為e1棋盤上能使PLAYER成三子一線的數(shù)目為e2，e1-e2作為最后權(quán)值參數(shù)：

board:

待評估棋盤返回：評估結(jié)果剪枝算法AlphaBeta剪枝主函數(shù)：intCTic_MFCDlg::AlphaBeta(intBoard[],intDepth,intturn,intAlpha,intBeta,int*result)完成功能：依照輸入棋盤，找尋深度，及其他參數(shù)，給出一個相應(yīng)的最優(yōu)解，存入result中。參數(shù)：board:待評估棋盤Depth:找尋深度turn:目前是機器走(MAX結(jié)點)還是玩家走(MIN結(jié)點)Alpha:alpha值，第一次調(diào)用默認(rèn)-100Beta:beta值，第一次調(diào)用默認(rèn)+100result:輸出結(jié)果返回：若當(dāng)前點為MAX節(jié)點，則返回alpha值；若目前點為MIN節(jié)點，則返回beta值.判斷勝敗intCTic_MFCDlg::isWin(intcurPos)完成功能：依照輸入棋盤，判斷目前棋盤的結(jié)果，COMPUTER勝PLAYER勝平局參數(shù)：board:待評估棋盤返回：-1表示：還沒有結(jié)束表示：平局表示：PLAYER勝表示：COMPUTER勝五、實驗截圖六、實驗總結(jié)經(jīng)過本次實驗進(jìn)一步對老師課堂上