人工智能αβ剪枝實(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è)3 X 3的格子，很像中國(guó)文字中的"井"字，所以得名"井字棋"。"井字棋"游戲的 規(guī)則與"五子棋"十分類似，"五子棋"的規(guī)則是一方首先五子連成一線就勝利；"井字棋"是一方首先 三子連成一線就勝利。2

2、. 極小極大分析法設(shè)有九個(gè)空格，由MAX min二人對(duì)弈，輪到誰(shuí)走棋誰(shuí)就往空格上放一只自己的棋子，誰(shuí)先使 自己的棋子構(gòu)成"三子成一線"(同一行或列或?qū)蔷€全是某人的棋子)，誰(shuí)就取得了勝利。OXOOOXX用圓圈表示MAX用叉號(hào)代表MIN比如左圖中就是MAX取勝的棋局。估價(jià)函數(shù)定義如下設(shè)棋局為P，估價(jià)函數(shù)為 e(P)。(1) 若P對(duì)任何一方來說都不是獲勝的位置，則e(P)=e(那些仍為MAX空著的完全的行、列 或?qū)蔷€的總數(shù))-e(那些仍為MIN空著的完全的行、列或?qū)蔷€的總數(shù))(2) 若P是MAX必勝的棋局，則e(P) = +(實(shí)際上賦了 60 )。(3) 若P是B必勝的棋局

3、，則e(P)=-(實(shí)際上賦了 -20 )。比如P如下圖示,則e(P)=5-4=1OX需要說明的是，+賦60，-賦-20的原因是機(jī)器若贏了，則不論玩 家下一步是否會(huì)贏，都會(huì)走這步必贏棋。剪枝算法3.上述的極小極大分析法，實(shí)際是先生成一棵博弈樹，然后再計(jì)算其倒 推值，至使極小極大分析法效率較低。于是在極小極大分析法的基礎(chǔ)上 提出了 -剪枝技術(shù)。- 剪枝技術(shù)的基本思想或算法是，邊生成博弈樹邊計(jì)算評(píng)估各節(jié)點(diǎn)的倒推值，并且根據(jù)評(píng)估出的倒推值范圍，及時(shí)停止擴(kuò)展那些已無必要再擴(kuò)展的子節(jié)點(diǎn)，即相當(dāng)于剪去了博弈樹上的一些分枝，從而節(jié)約了機(jī)器開銷，提高了搜索效率。具體的剪枝方法如下：(1) 對(duì)于一個(gè)與節(jié)點(diǎn)MIN，

4、若能估計(jì)出其倒推值的上確界 ，并且這個(gè) 值不大于MIN的 父節(jié)點(diǎn)(一定是或節(jié)點(diǎn))的估計(jì)倒推值的下確界 ，即 ，則就不必再擴(kuò)展該MIN節(jié)點(diǎn)的其余子 節(jié)點(diǎn)了(因?yàn)檫@些節(jié)點(diǎn)的估值對(duì) MIN父節(jié)點(diǎn)的倒推值已無任何影響了 )。這一過程稱為 剪枝。(2) 對(duì)于一個(gè)或節(jié)點(diǎn)MAX若能估計(jì)出其倒推值的下確界 ，并且這個(gè) 值不小于MAX的 父節(jié)點(diǎn)(一定是與節(jié)點(diǎn))的估計(jì)倒推值的上確界 ，即 ，則就不必再擴(kuò)展該MAX節(jié)點(diǎn)的其余子 節(jié)點(diǎn)了(因?yàn)檫@些節(jié)點(diǎn)的估值對(duì) MAX父節(jié)點(diǎn)的倒推值已無任何影響 了)。這一過程稱為 剪枝。從算法中看到：(1) MAX節(jié)點(diǎn)(包括起始節(jié)點(diǎn))的值永不減少;(2) MIN節(jié)點(diǎn)(包括起始節(jié)點(diǎn))的值

5、永不增加。值等于其后繼節(jié)點(diǎn)當(dāng)前最大的最終倒推值。 值等于其后繼節(jié)點(diǎn)當(dāng)前最小的最終倒推值。在搜索期間，和 值的計(jì)算如下：(1) 一個(gè)MAX節(jié)點(diǎn)的(2) 一個(gè)MIN節(jié)點(diǎn)的4.輸贏判斷算法設(shè)計(jì)因?yàn)槊看螌?dǎo)致輸贏的只會(huì)是當(dāng)前放置的棋子 ，輸贏算法中只需從當(dāng)前點(diǎn)開始掃描判斷是否已經(jīng)形成三子。對(duì)于這個(gè)子的八個(gè)方向判斷是否已經(jīng)形成三子。如果有，則說明有一方勝利，如果沒有則繼續(xù)搜索，直到有一方勝利或者搜索完整個(gè)棋盤。三、實(shí)驗(yàn)代碼#i nclude<iostream> using n ames pace std;int num=0;int p,q;int tmpQP 33;表示該格為空，int now

