16五子棋人机对弈_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
16五子棋人机对弈
阅读已结束，如果下载本文需要使用
想免费下载本文？
下载文档到电脑，查找使用更方便
还剩23页未读，继续阅读
你可能喜欢使用合作账号一键登录：
五子棋技巧 五子棋对弈中如何盘盘赢
　　五子棋是一项非常广泛的棋类游戏，学起来也不难，在所有棋类游戏中，会五子棋的人居多。虽然五子棋看起来简单，但是你想赢，也不是件易事。下五子棋有哪些技巧呢?如何才能够赢呢?下面就由小编为大家分析下吧。
　　1、 2、
　　3、 4、
　　5、 6、
　　五子棋的特点
　　五子棋是一项两个人对弈的纯策略型的棋类游戏，一般情况下双方两个人分别使用白色棋子和黑色棋子，然后下在棋盘直线与横线的交叉点上，谁先形成5子连线者就胜利了。
　　棋具与围棋通用，起源于中国上古时代的传统黑白棋种之一。主要流行于华人和汉字文化圈的国家以及欧美一些地区。
　　容易上手，老少皆宜，而且趣味横生，引人入胜;不仅能增强思维能力，提高智力，而且富含哲理，有助于修身养性。
　　五子棋具有四大特点，分别是，易学、快捷、深奥、普及。
　　(一)易学与深奥并存
　　五子棋的&易&，易在人门。规则简单而有趣，从不会到会下棋.不需高智商.不需时间长，不需论其年龄的幼与长。有一副棋盘、棋子就可对弈，占地只需2米见方。
　　五子棋的深奥是指棋理深，人门后深钻研下去，又能探索到变化莫测的攻防技巧，逐步体会到阴阳易理的高深哲理。它具有东方的神秘和西方的直观，是中西文化的交汇，是古今哲理的结晶。
　　(二)快捷与普及互促
　　五子棋空抨开局.节省了满盘开局棋种的摆子时间。落子交叉点比围棋少100多个。不吃子，没有消长子的反复。和棋成定局的均势棋，双方耗时最多耗不过225手棋就到尽头。五子棋不比占地盘大小，不比谁连五的次数多，判断胜负启用突然死亡法，一个连五形或黑方走出禁手的出现，就定胜负而局终，未走满整个棋盘就定胜负的居多。综上所述，五子棋对局用时总体比其他棋种少。
　　五子棋玩起来，节奏快捷，而且入门也很简单，这使得五子棋的普及面非常广泛。不信，你可以问问周围的人会下什么棋，肯定是五子棋最多。同样的，你走到中小学校问问学生，会下什么棋，自称会下五子棋的人占多数。
　　网络上下五子棋的人数，基本保持在各棋种前三位的地位。
　　基于五子棋以上所述的特点，会给对弈者带来诸多益处是不言而喻的了。
相关阅读推荐:
癌症每个人都害怕，但是喝了它保你一生不得癌。
这是一个神奇的运动，可以让你迅速瘦身，脱胎换骨。
呼吸是生存的根本，如果呼吸停止那生命也就结束了。
我要点评（0人参与，0条评论）
10天内自动登录
使用合作账号一键登录：4252人阅读
#include&iostream.h&
#include&stdlib.h&
#include&string.h&
#include&time.h&
/* Program of Game -- wuziqi Written by Zhang shuai, DEC.25th, 2010 */
#define GRID_NUM
15 //每一行(列)的棋盘交点数
#define GRID_COUNT
225//棋盘上交点总数
#define BLACK
//黑棋用0表示
#define WHITE
//白棋用1表示
#define NOSTONE 0xFF
//没有棋子
//这组宏定义了用以代表几种棋型的数字
#define STWO
#define STHREE
#define SFOUR
#define TWO
#define THREE
#define FOUR
#define FIVE
#define NOTYPE
11 //未定义
#define ANALSISED
255//已分析过的
#define TOBEANALSIS 0
//已分析过的
//这个宏用以检查某一坐标是否是棋盘上的有效落子点
#define IsValidPos(x,y) ((x&=0 && x&GRID_NUM) && (y&=0 && y&GRID_NUM)
//定义了枚举型的数据类型，精确，下边界，上边界
enum ENTRY_TYPE{exact,lower_bound,upper_bound};
//哈希表中元素的结构定义
typedef struct HASHITEM
//64位校验码
ENTRY_TYPE entry_//数据类型
//取得此值时的层次
//节点的值
typedef struct Node
//用以表示棋子位置的结构
typedef struct _stoneposition
}STONEPOS;
typedef struct _movestone
unsigned char nRenjuID;
POINT ptMoveP
}MOVESTONE;
//这个结构用以表示走法
typedef struct _stonemove
STONEPOS StoneP//棋子位置
//走法的分数
}STONEMOVE;
//=================================================================//
int AnalysisLine(unsigned char* position,int GridNum,int StonePos);
int AnalysisRight(unsigned char position[][GRID_NUM],int i,int j);
int AnalysisLeft(unsigned char position[][GRID_NUM],int i,int j);
int AnalysisVertical(unsigned char position[][GRID_NUM],int i,int j);
int AnalysisHorizon(unsigned char position[][GRID_NUM],int i,int j);
int Eveluate(unsigned int position[][GRID_NUM],bool bIsWhiteTurn);
int AddMove(int nToX, int nToY, int nPly);
int CreatePossibleMove(unsigned char position[][GRID_NUM], int nPly, int nSide);
void MergeSort(STONEMOVE* source,int n,bool direction);
void MergePass(STONEMOVE* source,STONEMOVE* target,const int s,const int n,const bool direction);
void Merge_A(STONEMOVE* source,STONEMOVE* target,int l,int m,int r);
void Merge(STONEMOVE* source,STONEMOVE* target,int l,int m,int r);
void EnterHistoryScore(STONEMOVE* move,int depth);
int GetHistoryScore(STONEMOVE* move);
void ResetHistoryTable();
int NegaScout(int depth,int alpha,int beta);
void SearchAGoodMove(unsigned char position[][GRID_NUM],int Type);
int IsGameOver(unsigned char position[][GRID_NUM],int nDepth);
void UnMakeMove(STONEMOVE* move);
unsigned char MakeMove(STONEMOVE* move,int type);
void _CSearchEngine();
void InitializeHashKey();
void EnterHashTable(ENTRY_TYPE entry_type, short eval, short depth, int TableNo);
int LookUpHashTable(int alpha, int beta, int depth, int TableNo);
void Hash_UnMakeMove(STONEMOVE *move,unsigned char CurPosition[][GRID_NUM]);
void Hash_MakeMove(STONEMOVE *move,unsigned char CurPosition[][GRID_NUM]);
void CalculateInitHashKey(unsigned char CurPosition[][GRID_NUM]);
__int64 rand64();
long rand32();
void CTranspositionTable();
void _CTranspositionTable();
bool OnInitDialog();
//=================================================================//
int m_HistoryTable[GRID_NUM][GRID_NUM];//历史得分表
STONEMOVE m_TargetBuff[225];
//排序用的缓冲队列
unsigned int m_nHashKey32[15][10][9];
//32位随机树组，用以生成32位哈希值
unsigned __int64 m_ulHashKey64[15][10][9];//64位随机树组，用以生成64位哈希值
HashItem *m_pTT[10];
//置换表头指针
unsigned int m_HashKey32;
//32位哈希值
__int64 m_HashKey64;
//64 位哈希值
STONEMOVE m_MoveList[10][225];//用以记录走法的数组
unsigned char m_LineRecord[30];
//存放AnalysisLine分析结果的数组
int TypeRecord[GRID_NUM ][GRID_NUM][4];//存放全部分析结果的数组,有三个维度,用于存放水平、垂直、左斜、右斜 4 个方向上所有棋型分析结果
int TypeCount[2][20];
//存放统记过的分析结果的数组
int m_nMoveC//此变量用以记录走法的总数
unsigned char CurPosition[GRID_NUM][GRID_NUM];//搜索时用于当前节点棋盘状态的数组
STONEMOVE m_cmBestM
//记录最佳走法的变量
//CMoveGenerator* m_pMG;
//走法产生器指针
//CEveluation* m_pE
//估值核心指针
int m_nSearchD
//最大搜索深度
int m_nMaxD
//当前搜索的最大搜索深度
unsigned char m_RenjuBoard[GRID_NUM][GRID_NUM];//棋盘数组，用于显示棋盘
int m_nUserStoneC
//用户棋子的颜色
//CSearchEngine* m_pSE;
//搜索引擎指针
//位置重要性价值表,此表从中间向外,越往外价值越低
int PosValue[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}
//全局变量,用以统计估值函数的执行遍数
int count=0;
int Eveluate(unsigned char position[][GRID_NUM],bool bIsWhiteTurn)
int i,j,k;
unsigned char nStoneT
count++;//计数器累加
//清空棋型分析结果
memset(TypeRecord,TOBEANALSIS,GRID_COUNT*4*4);
memset(TypeCount,0,40*4);
for(i=0;i&GRID_NUM;i++)
for(j=0;j&GRID_NUM;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&GRID_NUM;i++)
for(j=0;j&GRID_NUM;j++)
for(k =0;k&4;k++)
nStoneType=position[i][j];
if(nStoneType!=NOSTONE)
switch(TypeRecord[i][j][k])
case FIVE://五连
TypeCount[nStoneType][FIVE]++;
case FOUR://活四
TypeCount[nStoneType][FOUR]++;
case SFOUR://冲四
TypeCount[nStoneType][SFOUR]++;
case THREE://活三
TypeCount[nStoneType][THREE]++;
case STHREE://眠三
TypeCount[nStoneType][STHREE]++;
case TWO://活二
TypeCount[nStoneType][TWO]++;
case STWO://眠二
TypeCount[nStoneType][STWO]++;
//如果已五连,返回极值
if(bIsWhiteTurn)
if(TypeCount[BLACK][FIVE])
return -9999;
if(TypeCount[WHITE][FIVE])
return 9999;
if(TypeCount[BLACK][FIVE])
return 9999;
if(TypeCount[WHITE][FIVE])
return -9999;
//两个冲四等于一个活四
if(TypeCount[WHITE][SFOUR]&1)
TypeCount[WHITE][FOUR]++;
if(TypeCount[BLACK][SFOUR]&1)
TypeCount[BLACK][FOUR]++;
int WValue=0,BValue=0;
if(bIsWhiteTurn)//轮到白棋走
if(TypeCount[WHITE][FOUR])
return 9990;//活四,白胜返回极值
if(TypeCount[WHITE][SFOUR])
return 9980;//冲四,白胜返回极值
if(TypeCount[BLACK][FOUR])
return -9970;//白无冲四活四,而黑有活四,黑胜返回极值
if(TypeCount[BLACK][SFOUR] && TypeCount[BLACK][THREE])
return -9960;//而黑有冲四和活三,黑胜返回极值
if(TypeCount[WHITE][THREE] && TypeCount[BLACK][SFOUR]== 0)
return 9950;//白有活三而黑没有四,白胜返回极值
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
//否则白棋价值加200
if(TypeCount[WHITE][THREE])
WValue+=200;
if(TypeCount[BLACK][THREE]&1)
BValue+=500;//黑的活三多于一个,黑棋价值加500
//否则黑棋价值加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])
return 9990;//活四,黑胜返回极值
if(TypeCount[BLACK][SFOUR])
return 9980;//冲四,黑胜返回极值
if(TypeCount[WHITE][FOUR])
return -9970;//活四,白胜返回极值
if(TypeCount[WHITE][SFOUR] && TypeCount[WHITE][THREE])
return -9960;//冲四并活三,白胜返回极值
if(TypeCount[BLACK][THREE] && TypeCount[WHITE][SFOUR]==0)
return 9950;//黑活三,白无四。黑胜返回极值
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;
//否则黑棋价值加200
if(TypeCount[BLACK][THREE])
BValue+=200;
//白的活三多于一个,白棋价值加 500
if(TypeCount[WHITE][THREE]&1)
WValue+=500;
//否则白棋价值加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&GRID_NUM;i++)
for(j=0;j&GRID_NUM;j++)
nStoneType=position[i][j];
if(nStoneType!=NOSTONE)
if(nStoneType==BLACK)
BValue+=PosValue[i][j];
WValue+=PosValue[i][j];
//返回估值
if(!bIsWhiteTurn)
return BValue-WV
return WValue-BV
//分析棋盘上某点在水平方向上的棋型
int AnalysisHorizon(unsigned char position[][GRID_NUM],int i,int j)
//调用直线分析函数分析
AnalysisLine(position[i],15,j);
//拾取分析结果
for(int s=0;s&15;s++)
if(m_LineRecord[s]!=TOBEANALSIS)
TypeRecord[i][s][0]= m_LineRecord[s];
return TypeRecord[i][j][0];
//分析棋盘上某点在垂直方向上的棋型
int AnalysisVertical(unsigned char position[][GRID_NUM],int i,int j)
unsigned char tempArray[GRID_NUM];
//将垂直方向上的棋子转入一维数组
for(int k=0;k&GRID_NUM;k++)
tempArray[k]=position[k][j];
//调用直线分析函数分析
AnalysisLine(tempArray,GRID_NUM,i);
//拾取分析结果
for(int s=0;s&GRID_NUM;s++)
if(m_LineRecord[s]!=TOBEANALSIS)
TypeRecord[s][j][1]=m_LineRecord[s];
return TypeRecord[i][j][1];
//分析棋盘上某点在左斜方向上的棋型
int AnalysisLeft(unsigned char position[][GRID_NUM],int i,int j)
unsigned char tempArray[GRID_NUM];
//将斜方向上的棋子转入一维数组
for(int k=0;k&GRID_NUM;k++)
if(x+k&14 || y+k&14)
tempArray[k]=position[y+k][x+k];
//调用直线分析函数分析
AnalysisLine(tempArray,k,j-x);
//拾取分析结果
for(int s=0;s&k;s++)
if(m_LineRecord[s]!=TOBEANALSIS)
TypeRecord[y+s][x+s][2]=m_LineRecord[s];
return TypeRecord[i][j][2];
//分析棋盘上某点在右斜方向上的棋型
int AnalysisRight(unsigned char position[][GRID_NUM],int i,int j)
unsigned char tempArray[GRID_NUM];
if(14-i&j)
realnum=14-i;
realnum=j;
//将斜方向上的棋子转入一维数组
for(int k=0;k&GRID_NUM;k++)
if(x+k&14 || y-k&0)
tempArray[k]=position[y-k][x+k];
//调用直线分析函数分析
AnalysisLine(tempArray,k,j-x);
//拾取分析结果
for(int s=0;s&k;s++)
if(m_LineRecord[s]!=TOBEANALSIS)
TypeRecord[y-s][x+s][3]=m_LineRecord[s];
return TypeRecord[i][j][3];
int AnalysisLine(unsigned char* position,int GridNum,int StonePos)
unsigned char StoneT
unsigned char AnalyLine[30];
int nAnalyP
int LeftEdge,RightE
int LeftRange,RightR
if(GridNum&5)
//数组长度小于5没有意义
memset(m_LineRecord,ANALSISED,GridNum);
nAnalyPos=StoneP
memset(m_LineRecord,TOBEANALSIS,30);
memset(AnalyLine,0x0F,30);
//将传入数组装入AnalyL
memcpy(&AnalyLine,position,GridNum);
GridNum--;
StoneType=AnalyLine[nAnalyPos];
LeftEdge=nAnalyP
RightEdge=nAnalyP
//算连续棋子左边界
while(LeftEdge&0)
if(AnalyLine[LeftEdge-1]!=StoneType)
LeftEdge--;
//算连续棋子右边界
while(RightEdge&GridNum)
if(AnalyLine[RightEdge+1]!=StoneType)
RightEdge++;
LeftRange=LeftE
RightRange=RightE
//下面两个循环算出棋子可下的范围
while(LeftRange&0)
if(AnalyLine[LeftRange -1]==!StoneType)
LeftRange--;
while(RightRange&GridNum)
if(AnalyLine[RightRange+1]==!StoneType)
RightRange++;
//如果此范围小于4则分析没有意义
if(RightRange-LeftRange&4)
for(int k=LeftRk&=RightRk++)
m_LineRecord[k]=ANALSISED;
//将连续区域设为分析过的,防止重复分析此一区域
for(int k=LeftEk&=RightEk++)
m_LineRecord[k]=ANALSISED;
if(RightEdge-LeftEdge&3)
//如待分析棋子棋型为五连
m_LineRecord[nAnalyPos]=FIVE;
return FIVE;
if(RightEdge-LeftEdge== 3)
//如待分析棋子棋型为四连
bool Leftfour=
if(LeftEdge&0)
if(AnalyLine[LeftEdge-1]==NOSTONE)
Leftfour=//左边有气
if(RightEdge&GridNum)
//右边未到边界
if(AnalyLine[RightEdge+1]==NOSTONE)
//右边有气
if(Leftfour==true)//如左边有气
m_LineRecord[nAnalyPos]=FOUR;//活四
m_LineRecord[nAnalyPos]=SFOUR;//冲四
if(Leftfour==true)//如左边有气
m_LineRecord[nAnalyPos]=SFOUR;//冲四
if(Leftfour==true)//如左边有气
m_LineRecord[nAnalyPos]=SFOUR;//冲四
return m_LineRecord[nAnalyPos];
if(RightEdge-LeftEdge==2)
//如待分析棋子棋型为三连
bool LeftThree=
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;
LeftThree=
if(RightEdge&GridNum)
if(AnalyLine[RightEdge+1]==NOSTONE)
//右边有气
if(RightEdge&GridNum-1 && AnalyLine[RightEdge+2]==AnalyLine[RightEdge])
//右边隔1个己方棋子
m_LineRecord[RightEdge]=SFOUR;//冲四
m_LineRecord[RightEdge+2]=ANALSISED;
if(LeftThree==true)//如左边有气
m_LineRecord[RightEdge]=THREE;//活三
m_LineRecord[RightEdge]=STHREE; //冲三
if(m_LineRecord[LeftEdge]==SFOUR)//如左冲四
return m_LineRecord[LeftEdge];//返回
if(LeftThree==true)//如左边有气
m_LineRecord[nAnalyPos]=STHREE;//眠三
if(m_LineRecord[LeftEdge]==SFOUR)//如左冲四
return m_LineRecord[LeftEdge];//返回
if(LeftThree==true)//如左边有气
m_LineRecord[nAnalyPos]=STHREE;//眠三
return m_LineRecord[nAnalyPos];
if(RightEdge-LeftEdge==1)
//如待分析棋子棋型为二连
bool Lefttwo=
bool Leftthree=
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;//冲四
if(AnalyLine[LeftEdge-3]==NOSTONE)
//左边隔1个己方棋子
m_LineRecord[LeftEdge-2]=ANALSISED;
m_LineRecord[LeftEdge]=STHREE;//眠三
if(RightEdge&GridNum-2)
if(AnalyLine[RightEdge+1]==NOSTONE)
//右边有气
if(RightEdge+1&GridNum-1 && AnalyLine[RightEdge+2]==AnalyLine[RightEdge])
if(AnalyLine[RightEdge+3]==AnalyLine[RightEdge])
//右边隔两个己方棋子
m_LineRecord[RightEdge+3]=ANALSISED;
m_LineRecord[RightEdge+2]=ANALSISED;
m_LineRecord[RightEdge]=SFOUR;//冲四
if(AnalyLine[RightEdge+3]==NOSTONE)
//右边隔 1 个己方棋子
m_LineRecord[RightEdge+2]=ANALSISED;
m_LineRecord[RightEdge]=STHREE;//眠三
if(m_LineRecord[LeftEdge]==SFOUR)//左边冲四
return m_LineRecord[LeftEdge];//返回
if(m_LineRecord[LeftEdge]==STHREE)//左边眠三
return m_LineRecord[LeftEdge];
if(Lefttwo==true)
m_LineRecord[nAnalyPos]=TWO;//返回活二
m_LineRecord[nAnalyPos]=STWO;//眠二
if(m_LineRecord[LeftEdge]==SFOUR)//冲四返回
return m_LineRecord[LeftEdge];
if(Lefttwo==true)//眠二
m_LineRecord[nAnalyPos]=STWO;
return m_LineRecord[nAnalyPos];
//将历史记录表中所有项目全置为初值
void ResetHistoryTable()
memset(m_HistoryTable,10,GRID_COUNT*sizeof(int));
//从历史得分表中取给定走法的历史得分
int GetHistoryScore(STONEMOVE* move)
return m_HistoryTable[move-&StonePos.x][move-&StonePos.y];
//将一最佳走法汇入历史记录
void EnterHistoryScore(STONEMOVE* move,int depth)
m_HistoryTable[move-&StonePos.x][move-&StonePos.y]+=2&&
//对走法队列从小到大排序
//STONEMOVE* source原始队列
//STONEMOVE* target目标队列
//合并source[l&m]和 source[m +1&r]至target[l&r]
void Merge(STONEMOVE* source,STONEMOVE* target,int l,int m,int r)
//从小到大排序
int j=m+1;
while(i&=m && j&=r)
if(source[i].Score&=source[j].Score)
target[k++]=source[i++];
target[k++]=source[j++];
for(int q=j;q&=r;q++)
target[k++]=source[q];
for(int q=i;q&=m;q++)
target[k++]=source[q];
void Merge_A(STONEMOVE* source,STONEMOVE* target,int l,int m,int r)
//从大到小排序
int j=m+1;
while(i&=m &&j&=r)
if(source[i].Score&=source[j].Score)
target[k++]=source[i++];
target[k++]=source[j++];
for(int q=j;q&=r;q++)
target[k++]=source[q];
for(int q=i;q&=m;q++)
target[k++]=source[q];
//合并大小为 S 的相邻子数组
//direction 是标志,指明是从大到小还是从小到大排序
void MergePass(STONEMOVE* source,STONEMOVE* target,const int s,const int n,const bool direction)
while(i&=n-2*s)
//合并大小为 s的相邻二段子数组
if(direction)
Merge(source,target,i,i+s-1,i+2*s-1);
Merge_A(source,target,i,i+s-1,i+2*s-1);
if(i+s&n)//剩余的元素个数小于2s
if(direction)
Merge(source,target,i,i+s-1,n-1);
Merge_A(source,target,i,i+s-1,n-1);
for(int j=i;j&=n-1;j++)
target[j]=source[j];
void MergeSort(STONEMOVE* source,int n,bool direction)
while(s&n)
MergePass(source,m_TargetBuff,s,n,direction);
MergePass(m_TargetBuff,source,s,n,direction);
int CreatePossibleMove(unsigned char position[][GRID_NUM], int nPly, int nSide)
m_nMoveCount=0;
for(i=0;i&GRID_NUM;i++)
for(j=0;j&GRID_NUM;j++)
if(position[i][j]==(unsigned char)NOSTONE)
AddMove(j,i,nPly);
//使用历史启发类中的静态归并排序函数对走法队列进行排序
//这是为了提高剪枝效率
// CHistoryH
MergeSort(m_MoveList[nPly],m_nMoveCount,0);
return m_nMoveC//返回合法走法个数
//在m_MoveList中插入一个走法
//nToX是目标位置横坐标
//nToY是目标位置纵坐标
//nPly是此走法所在的层次
int AddMove(int nToX, int nToY, int nPly)
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];//使用位置价值表评估当前走法的价值
return m_nMoveC
void CNegaScout_TT_HH()
ResetHistoryTable();
// m_pThinkProgress=NULL;
void SearchAGoodMove(unsigned char position[][GRID_NUM],int Type)
memcpy(CurPosition,position,GRID_COUNT);
m_nMaxDepth=m_nSearchD
CalculateInitHashKey(CurPosition);
ResetHistoryTable();
Score=NegaScout(m_nMaxDepth,-);
X=m_cmBestMove.StonePos.y;
Y=m_cmBestMove.StonePos.x;
MakeMove(&m_cmBestMove,Type);
memcpy(position,CurPosition,GRID_COUNT);
int IsGameOver(unsigned char position[][GRID_NUM],int nDepth)
int score,i;//计算要下的棋子颜色
i=(m_nMaxDepth-nDepth)%2;
score=Eveluate(position,i);//调用估值函数
if(abs(score)&8000)//如果估值函数返回极值，给定局面游戏结束
//返回极值
return 0;//返回未结束
int NegaScout(int depth,int alpha,int beta)
int Count,i;
int a,b,t;
/* if(depth&0)
i= IsGameOver(CurPosition,depth);
//已分胜负，返回极值
side=(m_nMaxDepth-depth)%2;//计算当前节点的类型,极大0/极小1
score=LookUpHashTable(alpha,beta,depth,side);
if(score!=66666)
if(depth&=0)//叶子节点取估值
score=Eveluate(CurPosition,side);
EnterHashTable(exact,score,depth,side);//将估值存入置换表
Count=CreatePossibleMove(CurPosition,depth,side);
for(i=0;i&Ci++)
m_MoveList[depth][i].Score=GetHistoryScore(&m_MoveList[depth][i]);
MergeSort(m_MoveList[depth],Count,0);
int bestmove=-1;
int eval_is_exact=0;
for(i=0;i&Ci++)
type=MakeMove(&m_MoveList[depth][i],side);
Hash_MakeMove(&m_MoveList[depth][i],CurPosition);
t=-NegaScout(depth-1,-b,-a);//递归搜索子节点，对第 1 个节点是全窗口，其后是空窗探测
if(t&a && t&beta && i&0)
//对于第一个后的节点,如果上面的搜索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]);
eval_is_exact=1;
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);
/* set new null window */
if(bestmove!=-1)
EnterHistoryScore(&m_MoveList[depth][bestmove], depth);
if(eval_is_exact)
EnterHashTable(exact,a,depth,side);
EnterHashTable(upper_bound,a,depth,side);
unsigned char MakeMove(STONEMOVE* move,int type)
CurPosition[move-&StonePos.y][move-&StonePos.x]=
void UnMakeMove(STONEMOVE* move)
CurPosition[move-&StonePos.y][move-&StonePos.x]=NOSTONE;
__int64 rand64(void)
return rand()^((__int64)rand()&&15)^((__int64)rand()&&30)^
((__int64)rand()&&45)^((__int64)rand()&&60);
//生成32位随机数
long rand32(void)
return rand()^((long)rand()&&15)^((long)rand()&&30);
void CTranspositionTable()
InitializeHashKey();//建立哈希表，创建随机数组
void _CTranspositionTable()
//释放哈希表所用空间
delete m_pTT[0];
delete m_pTT[1];
void CalculateInitHashKey(unsigned char CurPosition[][GRID_NUM])
int j,k,nStoneT
m_HashKey32=0;
m_HashKey32=0;
//将所有棋子对应的哈希数加总
for(j=0;j&GRID_NUM;j++)
for(k=0;k&GRID_NUM;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];
void Hash_MakeMove(STONEMOVE *move,unsigned char CurPosition[][GRID_NUM])
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];
void Hash_UnMakeMove(STONEMOVE *move,unsigned char CurPosition[][GRID_NUM])
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];
int LookUpHashTable(int alpha, int beta, int depth, int TableNo)
//计算二十位哈希地址，如果读者设定的哈希表大小不是 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)//判断数据类型
case exact://确切值
return pht-&
case lower_bound://下边界
if(pht-&eval&=beta)
return pht-&
case upper_bound://上边界
if (pht-&eval&=alpha)
return pht-&
return 66666;
void EnterHashTable(ENTRY_TYPE entry_type, short eval, short depth, int TableNo)
x=m_HashKey32 & 0xFFFFF;//计算二十位哈希地址
pht=&m_pTT[TableNo][x]; //取到具体的表项指针
//将数据写入哈希表
pht-&checksum=m_HashKey64; //64位校验码
pht-&entry_type=entry_//表项类型
pht-&eval=
//要保存的值
pht-&depth=
void InitializeHashKey()
int i,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]=new HashItem[];//用于存放取极大值的节点数据
m_pTT[1]=new HashItem[];//用于存放取极小值的节点数据
int main()
char command[10]; //用于保存命令的字符串
for (int i = 0; i & GRID_NUM; i++)
for (int j = 0; j & GRID_NUM; j++)
m_RenjuBoard[i][j] = NOSTONE; //棋盘初始化
if(strcmp(command, "[START]") != 0)//读入第一条命令
return 0; //如果不是[START]则停止程序
cin && //读入己方颜色
colour=colour-1;
m_nUserStoneColor=1-
while (true)
int rival_x, rival_y; //用于保存对手上一步落子点
cin && //读入命令
if (strcmp(command, "[PUT]") != 0)
//如果不是[PUT]则停止程序
cin && rival_x && rival_y; //读入对手上一步落子点
if(colour == 0 && rival_x == -1 && rival_y == -1) //如果己方执黑且是第一步，则占据棋盘中心位置
m_RenjuBoard[GRID_NUM / 2][GRID_NUM / 2] = //更新棋盘信息
cout && GRID_NUM / 2 && ' ' && GRID_NUM / 2 && //输出
cout && //刷新缓冲区
m_RenjuBoard[rival_x][rival_y] = 1 -
//更新棋盘信息
m_nSearchDepth=3;
//最大搜索深度
CNegaScout_TT_HH();
//创建NegaScout_TT_HH搜索引擎
CTranspositionTable();
SearchAGoodMove(m_RenjuBoard,colour);
m_RenjuBoard[X][Y]=
cout && X && ' ' && Y && //输出
cout && //刷新缓冲区
_CTranspositionTable();
//结束循环
while (true);
//循环直至随机得到一个空位置
版权声明：本文为博主原创文章，未经博主允许不得转载。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：21507次
排名：千里之外
原创：18篇
(2)(1)(1)(1)(3)(1)(2)(2)(3)(2)(1)(1)(1)