用C语言在linux下编写一个五子棋程序！

五子棋的核心算法

五子棋是一种受大众广泛喜爱的游戏，其规则简单，变化多端，非常富有趣味性和消遣性。这里设计和实现了一个人机对下的五子棋程序，采用了博弈树的方法，应用了剪枝和最大最小树原理进行搜索发现最好的下子位置。介绍五子棋程序的数据结构、评分规则、胜负判断方法和搜索算法过程。

一、相关的数据结构

关于盘面情况的表示，以链表形式表示当前盘面的情况，目的是可以允许用户进行悔棋、回退等 *** 作。

CList StepList

其中Step结构的表示为：

struct Step

{

int m//m,n表示两个坐标值

int n

char side//side表示下子方

}

以数组形式保存当前盘面的情况，

目的是为了在显示当前盘面情况时使用：

char FiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE]

其中FIVE_MAX_LINE表示盘面最大的行数。

同时由于需要在递归搜索的过程中考虑时间和空间有效性，只找出就当前情况来说相对比较好的几个盘面，而不是对所有的可下子的位置都进行搜索，这里用变量CountList来表示当前搜索中可以选择的所有新的盘面情况对象的集合：

CList CountList

其中类CBoardSituiton为:

class CBoardSituation

{

CList StepList//每一步的列表

char FiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE]

struct Step machineStep //机器所下的那一步

double value//该种盘面状态所得到的分数

}

二、评分规则

对于下子的重要性评分，需要从六个位置来考虑当前棋局的情况，分别为：-,¦,/,\,//,\\

实际上需要考虑在这六个位置上某一方所形成的子的布局的情况，对于在还没有子的地方落子以后的当前局面的评分，主要是为了说明在这个地方下子的重要性程度，设定了一个简单的规则来表示当前棋面对机器方的分数。

基本的规则如下：

判断是否能成5, 如果是机器方的话给予100000分，如果是人方的话给予－100000 分；

判断是否能成活4或者是双死4或者是死4活3，如果是机器方的话给予10000分，如果是人方的话给予－10000分；

判断是否已成双活3，如果是机器方的话给予5000分，如果是人方的话给予－5000 分；

判断是否成死3活3，如果是机器方的话给予1000分，如果是人方的话给予－1000 分；

判断是否能成死4，如果是机器方的话给予500分，如果是人方的话给予－500分；

判断是否能成单活3，如果是机器方的话给予200分，如果是人方的话给予－200分；

判断是否已成双活2，如果是机器方的话给予100分，如果是人方的话给予－100分；

判断是否能成死3，如果是机器方的话给予50分，如果是人方的话给予－50分；

判断是否能成双活2，如果是机器方的话给予10分，如果是人方的话给予－10分；

判断是否能成活2，如果是机器方的话给予5分，如果是人方的话给予－5分；

判断是否能成死2，如果是机器方的话给予3分，如果是人方的话给予－3分。

实际上对当前的局面按照上面的规则的顺序进行比较，如果满足某一条规则的话，就给该局面打分并保存，然后退出规则的匹配。注意这里的规则是根据一般的下棋规律的一个总结，在实际运行的时候，用户可以添加规则和对评分机制加以修正。

三、胜负判断

实际上，是根据当前最后一个落子的情况来判断胜负的。实际上需要从四个位置判断，以该子为出发点的水平，竖直和两条分别为 45度角和135度角的线，目的是看在这四个方向是否最后落子的一方构成连续五个的棋子，如果是的话，就表示该盘棋局已经分出胜负。具体见下面的图示：

四、搜索算法实现描述

注意下面的核心的算法中的变量currentBoardSituation，表示当前机器最新的盘面情况, CountList表示第一层子节点可以选择的较好的盘面的集合。核心的算法如下：

void MainDealFunction()

