#include ".\robot.h"
//--------------------------------------------------------
int getValue(const CHECKERSTATE *const gState,int *const rTotal,int *const bTotal);
void getTotalChecker(const CHECKER *Data,const STATE state,int *common,int *king);
int getTotalBeKing(const CHECKER *Data,const STATE state,int const type);
int CheckEmpty(const CHECKER *Data);
void InitForSearch(CHECKERSTATE *const gState);
void InitForNextLevel(CHECKERSTATE *const pState,const CHECKERSTATE *const gState);
int FindCanMove(const CHECKERSTATE *const gState,CHECKER *move,int *const total,int *const MoveFlag);
int FindCanEat(const CHECKERSTATE *const gState,CHECKER *move,int *const total,int *const MoveFlag);
void DoDoubleEat(STATE state,CHECKER Change[12],CHECKER Delete[12],int X,int Y,int type);
int MaxValue(const CHECKERSTATE *const gState,int a,int b,int *const rTotal,int *const bTotal);
int MinValue(const CHECKERSTATE *const gState,int a,int b,int *const rTotal,int *const bTotal);
//--------------------------------------------------------
const int w[4][2] = {{-1,-1},{1,-1},{-1,1},{1,1}};
//--------------------------------------------------------
//移动棋子的计算
int AlphaBetaSearch(int *gameValue,int *RTotal,int *BTotal)
{
int i,j,x,y,X,Y,XX,YY,value,rTotal,bTotal;
int total=0,MoveFlag=0,a=GAME_MIN,b=GAME_MAX;
CHECKERSTATE gState,pState; //下一层的数据空间,同一层的棋局复用同一空间
CHECKER move[12],*pMove; //记录坐标及方向的数组
//本层要取下层返回值中的最大值，所以要先设其值为最小
*gameValue=GAME_MIN;
*RTotal=-1;
*BTotal=-1;
pMove=move;
for(i=0;i<12;i++,pMove++)
{
pMove->x=0;
pMove->y=0;
pMove->i=0;
}
//这个函数只用一次，把初始数据复制到该结构体
InitForSearch(&gState);
//根据传入的棋局，黑方要检查找能吃的或可移动的棋子，并更新棋局
if(!FindCanEat(&gState,move,&total,&MoveFlag)) //先查找有无可吃对方棋子
FindCanMove(&gState,move,&total,&MoveFlag); //再查找本方有无可移动的棋子
//根据MOVE数组中的数据布棋局
pMove=move;
for(i=0;i {
X=pMove->x;
Y=pMove->y;
for(j=0;j<4;j++)
{
//方向对应时，进入
if((pMove->i) & (1< {
x=w[j][0];
y=w[j][1];
XX=X+MoveFlag*x;
YY=Y+MoveFlag*y;
if((YY>=0)&&(YY<=7)&&(XX>=0)&&(XX<=7))
{
//初始化下一层的数据，gState复制到pState
InitForNextLevel(&pState,&gState);
//根据黑方的棋子形成下一层的棋局
//MoveFlag=1是移动，MoveFlag=2是吃子
//(state[Y][X]&0xf0)>>4，这个数表示棋子在棋子数组中的位置
//Com[].x等，表示棋子在state中的xy坐标
pState.state[YY][XX]=pState.state[Y][X];
pState.Com[(pState.state[Y][X]&0xf0)>>4].x=XX;
pState.Com[(pState.state[Y][X]&0xf0)>>4].y=YY;
//如果没成王，并且到达了相应的下边（高度为7）时，移动的棋子标记为王(state数据中的第二位)
if(!(pState.state[Y][X]&2)&&(YY==7))
{
pState.state[YY][XX] |= 2;
}
pState.state[Y][X]=1;
//吃子时要重新排列红方的棋子数组，清除红方的棋子，并递归查找有无连吃
if(MoveFlag==2)
{
SortChecker(pState.Pla,pState.state,(pState.state[Y+y][X+x]&0xf0)>>4);
pState.state[Y+y][X+x]=1;
DoDoubleEat(pState.state,pState.Com,pState.Pla,XX,YY,0);
}
//设置好棋局后向下层传递（MIN层，红方）
value=MinValue(&pState,a,b,&rTotal,&bTotal);
//取下层返回值中最大的值，相等时随机取,本层是MAX层
if((*gameValue ||((*gameValue==value)&&(*BTotal ||((*gameValue==value)&&(*BTotal==bTotal)&&(*RTotal>rTotal))\
||((*gameValue==value)&&(*BTotal==bTotal)&&(*RTotal==rTotal)&&GetRandomNumber(2)))
{
*gameValue=value;
*BTotal=bTotal;
*RTotal=rTotal;
//最终是设置以下四个变量
SelectX=move[i].x;
SelectY=move[i].y;
CursorX=SelectX+w[j][0]*MoveFlag;
CursorY=SelectY+w[j][1]*MoveFlag;
if(*gameValue > a) //更新alpha值,用于向下层说明本层此时的值最小为多少
a = *gameValue; //如果下层MIN层的值不大于此值，则MIN层剪枝返回
}
}
}
}
}
return 1;
}
//--------------------------------------------------------
int MinValue(const CHECKERSTATE *const gState,int a,int b,int *const rTotal,int *const bTotal)
{
int total=0,MoveFlag=0;
int i,j,value,gameValue,rrTotal,bbTotal;
CHECKERSTATE pState;
CHECKER move[12],*pMove;
//传入棋局后，判断是否到达了最后一层，是则返回棋局评估值
if(gState->depth==SEARCHDEPTH)
return getValue(gState,rTotal,bTotal);
//本层要取下层返回值中的最小值，所以要先设其值为最大
gameValue=GAME_MAX;
pMove=move;
for(i=0;i<12;i++,pMove++)
{
pMove->x=0;
pMove->y=0;
pMove->i=0;
}
//根据传入的棋局，红方要检查找能吃的或可移动的棋子，并更新棋局
//先检测有无棋子，无则本方棋子为空，返回EMPTY_MAX
//有则再检测有无可吃对方棋子，否，则检测本方可否移动，否，则无路可走，返回IMMOVE_MAX
if(!CheckEmpty(gState->Pla))
{
return EMPTY_MAX; //红方无棋子
}
else if(!FindCanEat(gState,move,&total,&MoveFlag))
{
if(!FindCanMove(gState,move,&total,&MoveFlag))
{
return IMMOVE_MAX; //红方无路可走
}
}
pMove=move;
for(i=0;i {
int X,Y;
X=pMove->x;
Y=pMove->y;
for(j=0;j<4;j++)
{
if((pMove->i) & (1< {
int x,y,XX,YY;
x=w[j][0];
y=w[j][1];
XX=X+MoveFlag*x;
YY=Y+MoveFlag*y;
if((YY>=0)&&(YY<=7)&&(XX>=0)&&(XX<=7))
{
//初始化下一层的数据
InitForNextLevel(&pState,gState);
//根据红方可移动的棋子形成下一层的棋局
pState.state[YY][XX]=pState.state[Y][X];
pState.Pla[(pState.state[Y][X]&0xf0)>>4].x=XX;
pState.Pla[(pState.state[Y][X]&0xf0)>>4].y=YY;
if(!(pState.state[Y][X]&2)&&(YY==0))
{
pState.state[YY][XX] |= 2;
}
pState.state[Y][X]=1;
if(MoveFlag==2)
{
SortChecker(pState.Com,pState.state,(pState.state[Y+y][X+x]&0xf0)>>4);
pState.state[Y+y][X+x]=1;
DoDoubleEat(pState.state,pState.Pla,pState.Com,XX,YY,1);
}
//设置好棋局后向下层传递（MAX层，黑方）
value=MaxValue(&pState,a,b,&rrTotal,&bbTotal);
//更新本层记录的评估值,保存小的值
if((gameValue>value)\
||((gameValue==value)&&(*rTotal ||((gameValue==value)&&(*rTotal==rrTotal)&&(*bTotal>bbTotal)))
{
gameValue=value;
*rTotal=rrTotal;
*bTotal=bbTotal;
//如果本层评估值不大于上层传来的alpha值(MAX层的最小值),则剪枝返回
//因为本层的不可能提供大于MAX层的值,再搜索无意义
if(gameValue <= a)
{
return gameValue;
}
if(gameValue < b) //更新beta值,用于向下层说明本层此时的值最大为多少
b = gameValue; //如果下层MAX层的值不小于此值，则MAX层剪枝返回
}
}
}
}
}
return gameValue;
}
//--------------------------------------------------------
int MaxValue(const CHECKERSTATE *const gState,int a,int b,int *const rTotal,int *const bTotal)
{
int total=0,MoveFlag=0;
int i,j,value,gameValue,rrTotal,bbTotal;
CHECKERSTATE pState;
CHECKER move[12],*pMove;
//传入棋局后，判断是否到达了最后一层，是则返回棋局评估值
if(gState->depth==SEARCHDEPTH)
return getValue(gState,rTotal,bTotal);
gameValue=GAME_MIN;
pMove=move;
for(i=0;i<12;i++,pMove++)
{
pMove->x=0;
pMove->y=0;
pMove->i=0;
}
//根据传入的棋局，黑方要检查找能吃的或可移动的棋子，并更新棋局
//先检测有无本方棋子，无则返回EMPTY_MIN
//有则再检测有无可吃对方棋子，否，则检测本方可否移动，否，则无路可走，返回IMMOVE_MIN
if(!CheckEmpty(gState->Com))
{
return EMPTY_MIN; //黑方无棋子
}
else if(!FindCanEat(gState,move,&total,&MoveFlag))
{
if(!FindCanMove(gState,move,&total,&MoveFlag))
{
return IMMOVE_MIN; //黑方无棋可走
}
}
pMove=move;
for(i=0;i {
int X,Y;
X=pMove->x;
Y=pMove->y;
for(j=0;j<4;j++)
{
if((pMove->i) & (1< {
int x,y,XX,YY;
x=w[j][0];
y=w[j][1];
XX=X+MoveFlag*x;
YY=Y+MoveFlag*y;
if((YY>=0)&&(YY<=7)&&(XX>=0)&&(XX<=7))
{
//初始化下一层的数据
InitForNextLevel(&pState,gState);
//根据黑方可移动的棋子形成下一层的棋局
pState.state[YY][XX]=pState.state[Y][X];
pState.Com[(pState.state[Y][X]&0xf0)>>4].x=XX;
pState.Com[(pState.state[Y][X]&0xf0)>>4].y=YY;
if(!(pState.state[Y][X]&2)&&(YY==7))
{
pState.state[YY][XX] |= 2;
}
pState.state[Y][X]=1;
if(MoveFlag==2)
{
SortChecker(pState.Pla,pState.state,(pState.state[Y+y][X+x]&0xf0)>>4);
pState.state[Y+y][X+x]=1;
DoDoubleEat(pState.state,pState.Com,pState.Pla,XX,YY,0);
}
//设置好棋局后向下层传递（MIN层，红方）
value=MinValue(&pState,a,b,&rrTotal,&bbTotal);
if((gameValue ||((gameValue==value)&&(*bTotal ||((gameValue==value)&&(*bTotal==bbTotal)&&(*rTotal>rrTotal)))
{
gameValue=value;
*rTotal=rrTotal;
*bTotal=bbTotal;
//如果本层评估值不小于上层传来的beta值(MIN层的最大值),则剪枝返回
//因为本层的不可能提供小于MIN层的值,再搜索无意义
if(gameValue >= b)
{
return gameValue;
}
if(gameValue > a) //更新alpha值,用于向下层说明本层此时的值最小为多少
a = gameValue; //如果下层MIN层的值不大于此值，则MIN层剪枝返回
}
}
}
}
}
return gameValue;
}
//--------------------------------------------------------
//无此颜色的棋子返回0，有返回1
int CheckEmpty(const CHECKER *Data)
{
int j;
for(j=0;j<12&&Data->i;j++,Data++)
{
return 1;
}
return 0;
}
//--------------------------------------------------------
//查找本方可吃对方棋子的棋子，保存坐标到MOVE数组，并计总数TOTAL，标记为吃子MOVEFLAG
int FindCanEat(const CHECKERSTATE *const gState,CHECKER *move,int *const total,int *const MoveFlag)
{
int j,x,y,m,X,Y,XX,YY;
const CHECKER *Checker;
//通过TYPE值选择相应的棋子数组：PLA红方，COM黑方
if(gState->type)
Checker=gState->Pla;
else
Checker=gState->Com;
//棋子数组有12个结构体，当结构体中的i域为1时，表示该项有效
for(j=0;j<12&&Checker->i;j++,Checker++)
{
X=Checker->x;
Y=Checker->y;
for(m=0;m<4;m++)
{
x=w[m][0];
y=w[m][1];
XX=X+2*x;
YY=Y+2*y;
//是否为王或者方向相同
//前面第二个是否超出边界
//前面第一个是否为空，是否为对方棋子,前面第二个是否为空
if(((gState->state[Y][X]&2)||(y==(gState->type?-1:1)))\
&&(YY>=0)&&(YY<=7)&&(XX>=0)&&(XX<=7)\
&&((gState->state[Y+y][X+x]&12)==(12-gState->type*4))&&((gState->state[YY][XX]&9)==1))
{
//记录坐标及方向
if(!(move->i))
{
move->x=X;
move->y=Y;
}
move->i |= 1< }
}
if(move->i)
{
(*total)++;
move++;
}
}
if(*total)
{
*MoveFlag=2;
return 1;
}
else
return 0;
}
//--------------------------------------------------------
//连吃检测，并修改相应数据
//state:棋局数据
//Change:吃子的一方，棋子移动时修改其结构体中的x、y域
//Delete:被吃子的一方，此结构体数组须用SortChecker()函数重新排序
//X、Y:起始坐标
//type:指示吃子的一方，1：红，0：黑
void DoDoubleEat(STATE state,CHECKER Change[12],CHECKER Delete[12],int X,int Y,int type)
{
int i,x,y,XX,YY;
for(i=0;i<4;i++)
{
x=w[i][0];
y=w[i][1];
XX=X+2*x;
YY=Y+2*y;
if(((state[Y][X]&2)||(y==(type?-1:1)))\
&&(YY>=0)&&(YY<=7)&&(XX>=0)&&(XX<=7)\
&&((state[Y+y][X+x]&12)==(12-type*4))&&((state[YY][XX]&9)==1))
{
state[YY][XX]=state[Y][X];
Change[(state[Y][X]&0xf0)>>4].x=XX;
Change[(state[Y][X]&0xf0)>>4].y=YY;
if(!(state[Y][X]&2)&&(YY==7*(1-type)))
{
state[YY][XX] |= 2;
}
SortChecker(Delete,state,(state[Y+y][X+x]&0xf0)>>4);
state[Y][X]=1;
state[Y+y][X+x]=1;
DoDoubleEat(state,Change,Delete,XX,YY,type);
break;
}
}
}
//--------------------------------------------------------
//查找本方可移动的棋子,记录其坐标,记录可移动的方向
//类似于FindCanEat()函数
int FindCanMove(const CHECKERSTATE *const gState,CHECKER *move,int *const total,int *const MoveFlag)
{
int j,x,y,m,X,Y,XX,YY;
const CHECKER *Checker;
//通过TYPE值选择相应的棋子数组：PLA红方，COM黑方
if(gState->type)
Checker=gState->Pla;
else
Checker=gState->Com;
for(j=0;j<12&&Checker->i;j++,Checker++)
{
X=Checker->x;
Y=Checker->y;
for(m=0;m<4;m++)
{
x=w[m][0];
y=w[m][1];
XX=X+x;
YY=Y+y;
//是否为王或者方向相同
//前面一个是否超出边界
//前面一个是否为空
if(((gState->state[Y][X]&2)||(y==(gState->type?-1:1)))\
&&(YY>=0)&&(YY<=7)&&(XX>=0)&&(XX<=7)&&((gState->state[YY][XX]&9)==1))
{
if(!(move->i))
{
move->x=X;
move->y=Y;
}
move->i |= 1< }
}
if(move->i)
{
(*total)++;
move++;
}
}
if(*total)
{
*MoveFlag=1;
return 1;
}
else
return 0;
}
//--------------------------------------------------------
//复制数据到结构体
void InitForSearch(CHECKERSTATE *const gState)
{
int i;
const int *pstate;
int*gstate;
const CHECKER *pCom,*pPla;
CHECKER *gCom,*gPla;
gState->type=0;
gState->depth=0;
pstate=CheckerData[0];
gstate=gState->state[0];
pCom=Computer;
pPla=Player;
gCom=gState->Com;
gPla=gState->Pla;
for(i=0;i<64;i++)
{
*gstate++=*pstate++;
}
for(i=0;i<12;i++)
{
gCom->x=pCom->x;
gCom->y=pCom->y;
gCom->i=pCom->i;
gPla->x=pPla->x;
gPla->y=pPla->y;
gPla->i=pPla->i;
pCom++;
pPla++;
gCom++;
gPla++;
}
}
//--------------------------------------------------------
//两个结构体间复制数据
void InitForNextLevel(CHECKERSTATE *const pState,const CHECKERSTATE *const gState)
{
int i;
int *pstate;
const int*gstate;
CHECKER *pCom,*pPla;
const CHECKER *gCom,*gPla;
pState->type=gState->type^1;
pState->depth=gState->depth+1;
pstate=pState->state[0];
gstate=gState->state[0];
pCom=pState->Com;
pPla=pState->Pla;
gCom=gState->Com;
gPla=gState->Pla;
for(i=0;i<64;i++)
{
*pstate++=*gstate++;
}
for(i=0;i<12;i++)
{
pCom->x=gCom->x;
pCom->y=gCom->y;
pCom->i=gCom->i;
pPla->x=gPla->x;
pPla->y=gPla->y;
pPla->i=gPla->i;
pCom++;
pPla++;
gCom++;
gPla++;
}
}
//--------------------------------------------------------
//重新排列DATA数组
//i:数组起始位置
//Data:被排列的数组
//state:棋局数组
void SortChecker(CHECKER *Data,STATE state,int j)
{
CHECKER *pTemp;
Data += j;
pTemp = Data+1;
for(;j<12;j++,pTemp++,Data++)
{
if(j<11 && pTemp->i)
{
Data->x=pTemp->x;
Data->y=pTemp->y;
state[Data->y][Data->x] &= 0x0f;
state[Data->y][Data->x] |= j<<4;
}
else
{
Data->i=0;
break;
}
}
}
//--------------------------------------------------------
//检测 type方 有无棋子可移动 或 有无棋子可吃对方棋子 ，有则返回1，无则返回0
int CheckCanMove(const CHECKER *Data,const int (*const state)[8],int const type)
{
int j,X,Y,XX,YY;
for(j=0;j<12&&Data->i;j++,Data++)
{
int x,y,m;
X=Data->x;
Y=Data->y;
for(m=0;m<4;m++)
{
x=w[m][0];
y=w[m][1];
XX=X+2*x;
YY=Y+2*y;
if((state[Y][X]&2)||(y==(type?-1:1)))
{
if(((Y+y)>=0)&&((Y+y)<=7)&&((X+x)>=0)&&((X+x)<=7)&&((state[Y+y][X+x]&9)==1))
{
return 1;
}
else if((YY>=0)&&(YY<=7)&&(XX>=0)&&(XX<=7)\
&&((state[Y+y][X+x]&12)==(12-type*4))&&((state[YY][XX]&9)==1))
{
return 1;
}
}
}
}
return 0;
}
//--------------------------------------------------------
//查找普通棋子和成王棋子的数量
void getTotalChecker(const CHECKER *Data,const STATE state,int *common,int *king)
{
int j;
for(j=0;j<12&&Data->i;j++,Data++)
{
if(state[Data->y][Data->x]&2)
(*king)++;
else
(*common)++;
}
}
//--------------------------------------------------------
//查找 type方 将成王的棋子，记录数据返回
int getTotalBeKing(const CHECKER *Data,const STATE state,int const type)
{
int j,x,y,X,Y,count=0;
//通过type即可确定y的值
y=type?-1:1;
for(j=0;j<12&&Data->i;j++,Data++)
{
X=Data->x;
Y=Data->y;
if(!(state[Y][X]&2)) //不是王
{
for(x=-1;x<2;x+=2)
{
if(((Y+y)==7*(1-type))&&((X+x)>=0)&&((X+x)<=7)&&((state[Y+y][X+x]&9)==1))
{
count++;
break;
}
}
}
}
return count;
}
//--------------------------------------------------------
//返回本棋局的评估值，相对于黑棋，值越大越有利
int getValue(const CHECKERSTATE *const gState,int *const rTotal,int *const bTotal)
{
int rNum=0,bNum=0,rKing=0,bKing=0,rBeKing=0,bBeKing=0;
if (!CheckCanMove(gState->Pla,gState->state,1)) // 当红棋无子可走时，返最大值
return IMMOVE_MAX;
if (!CheckCanMove(gState->Com,gState->state,0)) // 当黑棋无子可走时，返最小值
return IMMOVE_MIN;
getTotalChecker(gState->Com,gState->state,&bNum,&bKing);
getTotalChecker(gState->Pla,gState->state,&rNum,&rKing);
bBeKing=getTotalBeKing(gState->Com,gState->state,0);
rBeKing=getTotalBeKing(gState->Pla,gState->state,1);
*rTotal = rNum+rKing;
*bTotal = bNum+bKing;
return (CHESS*(bNum-rNum)+KING*(bKing-rKing)+BEKING*(bBeKing-rBeKing));
}
阅读(6899) | 评论(5) | 转发(0) |
