#include <stdio.h>
#define MAX 10000
enum Color {WHITE=-1,BLANK,BLACK};
struct Choice
{
int posX;
int posY;
int score;
};
struct Chessman
{
enum Color color;
unsigned stable; /* 棋子的稳定性(0~8),若棋子为BLANK则表示该位置落子后可翻过的棋子个数. */
};
struct Chessboard
{
struct Chessman cell[8][8];
unsigned whiteNum;
unsigned blackNum;
};
/*
* 初始化棋盘.
*/
void initChessboard(struct Chessboard *board)
{
int i,j;
board->whiteNum=2;
board->blackNum=2;
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
board->cell[i][j].color=BLANK;
board->cell[i][j].stable=0;
}
}
board->cell[3][3].color=board->cell[4][4].color=BLACK;
board->cell[3][4].color=board->cell[4][3].color=WHITE;
}
/*
* 复制棋盘.
*/
void clone(struct Chessboard *boardDest,const struct Chessboard *boardSource)
{
int i,j;
boardDest->whiteNum=boardSource->whiteNum;
boardDest->blackNum=boardSource->blackNum;
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
boardDest->cell[i][j].color=boardSource->cell[i][j].color;
boardDest->cell[i][j].stable=boardSource->cell[i][j].stable;
}
}
}
/*
* 显示棋盘.
*/
void view(struct Chessboard *board)
{
int i,j;
printf("\n-----");
for(i=0;i<8;i++)
{
printf("%d---",i+1);
}
printf("\n ────────────────\n");
for(i=0;i<8;i++)
{
printf("%d--│",i+1);
for(j=0;j<8;j++)
{
switch(board->cell[i][j].color)
{
case BLACK:
printf("●│");
break;
case WHITE:
printf("○│");
break;
case BLANK:
if(board->cell[i][j].stable)
{
printf("╳│");
}
else
{
printf(" │");
}
break;
default: /* 棋子颜色错误 */
printf("* │");
}
}
printf("\n ────────────────\n");
}
printf("\n白棋(○)个数为:%d",board->whiteNum);
printf("\t黑棋(●)个数为:%d\n\n",board->blackNum);
}
/*
*计算可落子的位置个数,及该位置落子后翻过的棋子的个数(board->cell[i][j].stable)
*/
int judge(struct Chessboard *board,enum Color player)
{
int i,j;
unsigned num=0;
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
if(board->cell[i][j].color==BLANK)
{
int x,y;
board->cell[i][j].stable=0;
for(x=-1;x<=1;x++)
{
for(y=-1;y<=1;y++)
{
if(x||y) /* 8个方向 */
{
int i2,j2;
unsigned num2=0;
for(i2=i+x,j2=j+y;i2>=0 && i2<=7 && j2>=0 && j2<=7;i2+=x,j2+=y)
{
if(board->cell[i2][j2].color==(enum Color)-player)
{
num2++;
}
else if(board->cell[i2][j2].color==player)
{
board->cell[i][j].stable+=player*num2;
break;
}
else if(board->cell[i2][j2].color==BLANK)
{
break;
}
}
}
}
}
if(board->cell[i][j].stable)
{
num++;
}
}
}
}
return num;
}
/*
* 落子,翻子.
*/
int putChess(struct Chessboard *board,struct Choice *choice,enum Color player)
{
int i=choice->posX,j=choice->posY;
int x,y;
if(board->cell[i][j].color!=BLANK || board->cell[i][j].stable==0 || player==BLANK)
{
return -1;
}
board->cell[i][j].color=player;
board->cell[i][j].stable=0;
if(player==WHITE)
{
board->whiteNum++;
}
else if(player==BLACK)
{
board->blackNum++;
}
for(x=-1;x<=1;x++)
{
for(y=-1;y<=1;y++)
{
if(x||y) /* 8个方向 */
{
int i2,j2;
unsigned num=0;
for(i2=i+x,j2=j+y;i2>=0 && i2<=7 && j2>=0 && j2<=7;i2+=x,j2+=y)
{
if(board->cell[i2][j2].color==(enum Color)-player)
{
num++;
}
else if(board->cell[i2][j2].color==player)
{
board->whiteNum+=(player*WHITE)*num;
board->blackNum+=(player*BLACK)*num;
for(i2-=x,j2-=y;num>0;num--,i2-=x,j2-=y)
{
board->cell[i2][j2].color=player;
board->cell[i2][j2].stable=0;
}
break;
}
else if(board->cell[i2][j2].color==BLANK)
{
break;
}
}
}
}
}
return 0;
}
/*
* 设置棋子的稳定性(计算得分的依据),空白处除外.
*/
void setStable(struct Chessboard *board)
{
int i,j;
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
if(board->cell[i][j].color!=BLANK)
{
int x,y;
board->cell[i][j].stable=1;
for(x=-1;x<=1;x++)
{
for(y=-1;y<=1;y++)
{
/* 4个方向 */
if(x==0 && y==0)
{
x=2;
y=2;
}
else
{
int i2,j2,flag=2;
for(i2=i+x,j2=j+y;i2>=0 && i2<=7 && j2>=0 && j2<=7;i2+=x,j2+=y)
{
if(board->cell[i2][j2].color!=board->cell[i][j].color)
{
flag--;
break;
}
}
for(i2=i-x,j2=j-y;i2>=0 && i2<=7 && j2>=0 && j2<=7;i2-=x,j2-=y)
{
if(board->cell[i2][j2].color!=board->cell[i][j].color)
{
flag--;
break;
}
}
if(flag) /* 在某一条线上稳定 */
{
board->cell[i][j].stable++;
}
}
}
}
}
}
}
}
/*
* 评价棋手得分.
*/
int evaluate(struct Chessboard *board,enum Color player)
{
int value=0;
int i,j;
setStable(board);
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
value+=(board->cell[i][j].color)*(board->cell[i][j].stable);
}
}
value+=64*board->cell[0][0].color;
value+=64*board->cell[0][7].color;
value+=64*board->cell[7][0].color;
value+=64*board->cell[7][7].color;
value-=32*board->cell[1][1].color;
value-=32*board->cell[1][6].color;
value-=32*board->cell[6][1].color;
value-=32*board->cell[6][6].color;
return value*player;
}
/*
*考虑step步,选择最优方案.采用最大最小博弈和α-β剪裁算法
*/
struct Choice * maximin(struct Chessboard *board,enum Color player,int step,int min,int max,struct Choice *choice)
{
int i,j,k,num;
struct Choice *allChoices;
choice->score=-MAX;
choice->posX=-1;
choice->posY=-1;
num=judge(board,player);
if(num==0) /* 无处落子 */
{
if(judge(board,(enum Color)-player)) /* �