人工智能α-β剪枝實(shí)現(xiàn)的一字棋實(shí)驗(yàn)報(bào)告

1、實(shí)驗(yàn)5:剪枝實(shí)現(xiàn)一字棋、實(shí)驗(yàn)?zāi)康膶W(xué)習(xí)極大極小搜索及剪枝算法實(shí)現(xiàn)一字棋.二、實(shí)驗(yàn)原理1.游戲規(guī)那么"一字棋"游戲(又叫"三子棋"或"井字棋"),是一款十分經(jīng)典的益智小游戲."井字棋的棋盤很簡(jiǎn)單,是一個(gè)3X3的格子,很像中國文字中的"井"字,所以得名"井字棋"."井字棋游戲的規(guī)那么與“五子棋"十分類似,"五子棋"的規(guī)那么是一方首先五子連成一線就勝利；“井字棋是一方首先三子連成一線就勝利.2.極小極大分析法設(shè)有九個(gè)空格,由MAX,MIN二人對(duì)弈,輪到誰

2、走棋誰就往空格上放一只自己的棋子,誰先使自己的棋子構(gòu)成"三子成一線(同一行或列或?qū)蔷€全是e(P)o(1)假設(shè)P對(duì)任何一方來說都不是獲勝的位置,那么著的完全的行、列或?qū)蔷€的總數(shù))-e(那些仍為MIN角線的總數(shù))e(P)=eCB些仍為MAX空空著的完全的行、列或?qū)?2)假設(shè)P是MAX必勝的棋局,那么e(P)=+假設(shè)P是B必勝的棋局,那么e(P)=-(實(shí)際上賦了60).(實(shí)際上賦了-20).上述的極小極大分析法,實(shí)際是先生成一棵博弈樹,然后再計(jì)算其倒推值,至使極小極大分析法效率較低.于是在極小極大分析法的根底上提出了-剪枝技術(shù).-剪枝技術(shù)的根本思想或算法是,邊生成博弈樹邊計(jì)算評(píng)估各節(jié)點(diǎn)

3、的倒推值,并且根據(jù)評(píng)估出的倒推值范圍,及時(shí)停止擴(kuò)展那些已無必要再擴(kuò)展的子節(jié)點(diǎn),即相當(dāng)于剪去了博弈樹上的一些分枝,從而節(jié)約了機(jī)器開銷,提升了搜索效率.具體的剪枝方法如下:(1)對(duì)于一個(gè)與節(jié)點(diǎn)MIN,假設(shè)能估計(jì)出其倒推值的上確界,并且這個(gè)值不大于MIN的父節(jié)點(diǎn)(一定是或節(jié)點(diǎn))的估計(jì)倒推值的下確界,即,那么就不必再擴(kuò)展該MIN節(jié)點(diǎn)的其余子節(jié)點(diǎn)了(由于這些節(jié)點(diǎn)的估值對(duì)MIN父節(jié)點(diǎn)的倒推值已無任何影響了).這一過程稱為剪枝.(2)對(duì)于一個(gè)或節(jié)點(diǎn)MAX,假設(shè)能估計(jì)出其倒推值的下確界,并且這個(gè)值不小于MAX的父節(jié)點(diǎn)(一定是與節(jié)點(diǎn))的估計(jì)倒推值的上確界,即,那么就不必再擴(kuò)展該MAX節(jié)點(diǎn)的其余子節(jié)點(diǎn)了(由于這些

4、節(jié)點(diǎn)的估值對(duì)MAX父節(jié)點(diǎn)的倒推值已無任何影響了).這一過程稱為剪枝.從算法中看到：(1) MAX節(jié)點(diǎn)(包括起始節(jié)點(diǎn))的值永不減少；(2) MIN節(jié)點(diǎn)(包括起始節(jié)點(diǎn))的值永不增加.在搜索期間,和值的計(jì)算如下:(1) 一個(gè)MAX節(jié)點(diǎn)的值等于其后繼節(jié)點(diǎn)當(dāng)前最大的最終倒推值.(2) 一個(gè)MIN節(jié)點(diǎn)的值等于其后繼節(jié)點(diǎn)當(dāng)前最小的最終倒推值.4.輸贏判斷算法設(shè)計(jì)由于每次導(dǎo)致輸贏的只會(huì)是當(dāng)前放置的棋子,輸贏算法中只需從當(dāng)前點(diǎn)開始掃描判斷是否已經(jīng)形成三子.對(duì)于這個(gè)子的八個(gè)方向判斷是否已經(jīng)形成三子.如果有,那么說明有一方勝利,如果沒有那么繼續(xù)搜索,直到有一方勝利或者搜索完整個(gè)棋盤.三、實(shí)驗(yàn)代碼#include&l