6、33; const int dep th=3;void lnit() for(i nt i=0;i<3;i+) for(i nt j=0;j<3;j+) n owij=0;/記錄棋盤上棋子的個(gè)數(shù)/判斷是否平局/表示棋盤數(shù)據(jù)的臨時(shí)數(shù)組，其中的元素0/存儲(chǔ)當(dāng)前棋盤的狀態(tài)/搜索樹的最大深度/初始化棋盤狀態(tài)/將初值均置為0/打印棋盤當(dāng)前狀態(tài)void P ri ntQ P()for(i nt i=0;i<3;i+) for(i nt j=0;j<3;j+) cout< <no wij<<'t' cout<<e ndl;/用戶通過

7、此函數(shù)來輸入落子的位置，比void playerinput()如：用戶輸入3 1，則表示用戶在第3行第1列落子。int x,y;L1: cout<<"請(qǐng)輸入您的棋子位置(X y):"<<endl;cin> >x>>y;if(x>0&&x<4&&y>0&& y<4&&n owx-1y-1=0)nowx-1y-1=-1;/站在電腦一方，玩家落子置為-1else/提醒輸入錯(cuò)誤/檢查是否有一方贏棋(返回0 :沒有coutvv"非法輸入！&

8、quot;vvendl; goto L1；int Checkwi n()任何一方贏； 1：計(jì)算機(jī)贏； -1 ：人贏) for(int i=0;i<3;i+)/ 該方法沒有判斷平局if(nowi0=1&&nowi1=1&&nowi2=1)|(now0i=1&&now1i=1&&no w2i=1)|(now00=1&&now11=1&&now22=1)|(now20=1&&now11=1&&n ow02=1)/ 正方行連成線return 1;if(nowi0=-1&

9、amp;&nowi1=-1&&nowi2=-1)|(now0i=-1&&now1i=-1& &now2i=-1)|(now00=-1&&now11=-1&&now22=-1)|(now20=-1& &now11=-1&&now02=-1) / 反方行連成線return -1;return 0;int value() 用 p 或 q 判斷是否平局)p=0; q=0;for(int i=0;i<3;i+) 自己的棋子，既將棋盤數(shù)組中的 0 變?yōu)?1 for(int j=0;

10、j<3;j+) if(nowij=0) tmpQPij=1;elsetmpQPij=nowij;/ 評(píng)估當(dāng)前棋盤狀態(tài)的值(同時(shí)可以/ 計(jì)算機(jī)一方 將棋盤中的空格填滿 for(int i=0;i<3;i+) p+=(tmpQPi0+tmpQPi1+tmpQPi2)/3;for(int i=0;i<3;i+) p+=(tmpQP0i+tmpQP1i+tmpQP2i)/3;p+=(tmpQP00+tmpQP11+tmpQP22)/3; 線p+=(tmpQP20+tmpQP11+tmpQP02)/3; for(int i=0;i<3;i+) / 計(jì)算共有多少連成/ 計(jì)算共有多少

11、連成/ 計(jì)算共有多少連成3個(gè) 1 的行3個(gè) 1 的列3個(gè) 1的對(duì)角/ 人一方/ 將棋盤中的空格填滿自己的棋子，既將棋盤數(shù)組中的 0 變?yōu)?-1 for(int j=0;j<3;j+) if(nowij=0) tmpQPij=-1; else tmpQPij=nowij; for(inti=0;i<3;i+)/ 計(jì)算共有多少連成 3 個(gè) -1 的q+=(tmpQPi0+tmpQPi1+tmpQPi2)/3;for(int i=0;i<3;i+)q+=(tmpQP0i+tmpQP1i+tmpQP2i)/3; q+=(tmpQP00+tmpQP11+tmpQP22)/3; 角線q+

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

