1、 數(shù) 學(xué) 與 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院三子棋游戲(yux)設(shè)計(jì)(shj)報(bào)告 課程名稱： 人工智能(rn n zh nn)原理及其應(yīng)用 年級專業(yè)： 11級計(jì)算機(jī)科學(xué)與技術(shù) 任課教師： 楊 炎 設(shè)計(jì)時(shí)間： 2014年4月20 日 小組成員： 姓 名 學(xué) 號 韓 磊 136263010068 張 雨 136263010064 孟 帝 136263010073目錄(ml) TOC o 1-3 h z u HYPERLINK l _Toc385967096 第一章：三子棋游戲軟件描述(mio sh) PAGEREF _Toc385967096 h 3 HYPERLINK l _Toc38596709

2、7 1.1 三子棋游戲(yux)簡介 PAGEREF _Toc385967097 h 3 HYPERLINK l _Toc385967098 1.2 軟件功能介紹 PAGEREF _Toc385967098 h 3 HYPERLINK l _Toc385967099 1.3 限制條件 PAGEREF _Toc385967099 h 3 HYPERLINK l _Toc385967100 第二章：軟件功能描述 PAGEREF _Toc385967100 h 3 HYPERLINK l _Toc385967101 第三章：三子棋游戲的分析 PAGEREF _Toc385967101 h 4 HYP

3、ERLINK l _Toc385967102 3.1 流程圖如下： PAGEREF _Toc385967102 h 4 HYPERLINK l _Toc385967103 3.2 程序所用到的算法分析： PAGEREF _Toc385967103 h 5 HYPERLINK l _Toc385967104 第四章：游戲程序 PAGEREF _Toc385967104 h 5 HYPERLINK l _Toc385967105 第五章：程序運(yùn)行圖 PAGEREF _Toc385967105 h 19 HYPERLINK l _Toc385967106 5.1 是否開始游戲進(jìn)行選擇。 PAGERE

4、F _Toc385967106 h 19 HYPERLINK l _Toc385967107 5.2 先下一方下棋 PAGEREF _Toc385967107 h 19 HYPERLINK l _Toc385967108 5.3 判斷勝利一方 PAGEREF _Toc385967108 h 19 HYPERLINK l _Toc385967109 5.4 判斷和棋 PAGEREF _Toc385967109 h 19第一章：三子棋游戲軟件描述(mio sh)1.1 三子棋游戲(yux)簡介 三子棋是一種人與機(jī)器對弈的小游戲，一方先下，輪流下棋(xi q)，直到一方先將三個(gè)棋子連成一條線，就可以

5、取勝。 1.2 軟件功能介紹井字棋游戲，也就是三子棋游戲。棋盤大小為33，在方格內(nèi)下棋，對弈雙方輪流下棋。只要有一方有3顆棋子連成一條線(行、列及對角線)，則該方獲勝，且游戲結(jié)束。如果所有位置都已經(jīng)下滿棋子，且沒有哪一方能贏棋，則是和棋。1.3 限制條件該程序必須在C+6.0環(huán)境中運(yùn)行。模式選擇時(shí)，不管輸入何種值，只要不是要求的輸入都是無效的。第二章： 軟件功能描述用戶進(jìn)入游戲后選擇2項(xiàng)其中之一:Y/N用戶進(jìn)入游戲開始界面后，玩游戲的人先下，然后電腦再下。用戶(yngh)進(jìn)入游戲后，根據(jù)屏幕的棋圖輸入第幾行第幾列，每次輸入一個(gè)值后，電腦也會對應(yīng)輸入值。當(dāng)棋盤上出現(xiàn)-1和1填滿棋盤時(shí)，電腦會判斷