5、t;iostream>usingnamespacestd;intnum=0;intp,q;inttmpQP33;表示該格為空,intnow33;constintdepth=3;voidInit()for(inti=0;i<3;i+)for(intj=0;j<3;j+)nowij=0;/記錄棋盤上棋子的個(gè)數(shù)/判斷是否平局表示棋盤數(shù)據(jù)的臨時(shí)數(shù)組,其中的元素0/存儲(chǔ)當(dāng)前棋盤的狀態(tài)/搜索樹的最大深度/將初值均置為0/初始化棋盤狀態(tài)voidPrintQP()打印棋盤當(dāng)前狀態(tài)for(inti=0;i<3;i+)for(intj=0；j<3；j+)cout<<now

6、ij<<'t'cout<<endl;voidplayerinput()/用戶通過此函數(shù)來輸入落子的位置,比如：用戶輸入31,那么表示用戶在第3行第1列落子.intx,y;L1:cout<<"請(qǐng)輸入您的棋子位置(xy):"<<endl;cin>>x>>y;if(x>0&&x<4&&y>0&&y<4&&nowx-1y-1=0)nowx-1y-1=-1;elsecout<<"非法輸入!

7、"<<endl;gotoL1;intCheckwin()任何一方贏；1:計(jì)算機(jī)贏；-1:人贏)for(inti=0;i<3;i+)/站在電腦一方,玩家落子置為-1/提醒輸入錯(cuò)誤/檢查是否有一方贏棋(返回0:沒有/該方法沒有判斷平局if(nowi0=1&&nowi1=1&&nowi2=1)|(now0i=1&&now1i=1&&now2i=1)|(now00=1&&now11=1&&now22=1)|(now20=1&&now11=1&&no

8、w02=1)正方行連成線return1;if(nowi0=-1&&nowi1=-1&&nowi2=-1)|(now0i=-1&&now1i=-1&&now2i=-1)|(now00=-1&&now11=-1&&now22=-1)|(now20=-1&&now11=-1&&now02=-1)/反方行連成線return-1;return0;intvalue()/評(píng)估當(dāng)前棋盤狀態(tài)的值(同時(shí)可以用p或q判斷是否平局)p=0;q=0;for(inti=0;i<3;i+)計(jì)

9、算機(jī)一方將棋盤中的空格填滿自己的棋子,既將棋盤數(shù)組中的0變?yōu)?for(intj=0;j<3;j+)if(nowij=0)tmpQPij=1;elsetmpQPij=nowij;)for(inti=0;i<3;i+)p+=(tmpQPi0+tmpQPi1+tmpQPi2)/3;for(inti=0;i<3;i+)p+=(tmpQP0i+tmpQP1i+tmpQP2i)/3;p+=(tmpQP00+tmpQP11+tmpQP22)/3;線p+=(tmpQP20+tmpQP11+tmpQP02)/3;for(inti=0;i<3;i+)既將棋盤數(shù)組中的0變?yōu)?1for(int

10、j=0;j<3;j+)/計(jì)算共有多少連成3個(gè)1的行/計(jì)算共有多少連成3個(gè)1的列/計(jì)算共有多少連成3個(gè)1的對(duì)角/人一方/將棋盤中的空格填滿自己的棋子,if(nowij=0)tmpQPij=-1;elsetmpQPij=nowij;)for(inti=0;i<3;i+)q+=(tmpQPi0+tmpQPi1+tmpQPi2)/3;for(inti=0;i<3;i+)q+=(tmpQP0i+tmpQP1i+tmpQP2i)/3;q+=(tmpQP00+tmpQP11+tmpQP22)/3;角線q+=(tmpQP20+tmpQP11+tmpQP02)/3;returnp+q;)int

11、cut(int&val,intdep,boolmax)val為上一個(gè)結(jié)點(diǎn)的估計(jì)值,dep為搜索深度,if(dep=depth|dep+num=9)度,或者深度加上當(dāng)前棋子數(shù)已經(jīng)到達(dá)returnvalue();inti,j,flag,temp;層求得的估計(jì)值boolout=false;if(max)層那么需要是下確界,記錄)/計(jì)算共有多少連成3個(gè)-1的行/計(jì)算共有多少連成3個(gè)1的列/計(jì)算共有多少連成3個(gè)1的對(duì)/返回評(píng)估出的棋盤狀態(tài)的值主算法局部,實(shí)現(xiàn)a-B剪枝的算法,max記錄上一個(gè)結(jié)點(diǎn)是否為上確界/如果搜索深度到達(dá)最大深9,就直接調(diào)用估計(jì)函數(shù)/flag記錄本層的極值,temp記錄下/o

12、ut記錄是否剪枝,初始為false/如果上一個(gè)結(jié)點(diǎn)是上確界,本flag為無窮大；反之,那么為記錄為負(fù)無窮大flag=10000;/flag記錄本層節(jié)點(diǎn)的極值elseflag=-10000;for(i=0;i<3&&!out;i+)/雙重循環(huán),遍歷棋盤所有位置for(j=0;j<3&&!out;j+)if(nowij=0)if(max)輪到用戶玩家走了./如果該位置上沒有棋子并且上一個(gè)結(jié)點(diǎn)為上確界,即本層為下確界nowij=-1;if(Checkwin()=-1)temp=-10000;else/該位置填上用戶玩家棋子如果用戶玩家贏了/置棋盤估計(jì)值為負(fù)

