Question

求五子棋AI算法

发c/c++的源代码也可以,不过最好加上注释
我的邮箱:rongshudmdmdm@163.com

Answer 1

在本次“五子棋“程序的编写中，只编写了人机对弈部分，运用了博弈树进行搜索，在选取最优的走步时使用极大极小分析法，考虑到搜索的时间复杂度和空间复杂度，在程序中只进行了2步搜索，即计算机在考虑下一步的走法时，只对玩家进行一步的推测。（程序中的棋盘规格为15*15）
下面对具体做法进行描述：
1． 数据结构定义：
棋盘定义：int board[15][15]；
在15*15的棋盘上，获胜的情况总共有572种，
如：
* * * * * ……
…… …… …… …… …… ……
…… …… …… …… …… ……
…… …… …… …… …… ……
…… …… …… …… …… ……
…… …… …… …… …… ……
中的第一行“*“所代表的格子就是一种获胜组合。
计算机和玩家的获胜组合情况bool ctable[15][15][572],
bool ptable[15][15][572]，来表示棋盘上的各个位置都在那种获胜组合中。
计算机和玩家在各个获胜组合中所填入的棋子数int win[2][572],如有一方在某一获胜组合的棋子数达到5个，该方即获胜。
Bool player:是否轮到玩家下棋
Bool computer:是否轮到计算机下棋
Bool start:游戏是否开始
Bool pwin:玩家是否获胜
Bool cwin:计算机是否获胜
CPoint m_pplastpos;//玩家走的前一步棋
CPoint m_pclastpos;//计算机走的前一步棋
为便于说明程序的主要算法，这里先说本程序中估价函数的选取方法：
e=p1+p2;
p1为下完当前这步棋时计算机的得分；p2为下完当前这步棋时玩家的得分（p2其实为负），这样做即考虑了进攻的因数，由考虑了防守的因数，两个方面都进行了考虑，防止计算机只考虑进攻而忽略防守，同时也防止计算机只考虑防守而忽略进攻，从而达到比较好的情况。
2．主要流程描述
其程序流程图如下：

