五子棋人機對弈

【概述】五子棋是一種大眾喜愛的游戲，其規(guī)則簡單，變化多端，非常富有趣味性何消遣性。這里設(shè)計了一個簡單的五子棋程序，采用對空格點進行評分排序的算法。近來隨著計算機的快速發(fā)展，各種棋類游戲被紛紛請進了電腦，使得那些喜愛下棋，又常?？嘤跊]有對手的棋迷們能隨時過足棋癮。而且這類軟件個個水平頗高，大有與人腦分庭抗禮之勢。其中戰(zhàn)勝過國際象棋世界冠軍-卡斯帕羅夫的''深藍〃便是最具說服力的代表；其它像圍棋的''手淡〃、象棋的''將族〃等也以其優(yōu)秀的人工智能深受棋迷喜愛；而我也做了一個“無比”簡單的五子棋算法?？偟膩碚f（我們假定您熟悉五子棋的基本規(guī)則），要讓電腦知道該在哪一點下子，就要根據(jù)盤面的形勢，為每一可能落子的點計算其重要程度，也就是當這子落下后會形成什么棋型（如：''沖四〃、''活三〃等），然后通覽全盤選出最重要的一點，這便是最基本的算法。主程序模塊包括：數(shù)據(jù)結(jié)構(gòu)，評分規(guī)則，勝負判斷，搜索最優(yōu)空格的算法過程?！娟P(guān)鍵字】人工智能，博弈樹，五子棋，無禁手，評分，搜索，C，隨機。【環(huán)境】XP/TC3.0【算法及解析】（無禁手）一.數(shù)據(jù)結(jié)構(gòu)：本程序中只使用了一個19X19的二元結(jié)構(gòu)數(shù)組如下定義：TypedefStruet{int player;int value[8][5];longintscore;}map[19][19];其中map[i][jH呆存i行j列棋子信息，player為下棋方，value數(shù)組記錄八個方向的連續(xù)5個棋子的信息，為以后評分服務(wù)。Score為空格評分。以及數(shù)據(jù)結(jié)構(gòu)可以滿足初級人機對弈程序的功用。對比其他程序結(jié)構(gòu):王小春五子棋源碼：該程序采用鏈表節(jié)點結(jié)構(gòu)，保存下子信息，該結(jié)構(gòu)主要為悔棋提供方便（雖該源碼為開發(fā)悔棋功能）TypedefstruetStep{intm;intn;charside;}；為鏈表clist節(jié)點,m,n表示兩個坐標值，side表示下子方相對于我的程序中的player.另外該程序還使用一個二維數(shù)組map[][]，來保存棋盤信息。二?預(yù)定義單元TOC\o"1-5"\h\z#defineblank 0#defineblack 1#definewhite 2#defineNUM_HIGH19#defineNUM_LINE19#defineman1#definebot2其中blank表示空白點，black該點放黑子（即man）,white該點放白子（即robot）NUM_HIGH,NUM_LINE分別定義棋盤的高度與寬度。Turn為輪流下子方。三?評分機制判斷是否能成活四或者是雙死四或者是死四活三，如果是機器方的話給予10,000,000；判斷是否已成沖四，如果是機器方的話給予6，000，000；判斷是否成死3活3,如果是機器方的話給予1，500，000；；判斷是否已成雙活2,如果是機器方的話給予100，00；判斷是否能成活2,如果是機器方的話給予70,000；判斷是否能成死2,如果是機器方的話給予30,000。四?函數(shù)定義及其功能。Voidinit()初始化棋盤bgi圖形與棋盤棋型。將棋盤標記map[][].player都置為blank(空白)，各點8方向的連續(xù)五個棋子信息也初始為0,各點評分數(shù)也置為0。voidinit(){inti,j,m,n;intgdriver二DETECT,gmode;initgraph(&gdriver，&gmode,"..\\bgi");for(i=0;i<19;i++)for(j=0;j<19;j++){map[i][j].player=blank;for(m=0;m<8;m++)for(n=0;n<4;n++)map[i][j].value[m][n]=blank;map[i][j].score=blank;}}Voidpaint()畫棋盤函數(shù)，本五子棋程序使用的是標準圍棋棋盤，規(guī)格19X19，每格25大小(象素)，并且規(guī)定man棋子顏色為黑，robot為白色，黑棋優(yōu)先。最后初始化光標(開始位置)位置。voidpaint()inti,j;clearviewport();setbkcolor(BLUE);//設(shè)置背景色setcolor(WHITE);//設(shè)置作圖色for(i=20;i<=470;i+=25)line(20,i,470,i);for(j=20;j<=470;j+=25)line(j,20,j,470);outtextxy(525,160,"Man");setcolor(DARKGRAY);setfillstyle(SOLID_FILL,DARKGRAY);pieslice(545,185,0,360,10);setcolor(WHITE);outtextxy(520,210,"Robot");setcolor(WHITE);setfillstyle(SOLID_FILL,WHITE);pieslice(545,235,0,360,10);moverel(245,245);//開始游戲時man下棋的位置}voidmain()主函數(shù)控制。初始化圖形及棋型，規(guī)定黑子優(yōu)先，畫棋盤，開始下子。(略)Voidhuman()Man下棋函數(shù)，其中添加了防棋子覆蓋控制。voidhuman(void){charch=l;intsize,x,y;void*buf;while(ch!=32){ch=getch();putimage(getx()-10,gety()T0,buf,C0PY_PUT);if(ch==27)//ESC退出exit(l);if(ch=='w'||ch=='W')//移動控制單元moverel(0,-25);elseif(ch=='s' ||ch=='S')moverel(0,25);elseif(ch=='a' ||ch=='A')moverel(-25,0);elseif(ch=='d' ||ch=='D')moverel(25,0);if(getx()<20) //防止man下棋越界moverel(25,0);if(getx()>470)moverel(-25,0);if(gety()<20)moverel(0,25);if(gety()>470)moverel(0,-25);size=imagesize(getx()-10,gety()T0,getx()+10,gety()+10);buf=malloc(size);getimage(getx()-10,gety()T0,getx()+10,gety()+10,buf);if(man==black){setcolor(DARKGRAY);setfillstyle(SOLID_FILL,DARKGRAY);}else{setcolor(WHITE);setfillstyle(SOLID_FILL,WHITE);}pieslice(getx(),gety(),0,360,10); //光標顯示x=(getx()-20)/25;//計算man下棋的棋盤位置y=(gety()-20)/25;if(ch==32&&map[y][x].player!=0)//防止man棋子覆蓋ch=1;map[y][x].player=man;mark(x,y);}Voidmark(int,int)標記棋子，robot標記為白棋，man標記為黑棋。在程序結(jié)束添加了判斷下子方是否勝出(結(jié)束)判斷函數(shù)，check(int,int).voidmark(intx,inty)//標記棋子{inti,j,m,n;m=x;n=y;if(turn==man){setcolor(DARKGRAY);setfillstyle(SOLID_FILL,DARKGRAY);}else{setcolor(WHITE);setfillstyle(SOLID_FILL,WHITE);}if(turn==bot)for(x=0;x<19;x++) //bot下完子后，對評分機制初始化for(y=0;y<19;y++)if(map[x][y].player==blank){for(i=0;i<8;i++)for(j=0;j<5;j++)map[x][y].value[i][j]=blank;map[x][y].score=blank;}check(n,m);}voidcheck(int,int)判斷程序是否結(jié)束函數(shù)(一方勝利)，共判斷了四個方向：水平方向，豎直方向，左斜線方向，右斜線方向。如果發(fā)現(xiàn)存在超過或等于5各連續(xù)棋子，則判斷一方勝利，調(diào)用win(int)函數(shù)，顯示結(jié)果，程序結(jié)束。程序結(jié)尾，添加交換下子部分。voidcheck(intm,intn){intWinTag二map[m][n].player;inti二m,j二n,level=l;//outtextxy((m*25+20),(n*25+20),".");if(WinTag==man)outtextxy((n*25+17),(m*25+17),"M");elseouttextxy((n*25+17),(m*25+17),"R");//水平位置判斷while(map[i-l][j].player二二WinTag&&i>=l){level++;i—;}i=m;while(map[i+l][j].player二二WinTag&&i<(NUM_LINE-l)){level++;i++;}if(level>=5)win(WinTag);level=1;//豎直方向判斷i=m； j=n;while(map[i][j-l].player二二WinTag&&j>=1){level++;j—;}j=n;while(map[i][j+l].player二二WinTag&&j<(NUM_HIGH-l)){level++;j++;}if(level>=5)win(WinTag);level=l;//左斜線判斷i=m； j=n;while(map[i-l][j-l].player二二WinTag&&i>=l&&j>=l){level++;i--;j--;}i=m;j=n;while(map[i+l][j+l].player==WinTag&&i<(NUM_LINE-l)&&j<(NUM_HIGH-l)){level++;i++;j++;}if(level>=5)win(WinTag);level=1;//右斜線判斷i=m;j=n;while(map[i+l][j-l].player二二WinTag&&i<NUM_LINE&&j>=1){level++;i++;j--;}i=m;j=n;while(map[i-l][j+l].player二二WinTag&&i>=l&&j<(NUM_HIGH-l))level++;i--;j++;}if(level>=5)win(WinTag);//交換下棋順序if(turn==man){turn=bot; robot();}else{turn=man;human();}Voidwin(int)voidwin(intwinner){charch;setbkcolor(LIGHTGRAY);setcolor(YELLOW);//ch=getch();while(ch!=27){if(winner==man)outtextxy(240,210,""Youarethewinner!"");elseouttextxy(240,210,"Youarelost!"");outtextxy(245,250,"PressESCtoExit!〃)；printf("%d",winner);closegraph();}exit(1);}voidrobot()也是人機對弈五子棋最核心的部分，其中包括了評價機制，估值，搜索部分搜索空格的八個方向，如：1 0 27空格36 5 4最后將權(quán)值最大的幾個點的位置信息保存于xposition[]與yposition[]數(shù)組中，如果極值權(quán)重相同，使用隨機函數(shù)選擇其中一點下棋。voidrobot(void){intx,y,X,Y,i,j；int*p,*mp;//用于指向特定數(shù)組longintxposition[38],yposition[38]; //存儲相同得權(quán)值longintmax;//當前最大權(quán)值//將空格信息填入特定數(shù)組，用于bot評分并下子，將360度分成8個方向//即同一個空格可能五子相連的八個方向，具體看readme文件for(X=0;X<19;X++) //0方向檢查for(Y=18;Y>4;Y—)if(map[Y][X].player==blank)for(i=0,x=X,y=Y;y>Y-5;i++,y—)map[Y][X].value[O][i]=map[y-1][x].player;for(X=0;X<19;X++) //4方向檢查for(Y=0;Y<10;Y++)if(map[Y][X].player==blank)for(i=0,x=X,y=Y;y<Y+5;i++,y++)map[Y][X].value[4][i]=map[y+1][x].player;//'/'檢查，1方向檢查開始for(i=4;i<19;i++) //'/'檢查，1方向檢查，左上部分for(X=0,Y=i;Y>3;X++,Y—) //檢查一斜行if(map[Y][X].player==blank)for(j=0,x=X,y=Y;(y>Y-5)||(y>0);j++,x++,y--)map[Y][X].value[1][j]=map[y-1][x+1].player;for(i=1;i<11;i++)for(X=i,Y=18;X<11;X++,Y--)//1方向檢查，右下部分if(map[Y][X].player==blank)map[Y][X].value[l][j]=map[y-l][x+l].player;for(i=18;i>3;i—)//'/'檢查，5方向檢查，左上部分for(X=i,Y=0;X>3;X—,Y++)if(map[Y][X].player==blank)for(j=0,x=X,y=Y;(x>X—5)||(x>0);j++,x--,y++)map[Y][X].value[5][j]=map[y+l][xT].player;for(i=1;i<11;i++)//5方向檢查，右下部分for(X=1&Y=i;Y<11;X--,Y++)if(map[Y][X].player==blank)for(j=0,x=X,y=Y;(y<Y+5)||(y<14);j++,x--,y++)map[Y][X].value[5][j]=map[y+1][xT].player;//'/'檢查結(jié)束，5方向檢查結(jié)束for(Y=0;Y<19;Y++)//2方向檢查，從左到右for(X=0;X<10;X++)if(map[Y][X].player==blank)for(j=0,x=X,y=Y;x<X+5;j++,x++)map[Y][X].value[2][j]=map[y][x+1].player;for(Y=0;Y<19;Y++)//6方向檢查，從右到左for(X=18;X>4;X--)if(map[Y][X].player==blank)for(j=0,x=X,y=Y;x>X-5;j++,x--)map[Y][X].value[6][j]=map[y][xT].player;//'\'檢查開始，3方向檢查開始for(i=0;i<11;i++)//3方向檢查，右上部分for(X=i,Y=0;X<11;X++,Y++)if(map[Y][X].player==blank)for(j=0,x=X,y=Y;(x<X+5)||(x<18);j++,x++,y++)map[Y][X].value[3][j]=map[y+1][x+1].player;for(i=1;i<11;i++)//3方向檢查，左下部分for(X=0,Y=i;Y<11;X++,Y++)if(map[Y][X].player==blank)for(j=0,x=X,y=Y;(y<Y+5)||(y<18);j++,x++,y++)map[Y][X].value[3][j]=map[y+1][x+1].player;for(i=18;i>3;i--)//7方向檢查，右上部分for(X=1&Y=i;Y>3;X—,Y—)if(map[Y][X].player==blank)for(j=0,x=X,y=Y;(y>Y-5)||(y>0);j++,x--,y--)map[Y][X].value[7][j]=map[y-1][xT].player;for(i=17;i>3;i--)//7方向檢查，左下部分for(X=i,Y=18;X>3;X--,Y--)if(map[Y][X].player==blank)for(j=0,x=X,y=Y;(x>X-5)||(x>0);j++,x--,y--)map[Y][X].value[7][j]=map[y-1][x-1].player;//'\'檢查結(jié)束，7方向檢查結(jié)束，bot檢查棋盤空格結(jié)束//進入bot判斷，對棋盤上每一個空格進行評分for(y=0;y<19;y++)for(x=0;x<19;x++)if(map[y][x].player==blank)for(i=0;i<8;i++){//for控制對一個空格的8個方向評分p=&map[y][x].value[i][O];//mp與p剛好組成空格的兩頭if(i<4)mp=&map[y][x].value[i+4][0];elsemp=&map[y][x].value[i-4][0];//b為bot,m為man,o為空格，x為評分點//己方已經(jīng)可以贏，或是對方可能有四子相連的評分為100,000,000—億的情況if(*p==bot&&*(p+1)==bot&&*(p+2)==bot&&*(p+3)==bot)map[y][x].score+=100000000;if(*p==man&&*(p+1)==man&&*(p+2)==man&&*(p+3)==man)map[y][x].score+=100000000;if(*p==bot&&*(p+1)==bot&&*(p+2)==bot&&*mp==bot)map[y][x].score+=100000000;if(*p==man&&*(p+1)==man&&*(p+2)==man&&*mp==man)map[y][x].score+=100000000;if(*p==man&&*(p+1)==man&&*mp==man&&*(mp+1)==man)map[y][x].score+=100000000;//活四評分為10,000,000—千萬的情況if(*p==bot&&*(p+1)==bot&&*(p+2)==bot&&*(p+3)==blank&&*mp==blank)map[y][x].score+=10000000;if(*p==man&&*(p+1)==man&&*(p+2)==man&&*(p+3)==blank)map[y][x].score+=10000000;if(*p==bot&&*(p+1)==bot&&*(p+2)==blank&&*mp==man&&*(mp+1)==blank)map[y][x].score+=10000000;if(*p==man&&*(p+1)==man&&*(p+2)==blank&&*mp==man&&*(mp+1)==blank)map[y][x].score+=10000000;if(*p==blank&&*(p+1)==bot&&*(p+2)==bot&&*(p+3)==bot&&*(p+4)==blank&&*mp==blank)map[y][x].score+=10000000;//沖四評分為8,000,000八百萬的情況if(*p==bot&&*(p+1)==bot&&*(p+2)==bot&&*(p+3)==man&&*mp==blank)map[y][x].score+=8000000;if(*p==bot&&*(p+1)==bot&&*(p+2)==man&&*mp==bot&&*(mp+1)==blank)map[y][x].score+=8000000;if(*mp==blank&&*p==blank&&*(p+1)==bot&&*(p+2)==bot&&*(p+3)==bot&&*(p+4)==man)map[y][x].score+=8000000;if(*mp==bot&&*(mp+1)==blank&&*p==blank&&*(p+1)==bot&&*(p+2)==bot&&*(p+3)==man)map[y][x].score+=8000000;//防對方?jīng)_四評分為6,000,000的情況if(*p==man&&*(p+1)==man&&*(p+2)==man&&*(p+3)==bot&&*mp==blank)map[y][x].score+=6000000;if(*p==man&&*(p+1)==man&&*(p+2)==bot&&*mp==man&&*(mp+1)==blank)map[y][x].score+=6000000;//活三評分為4,000,000四百萬的情況if(*p==bot&&*(p+1)==bot&&*(p+2)==blank&&*mp==blank)map[y][x].score+=4000000;if(*p==man&&*(p+1)==man&&*(p+2)==blank&&*mp==blank)map[y][x].score+=4000000;if(*p==man&&*(p+1)==blank&&*(p+2)==man&&*(p+3)==blank&&*mp==blank)map[y][x].score+=4000000;if(*p==bot&&*(p+1)==blank&&*mp==bot&&*(mp+1)==blank)map[y][x].score+=4000000;if(*p==man&&*(p+1)==blank&&*mp==bot&&*(mp+1)==blank)//死三評分為1,500,000—百五十萬的情況，進攻為主if(*p==bot&&*(p+1)==bot&&*(p+2)==man&&*mp==blank)map[y][x].score+=1500000;if(*p==bot&&*(p+1)==man&&*mp==bot&&*(mp+1)==blank)map[y][x].score+=1500000;if(*mp==man&&*p==bot&&*(p+1)==bot&&*(p+2)二二blank)map[y][x].score+=1500000;if(*mp==blank&&*p==blank&&*(p+1)==bot&&*(p+2)==bot&&*(p+3)==man)map[y][x].score+=1500000;//活二評分為100,000十萬的情況if(*p==bot&&*(p+1)==blank&&*mp==blank)map[y][x].score+=100000;if(*p==blank&&*(p+1)==bot&&*(p+2)==blank&&*mp==blank)map[y][x].score+=100000;//活二評分為70,000七萬的情況if(*p==man&&*(p+1)==blank&&*mp==blank)map[y][x].score+=70000;if(*p==blank&&*(p+1)==man&&*(p+2)==blank&&*mp==blank)map[y][x].score+=70000;//沖二評分為30,000三萬的情況if(*mp==blank&&*p==bot&&*(p+1)==man)map[y][x].score+=30000;if(*mp==blank&&*p==blank&&*(p+1)==bot&&*(p+2)==man)map[y][x].score+=30000;//沖二評分為10,000—萬的情況，防守為主if(*mp==blank&&*p==man&&*(p+1)==bot)map[y][x].score+=10000;//開局情況，并限定下子范圍if(step==blank){do{x=random(19);y=random(19);if(map[y][x].player!=blank)x=blank;y-10>0);}while(x-5<0||x-10>0||yy-10>0);step+=1;}}max=blank; //權(quán)值評分機制初始化for(y=0;y<19;y++) //搜尋權(quán)值最大點for(x=0;x<19;x++)if(map[y][x].player==blank){if(map[y][x].score>max){max=map[y][x].score;for(i=0;i<38;i++)xposition[i]二blank;yposition[i]二blank;xposition[0]二x;yposition[0]二y;}elseif(map[y][x].score==max){i+=1；xposition[i]二x;xposition[i]二y;}}if(xposition[2]==blank)//選擇最大權(quán)值點做下子點{map[yposition[0]][xposition[0]].player=bot;mark(xposition[0],yposition[0]);}else//在最大權(quán)值相等的位置中隨機選擇下子點*/{i=random(lO);x=xposition[i];y=yposition[i];map[y][x].player=bot;mark(x,y);【相關(guān)知識】篇幅所限制，活三，沖四等棋型在此就不贅述.【心得體會】通過本次實踐，初步掌握了五子棋“人機博弈”的基本算法，由于開發(fā)較為智能的程序，算法復(fù)雜度較高，固在此只進行了一層搜索。采用博弈樹的算法，搜索最佳位置后，然后剪枝，選擇最優(yōu)。實際上按照王小春的說法，要進行深度為4搜索，計算機可能要思考15秒左右，算法時間性能較差，況且時間較倉促，沒有進行更深層次的思考，期間遇到不少挫折，程序規(guī)模較以前相比龐大了不少，參照了不少源碼（15X15）。人工智能算法博大精深，日前在網(wǎng)上看到一種所謂“稀疏矩陣”的算法，采用“易語言”編譯，時間性能尚可。有機會向作者請教請教?！緟⒖嘉墨I及相關(guān)資料】《PC游戲編程（人機博弈）》 王小春《算法分析與設(shè)計技術(shù)》 馬紹漢CSDN專欄Programfan.Com論壇baker五子棋是一種受大眾廣泛喜愛的游戲，其規(guī)則簡單，變化多端，非常富有趣味性和消遣性這里設(shè)計和實現(xiàn)了一個人機對下的五子棋程序，采用了博弈樹的方法，應(yīng)用了剪枝和最大最小樹原理進行搜索發(fā)現(xiàn)最好的下子位置。介紹五子棋程序的數(shù)據(jù)結(jié)構(gòu)、評分規(guī)則、勝負判斷方法和搜索算法過程。一、相關(guān)的數(shù)據(jù)結(jié)構(gòu)關(guān)于盤面情況的表示，以鏈表形式表示當前盤面的情況，目的是可以允許用戶進行悔棋、回退等操作。CListStepList;其中Step結(jié)構(gòu)的表示為：structStep{intm;//m,n表示兩個坐標值intn;charside;//side表示下子方};以數(shù)組形式保存當前盤面的情況，目的是為了在顯示當前盤面情況時使用：charFiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE];其中FIVE_MAX_LINE表示盤面最大的行數(shù)。同時由于需要在遞歸搜索的過程中考慮時間和空間有效性，只找出就當前情況來說相對比較好的幾個盤面，而不是對所有的可下子的位置都進行搜索，這里用變量CountList來表示當前搜索中可以選擇的所有新的盤面情況對象的集合：CListCountList;其中類CBoardSituiton為:classCBoardSituation{CListStepList;//每一步的列表charFiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE];structStepmachineStep;//機器所下的那一步doublevalue;//該種盤面狀態(tài)所得到的分數(shù)}二、評分規(guī)則對于下子的重要性評分，需要從六個位置來考慮當前棋局的情況，分別為：-二/\//,\\實際上需要考慮在這六個位置上某一方所形成的子的布局的情況，對于在還沒有子的地方落子以后的當前局面的評分，主要是為了說明在這個地方下子的重要性程度，設(shè)定了一個簡單的規(guī)則來表示當前棋面對機器方的分數(shù)。基本的規(guī)則如下：判斷是否能成5,如果是機器方的話給予100000分，如果是人方的話給予－100000分；判斷是否能成活4或者是雙死4或者是死4活3，如果是機器方的話給予10000分，如果是人方的話給予－10000分；判斷是否已成雙活3，如果是機器方的話給予5000分，如果是人方的話給予－5000分；判斷是否成死3活3，如果是機器方的話給予1000分，如果是人方的話給予－1000分；判斷是否能成死4，如果是機器方的話給予500分，如果是人方的話給予－500分；判斷是否能成單活3，如果是機器方的話給予200分，如果是人方的話給予－200分；判斷是否已成雙活2，如果是機器方的話給予100分，如果是人方的話給予－100分；判斷是否能成死3，如果是機器方的話給予50分，如果是人方的話給予－50分；判斷是否能成雙活2，如果是機器方的話給予10分，如果是人方的話給予－10分；判斷是否能成活2，如果是機器方的話給予5分，如果是人方的話給予－5分；判斷是否能成死2，如果是機器方的話給予3分，如果是人方的話給予－3分。實際上對當前的局面按照上面的規(guī)則的順序進行比較，如果滿足某一條規(guī)則的話，就給該局面打分并保存，然后退出規(guī)則的匹配。注意這里的規(guī)則是根據(jù)一般的下棋規(guī)律的一個總結(jié)，在實際運行的時候，用戶可以添加規(guī)則和對評分機制加以修正。三、勝負判斷實際上，是根據(jù)當前最后一個落子的情況來判斷勝負的。實際上需