在本次“五子棋“程序的编写中，只编写了人机对弈部分，运用了博弈树进行搜索，在选取最优的走步时使用极大极小分析法，考虑到搜索的时间复杂度和空间复杂度，在程序中只进行了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);
}