（1） 初始化棋盘：判断哪方先开始，（2） 初始化计算机和玩家的获胜组合情况
bool ctable[15][15][572],bool ptable[15][15][572]
void CMyChessDlg::InitializeBoard()
{
//初始时双方都还没下子
int i,j,count=0,k;
m_pclastpos.x=-1;
m_pclastpos.y=-1;
m_pplastpos.x=-1;
m_pplastpos.y=-1;
start=true;
//判断哪方先开始
if(m_bwfirst)
{
player=false;
computer=true;
}
else
{
player=true;
computer=false;
}
pwin=cwin=false;
//初始化计算机和玩家的获胜组合情况
for(i=0;i<15;i++)
for(j=0;j<15;j++)
for(k=0;k<572;k++)
{
ptable[i][j][k]=false;
ctable[i][j][k]=false;
}
for(i=0;i<2;i++)
for(j=0;j<572;j++)
win[i][j]=0;
for(i=0;i<15;i++)
for(j=0;j<15;j++)
board[i][j]=2;
for(i=0;i<15;i++)
for(j=0;j<11;j++)
{
for(k=0;k<5;k++)
{
ptable[j+k][i][count]=true;
ctable[j+k][i][count]=true;
}
count++;
}
for(i=0;i<15;i++)
for(j=0;j<11;j++)
{
for(k=0;k<5;k++)
{
ptable[i][j+k][count]=true;
ctable[i][j+k][count]=true;
}
count++;
}
for(i=0;i<11;i++)
for(j=0;j<11;j++)
{
for(k=0;k<5;k++)
{
ptable[j+k][i+k][count]=true;
ctable[j+k][i+k][count]=true;
}
count++;
}
for(i=0;i<11;i++)
for(j=14;j>=4;j--)
{
for(k=0;k<5;k++)
{
ptable[j-k][i+k][count]=true;
ctable[j-k][i+k][count]=true;
}
count++;
}
}
（3） 给出下了一个子后的分数：
int CMyChessDlg::GiveScore(int type, int x, int y)
{
int i,score=0;
for(i=0;i<572;i++)
{
//计算机下
if(type==1)
{
if(ctable[x][y][i])
{
switch(win[1][i])
{
case 1:
score+=5;
break;
case 2:
score+=50;
break;
case 3:
score+=100;
break;
case 4:
score+=10000;
break;
default:
break;
}
}
}
//人下
else
{
if(ptable[x][y][i])
{
switch(win[0][i])
{
case 1:
score-=5;
break;
case 2:
score-=50;
break;
case 3:
score-=500;
break;
case 4:
score-=5000;
break;
default:
break;
}
}
}
}
return score;
}
（4） 核心程序 ，（5） 即计算机如何运用极小极大法分析，（6） 选取最优走法，（7）
在程序中极小极大法即体现在两个while循环前后及之间的内容，其估价函数的体现在ctemp+pscore中
void CMyChessDlg::ComTurn()
{
//bestx,best为当前最佳位置，i，j是人能下的各种位置；pi，pj是计算机能下的各种位置
Int bestx,besty,i,j,pi,pj,ptemp,ctemp,pscore=10,cscore=-10000,
ctempboard[15][15],ptempboard[15][15];
int m,n,temp1[20],temp2[20];//暂存第一步搜索的信息
if(start)
{
if(board[7][7]==2)
{
bestx=7;
besty=7;
}
else
{
bestx=8;
besty=8;
}
start=false;
}
else
{//寻找最佳位置
GetBoard(ctempboard,board);
while(SearchBlank(i,j,ctempboard))
{//进行第一步查找
n=0;
pscore=10;
GetBoard(ptempboard,board);//获取当前棋盘状态
ctempboard[i][j]=3;//标记已被查找
ctemp=GiveScore(1,i,j);
for(m=0;m<572;m++)
{//暂时更改玩家信息
if(ptable[i][j][m])
{
temp1[n]=m;
ptable[i][j][m]=false;
temp2[n]=win[0][m];
win[0][m]=7;
n++;
}
}
ptempboard[i][j]=1;
/***********************************************/
/* 是否胜利,是返回1 */
int victory(int player)
{
int column=E_column,row=E_row;
int left_sum=0,right_sum=0;
int top_sum=0,down_sum=0;
int left_top_sum=0,right_down_sum=0;
int right_top_sum=0,left_down_sum=0;
int i,j;

for (i=column;i>=column-4 && i>0;i--)
if (chess_map[i-1][row-1]==player)
left_sum++;
else
break;
for (i=column;i<=column+4 && i<17;i++)
if (chess_map[i-1][row-1]==player)
right_sum++;
else
break;
if ((left_sum+right_sum)==6)
return 1;

for (j=row;j>=row-4 && j>0;j--)
if (chess_map[column-1][j-1]==player)
top_sum++;
else
break;
for (j=row;j<=row+4 && j<17;j++)
if (chess_map[column-1][j-1]==player)
down_sum++;
else
break;
if ((top_sum+down_sum)==6)
return 1;

for (i=column,j=row;i>=column-4 && j>=row-4 && i>0 && j>0;i--,j--)
if (chess_map[i-1][j-1]==player)
left_top_sum++;
else
break;
for (i=column,j=row;i<=column+4 && j<=row+4 && i<17 && j<17;i++,j++)
if (chess_map[i-1][j-1]==player)
right_down_sum++;
else
break;
if ((left_top_sum+right_down_sum)==6)
return 1;

for (i=column,j=row;i<=column+4 && j>=row-4 && i<17 && j>0;i++,j--)
if (chess_map[i-1][j-1]==player)
right_top_sum++;
else
break;
for (i=column,j=row;i>=column-4 && j<=row+4 && j<17 && i>0;j++,i--)
if (chess_map[i-1][j-1]==player)
left_down_sum++;
else
break;
if (right_top_sum+left_down_sum==6)
return 1;
return 0;
}

/**********************AI**********************/
int AI(int *m,int *n)
{
int bestx=8,besty=8;
long f_score=0,score=0;
int i,j;
int a[8],b[8];
for (i=0;i<8;i++)
{a[i]=0,b[i]=0;}

for (i=0;i<16;i++)
for (j=0;j<16;j++)
{
score=0;
if (chess_map[i][j]==0)
{
/********************进攻分数**********************/
chess_map[i][j]=computer;
for (i=column;i>=column-4 && i>0;i--)
if (chess_map[i-1][row-1]==computer)
a[0]++;
else
break;
for (i=column;i<=column+4 && i<17;i++)
if (chess_map[i-1][row-1]==computer)
a[1]++;
else
break;
for (j=row;j>=row-4 && j>0;j--)
if (chess_map[column-1][j-1]==computer)
a[2]++;
else
break;
for (j=row;j<=row+4 && j<17;j++)
if (chess_map[column-1][j-1]==computer)
a[3]++;
else
break;
for (i=column,j=row;i>=column-4 && j>=row-4 && i>0 && j>0;i--,j--)
if (chess_map[i-1][j-1]==computer)
a[4]++;
else
break;
for (i=column,j=row;i<=column+4 && j<=row+4 && i<17 && j<17;i++,j++)
if (chess_map[i-1][j-1]==computer)
a[5]++;
else
break;
for (i=column,j=row;i<=column+4 && j>=row-4 && i<17 && j>0;i++,j--)
if (chess_map[i-1][j-1]==computer)
a[6]++;
else
break;
for (i=column,j=row;i>=column-4 && j<=row+4 && j<17 && i>0;j++,i--)
if (chess_map[i-1][j-1]==computer)
a[7]++;
else
break;
for (i=0;i<8;i++)
{
switch(a[i]-1)
{
case 1:
score+=5;
break;
case 2:
score+=50;
break;
case 3:
score+=100;
break;
case 4:
score+=10000;
break;
default:
break;
}
}
/********************进攻分数**********************/
/********************防守分数**********************/
chess_map[i][j]=elva6401;
for (i=column;i>=column-4 && i>0;i--)
if (chess_map[i-1][row-1]==elva6401)
b[0]++;
else
break;
for (i=column;i<=column+4 && i<17;i++)
if (chess_map[i-1][row-1]==elva6401)
b[1]++;
else
break;
for (j=row;j>=row-4 && j>0;j--)
if (chess_map[column-1][j-1]==elva6401)
b[2]++;
else
break;
for (j=row;j<=row+4 && j<17;j++)
if (chess_map[column-1][j-1]==elva6401)
b[3]++;
else
break;
for (i=column,j=row;i>=column-4 && j>=row-4 && i>0 && j>0;i--,j--)
if (chess_map[i-1][j-1]==elva6401)
b[4]++;
else
break;
for (i=column,j=row;i<=column+4 && j<=row+4 && i<17 && j<17;i++,j++)
if (chess_map[i-1][j-1]==elva6401)
b[5]++;
else
break;
for (i=column,j=row;i<=column+4 && j>=row-4 && i<17 && j>0;i++,j--)
if (chess_map[i-1][j-1]==elva6401)
b[6]++;
else
break;
for (i=column,j=row;i>=column-4 && j<=row+4 && j<17 && i>0;j++,i--)
if (chess_map[i-1][j-1]==elva6401)
b[7]++;
else
break;
for(i=0;i<8;i++)
{
switch(b[i]-1)
{
case 1:
score-=5;
break;
case 2:
score-=50;
break;
case 3:
score-=500;
break;
case 4:
score-=5000;
break;
default:
break;
}
}
/********************防守分数**********************/
chess_map[i][j]=0;
if (score>f_score)
{
bestx=i+1;
besty=j+1;
f_score=score;
}
}
}
E_column=bestx,* m=bestx;
E_row=besty,* n=besty;
chess_map[bestx-1][besty-1]=computer;
}
/**********************AI***********************/

/***********************************************/
/* main */
int main()
{
int gdriver=DETECT,gmode;
initgraph(&gdriver,&gmode," ");
setbkcolor(BLUE);
init();
column=9,row=9;
chess_map[column-1][row-1]=computer;
draw_chess(computer);
while(1)
{
init_col_row();
flag=1;
while(flag==1)
{
move_chess(elva6401);
getch();
}
draw_chess(elva6401);
if(victory(elva6401))
{
outtextxy(550,400,"You win the game\n");
getch();
return 0;
}
AI(&column,&row);
draw_chess(computer);
if(victory(computer))
{
outtextxy(550,400,"You lost the game\n");
getch();
return 0;
}
}
}
// ChangeStatus(ptempboard);
pi=i;
pj=j;
while(SearchBlank(i,j,ptempboard))
{//进行第二不查找
ptempboard[i][j]=3;//标记已被查找
ptemp=GiveScore(0,i,j);
if(pscore>ptemp)//此时为玩家下子，运用极小极大法时应选取最小值
pscore=ptemp;
}
for(m=0;m<n;m++)
{//恢复玩家信息
ptable[pi][pj][temp1[m]]=true;
win[0][temp1[m]]=temp2[m];
}
//ctemp+pscore为实际估价函数
if(ctemp+pscore>cscore) //此时为计算机下子，运用极小极大法时应选取最最大值
{
cscore=ctemp+pscore;
bestx=pi;
besty=pj;
}
}
}
board[bestx][besty]=1;
if(m_pclastpos.x!=-1&&m_pclastpos.y!=-1)
{//画前一棋子
if(!m_bwfirst)
DrawBlackChess(m_pclastpos.x,m_pclastpos.y);
else
DrawWhiteChess(m_pclastpos.x,m_pclastpos.y);
}

if(!m_bwfirst)
DrawNowBlack(bestx,besty);
else
DrawNowWhite(bestx,besty);
m_pclastpos.x=bestx;
m_pclastpos.y=besty;
for(i=0;i<572;i++)
{//修改计算机下子后，棋盘的变化状况
if(ctable[bestx][besty][i]&&win[1][i]!=7)
win[1][i]++;
if(ptable[bestx][besty][i])
{
ptable[bestx][besty][i]=false;
win[0][i]=7;
}
}
computer=false;
player=true;
}
（8） 玩家下棋：（其中坐标（9） 加减目的是调整图片的位置和棋盘对齐）
void CMyChessDlg::OnLButtonDown(UINT nFlags, CPoint point)
{
int x,y,tx,ty;
// TODO: Add your message handler code here and/or call default
if(player&&point.x<=535&&point.y<=535)//判断是否在有效区域
{
tx=x=point.x-24;
ty=y=point.y-25;
while(tx>=36)
tx-=36;
while(ty>=36)
ty-=36;
tx+=x/36;
ty+=y/36;
if(tx>18)
x=x/36+1;
else
x=x/36;
if(ty>18)
y=y/36+1;
else
y=y/36;
if(board[x][y]==2)
{
board[x][y]=0;//设为玩家的棋子
if(m_pplastpos.x!=-1&&m_pplastpos.y!=-1)
{
if(!m_bwfirst)
DrawWhiteChess(m_pplastpos.x,m_pplastpos.y);
else
DrawBlackChess(m_pplastpos.x,m_pplastpos.y);
}

if(!m_bwfirst)
DrawNowWhite(x,y);
else
DrawNowBlack(x,y);
m_pplastpos.x=x;
m_pplastpos.y=y;
for(int i=0;i<572;i++)//修改玩家下子后棋盘状态的变化
{
if(i==80)
i=80;
if(ptable[x][y][i]&&win[0][i]!=7)
win[0][i]++;
if(ctable[x][y][i])
{
ctable[x][y][i]=false;
win[1][i]=7;
}
}
player=false;
computer=true;
}
}
CDialog::OnLButtonDown(nFlags, point);
}

Answer 2

我给你发了一个xl的源代码，是所有开源的五子棋中AI水平最高的了

Answer 3

D