基于C++博弈树使用α-β剪枝加以改进的AI五子棋游戏能进行人机对战AI目前可以推算四层局面源码.zip

#include <cstdlib> #include <iostream> #include <stdlib.h> #include <string.h> #include <time.h> #include "Packdef.h" using namespace std; //定义了枚举型的数据类型，精确，下边界，上边界 enum ENTRY_TYPE{exact,lower_bound,upper_bound}; //哈希表中元素的结构定义 typedef struct HASHITEM { __int64 checksum; //64位校验码 ENTRY_TYPE entry_type; //数据类型 short depth; //取得此值时的层次 short eval; //节点的值 }HashItem; typedef struct Node { int x; int y; }POINT; //用以表示棋子位置的结构 typedef struct _stoneposition { unsigned char x; unsigned char y; }STONEPOS; typedef struct _movestone { unsigned char nRenjuID; POINT ptMovePoint; }MOVESTONE; //这个结构用以表示走法 typedef struct _stonemove { STONEPOS StonePos; //棋子位置 int Score; //走法的分数 }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_nMoveCount; //此变量用以记录走法的总数 unsigned char CurPosition[GRID_NUM][GRID_NUM]; //搜索时用于当前节点棋盘状态的数组 STONEMOVE m_cmBestMove; //记录最佳走法的变量 //CMoveGenerator* m_pMG; //走法产生器指针 //CEveluation* m_pEval; //估值核心指针 int m_nSearchDepth; //最大搜索深度 int m_nMaxDepth; //当前搜索的最大搜索深度 unsigned char m_RenjuBoard[GRID_NUM][GRID_NUM]; //棋盘数组，用于显示棋盘 int m_nUserStoneColor; //用户棋子的颜色 //CSearchEngine* m_pSE; //搜索引擎指针 int X,Y; //AI输出落子位置 int SL; //胜利标记 //位置重要性价值表,此表从中间向外,越往外价值越低 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} }; char mark[20]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E'}; //全局变量,用以统计估值函数的执行遍数 int icount=0; int Eveluate(unsigned char position[][GRID_NUM],bool bIsWhiteTurn) { int i,j,k; unsigned char nStoneType; icount++;//计数器累加 //清空棋型分析结果 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]++; break; case FOUR://活四 TypeCount[nStoneType][FOUR]++; break; case SFOUR://冲四 TypeCount[nStoneType][SFOUR]++; break; case THREE://活三 TypeCount[nStoneType][THREE]++; break; case STHREE://眠三 TypeCount[nStoneType][STHREE]++; break; case TWO://活二 TypeCount[nStoneType][TWO]++; break; case STWO://眠二 TypeCount[nStoneType][STWO]++; break; default: break; } } } //如果已五连,返回极值 if(bIsWhiteTurn) { if(TypeCount[BLACK][FIVE]) return -9999; if(TypeCount[WHITE][FIVE]) return 9999; } else { 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 else //否则白棋价值加200 if(TypeCount[WHITE][THREE]) WValue+=200; if(TypeCount[BLACK][THREE]>1) BValue+=500;//黑的活三多于一个,黑棋价值加500 else //否则黑棋价值加100