{

value=－MAXINT//对初始根节点的value赋值

CalSeveralGoodPlace(currentBoardSituation,CountList)

//该函数是根据当前的盘面情况来比较得到比较好的可以考虑的几个盘面的情况，可以根据实际的得分情况选取分数比较高的几个盘面，也就是说在第一层节点选择的时候采用贪婪算法，直接找出相对分数比较高的几个形成第一层节点，目的是为了提高搜索速度和防止堆栈溢出。

pos=CountList.GetHeadPosition()

CBoardSituation＊ pBoard

for(i=0ivalue=Search(pBoard,min,value,0)

Value=Select(value,pBoard－>value,max)

//取value和pBoard－>value中大的赋给根节点

}

for(i=0ivalue)

//找出那一个得到最高分的盘面

{

currentBoardSituation=pBoard

PlayerMode=min//当前下子方改为人

Break

}

}

其中对于Search函数的表示如下：实际上核心的算法是一个剪枝过程，其中在这个搜索过程中相关的四个参数为：（1）当前棋局情况；（2）当前的下子方，可以是机器(max)或者是人(min)；（3）父节点的值oldValue；（4）当前的搜索深度depth。

double Search(CBoardSituation＆

board,int mode,double oldvalue,int depth)

{

CList m_DeepList

if(deptholdvalue))== TRUE)

{

if(mode==max)

value=select(value,search(successor

Board,min,value,depth＋1),max)

else

value=select(value,search(successor

Board,max,value,depth＋1),min)

}

return value

}

else

{

if ( goal(board)<>0)

//这里goal(board)<>0表示已经可以分出胜负

return goal(board)

else

return evlation(board)

}

}

注意这里的goal(board)函数是用来判断当前盘面是否可以分出胜负，而evlation(board)是对当前的盘面从机器的角度进行打分。

下面是Select函数的介绍，这个函数的主要目的是根据 PlayerMode情况，即是机器还是用户来返回节点的应有的值。

double Select(double a,double b,int mode)

{

if(a>b ＆＆ mode==max)¦¦ (a<b ＆＆ mode==min)

return a

else

return b

}

五、小结

在Windows *** 作系统下，用VC＋＋实现了这个人机对战的五子棋程序。和国内许多只是采用规则或者只是采用简单递归而没有剪枝的那些程序相比，在智力上和时间有效性上都要好于这些程序。同时所讨论的方法和设计过程为用户设计其他的游戏（如象棋和围棋等）提供了一个参考。

参考资料：http://www.3800hk.com/Article/cxsj/vc/jdsfvc/2005-08-06/Article_33695.html

“猜数字小游戏”，每个数字后按空格，最后按回车确认

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

int a[4],b[4]

int count=0  //计算猜测次数

void csh( )  //初始化

void start( )  //开始游戏

int main( )

{ csh( )

start( )

}

void csh( )  //初始化

{ printf("\n\n         猜  数  字  小  游  戏\n\n")

printf(“    猜四个数字，如数字与顺序都正确记为A，数字正确位置不对记为B.\n”)

}

void start( )  //开始游戏

{int m,n  //m是完全猜对的个数,n是顺序不对的个数

while(1)

{srand((unsigned)time(NULL))  //初始化随机数发生器srand( )

while(1) { for(int i=0i<4i++) a[i]=rand( )%10 //rand( )函数每次随机产生一个0-9的数

if( (a[3]!=a[2]&&a[3]!=a[1]&&a[3]!=a[0])&&

(a[2]!=a[1]&&a[2]!=a[0])&&a[1]!=a[0] ) break}  //4个随机数各自不相等

printf("    请依次输入4个一位整数:\n\n   ")

while(1)

{for(int i=0i<4i++) scanf(“%d”,&b[i])

printf("    你输入的是:%d  %d  %d  %d ",b[0],b[1],b[2],b[3])

m=0n=0

for(int i=0i<4i++)

{for(int j=0j<4j++)

{ if(b[i]==a[j]&&i==j)m=m+1if(b[i]==a[j]&&i!=j)n=n+1}

}

count=count+1

printf("      %dA  %dB   你试了%d次\n   ",m,n,count)

if(m==4)break

if(count==8){ count=0break}

}

printf("\n")

if(m==4)printf("     你猜对了(^-^)！ 就是：%d %d %d %d\n",a[0],a[1],a[2],a[3])

else printf("     你输了(T-T)！哈哈！应该是:%d %d %d %d\n",a[0],a[1],a[2],a[3])

int z

printf("     （要继续吗？1或0）\n   ")

scanf(“%d”,&z)

if(z==0) break

}

}