13、flag 記錄本層的極值， temp記錄bool out=false;/out 記錄是否剪枝， 初始為if(max)/ 如果上一個(gè)結(jié)點(diǎn)是上確界，層則需要是下確界，記錄 flag 為無窮大；反之，則為記錄為負(fù)無窮大 flag=10000;/flag 記錄本層節(jié)點(diǎn)的極值elseflag=-10000;for(i=0;i<3 && !out;i+)for(j=0;j<3 && !out;j+)if(nowij=0)if(max) 輪到用戶玩家走了。nowij=-1; if(Checkwin()=-1) temp=-10000;elsetemp=cut(fl

14、ag,dep+1,!max); / 否則繼續(xù)調(diào)用 a-B 剪枝函數(shù) / 如果下一步棋盤的估計(jì)值小于本層節(jié)點(diǎn)的極false本/ 雙重循環(huán)，遍歷棋盤所有位置/ 如果該位置上沒有棋子/ 并且上一個(gè)結(jié)點(diǎn)為上確界，即本層為下確界/ 該位置填上用戶玩家棋子/ 如果用戶玩家贏了/ 置棋盤估計(jì)值為負(fù)無窮if(temp<flag) 值，則置本層極值為更小者flag=temp;if(flag<=val) 值，則不需要搜索下去，剪枝out=true;/ 如果本層的極值已經(jīng)小于上一個(gè)結(jié)點(diǎn)的估計(jì)else 界,輪到計(jì)算機(jī)走了。nowij=1; if(Checkwin()=1) temp=10000;else/

15、 如果上一個(gè)結(jié)點(diǎn)為下確界，即本層為上確/ 該位置填上計(jì)算機(jī)棋子/ 如果計(jì)算機(jī)贏了/ 置棋盤估計(jì)值為無窮temp=cut(flag,dep+1,!max);/ 否則繼續(xù)調(diào)用 a-B 剪枝函數(shù) if(temp>flag)flag=temp;if(flag>=val)out=true;nowij=0;/ 把模擬下的一步棋還原，回溯if(max) 極值修改上一個(gè)結(jié)點(diǎn)的估計(jì)值 if(flag>val) val=flag;/ 根據(jù)上一個(gè)結(jié)點(diǎn)是否為上確界，用本層的elseif(flag<val) val=flag; return flag;int computer()int m=-1

16、0000,val=-10000,dep=1;int x_pos,y_pos; char ch; cout<<" 您希望先走嗎 ?(y/n)" cin>>ch;while(ch!='y'&&ch!='n')cout<<" 非法輸入 !"<<" 您希望先走嗎 (y/n)"<<endl; cin>>ch; system("cls");Init();cout<<" 棋盤如下 : &q

17、uot;<<endl;PrintQP(); if(ch='n')L5:/ 函數(shù)返回的是本層的極值/m 用來存放最大的 val / 記錄最佳走步的坐標(biāo)/ 計(jì)算機(jī)先走for(int x=0;x<3;x+) for(int y=0;y<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+

18、1<<endl; PrintQP();cout<<" 電腦獲勝 ! 游戲結(jié)束 ."<<endl; return 0;if(val>m)/m 要記錄通過試探求得的棋盤狀態(tài)的最大估計(jì)值m=val; x_pos=x;y_pos=y;val=-10000; nowxy=0; nowx_posy_pos=1; val=-10000;m=-10000;dep=1;cout<<" 電腦將棋子放在 :"<<x_pos+1<<y_pos+1<<endl; PrintQP(); cou

19、t<<endl;num+;value();if(p=0)cout<<" 平局 !"<<endl; return 0;/ 玩家走一步棋 playerinput(); PrintQP(); cout<<endl; num+; value(); if(p=0) cout<<" 平局 !"<<endl; return 0; if(Checkwin()=-1) cout<<" 您獲勝 ! 游戲結(jié)束 ."<<endl; return 0;goto L5

20、;/ 人先走elseL4: playerinput();PrintQP(); cout<<endl; num+; value(); if(q=0) cout<<" 平局 !"<<endl; return 0;if (Checkwin()=-1) cout<<" 您獲勝! 游戲結(jié)束 ."<<endl; return 0;for(int x=0;x<3;x+) for(int y=0;y<3;y+) if(nowxy=0) nowxy=1; cut(val,dep,1); if(Chec

21、kwin()=1) cout<<" 電腦將棋子放在 :"<<x+1<<y+1<<endl; PrintQP();cout<<" 電腦獲勝 ! 游戲結(jié)束 ."<<endl; return 0; if(val>m) m=val; x_pos=x;y_pos=y; val=-10000; nowxy=0; nowx_posy_pos=1; val=-10000;m=-10000; dep=1;cout<<" 電腦將棋子放在 :"<<x_po

22、s+1<<y_pos+1<<endl; PrintQP();cout<<endl; num+; value();if(q=0) cout<<" 平局 !"<<endl; return 0; goto L4; return 0; int main() computer(); system("pause"); return 0;4.主要函數(shù)1估值函數(shù)估價(jià)函數(shù)：int CTic_MFCDIg:evaluate(i nt board)完成功能：根據(jù)輸入棋盤，判斷當(dāng)前棋盤的估值，估價(jià)函數(shù)為前面所講: 若是MAX的必勝局，則e = +INFINITY，這里為+60 若是MIN則不考慮其它因素。