游戏树 c 语言双陆棋算法,游戏树加阿尔法-贝塔剪枝算法制成的双陆棋人工智能向前推进 6 步无压力 ...
#include
#include
#include
#include
#include
#define GRID_NUM 15 //每一行(列)的棋盘交点数
#define GRID_COUNT 225//棋盘上交点总数
#define BLACK 0 //黑棋用0表示
#define WHITE 1 //白棋用1表示
#define NOSTONE '+' //没有棋子
//这组宏定义了用以代表几种棋型的数字
#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
//定义了枚举型的数据类型,精确,下边界,上边界
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}
};
//全局变量,用以统计估值函数的执行遍数
int count=0;
int Eveluate(unsigned char position[][GRID_NUM],bool bIsWhiteTurn)
{
int i,j,k;
unsigned char nStoneType;
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);
<上一篇: Python数据分析-房价预测机器学习