一个“歼灭敌机”的小游戏，DEVc++编译通过：

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <windows.h>

#include <time.h>

#define zlx 10  //增量坐标(x)让游戏框不靠边

#define zly 3   //增量坐标(y)让游戏框不靠边

#define W 26  //游戏框的宽度

#define H 24  //游戏框的高度

int jiem[22][22]={0}, wj=10  //界面数组, 我机位置(初值为10)

int speed=4,density=30, score=0,death=0//敌机速度, 敌机密度, 玩家成绩,死亡次数

int m=0,n=0 // m,n是控制敌机的变量

void gtxy (int x, int y)  //控制光标位置的函数

{ COORD pos

pos.X = x  pos.Y = y

SetConsoleCursorPosition ( GetStdHandle (STD_OUTPUT_HANDLE), pos )

}

void Color(int a)  //设定颜色的函数(a应为1-15)

{ SetConsoleTextAttribute( GetStdHandle(STD_OUTPUT_HANDLE), a )}

void yinc(int x=1,int y=0)   //隐藏光标的函数

{ CONSOLE_CURSOR_INFO  gb={x,y}   //y设为0即隐藏

SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &gb)

}

void csh( )  //初始化函数

{ int i

Color(7)

gtxy(zlx,zly)printf("╔")  gtxy(zlx+W-2,zly)printf("╗")  //左上角和右上角的框角

gtxy(zlx,zly+H-1)printf("╚")gtxy(zlx+W-2,zly+H-1)printf("╝")//下边两框角

for(i=2i<W-2i+=2) {gtxy(zlx+i,zly)  printf("═")}      //打印上横框

for(i=2i<W-2i+=2) {gtxy(zlx+i,zly+H-1)printf("═")}  //打印下横框

for(i=1i<H-1i++) { gtxy(zlx,zly+i) printf("║")}       //打印左竖框

for(i=1i<H-1i++) {gtxy(zlx+W-2,zly+i)printf("║")}  //打印右竖框

Color(14)gtxy(19,2)printf("歼灭敌机")Color(10)

gtxy(37,5)printf("设置：Esc ")

gtxy(37,7)printf("发射：↑ ")

gtxy(37,9)printf("控制：← → ")

gtxy(37,11)printf("得分：%d",score)

gtxy(37,13)printf("死亡：%d",death)

yinc(1,0)

}

void qcjm( )  //清除界面函数

{int i,j

for(i=0i<H-2i++)

for(j=0j<W-4j++){gtxy(zlx+2+j,zly+1+i)printf(" ")}

}

void feiji( )  //飞机移动函数

{int i,j

for(i=21i>=0i--)  //从底行往上是为了避免敌机直接冲出数组

  for(j=0j<22j++)

     {if(i==21&&jiem[i][j]==3) jiem[i][j]=0  //底行赋值0 以免越界

       if(jiem[i][j]==3) jiem[i][j]=0, jiem[i+1][j]=3

     }

if(jiem[20][wj]==3&&jiem[21][wj]==1) death++

}

void zidan( )  //子d移动函数

{ int i,j

for(i=0i<22i++)

  for(j=0j<22j++)

     {if(i==0&&jiem[i][j]==2) jiem[i][j]=0

     if(jiem[i][j]==2) { if(jiem[i-1][j]==3) score+=100,printf("\7")

                                 jiem[i][j]=0,jiem[i-1][j]=2}

     }

}

void print(  )  //输出界面函数

{int i,j

qcjm( )

for(i=0i<22i++)

for(j=0j<22j++)

{ gtxy(12+j,4+i)

if(jiem[i][j]==3) {Color(13)printf("□")}

if(jiem[i][j]==2) {Color(10)printf(".")}

if(jiem[i][j]==1) {Color(10)printf("■")}

}

gtxy(37,11)Color(10)printf("得分：%d",score)

gtxy(37,13)printf("死亡：%d",death)

}

void setting( )  //游戏设置函数