6、那方勝利，或者判斷是否是和棋，然后游戲(yux)結(jié)束。第三章： 三子棋游戲(yux)的分析 游戲界面關(guān)閉游戲退出游戲是否進(jìn)行新游戲判斷和棋判斷輸贏進(jìn)行對弈人機(jī)對戰(zhàn)游戲模式開 始3.1 流程圖如下：3.2 程序所用到的算法(sun f)分析：1. 計(jì)算某個(gè)棋局狀態(tài)中甲方是否已經(jīng)(y jing)勝出算法：對矩陣(j zhn)的列，行，斜線求和。若和為3，則甲已經(jīng)勝出，否則返回02.計(jì)算中某個(gè)棋局狀態(tài)中甲方或乙方全占滿的行，列，斜線數(shù)總和把矩陣中和為3的行數(shù)，列數(shù)，斜線數(shù)總和返回3.計(jì)算估價(jià)函數(shù)值算法：對某個(gè)棋局狀態(tài)，首先把該棋局狀態(tài)的空格塞滿甲方的棋子，算出現(xiàn)在甲方棋子占滿整行，整列，整斜線的總數(shù)

7、。然后在原來的棋局狀態(tài)的空格塞滿乙方的棋子，算出乙方棋子占滿整行，整列，整斜線的總數(shù)。然后求兩者差。4.使用的-剪枝技術(shù)的基本思想或算法： 邊生成博弈樹邊計(jì)算評估各節(jié)點(diǎn)的倒推值，并且根據(jù)評估值的倒推值的范圍，及時(shí)停止擴(kuò)展那些已無必要再擴(kuò)展的子節(jié)點(diǎn)，即相當(dāng)于剪去了博弈樹上的一些分枝，從而節(jié)約了機(jī)器開銷，提高了搜索效益。第四章： 游戲程序#includeint num=0; /記錄棋盤上棋子的個(gè)數(shù)int p,q; int tmpQP33; /表示棋盤數(shù)據(jù)的臨時(shí)數(shù)組，其中的元素0表示該格為空，int cur33; /存儲當(dāng)前棋盤的狀態(tài)const int depth=3; /搜索樹的最大深度void

8、Init() /初始化棋盤(qpn)狀態(tài) for(int i=0;i3;i+)for(int j=0;j3;j+)curij=0;void PrintQP() /打印(d yn)棋盤當(dāng)前狀態(tài)for(int i=0;i3;i+)for(int j=0;j3;j+)coutcurijt;coutendl; void UserInput()/用戶通過(tnggu)此函數(shù)來輸入落子的位置，比如：用戶輸入31，則表示用戶在第3行第1列落子。int pos,x,y;L1: coutpos;x=pos/10,y=pos%10;if(x0&x0&y4&curx-1y-1=0)curx-1y-1=-1;else

9、coutInput Error!;goto L1;int CheckWin() /檢查是否有一方(y fn)贏棋（返回 0：沒有任何一方贏；1：計(jì)算機(jī)贏；-1：人贏） /該方法(fngf)沒有判斷平局for(int i=0;i3;i+)if(curi0=1&curi1=1&curi2=1)return 1;if(curi0=-1&curi1=-1&curi2=-1)return -1;for(i=0;i3;i+)if(cur0i=1&cur1i=1&cur2i=1)return 1;if(cur0i=-1&cur1i=-1&cur2i=-1)return -1;if(cur00=1&cur11

10、=1&cur22=1)|(cur20=1&cur11=1&cur02=1)return 1;if(cur00=-1&cur11=-1&cur22=-1)|(cur20=-1&cur11=-1&cur02=-1)return -1;return 0;int value()/評估當(dāng)前棋盤狀態(tài)的值（同時(shí)可以(ky)用p或q判斷是否平局）p=0;q=0;for(int i=0;i3;i+) /計(jì)算機(jī)一方(y fn) /將棋盤中的空格(kn )填滿自己的棋子，既將棋盤數(shù)組中的0變?yōu)?for(int j=0;j3;j+)if(curij=0)tmpQPij=1;elsetmpQPij=curij; for

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