13、無窮temp=cut(flag,dep+1,!max);/否那么繼續(xù)調(diào)用a-B剪枝函數(shù)if(temp<flag)值,那么置本層極值為更小者flag=temp;if(flag<=val)值,那么不需要搜索下去,剪枝out=true;/如果下一步棋盤的估計(jì)值小于本層節(jié)點(diǎn)的極/如果本層的極值已經(jīng)小于上一個(gè)結(jié)點(diǎn)的估計(jì)else/如果上一個(gè)結(jié)點(diǎn)為下確界,即本層為上確界,輪到計(jì)算機(jī)走了./該位置填上計(jì)算機(jī)棋子/如果計(jì)算機(jī)贏了/置棋盤估計(jì)值為無窮nowij=1;if(Checkwin()=1)temp=10000;elsetemp=cut(flag,dep+1,!max);/否那么繼續(xù)調(diào)用a-B剪

14、枝函數(shù)if(temp>flag)flag=temp;if(flag>=val)out=true;nowij=0;把模擬下的一步棋復(fù)原,回溯根據(jù)上一個(gè)結(jié)點(diǎn)是否為上確界,用本層的if(max)極值修改上一個(gè)結(jié)點(diǎn)的估計(jì)值if(flag>val)val=flag;)elseif(flag<val)val=flag;)returnflag;函數(shù)返回的是本層的極值)intcomputer()/m用來存放最大的val/記錄最正確走步的坐標(biāo)intm=-10000,val=-10000,dep=1;intx_pos,y_pos;charch;cout<<"您希望先走

15、嗎？(y/n);cin>>ch;while(ch!='y'&&ch!='n')cout<<"非法輸入!"<<"您希望先走嗎(y/n)"<<endl;cin>>ch;)system("cls");Init();cout<<"棋盤如下："<<endl;PrintQP();if(ch='n')/計(jì)算機(jī)先走L5:for(intx=0;x<3;x+)for(inty=0;y

16、<3;y+)if(nowxy=0)nowxy=1;cut(val,dep,1);計(jì)算機(jī)試探的走一步棋,棋盤狀態(tài)改變了,在該狀態(tài)下計(jì)算出深度為dep-1的棋盤狀態(tài)估計(jì)值valif(Checkwin()=1)cout<<"電腦將棋子放在："<<x+1<<y+1<<endl;PrintQP();cout<<"電腦獲勝！游戲結(jié)束."<<endl;return0;)if(val>m)/m要記錄通過試探求得的棋盤狀態(tài)的最大估計(jì)值m=val;x_pos=x;y_pos=y;)val=-

17、10000;nowxy=0;)nowx_posy_pos=1;val=-10000;m=-10000;dep=1;cout<<"電腦將棋子放在："<<x_pos+1<<y_pos+1<<endl;PrintQP();cout<<endl;num+;value();if(p=0)cout<<"平局!"<<endl;return0;)playerinput();/玩家走一步棋PrintQP();cout<<endl;num+;value();if(p=0)cout

18、<<"平局!"<<endl;return0;)if(Checkwin()=-1)cout<<"您獲勝！游戲結(jié)束."<<endl;return0;)gotoL5;)else/人先走L4:playerinput();PrintQP();cout<<endl;num+;value();if(q=0)cout<<"平局!"<<endl;return0;)if(Checkwin()=-1)cout<<"您獲勝！游戲結(jié)束."<

19、<endl;return0;)for(intx=0;x<3;x+)for(inty=0;y<3;y+)if(nowxy=0)nowxy=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;nowxy=0;)nowx_posy_pos=

20、1;val=-10000;m=-10000;dep=1;cout«"電腦將棋子放在:"«x_pos+1«y_pos+1«endl;PrintQP();cout«endl;num+;value();if(q=o)cout«"平局!"«endl;return0;)gotoL4;)return0;)intmain()computer();system("pause");return0;4.主要函數(shù)1估值函數(shù)估價(jià)函數(shù)：intCTic_MFCDlg:evaluate(intboard)完成功能：根據(jù)輸乂血盤,判斷當(dāng)前棋盤的估值,估價(jià)函數(shù)為前面所講:假設(shè)是MAX的必勝局,那么e=+INFINITY,這里為+60假設(shè)是MIN的必勝局,那么e=-INFINITY,這里為-20,這樣賦值的原因是機(jī)器假設(shè)贏了,那么不考慮其它因素.其它情況,棋盤上能使CUMPUTER成三子一線的數(shù)目為e1棋盤上能使PLAYER成三子一線的數(shù)目為e2,e1-e2作為最終權(quán)值參數(shù)：board待評(píng)估棋盤返回：評(píng)估結(jié)果2.Alpha-Beta剪枝算法AlphaBeta剪枝主函數(shù)：intCTic_MFCDlg:AlphaBeta(intBoard,intDepth,inttu