五子棋人机对弈代码——之博弈树算法

#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;

}

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,590评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 86,808评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,151评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,779评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,773评论 5赞 367
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,656评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,022评论 3赞 398
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,678评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 41,038评论 1赞 299
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,659评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,756评论 1赞 330
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,411评论 4赞 321
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,005评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,973评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,203评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,053评论 2赞 350
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,495评论 2赞 343

推荐阅读更多精彩内容