五子棋人机对战

五子棋人机对战

-

五子棋人机博弈实验报告

目录

一(课程设计目的………………………………………2二(课程设计要

求………………………………………2三(课程设计内

容………………………………………2四(课程设计思

想………………………………………2五(系统实

现……………………………………………2

设计平台………………………………………2

数据结构设计…………………………………3

程序流程图设计………………………………3

主要算法设计…………………………………4

程序调试及运行结果…………………………4六(课程设计总

结………………………………………5七(参考资

料……………………………………………6八(附录:五子棋博弈算法源代

码……………………7

1

一(课程设计目的

通过上学期学习的《人工智能》学科，运用推理技术、搜索方法和决策

规划和博弈树设计五子棋人机博弈系统，以此进一步深化对理论知识技术的

了解，培养学生编程能力以及实践水平。

二(课程设计要求

通过本次课程设计要求学生掌握以下内容:

1.深入了解博弈树和alpha-beta剪枝算法。

2.设计出适合五子棋算法的启发式函数。

3.熟练掌握启发式的搜索方法。

三(课程设计内容

本系统实现的是五子棋博弈算法，运用java语言实现了图形用户界面，

方便用户使用。算法采用了博弈算法和启发式函数进行搜索，人机对弈可自

动判断输赢，结束后可重新开局。

四(课程设计思想

本系统实现的是五子棋博弈算法，为了方便用户的使用，采用的是java图形

用户界面技术。为了记录棋盘的每一个下棋点，定义数组array[19][19]。并用

shape[16][16][5]记录所有获胜的组合。首先由玩家落子，前两步电脑根据玩家的

落子情况在附近随机落子，第三步电脑开始搜索，并根据玩家落子情况对棋盘进行

全局搜索(Scan)并排序(Sort)，并对每一个落子点进行打分并选择分值最大的点

(Evaluate)落子，判断玩家或电脑是否获胜(Judge)，一方获胜则结束。五(系统

实现

1.实验平台:

myeclipse8.5

2

2.数据结构设计:

(1)intarray[19][19]:记录棋盘的每一个下棋点

(2)intmax_x:记录最大评估值的横坐标

intmax_y:记录最大评估值的纵坐标

intmax:记录最大评估值

(3)intshape[16][16][5]:记录所有获胜组合3.程序流程图设计:

开始

玩家落子

是

玩家是否获胜

电脑对棋盘进行搜索，对每个点

打分，记录最大值及其位置

电脑选择分值最大的点落子否

电脑是否获胜

是

是否重新开局

是

否

结束

3

4.主要算法设计:

(1)classChessPad:绘制棋盘棋子，初始化棋盘，添加鼠标点击事件。

(2)classChessPoint_black:黑棋下棋的走法和显示

(3)classChessPoint_white:白棋下棋的走法和显示

(4)classChess:棋盘属性的设置

(5)classEvaluate:对每一步可选择的方法进行打分，选择最大值,记录

坐标。

(6)classScan:查看八个方向上相邻相同颜色棋子的个数。

(7)classJudge:判断是否有一方获得胜利。

(8)classAutoPlay:电脑的下棋走法，依据玩家当前的落子位置来判断

自己的走子位置。

5.运行结果:

(1)人机对弈，黑棋为人操作，白棋为计算机操作，人赢得胜利的页面截图如

下:

4

(2)人机对弈，黑棋为人操作，白棋为计算机操作，计算机赢得胜利的页面截

图如下:

六(课程设计总结:

通过小组合作完成五子棋人机博弈系统，自己更透彻的了解

了上学期学习的《人工智能》教授的知识，可谓一大收获;同时

更强化了VisualC++的一些基本技术，捡回了选修课讲过的很多

相关知识，可谓是另一大收获。在对五子棋人机博弈的估值搜索

算法的设计上，采用博弈搜索的方法，采用静态估值函数对各节

点的代价进行估计，使算法达到最优。小组合作区别与自己独立

实验，此一形式，让我们扬长避短，体味到了团队合作的快乐～

5

七(参考资料:

[1]蔡自兴(人工智能及其应用[M](北京:清华大学出版社，1999[2]王小春

(游戏编程(人机博弈)[M](重庆:重庆大学出版社，2002[3]潘金贵，顾铁成，曾

俭等编译(现代计算机常用数据结构和算法[M](南京:南京大学

出版社，1994

[4]王永庆(人工智能原理与方法[M](西安:西安交通大学出版社，1998[5]

林尧瑞，马少平(人工智能导论[M](北京:清华出版社，1989[6]田盛丰，黄厚宽

(人工智能与知识工程[M](北京:中国铁道出版社，1999[7]王镌(博弈树搜索的算

法改进[J](福建电脑(2004，(2)

[8]VisualC++游戏设计入门.机械工业出版社普悠玛数科技著[9]标准

C++实用教程.电子工业出版社康晓明汪涛等编著[10]C++面向对象程序设计—

—陈维兴林小茶编著中国铁道出版社[11]五子棋必读——作者:彭建国编

6

附录:五子棋博弈算法源代码:

.*;

.*;

classChessPadextendsPanelimplements

MouseListener,ActionListener{

intarray[][]=newint[19][19];

Scanscanp=newScan();

Scanscanc=newScan();

AutoPlayautoPlay=newAutoPlay();

Evaluateevaluatep=newEvaluate();

Evaluateevaluatec=newEvaluate();

Sortsort=newSort();

inti=0;

intx=-1,y=-1,棋子颜色=1;

Buttonbutton=newButton("重新开局");

TextFieldtext_1=newTextField("请黑棋下子"),

text_2=newTextField(),

text_3=newTextField();

ChessPad(){//棋盘初始化

setSize(440,440);

setLayout(null);setBackground(_GRAY);

addMouseListener(this);add(button);nds(10,5,60,26);

ionListener(this);

add(text_1);text_nds(90,5,90,24);

add(text_2);text_nds(290,5,90,24);

add(text_3);text_nds(200,5,80,24);

for(inti=0;i<19;i++)

for(intj=0;j<19;j++)

{array[i][j]=0;}

for(inti=0;i<19;i++)

for(intj=0;j<19;j++)

for(inth=0;h<5;h++)

{[i][j][h]=0;

[i][j][h]=0;}

text_table(false);

text_table(false);

text_table(false);

}

publicvoidpaint(Graphicsg){//棋盘布局

for(inti=40;i<=400;i=i+20){

ne(40,i,400,i);

}

7

for(intj=40;j<=400;j=j+20){

ne(j,40,j,400);

}

al(97,97,6,6);//棋盘上的五个什么点

al(337,97,6,6);

al(97,337,6,6);

al(337,337,6,6);

al(217,217,6,6);

}

publicvoidmousePressed(MouseEvente){

inta=0,b=0;

if(ifiers()==1_MASK){//鼠标点击，判断是否

可以落子

x=(int)();y=(int)();

ChessPoint_blackchesspoint_black=newChessPoint_black(this);

ChessPoint_whitechesspoint_white=newChessPoint_white(this);

i++;

text_t("这是第"+i+"步");

if((x+5)/20<2||(y+5)/2019||(y-5)/20>19)//局外

{}

else{a=(x+10)/20;b=(y+10)/20;

if(array[b-2][a-2]==0&&棋子颜色==1){//用变量棋子颜色来判断是黑还

是白下子

(chesspoint_black);

chesspoint_nds(a*20-9,b*20-9,18,18);

棋子颜色=棋子颜色*(-1);

array[b-2][a-2]=1;

if((array,1)){

text_t("黑棋赢!");棋子颜色=2;removeMouseListener(this);}

else{

text_t("");}

}

}

8

if(i>2&&棋子颜色==-1){//电脑下子

(array,1);

(array,-1);

();

();

te();

te();

棋子颜色=棋子颜色*(-1);

(chesspoint_white);

if(>){

chesspoint_nds((_y+2)*20-

9,(_x+2)*20-9,18,18);

array[_x][_y]=-1;

text_t("请黑棋下子");

for(inti=0;i<19;i++)

for(intj=0;j<19;j++)

for(inth=0;h<5;h++)

{[i][j][h]=0;

[i][j][h]=0;}

}

else

{

chesspoint_nds((_y+2)*20-

9,(_x+2)*20-9,18,18);

array[_x][_y]=-1;

if((array,-1))

{

text_t("白棋赢!");棋子颜色=2;removeMouseListener(this);}

else{

text_t("请黑棋下子");

for(inti=0;i<19;i++)

for(intj=0;j<19;j++)

for(inth=0;h<5;h++)

9

{[i][j][h]=0;

[i][j][h]=0;}

}

}

}

if(i<=2&&棋子颜色==-1)

{

ay(array,b-2,a-2);

(chesspoint_white);

棋子颜色=棋子颜色*(-1);

chesspoint_nds((autoPlay.y+2)*20-9,(autoPlay.x+2)*20-

9,18

,18);

array[autoPlay.x][autoPlay.y]=-1;

if((array,-1))

{

text_t("白棋赢!");棋子颜色=2;removeMouseListener(this);}

else{

text_t("请黑棋下子");

text_t(autoPlay.x+""+autoPlay.y);}

}

}

}

publicvoidmouseReleased(MouseEvente){}publicvoid

mouseEntered(MouseEvente){}publicvoidmouseExited(MouseEvente){}

publicvoidmouseClicked(MouseEvente){}

publicvoidactionPerformed(ActionEvente)

{All();

棋子颜色=1;

add(button);nds(10,5,60,26);

add(text_1);text_nds(90,5,90,24);

text_t("");

text_t("请黑棋下子");

add(text_2);

text_nds(290,5,90,24);

add(text_3);text_nds(200,5,80,24);

i=0;

text_t("这是第"+i+"步");

10

for(inti=0;i<19;i++)

for(intj=0;j<19;j++)

{array[i][j]=0;}

for(inti=0;i<19;i++)

for(intj=0;j<19;j++)

for(inth=0;h<5;h++)

{[i][j][h]=0;

[i][j][h]=0;}

addMouseListener(this);

}

}

classChessPoint_blackextendsCanvasimplementsMouseListener{

ChessPadchesspad=null;

ChessPoint_black(ChessPadp){

setSize(20,20);

addMouseListener(this);

chesspad=p;

}

publicvoidpaint(Graphicsg){

or();al(0,0,18,18);

}

publicvoidmousePressed(MouseEvente){

/*if(ifiers()==3_MASK){

(this);

chesspad.棋子颜色=1;

_t("");

_t("请黑棋下子");

}*/

}

publicvoidmouseReleased(MouseEvente){}

publicvoidmouseEntered(MouseEvente){}

publicvoidmouseExited(MouseEvente){}

publicvoidmouseClicked(MouseEvente){

}

}

classChessPoint_whiteextendsCanvasimplementsMouseListener{

ChessPadchesspad=null;

ChessPoint_white(ChessPadp){

setSize(20,20);addMouseListener(this);

chesspad=p;

}

publicvoidpaint(Graphicsg){

or();al(0,0,18,18);

11

}

publicvoidmousePressed(MouseEvente){

/*if(ifiers()==3_MASK){

(this);

chesspad.棋子颜色=-1;

_t("请白棋下子");

_t("");

}*/

}

publicvoidmouseReleased(MouseEvente){}

publicvoidmouseEntered(MouseEvente){}

publicvoidmouseExited(MouseEvente){}

publicvoidmouseClicked(MouseEvente){

}

}

publicclassChessextendsFrame{

ChessPadchesspad=newChessPad();

Chess(){

setVisible(true);

setLayout(null);

Labellabel=newLabel("五子棋",);

add(label);nds(70,55,440,26);

kground();

add(chesspad);nds(70,90,440,440);

addWindowListener(newWindowAdapter()

{publicvoidwindowClosing(WindowEvente)

{(0);}

});

pack();setSize(600,550);

}

publicstaticvoidmain(Stringargs[]){

Chesschess=newChess();

}

}

12

publicclassAutoPlay{//前2步棋走法

intx,y;

voidautoPlay(intchesspad[][],inta,intb){

intrandomNumber=(int)(()*8)+1;

switch(randomNumber){

case(1):

if(chesspad[a-1][b-1]==0)

{x=a-1;y=b-1;}

elseif(chesspad[a-2][b-2]==0)

{x=a-2;y=b-2;}

else{x=a-3;y=b-3;}

break;

case(2):

if(chesspad[a-1][b]==0)

{x=a-1;y=b;}

elseif(chesspad[a-2][b]==0)

{x=a-2;y=b;}

else{x=a-3;y=b;}

break;

case(3):

if(chesspad[a-1][b+1]==0)

{x=a-1;y=b+1;}

elseif(chesspad[a-2][b+2]==0)

{x=a-2;y=b+2;}

else{x=a-3;y=b+3;}

break;

case(4):

if(chesspad[a][b+1]==0)

{x=a;y=b+1;}

elseif(chesspad[a][b+2]==0)

{x=a;y=b+2;}

else{x=a;y=b+3;}

break;

case(5):

if(chesspad[a+1][b+1]==0)

{x=a+1;y=b+1;}

elseif(chesspad[a+2][b+2]==0)

{x=a+2;y=b+2;}

else{x=a+3;y=b+3;}

break;

case(6):

if(chesspad[a+1][b]==0)

{x=a+1;y=b;}

13

elseif(chesspad[a+2][b]==0)

{x=a+2;y=b;}

else{x=a+3;y=b;}

break;

case(7):

if(chesspad[a+1][b-1]==0)

{x=a+1;y=b-1;}

elseif(chesspad[a+2][b-2]==0)

{x=a+2;y=b-2;}

else{x=a+3;y=b-3;}

break;

case(8):

if(chesspad[a][b-1]==0)

{x=a;y=b-1;}

elseif(chesspad[a][b-2]==0)

{x=a;y=b-2;}

else{x=a;y=b+3;}

break;

}

}

}

publicclassEvaluate{

intmax_x,max_y,max;

publicvoidevaluate(intshape[][][]){

inti=0,j=0;

for(i=0;i<19;i++)

for(j=0;j<19;j++){

switch(shape[i][j][0]){

case5:

shape[i][j][4]=200;

break;

case4:

switch(shape[i][j][1]){

case4:

shape[i][j][4]=150+shape[i][j][2]+

shape[i][j][3];

14

break;

case3:

shape[i][j][4]=100+

shape[i][j][2]+

shape[i][j][3];

break;

default:

shape[i][j][4]=50+

shape[i][j][2]+

shape[i][j][3];

}

break;

case3:

switch(shape[i][j][1]){

case3:

shape[i][j][4]=75+

shape[i][j][2]+

shape[i][j][3];

break;

default:

shape[i][j][4]=20+

shape[i][j][2]+

shape[i][j][3];

}

break;

case2:

shape[i][j][4]=10+shape[i][j][1]

+shape[i][j][2]

+shape[i][j][3];

break;

case1:

shape[i][j][4]=shape[i][j][0]+shape[i][j][1]

+shape[i][j][2]

+shape[i][j][3];

default:shape[i][j][4]=0;

}

}

intx=0,y=0;

max=0;

for(x=0;x<19;x++)

for(y=0;y<19;y++)

if(max

15

max=shape[x][y][4];

max_x=x;max_y=y;}

}

}

publicclassJudge{//判断是否有一方获得胜利

staticbooleanjudge(inta[][],intcolor){

inti,j,flag;

for(i=0;i<19;i++){//判断同一行

flag=0;

for(j=0;j<19;j++)

if(a[i][j]==color){

flag++;

if(flag==5)

returntrue;}

elseflag=0;

}

for(j=0;j<19;j++){//判断同一列

flag=0;

for(i=0;i<19;i++)

if(a[i][j]==color)

{flag++;

if(flag==5)

returntrue;}

elseflag=0;

}

for(j=4;j<19;j++){//斜线方向

flag=0;intm=j;

for(i=0;i<=j;i++){

if(a[i][m--]==color){

flag++;

if(flag==5)

returntrue;}

elseflag=0;}

}

for(j=14;j>=0;j--){

flag=0;intm=j;

for(i=0;i<=18-j;i++){

16

if(a[i][m++]==color){

flag++;

if(flag==5)

returntrue;}

elseflag=0;}

}

for(i=14;i>=0;i--){

flag=0;intn=i;

for(j=0;j<19-i;j++){

if(a[n++][j]==color){

flag++;

if(flag==5)

returntrue;}

elseflag=0;}

}

for(j=14;j>=0;j--){

flag=0;intm=j;

for(i=18;i>=j;i--){

if(a[i][m++]==color){

flag++;

if(flag==5)

returntrue;}

elseflag=0;}

}

returnfalse;}

}

publicclassScan{//浏览全局

intshape[][][]=newint[19][19][5];

voidscan(intchesspad[][],intcolour){

inti,j;

for(i=0;i<=18;i++)

for(j=0;j<=18;j++)

17

if(chesspad[i][j]==0){

intm=i,n=j;

while(n-1>=0&&chesspad[m][--n]==colour){

shape[i][j][0]++;

}

n=j;

while(n+1<=18&&chesspad[m][++n]==colour){

shape[i][j][0]++;

}

n=j;

while(m-1>=0&&chesspad[--m][n]==colour){

shape[i][j][1]++;

}

m=i;

while(m+1<=18&&chesspad[++m][n]==colour){

shape[i][j][1]++;

}

m=i;

while(m-1>=0&&n+1<=18&&chesspad[--m][++n]==colour){

shape[i][j][2]++;

}

m=i;n=j;

while(m+1=0&&chesspad[++m][--n]==colour){

shape[i][j][2]++;

}

m=i;n=j;

while(m-1>=0&&n-1>=0&&chesspad[--m][--n]==colour){

shape[i][j][3]++;

}

m=i;n=j;

while(m+1<=18&&n+1<=18&&chesspad[++m][++n]==colour){

shape[i][j][3]++;

}

18

}

}

}

publicclassSort{

publicvoidsort(intshape[][][]){

inttemp;

for(inti=0;i<19;i++)

for(intj=0;j<19;j++){

for(inth=1;h<=3;h++){

for(intw=3;w>=h;w--){

if(shape[i][j][w-1]

temp=shape[i][j][w-1];

shape[i][j][w-1]=shape[i][j][w];

shape[i][j][w]=temp;

}

}

}

}

}

}

19