“五子棋”软件设计报告 杭州电子科技大学 胡峰令    在本次“五子棋“程序的编写中，只编写了人机对弈部分，运用了博弈树进行搜索，在选取最优的走步时使用极大极小分析法，考虑到搜索的时间复杂度和空间复杂度，在程序中只进行了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++;         } }

评论