12、ij;for(i=0;i3;i+) /計(jì)算(j sun)共有多少連成3個(gè)-1的行q+=(tmpQPi0+tmpQPi1+tmpQPi2)/3;for(i=0;i3;i+) /計(jì)算(j sun)共有多少連成3個(gè)-1的列q+=(tmpQP0i+tmpQP1i+tmpQP2i)/3;q+=(tmpQP00+tmpQP11+tmpQP22)/3;/計(jì)算(j sun)共有多少連成3個(gè)-1的對角線q+=(tmpQP20+tmpQP11+tmpQP02)/3;return p+q; /返回評估出的棋盤狀態(tài)的值int cut(int &val,int dep,bool max)/主算法部分，實(shí)現(xiàn)a-B剪枝的算

13、法，val為上一層的估計(jì)值，dep為搜索深度，max記錄上一層是否為極大層 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; /flag記錄本層的極值，temp記錄下層求得的估計(jì)值 bool out=false; /out記錄是否剪枝，初始為false /*if(CheckWin()=1) /如果計(jì)算機(jī)贏了，就置上一層的估計(jì)值為無窮（用很大的值代表無窮） val=10000; return 0; */ if(max) /如果(rgu)上一層是極大

14、層，本層則需要是極小層，記錄flag為無窮大；反之，則為記錄為負(fù)無窮大flag=10000; /flag記錄本層節(jié)點(diǎn)(ji din)的極值 else flag=-10000; for(i=0;i3 & !out;i+) /雙重循環(huán)，遍歷棋盤(qpn)所有位置 for(j=0;j3 & !out;j+) if(curij=0) /如果該位置上沒有棋子 if(max) /并且上一層為極大層，即本層為極小層,輪到用戶玩家走了。 curij=-1; /該位置填上用戶玩家棋子 if(CheckWin()=-1) /如果用戶玩家贏了temp=-10000; /置棋盤估計(jì)值為負(fù)無窮 else temp=cu

15、t(flag,dep+1,!max); /否則繼續(xù)調(diào)用a-B剪枝函數(shù) if(tempflag) /如果下一步棋盤的估計(jì)值小于本層節(jié)點(diǎn)的極值，則置本層極值為更小者 flag=temp; if(flagflag) flag=temp; if(flag=val) out=true; curij=0; /把模擬下的一步棋還原，回溯 if(max) /根據(jù)上一層是否為極大層，用本層的極值修改上一層的估計(jì)值 if(flagval) val=flag; else if(flagval) val=flag; return flag; /函數(shù)返回(fnhu)的是本層的極值int main()/主程序int m=

16、-10000,val=-10000,dep=1; /m用來(yn li)存放最大的valint x_pos,y_pos; /記錄(jl)最佳走步的坐標(biāo)Init();coutQipan: endl;PrintQP();char IsFirst;coutIsFirst;while(IsFirst!=y&IsFirst!=n)coutERROR!IsFirst;if(IsFirst=n)/計(jì)算機(jī)先走L5:for(int x=0;x3;x+)for(int y=0;y3;y+)if(curxy=0)curxy=1;cut(val,dep,1);/計(jì)算機(jī)試探的走一步棋，棋盤狀態(tài)(zhungti)改變了，

17、在該狀態(tài)下計(jì)算出深度為dep-1的棋盤狀態(tài)估計(jì)值valif(CheckWin()=1)coutThe computer put the qizi at:x+1y+1endl;PrintQP();coutThe computer WIN! GAME OVER.m) /m要記錄通過試探(shtn)求得的棋盤狀態(tài)的最大估計(jì)值m=val;x_pos=x;y_pos=y;val=-10000;curxy=0;curx_posy_pos=1;val=-10000;m=-10000;dep=1;coutThe computer put the qizi at:x_pos+1y_pos+1endl;Print

18、QP();coutendl;num+;value();if(p=0)coutDOWN GAME!endl;return 0;UserInput(); /玩家走一步棋PrintQP(); coutendl;num+;value();if(p=0)coutDOWN GAME!endl;return 0;if(CheckWin()=-1)coutConguatulations! You Win! GAME OVER.endl;return 0;goto L5;else /人先走 L4:UserInput(); PrintQP();coutendl;num+;value();if(q=0)coutDOWN GAME!endl;return 0;if (CheckWin()=-1)c