#include
#include
#include
#include
/* Program of Game -- wuziqi Written by Zhang shuai, DEC.25th, 2010 */
#define GRID_NUM 15 //每一行(列)的棋盘交点数
#define GRID_COUNT 225//棋盘上交点总数
#define BLACK 0 //黑棋用0表示
#define WHITE 1 //白棋用1表示
#define NOSTONE 0xFF //没有棋子
//这组宏定义了用以代表几种棋型的数字
#define STWO 1 //眠二
#define STHREE 2 //眠三
#define SFOUR 3 //冲四
#define TWO 4 //活二
#define THREE 5 //活三
#define FOUR 6 //活四
#define FIVE 7 //五连
#define NOTYPE 11 //未定义
#define ANALSISED 255//已分析过的
#define TOBEANALSIS 0 //已分析过的
//这个宏用以检查某一坐标是否是棋盘上的有效落子点
#define IsValidPos(x,y) ((x>=0 && x=0 && y
//定义了枚举型的数据类型，精确，下边界，上边界
enumENTRY_TYPE{exact,lower_bound,upper_bound};
//哈希表中元素的结构定义
typedefstructHASHITEM
{
__int64checksum;//64位校验码
ENTRY_TYPE entry_type;//数据类型
shortdepth;//取得此值时的层次
shorteval;//节点的值
}HashItem;
typedefstructNode
{
intx;
inty;
}POINT;
//用以表示棋子位置的结构
typedefstruct_stoneposition
{
unsignedcharx;
unsignedchary;
}STONEPOS;
typedefstruct_movestone
{
unsignedcharnRenjuID;
POINT ptMovePoint;
}MOVESTONE;
//这个结构用以表示走法
typedefstruct_stonemove
{
STONEPOS StonePos;//棋子位置
intScore;//走法的分数
}STONEMOVE;
//=================================================================//
intAnalysisLine(unsignedchar* position,intGridNum,intStonePos);
intAnalysisRight(unsignedcharposition[][GRID_NUM],inti,intj);
intAnalysisLeft(unsignedcharposition[][GRID_NUM],inti,intj);
intAnalysisVertical(unsignedcharposition[][GRID_NUM],inti,intj);
intAnalysisHorizon(unsignedcharposition[][GRID_NUM],inti,intj);
intEveluate(unsignedintposition[][GRID_NUM],boolbIsWhiteTurn);
intAddMove(intnToX,intnToY,intnPly);
intCreatePossibleMove(unsignedcharposition[][GRID_NUM],intnPly,intnSide);
voidMergeSort(STONEMOVE* source,intn,booldirection);
voidMergePass(STONEMOVE* source,STONEMOVE* target,constints,constintn,constbooldirection);
voidMerge_A(STONEMOVE* source,STONEMOVE* target,intl,intm,intr);
voidMerge(STONEMOVE* source,STONEMOVE* target,intl,intm,intr);
voidEnterHistoryScore(STONEMOVE* move,intdepth);
intGetHistoryScore(STONEMOVE* move);
voidResetHistoryTable();
intNegaScout(intdepth,intalpha,intbeta);
voidSearchAGoodMove(unsignedcharposition[][GRID_NUM],intType);
intIsGameOver(unsignedcharposition[][GRID_NUM],intnDepth);
voidUnMakeMove(STONEMOVE* move);
unsignedcharMakeMove(STONEMOVE* move,inttype);
void_CSearchEngine();
voidInitializeHashKey();
voidEnterHashTable(ENTRY_TYPE entry_type,shorteval,shortdepth,intTableNo);
intLookUpHashTable(intalpha,intbeta,intdepth,intTableNo);
voidHash_UnMakeMove(STONEMOVE *move,unsignedcharCurPosition[][GRID_NUM]);
voidHash_MakeMove(STONEMOVE *move,unsignedcharCurPosition[][GRID_NUM]);
voidCalculateInitHashKey(unsignedcharCurPosition[][GRID_NUM]);
__int64rand64();
longrand32();
voidCTranspositionTable();
void_CTranspositionTable();
boolOnInitDialog();
//=================================================================//
intm_HistoryTable[GRID_NUM][GRID_NUM];//历史得分表
STONEMOVE m_TargetBuff[225];//排序用的缓冲队列
unsignedintm_nHashKey32[15][10][9];//32位随机树组，用以生成32位哈希值
unsigned__int64m_ulHashKey64[15][10][9];//64位随机树组，用以生成64位哈希值
HashItem *m_pTT[10];//置换表头指针
unsignedintm_HashKey32;//32位哈希值
__int64m_HashKey64;//64 位哈希值
STONEMOVE m_MoveList[10][225];//用以记录走法的数组
unsignedcharm_LineRecord[30];//存放AnalysisLine分析结果的数组
intTypeRecord[GRID_NUM ][GRID_NUM][4];//存放全部分析结果的数组,有三个维度,用于存放水平、垂直、左斜、右斜 4 个方向上所有棋型分析结果
intTypeCount[2][20];//存放统记过的分析结果的数组
intm_nMoveCount;//此变量用以记录走法的总数
unsignedcharCurPosition[GRID_NUM][GRID_NUM];//搜索时用于当前节点棋盘状态的数组
STONEMOVE m_cmBestMove;//记录最佳走法的变量
//CMoveGenerator* m_pMG; //走法产生器指针
//CEveluation* m_pEval; //估值核心指针
intm_nSearchDepth;//最大搜索深度
intm_nMaxDepth;//当前搜索的最大搜索深度
unsignedcharm_RenjuBoard[GRID_NUM][GRID_NUM];//棋盘数组，用于显示棋盘
intm_nUserStoneColor;//用户棋子的颜色
//CSearchEngine* m_pSE; //搜索引擎指针
intX,Y;
//位置重要性价值表,此表从中间向外,越往外价值越低
intPosValue[GRID_NUM][GRID_NUM]=
{
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,1,1,1,1,1,1,1,1,1,1,1,1,1,0},
{0,1,2,2,2,2,2,2,2,2,2,2,2,1,0},
{0,1,2,3,3,3,3,3,3,3,3,3,2,1,0},
{0,1,2,3,4,4,4,4,4,4,4,3,2,1,0},
{0,1,2,3,4,5,5,5,5,5,4,3,2,1,0},
{0,1,2,3,4,5,6,6,6,5,4,3,2,1,0},
{0,1,2,3,4,5,6,7,6,5,4,3,2,1,0},
{0,1,2,3,4,5,6,6,6,5,4,3,2,1,0},
{0,1,2,3,4,5,5,5,5,5,4,3,2,1,0},
{0,1,2,3,4,4,4,4,4,4,4,3,2,1,0},
{0,1,2,3,3,3,3,3,3,3,3,3,2,1,0},
{0,1,2,2,2,2,2,2,2,2,2,2,2,1,0},
{0,1,1,1,1,1,1,1,1,1,1,1,1,1,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
};
//全局变量,用以统计估值函数的执行遍数
intcount=0;
intEveluate(unsignedcharposition[][GRID_NUM],boolbIsWhiteTurn)
{
inti,j,k;
unsignedcharnStoneType;
count++;//计数器累加
//清空棋型分析结果
memset(TypeRecord,TOBEANALSIS,GRID_COUNT*4*4);
memset(TypeCount,0,40*4);
for(i=0;i
for(j=0;j
{
if(position[i][j]!=NOSTONE)
{
//如果水平方向上没有分析过
if(TypeRecord[i][j][0]==TOBEANALSIS)
AnalysisHorizon(position,i,j);
//如果垂直方向上没有分析过
if(TypeRecord[i][j][1]==TOBEANALSIS)
AnalysisVertical(position,i,j);
//如果左斜方向上没有分析过
if(TypeRecord[i][j][2]==TOBEANALSIS)
AnalysisLeft(position,i,j);
//如果右斜方向上没有分析过
if(TypeRecord[i][j][3]==TOBEANALSIS)
AnalysisRight(position,i,j);
}
}
//对分析结果进行统计,得到每种棋型的数量
for(i=0;i
for(j=0;j
for(k =0;k<4;k++)
{
nStoneType=position[i][j];
if(nStoneType!=NOSTONE)
{
switch(TypeRecord[i][j][k])
{
caseFIVE://五连
TypeCount[nStoneType][FIVE]++;
break;
caseFOUR://活四
TypeCount[nStoneType][FOUR]++;
break;
caseSFOUR://冲四
TypeCount[nStoneType][SFOUR]++;
break;
caseTHREE://活三
TypeCount[nStoneType][THREE]++;
break;
caseSTHREE://眠三
TypeCount[nStoneType][STHREE]++;
break;
caseTWO://活二
TypeCount[nStoneType][TWO]++;
break;
caseSTWO://眠二
TypeCount[nStoneType][STWO]++;
break;
default:
break;
}
}
}
//如果已五连,返回极值
if(bIsWhiteTurn)
{
if(TypeCount[BLACK][FIVE])
return-9999;
if(TypeCount[WHITE][FIVE])
return9999;
}
else
{
if(TypeCount[BLACK][FIVE])
return9999;
if(TypeCount[WHITE][FIVE])
return-9999;
}
//两个冲四等于一个活四
if(TypeCount[WHITE][SFOUR]>1)
TypeCount[WHITE][FOUR]++;
if(TypeCount[BLACK][SFOUR]>1)
TypeCount[BLACK][FOUR]++;
intWValue=0,BValue=0;
if(bIsWhiteTurn)//轮到白棋走
{
if(TypeCount[WHITE][FOUR])
return9990;//活四,白胜返回极值
if(TypeCount[WHITE][SFOUR])
return9980;//冲四,白胜返回极值
if(TypeCount[BLACK][FOUR])
return-9970;//白无冲四活四,而黑有活四,黑胜返回极值
if(TypeCount[BLACK][SFOUR] && TypeCount[BLACK][THREE])
return-9960;//而黑有冲四和活三,黑胜返回极值
if(TypeCount[WHITE][THREE] && TypeCount[BLACK][SFOUR]== 0)
return9950;//白有活三而黑没有四,白胜返回极值
if(TypeCount[BLACK][THREE]>1 && TypeCount[WHITE][SFOUR]==0 && TypeCount[WHITE][THREE]==0 && TypeCount[WHITE][STHREE]==0)
return-9940;//黑的活三多于一个,而白无四和三,黑胜返回极值
if(TypeCount[WHITE][THREE]>1)
WValue+=2000;//白活三多于一个,白棋价值加2000
else
//否则白棋价值加200
if(TypeCount[WHITE][THREE])
WValue+=200;
if(TypeCount[BLACK][THREE]>1)
BValue+=500;//黑的活三多于一个,黑棋价值加500
else
//否则黑棋价值加100
if(TypeCount[BLACK][THREE])
BValue+=100;
//每个眠三加10
if(TypeCount[WHITE][STHREE])
WValue+=TypeCount[WHITE][STHREE]*10;
//每个眠三加10
if(TypeCount[BLACK][STHREE])
BValue+=TypeCount[BLACK][STHREE]*10;
//每个活二加4
if(TypeCount[WHITE][TWO])
WValue+=TypeCount[WHITE][TWO]*4;
//每个活二加4
if(TypeCount[BLACK][STWO])
BValue+=TypeCount[BLACK][TWO]*4;
//每个眠二加1
if(TypeCount[WHITE][STWO])
WValue+=TypeCount[WHITE][STWO];
//每个眠二加1
if(TypeCount[BLACK][STWO])
BValue+=TypeCount[BLACK][STWO];
}
else//轮到黑棋走
{
if(TypeCount[BLACK][FOUR])
return9990;//活四,黑胜返回极值
if(TypeCount[BLACK][SFOUR])
return9980;//冲四,黑胜返回极值
if(TypeCount[WHITE][FOUR])
return-9970;//活四,白胜返回极值
if(TypeCount[WHITE][SFOUR] && TypeCount[WHITE][THREE])
return-9960;//冲四并活三,白胜返回极值
if(TypeCount[BLACK][THREE] && TypeCount[WHITE][SFOUR]==0)
return9950;//黑活三,白无四。黑胜返回极值
if(TypeCount[WHITE][THREE]>1 && TypeCount[BLACK][SFOUR]==0 && TypeCount[BLACK][THREE]==0 && TypeCount[BLACK][STHREE]==0)
return-9940;//白的活三多于一个,而黑无四和三,白胜返回极值
//黑的活三多于一个,黑棋价值加2000
if(TypeCount[BLACK][THREE]>1)
BValue+=2000;
else
//否则黑棋价值加200
if(TypeCount[BLACK][THREE])
BValue+=200;
//白的活三多于一个,白棋价值加 500
if(TypeCount[WHITE][THREE]>1)
WValue+=500;
else
//否则白棋价值加100
if(TypeCount[WHITE][THREE])
WValue+=100;
//每个眠三加10
if(TypeCount[WHITE][STHREE])
WValue+=TypeCount[WHITE][STHREE]*10;
//每个眠三加10
if(TypeCount[BLACK][STHREE])
BValue+=TypeCount[BLACK][STHREE]*10;
//每个活二加4
if(TypeCount[WHITE][TWO])
WValue+=TypeCount[WHITE][TWO]*4;
//每个活二加4
if(TypeCount[BLACK][STWO])
BValue+=TypeCount[BLACK][TWO]*4;
//每个眠二加1
if(TypeCount[WHITE][STWO])
WValue+=TypeCount[WHITE][STWO];
//每个眠二加1
if(TypeCount[BLACK][STWO])
BValue+=TypeCount[BLACK][STWO];
}
//加上所有棋子的位置价值
for(i=0;i
for(j=0;j
{
nStoneType=position[i][j];
if(nStoneType!=NOSTONE)
if(nStoneType==BLACK)
BValue+=PosValue[i][j];
else
WValue+=PosValue[i][j];
}
//返回估值
if(!bIsWhiteTurn)
returnBValue-WValue;
else
returnWValue-BValue;
}
//分析棋盘上某点在水平方向上的棋型
intAnalysisHorizon(unsignedcharposition[][GRID_NUM],inti,intj)
{
//调用直线分析函数分析
AnalysisLine(position[i],15,j);
//拾取分析结果
for(ints=0;s<15;s++)
if(m_LineRecord[s]!=TOBEANALSIS)
TypeRecord[i][s][0]= m_LineRecord[s];
returnTypeRecord[i][j][0];
}
//分析棋盘上某点在垂直方向上的棋型
intAnalysisVertical(unsignedcharposition[][GRID_NUM],inti,intj)
{
unsignedchartempArray[GRID_NUM];
//将垂直方向上的棋子转入一维数组
for(intk=0;k
tempArray[k]=position[k][j];
//调用直线分析函数分析
AnalysisLine(tempArray,GRID_NUM,i);
//拾取分析结果
for(ints=0;s
if(m_LineRecord[s]!=TOBEANALSIS)
TypeRecord[s][j][1]=m_LineRecord[s];
returnTypeRecord[i][j][1];
}
//分析棋盘上某点在左斜方向上的棋型
intAnalysisLeft(unsignedcharposition[][GRID_NUM],inti,intj)
{
unsignedchartempArray[GRID_NUM];
intx,y;
if(i
{
y=0;
x=j-i;
}
else
{
x=0;
y=i-j;
}
//将斜方向上的棋子转入一维数组
for(intk=0;k
{
if(x+k>14 || y+k>14)
break;
tempArray[k]=position[y+k][x+k];
}
//调用直线分析函数分析
AnalysisLine(tempArray,k,j-x);
//拾取分析结果
for(ints=0;s
if(m_LineRecord[s]!=TOBEANALSIS)
TypeRecord[y+s][x+s][2]=m_LineRecord[s];
returnTypeRecord[i][j][2];
}
//分析棋盘上某点在右斜方向上的棋型
intAnalysisRight(unsignedcharposition[][GRID_NUM],inti,intj)
{
unsignedchartempArray[GRID_NUM];
intx,y,realnum;
if(14-i
{
y=14;
x=j-14+i;
realnum=14-i;
}
else
{
x=0;
y=i+j;
realnum=j;
}
//将斜方向上的棋子转入一维数组
for(intk=0;k
{
if(x+k>14 || y-k<0)
break;
tempArray[k]=position[y-k][x+k];
}
//调用直线分析函数分析
AnalysisLine(tempArray,k,j-x);
//拾取分析结果
for(ints=0;s
if(m_LineRecord[s]!=TOBEANALSIS)
TypeRecord[y-s][x+s][3]=m_LineRecord[s];
returnTypeRecord[i][j][3];
}
intAnalysisLine(unsignedchar* position,intGridNum,intStonePos)
{
unsignedcharStoneType;
unsignedcharAnalyLine[30];
intnAnalyPos;
intLeftEdge,RightEdge;
intLeftRange,RightRange;
if(GridNum<5)
{
//数组长度小于5没有意义
memset(m_LineRecord,ANALSISED,GridNum);
return0;
}
nAnalyPos=StonePos;
memset(m_LineRecord,TOBEANALSIS,30);
memset(AnalyLine,0x0F,30);
//将传入数组装入AnalyLine;
memcpy(&AnalyLine,position,GridNum);
GridNum--;
StoneType=AnalyLine[nAnalyPos];
LeftEdge=nAnalyPos;
RightEdge=nAnalyPos;
//算连续棋子左边界
while(LeftEdge>0)
{
if(AnalyLine[LeftEdge-1]!=StoneType)
break;
LeftEdge--;
}
//算连续棋子右边界
while(RightEdge
{
if(AnalyLine[RightEdge+1]!=StoneType)
break;
RightEdge++;
}
LeftRange=LeftEdge;
RightRange=RightEdge;
//下面两个循环算出棋子可下的范围
while(LeftRange>0)
{
if(AnalyLine[LeftRange -1]==!StoneType)
break;
LeftRange--;
}
while(RightRange
{
if(AnalyLine[RightRange+1]==!StoneType)
break;
RightRange++;
}
//如果此范围小于4则分析没有意义
if(RightRange-LeftRange<4)
{
for(intk=LeftRange;k<=RightRange;k++)
m_LineRecord[k]=ANALSISED;
returnfalse;
}
//将连续区域设为分析过的,防止重复分析此一区域
for(intk=LeftEdge;k<=RightEdge;k++)
m_LineRecord[k]=ANALSISED;
if(RightEdge-LeftEdge>3)
{
//如待分析棋子棋型为五连
m_LineRecord[nAnalyPos]=FIVE;
returnFIVE;
}
if(RightEdge-LeftEdge== 3)
{
//如待分析棋子棋型为四连
boolLeftfour=false;
if(LeftEdge>0)
if(AnalyLine[LeftEdge-1]==NOSTONE)
Leftfour=true;//左边有气
if(RightEdge
//右边未到边界
if(AnalyLine[RightEdge+1]==NOSTONE)
//右边有气
if(Leftfour==true)//如左边有气
m_LineRecord[nAnalyPos]=FOUR;//活四
else
m_LineRecord[nAnalyPos]=SFOUR;//冲四
else
if(Leftfour==true)//如左边有气
m_LineRecord[nAnalyPos]=SFOUR;//冲四
else
if(Leftfour==true)//如左边有气
m_LineRecord[nAnalyPos]=SFOUR;//冲四
returnm_LineRecord[nAnalyPos];
}
if(RightEdge-LeftEdge==2)
{
//如待分析棋子棋型为三连
boolLeftThree=false;
if(LeftEdge>1)
if(AnalyLine[LeftEdge-1]==NOSTONE)
//左边有气
if(LeftEdge>1 && AnalyLine[LeftEdge-2]==AnalyLine[LeftEdge])
{
//左边隔一空白有己方棋子
m_LineRecord[LeftEdge]=SFOUR;//冲四
m_LineRecord[LeftEdge-2]=ANALSISED;
}
else
LeftThree=true;
if(RightEdge
if(AnalyLine[RightEdge+1]==NOSTONE)
//右边有气
if(RightEdge
{
//右边隔1个己方棋子
m_LineRecord[RightEdge]=SFOUR;//冲四
m_LineRecord[RightEdge+2]=ANALSISED;
}
else
if(LeftThree==true)//如左边有气
m_LineRecord[RightEdge]=THREE;//活三
else
m_LineRecord[RightEdge]=STHREE;//冲三
else
{
if(m_LineRecord[LeftEdge]==SFOUR)//如左冲四
returnm_LineRecord[LeftEdge];//返回
if(LeftThree==true)//如左边有气
m_LineRecord[nAnalyPos]=STHREE;//眠三
}
else
{
if(m_LineRecord[LeftEdge]==SFOUR)//如左冲四
returnm_LineRecord[LeftEdge];//返回
if(LeftThree==true)//如左边有气
m_LineRecord[nAnalyPos]=STHREE;//眠三
}
returnm_LineRecord[nAnalyPos];
}
if(RightEdge-LeftEdge==1)
{
//如待分析棋子棋型为二连
boolLefttwo=false;
boolLeftthree=false;
if(LeftEdge>2)
if(AnalyLine[LeftEdge-1]==NOSTONE)
//左边有气
if(LeftEdge-1>1 && AnalyLine[LeftEdge-2]==AnalyLine[LeftEdge])
if(AnalyLine[LeftEdge-3]==AnalyLine[LeftEdge])
{
//左边隔2个己方棋子
m_LineRecord[LeftEdge-3]=ANALSISED;
m_LineRecord[LeftEdge-2]=ANALSISED;
m_LineRecord[LeftEdge]=SFOUR;//冲四
}
else
if(AnalyLine[LeftEdge-3]==NOSTONE)
{
//左边隔1个己方棋子
m_LineRecord[LeftEdge-2]=ANALSISED;
m_LineRecord[LeftEdge]=STHREE;//眠三
}
else
Lefttwo=true;
if(RightEdge
if(AnalyLine[RightEdge+1]==NOSTONE)
//右边有气
if(RightEdge+1
if(AnalyLine[RightEdge+3]==AnalyLine[RightEdge])
{
//右边隔两个己方棋子
m_LineRecord[RightEdge+3]=ANALSISED;
m_LineRecord[RightEdge+2]=ANALSISED;
m_LineRecord[RightEdge]=SFOUR;//冲四
}
else
if(AnalyLine[RightEdge+3]==NOSTONE)
{
//右边隔 1 个己方棋子
m_LineRecord[RightEdge+2]=ANALSISED;
m_LineRecord[RightEdge]=STHREE;//眠三
}
else
{
if(m_LineRecord[LeftEdge]==SFOUR)//左边冲四
returnm_LineRecord[LeftEdge];//返回
if(m_LineRecord[LeftEdge]==STHREE)//左边眠三
returnm_LineRecord[LeftEdge];
if(Lefttwo==true)
m_LineRecord[nAnalyPos]=TWO;//返回活二
else
m_LineRecord[nAnalyPos]=STWO;//眠二
}
else
{
if(m_LineRecord[LeftEdge]==SFOUR)//冲四返回
returnm_LineRecord[LeftEdge];
if(Lefttwo==true)//眠二
m_LineRecord[nAnalyPos]=STWO;
}
returnm_LineRecord[nAnalyPos];
}
return0;
}
//将历史记录表中所有项目全置为初值
voidResetHistoryTable()
{
memset(m_HistoryTable,10,GRID_COUNT*sizeof(int));
}
//从历史得分表中取给定走法的历史得分
intGetHistoryScore(STONEMOVE* move)
{
returnm_HistoryTable[move->StonePos.x][move->StonePos.y];
}
//将一最佳走法汇入历史记录
voidEnterHistoryScore(STONEMOVE* move,intdepth)
{
m_HistoryTable[move->StonePos.x][move->StonePos.y]+=2<
}
//对走法队列从小到大排序
//STONEMOVE* source原始队列
//STONEMOVE* target目标队列
//合并source[l…m]和 source[m +1…r]至target[l…r]
voidMerge(STONEMOVE* source,STONEMOVE* target,intl,intm,intr)
{
//从小到大排序
inti=l;
intj=m+1;
intk=l;
while(i<=m && j<=r)
if(source[i].Score<=source[j].Score)
target[k++]=source[i++];
else
target[k++]=source[j++];
if(i>m)
for(intq=j;q<=r;q++)
target[k++]=source[q];
else
for(intq=i;q<=m;q++)
target[k++]=source[q];
}
voidMerge_A(STONEMOVE* source,STONEMOVE* target,intl,intm,intr)
{
//从大到小排序
inti=l;
intj=m+1;
intk=l;
while(i<=m &&j<=r)
if(source[i].Score>=source[j].Score)
target[k++]=source[i++];
else
target[k++]=source[j++];
if(i>m)
for(intq=j;q<=r;q++)
target[k++]=source[q];
else
for(intq=i;q<=m;q++)
target[k++]=source[q];
}
//合并大小为 S 的相邻子数组
//direction 是标志,指明是从大到小还是从小到大排序
voidMergePass(STONEMOVE* source,STONEMOVE* target,constints,constintn,constbooldirection)
{
inti=0;
while(i<=n-2*s)
{
//合并大小为 s的相邻二段子数组
if(direction)
Merge(source,target,i,i+s-1,i+2*s-1);
else
Merge_A(source,target,i,i+s-1,i+2*s-1);
i=i+2*s;
}
if(i+s
{
if(direction)
Merge(source,target,i,i+s-1,n-1);
else
Merge_A(source,target,i,i+s-1,n-1);
}
else
for(intj=i;j<=n-1;j++)
target[j]=source[j];
}
voidMergeSort(STONEMOVE* source,intn,booldirection)
{
ints=1;
while(s
{
MergePass(source,m_TargetBuff,s,n,direction);
s+=s;
MergePass(m_TargetBuff,source,s,n,direction);
s+=s;
}
}
intCreatePossibleMove(unsignedcharposition[][GRID_NUM],intnPly,intnSide)
{
inti,j;
m_nMoveCount=0;
for(i=0;i
for(j=0;j
{
if(position[i][j]==(unsignedchar)NOSTONE)
AddMove(j,i,nPly);
}
//使用历史启发类中的静态归并排序函数对走法队列进行排序
//这是为了提高剪枝效率
// CHistoryHeuristic history;
MergeSort(m_MoveList[nPly],m_nMoveCount,0);
returnm_nMoveCount;//返回合法走法个数
}
//在m_MoveList中插入一个走法
//nToX是目标位置横坐标
//nToY是目标位置纵坐标
//nPly是此走法所在的层次
intAddMove(intnToX,intnToY,intnPly)
{
m_MoveList[nPly][m_nMoveCount].StonePos.x=nToX;
m_MoveList[nPly][m_nMoveCount].StonePos.y=nToY;
m_nMoveCount++;
m_MoveList[nPly][m_nMoveCount].Score=PosValue[nToY][nToX];//使用位置价值表评估当前走法的价值
returnm_nMoveCount;
}
voidCNegaScout_TT_HH()
{
ResetHistoryTable();
// m_pThinkProgress=NULL;
}
voidSearchAGoodMove(unsignedcharposition[][GRID_NUM],intType)
{
intScore;
memcpy(CurPosition,position,GRID_COUNT);
m_nMaxDepth=m_nSearchDepth;
CalculateInitHashKey(CurPosition);
ResetHistoryTable();
Score=NegaScout(m_nMaxDepth,-20000,20000);
X=m_cmBestMove.StonePos.y;
Y=m_cmBestMove.StonePos.x;
MakeMove(&m_cmBestMove,Type);
memcpy(position,CurPosition,GRID_COUNT);
}
intIsGameOver(unsignedcharposition[][GRID_NUM],intnDepth)
{
intscore,i;//计算要下的棋子颜色
i=(m_nMaxDepth-nDepth)%2;
score=Eveluate(position,i);//调用估值函数
if(abs(score)>8000)//如果估值函数返回极值，给定局面游戏结束
returnscore;//返回极值
return0;//返回未结束
}
intNegaScout(intdepth,intalpha,intbeta)
{
intCount,i;
unsignedchartype;
inta,b,t;
intside;
intscore;
/* if(depth>0)
{
i= IsGameOver(CurPosition,depth);
if(i!=0)
return i; //已分胜负，返回极值
}
*/
side=(m_nMaxDepth-depth)%2;//计算当前节点的类型,极大0/极小1
score=LookUpHashTable(alpha,beta,depth,side);
if(score!=66666)
returnscore;
if(depth<=0)//叶子节点取估值
{
score=Eveluate(CurPosition,side);
EnterHashTable(exact,score,depth,side);//将估值存入置换表
returnscore;
}
Count=CreatePossibleMove(CurPosition,depth,side);
for(i=0;i
m_MoveList[depth][i].Score=GetHistoryScore(&m_MoveList[depth][i]);
MergeSort(m_MoveList[depth],Count,0);
intbestmove=-1;
a=alpha;
b=beta;
inteval_is_exact=0;
for(i=0;i
{
type=MakeMove(&m_MoveList[depth][i],side);
Hash_MakeMove(&m_MoveList[depth][i],CurPosition);
t=-NegaScout(depth-1,-b,-a);//递归搜索子节点，对第 1 个节点是全窗口，其后是空窗探测
if(t>a && t0)
{
//对于第一个后的节点,如果上面的搜索failhigh
a=-NegaScout(depth-1,-beta,-t);//re-search
eval_is_exact=1;//设数据类型为精确值
if(depth==m_nMaxDepth)
m_cmBestMove=m_MoveList[depth][i];
bestmove=i;
}
Hash_UnMakeMove(&m_MoveList[depth][i],CurPosition);
UnMakeMove(&m_MoveList[depth][i]);
if(a
{
eval_is_exact=1;
a=t;
if(depth==m_nMaxDepth)
m_cmBestMove=m_MoveList[depth][i];
}
if(a>= beta)
{
EnterHashTable(lower_bound,a,depth,side);
EnterHistoryScore(&m_MoveList[depth][i],depth);
returna;
}
b=a+1;/* set new null window */
}
if(bestmove!=-1)
EnterHistoryScore(&m_MoveList[depth][bestmove], depth);
if(eval_is_exact)
EnterHashTable(exact,a,depth,side);
else
EnterHashTable(upper_bound,a,depth,side);
returna;
}
unsignedcharMakeMove(STONEMOVE* move,inttype)
{
CurPosition[move->StonePos.y][move->StonePos.x]=type;
return0;
}
voidUnMakeMove(STONEMOVE* move)
{
CurPosition[move->StonePos.y][move->StonePos.x]=NOSTONE;
}
__int64rand64(void)
{
returnrand()^((__int64)rand()<<15)^((__int64)rand()<<30)^
((__int64)rand()<<45)^((__int64)rand()<<60);
}
//生成32位随机数
longrand32(void)
{
returnrand()^((long)rand()<<15)^((long)rand()<<30);
}
voidCTranspositionTable()
{
InitializeHashKey();//建立哈希表，创建随机数组
}
void_CTranspositionTable()
{
//释放哈希表所用空间
deletem_pTT[0];
deletem_pTT[1];
}
voidCalculateInitHashKey(unsignedcharCurPosition[][GRID_NUM])
{
intj,k,nStoneType;
m_HashKey32=0;
m_HashKey32=0;
//将所有棋子对应的哈希数加总
for(j=0;j
for(k=0;k
{
nStoneType=CurPosition[j][k];
if(nStoneType!=0xFF)
{
m_HashKey32=m_HashKey32^m_nHashKey32[nStoneType][j][k];
m_HashKey64=m_HashKey64^m_ulHashKey64[nStoneType][j][k];
}
}
}
voidHash_MakeMove(STONEMOVE *move,unsignedcharCurPosition[][GRID_NUM])
{
inttype;
type=CurPosition[move->StonePos.y][move->StonePos.x];//将棋子在目标位置的随机数添入
m_HashKey32=m_HashKey32^m_nHashKey32[type][move->StonePos.y][move->StonePos.x];
m_HashKey64=m_HashKey64^m_ulHashKey64[type][move->StonePos.y][move->StonePos.x];
}
voidHash_UnMakeMove(STONEMOVE *move,unsignedcharCurPosition[][GRID_NUM])
{
inttype;
type=CurPosition[move->StonePos.y][move->StonePos.x];//将棋子现在位置上的随机数从哈希值当中去除
m_HashKey32=m_HashKey32^m_nHashKey32[type][move->StonePos.y][move->StonePos.x];
m_HashKey64=m_HashKey64^m_ulHashKey64[type][move->StonePos.y][move->StonePos.x];
}
intLookUpHashTable(intalpha,intbeta,intdepth,intTableNo)
{
intx;
HashItem* pht;
//计算二十位哈希地址，如果读者设定的哈希表大小不是 1M*2 的,
//而是 TableSize*2，TableSize为读者设定的大小
//则需要修改这一句为m_HashKey32% TableSize
//下一个函数中这一句也一样
x=m_HashKey32 & 0xFFFFF;
pht=&m_pTT[TableNo][x];//取到具体的表项指针
if(pht->depth>=depth && pht->checksum==m_HashKey64)
{
switch(pht->entry_type)//判断数据类型
{
caseexact://确切值
returnpht->eval;
caselower_bound://下边界
if(pht->eval>=beta)
returnpht->eval;
else
break;
caseupper_bound://上边界
if(pht->eval<=alpha)
returnpht->eval;
else
break;
}
}
return66666;
}
voidEnterHashTable(ENTRY_TYPE entry_type,shorteval,shortdepth,intTableNo)
{
intx;
HashItem* pht;
x=m_HashKey32 & 0xFFFFF;//计算二十位哈希地址
pht=&m_pTT[TableNo][x];//取到具体的表项指针
//将数据写入哈希表
pht->checksum=m_HashKey64;//64位校验码
pht->entry_type=entry_type;//表项类型
pht->eval=eval;//要保存的值
pht->depth=depth;//层次
}
voidInitializeHashKey()
{
inti,j,k;
srand((unsigned)time(NULL));
//填充随机数组
for(i=0;i<15;i++)
for(j=0;j<10;j++)
for(k=0;k<9;k++)
{
m_nHashKey32[i][j][k]=rand32();
m_ulHashKey64[i][j][k]=rand64();
}
//申请置换表所用空间。1M "2 个条目，读者也可指定其他大小
m_pTT[0]=newHashItem[1024*1024];//用于存放取极大值的节点数据
m_pTT[1]=newHashItem[1024*1024];//用于存放取极小值的节点数据
}
intmain()
{
intcolour;
charcommand[10];//用于保存命令的字符串
for(inti = 0; i < GRID_NUM; i++)
for(intj = 0; j < GRID_NUM; j++)
m_RenjuBoard[i][j] = NOSTONE;//棋盘初始化
cin >> command;
if(strcmp(command,"[START]") != 0)//读入第一条命令
{
return0;//如果不是[START]则停止程序
}
cin >> colour;//读入己方颜色
colour=colour-1;
m_nUserStoneColor=1-colour;
while(true)
{
intrival_x, rival_y;//用于保存对手上一步落子点
cin >> command;//读入命令
if(strcmp(command,"[PUT]") != 0)
break;//如果不是[PUT]则停止程序
cin >> rival_x >> rival_y;//读入对手上一步落子点
if(colour == 0 && rival_x == -1 && rival_y == -1)//如果己方执黑且是第一步，则占据棋盘中心位置
{
m_RenjuBoard[GRID_NUM / 2][GRID_NUM / 2] = colour;//更新棋盘信息
cout << GRID_NUM / 2 <<' '<< GRID_NUM / 2 << endl;//输出
cout << flush;//刷新缓冲区
}
else
{
m_RenjuBoard[rival_x][rival_y] = 1 - colour;
//更新棋盘信息
m_nSearchDepth=3;
//最大搜索深度
do
{
CNegaScout_TT_HH();//创建NegaScout_TT_HH搜索引擎
CTranspositionTable();
SearchAGoodMove(m_RenjuBoard,colour);
m_RenjuBoard[X][Y]=colour;
cout << X <<' '<< Y << endl;//输出
cout << flush;//刷新缓冲区
_CTranspositionTable();
break;//结束循环
}
while(true);
//循环直至随机得到一个空位置
}
}
return0;
}
网友评论