【概述】五子棋是一种大众喜爱的游戏，其规则简单，变化多端，非常富有趣味性何消遣性。这里设计了一个简单的五子棋程序，采用对空格点进行评分排序的算法。 近来随着计算机的快速发展，各种棋类游戏被纷纷请进了电脑，使得那些喜爱下棋，又常常苦于没有对手的棋迷们能随时过足棋瘾。而且这类软件个个水平颇高，大有与人脑分庭抗礼之势。其中战胜过国际象棋世界冠军-卡斯帕罗夫的“深蓝”便是最具说服力的代表；其它像围棋的“手淡”、象棋的“将族”等也以其优秀的人工智能深受棋迷喜爱；而我也做了一个“无比”简单的五子棋算法。　　总的来说（我们假定您熟悉五子棋的基本规则），要让电脑知道该在哪一点下子，就要根据盘面的形势，为每一可能落子的点计算其重要程度，也就是当这子落下后会形成什么棋型（如：“冲四”、“活三”等），然后通览全盘选出最重要的一点，这便是最基本的算法。 主程序模块包括：数据结构，评分规则，胜负判断，搜索最优空格的算法过程。 【关键字】人工智能，博弈树，五子棋，无禁手，评分，搜索，C，随机。 【环境】XP/TC3.0 【算法及解析】（无禁手） 一.   数据结构： 本程序中只使用了一个19×19的二元结构数组如下定义： Typedef  Struct {     int     player;             int     value[8][5];             long int  score;        }map[19][19]; 其中map[i][j]保存i行j列棋子信息，player为下棋方，value数组记录八个方向的连续5个棋子的信息，为以后评分服务。Score为空格评分。 以及数据结构可以满足初级人机对弈程序的功用。 对比其他程序结构： 王小春五子棋源码：该程序采用链表节点结构，保存下子信息，该结构主要为悔棋提供方便（虽该源码为开发悔棋功能）  Typedef struct Step   {    int m;    int n;    char side;   }; 为链表clist节点,m,n表示两个坐标值，side表示下子方相对于我的程序中的player. 另外该程序还使用一个二维数组map[][],来保存棋盘信息。 二．预定义单元 #define blank   0 #define black   1 #define white   2 #define NUM_HIGH 19 #define NUM_LINE 19 #define man 1 #define bot 2 其中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。 四．函数定义及其功能。 1.Void init()    初始化棋盘bgi图形与棋盘棋型。    将棋盘标记map[][].player都置为blank（空白），各点8方向的连续五个棋子信息也初始为0，各点评分数也置为0。  void init() {     int i, j, m, n;     int gdriver=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;         } } 2．Void paint() 画棋盘函数，本五子棋程序使用的是标准围棋棋盘，规格19×19，每格25大小（象素），并且规定man棋子颜色为黑，robot为白色，黑棋优先。最后初始化光标（开始位置）位置。 void paint() {     int i, j;     clearviewport();     setbkcolor(BLUE);//设置背景色     setcolor(WHITE);//设置作图色     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 下棋的位置 } 3.void main()   主函数控制。初始化图形及棋型，规定黑子优先，画棋盘，开始下子。   （略） 4．Void human() Man下棋函数，其中添加了防棋子覆盖控制。 void human(void) {     char ch=1;     int size, x, y;     void *buf;     while( ch != 32 )      {         ch = getch();         putimage( getx()-10, gety()-10, buf, COPY_PUT);         if( ch == 27)   //ESC退出             exit(1);         if( ch == 'w' || ch == 'W') //移动控制单元             moverel( 0, -25);         else if( ch == 's' || ch == 'S')             moverel( 0, 25);         else if( ch == 'a' || ch == 'A')             moverel( -25, 0);         else if( 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()-10, getx()+10, gety()+10);         buf = malloc(size);         getimage( getx()-10, gety()-10, 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); } 5．Void mark(int,int) 标记棋子，robot标记为白棋，man标记为黑棋。 在程序结束添加了判断下子方是否胜出（结束）判断函数，check(int,int). void mark( int x, int y)  //标记棋子 {     int i, j,m,n;     m=x;     n=y;     if( turn == man)     {         setcolor(DARKGRAY);         setfillstyle(SOLID_FILL, DARKGRAY);     }     else     {         setcolor(WHITE);         setfillstyle(SOLID_FILL, WHITE);     }     pieslice( (x * 25 + 20), (y * 25 + 20), 0, 360, 10);  //棋盘前端显示     setcolor(RED);     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); } 6.void check(int,int) 判断程序是否结束函数（一方胜利），共判断了四个方向：水平方向，竖直方向，左斜线方向，右斜线方向。如果发现存在超过或等于5各连续棋子，则判断一方胜利，调用win(int)函数，显示结果，程序结束。 程序结尾，添加交换下子部分。 void check(int m,int n) {     int WinTag=map[m][n].player;     int i=m,j=n,level=1;     //outtextxy((m * 25 + 20), (n * 25 + 20),".");     if(WinTag==man) outtextxy((n* 25 + 17), (m * 25 + 17),"M");     else outtextxy((n * 25 + 17), (m * 25 + 17),"R");     //水平位置判断 while(map[i-1][j].player==WinTag&&i>=1) {         level++;  i--; } i=m; while(map[i+1][j].player==WinTag&&i<(NUM_LINE-1)) {         level++;  i++; } if(level>=5)win(WinTag); level=1; //竖直方向判断 i=m；     j=n; while(map[i][j-1].player==WinTag&&j>=1) {         level++;  j--; } j=n; while(map[i][j+1].player==WinTag&&j<(NUM_HIGH-1)) {         level++;  j++; } if(level>=5)win(WinTag); level=1; //左斜线判断 i=m；    j=n; while(map[i-1][j-1].player==WinTag&&i>=1&&j>=1) {         level++; i--;j--; } i=m;       j=n; while(map[i+1][j+1].player==WinTag&&i<(NUM_LINE-1)&&j<(NUM_HIGH-1)) {         level++;  i++; j++; } if(level>=5)win(WinTag); level=1; //右斜线判断 i=m;        j=n; while(map[i+1][j-1].player==WinTag&&i<NUM_LINE&&j>=1) {         level++;   i++; j--; } i=m;       j=n; while(map[i-1][j+1].player==WinTag&&i>=1&&j<(NUM_HIGH-1)) {         level++; i--; j++; } if(level>=5)win(WinTag);    //交换下棋顺序     if( turn == man)     {         turn = bot;   robot();     }     else     {         turn = man;   human();     } 7．Void win(int) void win( int winner) {     char ch;     setbkcolor(LIGHTGRAY);     setcolor(YELLOW);     //ch = getch();     while( ch != 27)     {         if(winner==man)outtextxy( 240, 210, "You are the winner !");         else outtextxy( 240, 210, "You are lost !");         outtextxy( 245, 250, "Press ESC to Exit!");         printf("%d",winner);         ch = getch();     }     closegraph();     exit(1); }  } 下一页

评论