{ qcjm( )

gtxy(12,4)printf("选择敌机速度:")

gtxy(12,5)printf("  1.快 2.中 3.慢>>")

switch(getche( ))

    {case '1': speed=2break

     case '2': speed=4break

     case '3': speed=5break

     default: gtxy(12,6)printf("  错误！默认值")

   }

gtxy(12,7)printf("选择敌机密度:")

gtxy(12,8)printf("  1.大 2.中 3.小>>")

switch(getche( ))

     {case '1': density=20break

case '2': density=30 break

case '3': density=40break

     default: gtxy(12,9)printf("  错误！默认值")

     }

for(int i=0i<22i++)

 for(int j=0j<22j++)jiem[i][j]=0

jiem[21][wj=10]=1jiem[0][5]=3

gtxy(12,10)printf("  按任意键保存...")

getch( )

qcjm( )

}

void run( )  //游戏运行函数

{ jiem[21][wj]=1  //值为1代表我机(2则为子d)

jiem[0][5]=3   //值为3代表敌机

SetConsoleTitle("歼灭敌机") //设置窗口标题

while(1)

{ if (kbhit( ))  //如有键按下，控制我机左右移动、发射或进行设定

     {int key

      if((key=getch( ))==224) key=getch( )

      switch(key)

      { case 75: if(wj>0) jiem[21][wj]=0,jiem[21][--wj]=1break

        case 77: if(wj<20) jiem[21][wj]=0,jiem[21][++wj]=1 break

        case 72: jiem[20][wj]=2break

       case 27: setting( )

      }

   }

   if(++n%density==0)  //控制产生敌机的速度

     { n=0srand((unsigned)time(NULL))

       jiem[0][rand( )%20+1]=3

     }

    if(++m%speed==0) {feiji( )m=0}  //控制敌机移动速度(相对子d而言)

    zidan( )

   print( )

Sleep(120) //延时120毫秒

  }

}

int main( )

{csh( )

 run( )

 return 0

}

新手要方便写代码，可以收藏下面几个自编函数：

SetConsoleTitle("俄罗斯方块")  //设置窗口左上角标题栏处出现"俄罗斯方块"5个字

srand( (unsigned) time(NULL) ) //初始化随机数发生器

n= rand(  ) % 20  //产生随机数0-19中的一个. 如 rand(  )%5 就产生0-4中的一个数

SetConsoleTitle(  )函数在<windows.h>里, srand(  )函数与rand(  )函数要配合用，

就是同时要用,在<stdlib.h>里。如果 rand( )%10+1 就产生1-10之中的一个数。

Sleep(300)  //延时300毫秒(就是程序暂停300毫秒后继续运行)

system("cls")  //清屏(把窗口里的内容全部清除，光标定于(0,0)位置处)

这两个函数都在<windows.h>里。开头4个自编函数 编写如下：

void gtxy (int x, int y)  //控制光标位置的函数

{ COORD pos

pos.X = x

pos.Y = y

SetConsoleCursorPosition ( GetStdHandle (STD_OUTPUT_HANDLE), pos )

}

void Color (int a)  //设定颜色的函数

{ SetConsoleTextAttribute ( GetStdHandle ( STD_OUTPUT_HANDLE ),a )}

void yinc (int x,int y)   //隐藏光标的函数

{ CONSOLE_CURSOR_INFO   gb={ x , y }  //gb代表光标

SetConsoleCursorInfo ( GetStdHandle(STD_OUTPUT_HANDLE),  &gb )

}

void kou(int w,int h)  //设置窗口大小的函数

{HANDLE  hl=GetStdHandle ( STD_OUTPUT_HANDLE )

COORD  size={ w , h }

SetConsoleScreenBufferSize( hl , size )

SMALL_RECT  rc={ 0, 0, w, h }

SetConsoleWindowInfo( hl, 1, &rc )

}

最后这个函数,参数w是宽h是高。里边5行中第一行定义了句柄型变量hl,并给它赋值。

第二行定义了坐标型结构体变量size,它的取值决定了缓冲区的大小。第三行就是使用

size的值设置好缓冲区大小。第四行定义了变量rc,它的值决定当前窗口显示的位置与

大小(不得超过缓冲区的大小)。前两个0,0是从缓冲区左上角0列0行位置处开始，后两

个参数可以小于w和h.比如 rc={0,0,w-10,h-5}最后一行使用rc的值设置好窗口，中间

那个参数要为" 1 "或写“ true ”才有效。

---