您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
基于C语言五子棋小游戏总结.doc 39页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
你可能关注的文档：
··········
··········
五子棋小游戏
现在有越来越多的人使用电脑，而且五子棋的受众广泛但实体棋操作较为繁琐且平时较难实现，所以电脑版的五子棋游戏应运而生。大家对于这个小游戏的需求如下：首先，设计这个游戏最基本的就是实现玩家之间对战，玩家可以通过某些操作来实现对战功能；有时候可能由于时间等原因，玩家可能需要保存游戏，此时需要一个“保存”功能；有时候可能玩家由于失误会走错棋，此时就需要“悔棋”功能；有时候玩家可能觉得这局游戏玩的非常不好，这时候就需要“重新开始游戏”功能；玩家在玩过游戏之后有可能想保存游戏记录便于以后分析此时就需要“排行榜”功能；有些玩家在玩游戏时喜欢听音乐，这时候就需要在下棋时可以播放背景音乐的功能；最基本的通过输入坐标来实现落子的操作方式很繁琐而且很不方便，这时候就可以将落子机制改为更直观的光标移动模式。
1.玩家对战功能：在玩家对战功能中，玩家可以通过按方向键来移动光标、按空格来实现落子，最终在横或竖或斜方向上达成五个相同颜色的棋子来获得胜利。
基本思路：
（1）使用二维数组保存棋局。
由于要使用光标，所以使用输出缓冲器。
打印棋盘。
主要使用Print()函数来算出棋盘并将缓冲器内容输出。
其余为其中调用的辅助函数。chessPrint()是打印交点坐标的字符的函数；getCurse()是打印光标的函数；write()函数是用来向缓冲器里面写入字符串的函数；ln()函数是负责将缓冲器写入位置提行的函数；Display()函数是将缓冲器中内容输出到屏幕的函数。
下子，在后文有详细介绍。
胜负平判断
调用Check()函数进行四个方向的检查，检查是否有五子连珠。
判断完毕后输出结果（如果存在结果）
2.保存游戏和装载游戏功能：在游戏过程中，只要按“1”键就可以保存游戏到指定名称的文档中；在游戏开始界面，只要按“2”选择“load board”就可以装载指定名称的游戏。
基本思路：
调用saveGame()函数将当前棋局的相关信息全部保存到结构体变量saveChess中，并将其中的内容全部保存到文件里。
加载时将结构体变量里的数据全部读出，赋给当前棋局相关信息变量，之后正常运行游戏即可。
3.悔棋功能：在游戏过程中，只要按“2”键就可以返回到上一步的局面。
基本思路：
玩家对战时，每个玩家每次成功落子之后，棋盘的相关信息就会被记录到一个结构体数组里。
每次悔棋时，就调用一个函数把储存在结构体数组里的上一回合的信息全部赋给当前棋局信息变量。
4.重新开始游戏功能：在游戏过程中，只要按“3”键就可以初始化棋局，重新开始游戏。
基本思路：
玩家对战时每一次重新开始游戏就调用runGame（）函数，并返回当前玩家信息。
人机对战时每一重新开始游戏就调用自身，并返回当前玩家信息。
5.排行榜功能：在一局游戏结束时，按照提示输入“1”则可以将自己的名字及成绩保存到排行榜文件中。在游戏开始界面，只要按“3”就可以查看排行榜。（排行榜按照步数由小到大，棋色又白到黑排序）
基本思路：
一局游戏结束时调用inList()函数，inList()函数又调用addList()函数，将关于棋局的部分信息保存到文件。
关于排序设置了单独的函数sortList()函数，其在addList()里面被调用。此处使用了结构体数组，按照其中的“步数”成员将结构体数组中的元素进行“冒泡排序”。
这里比较特别的是，每次都是先将要加入的内容写到文件末尾，再将文件中所有内容读出后进行排序，最后再将排好序的内容全部写入文件。
6.背景音乐功能：在游戏过程中会一直循环播放音乐，带给玩家不一样的享受。
基本思路：
使用Windows.h头文件，并加上相关指令
再调用PlaySoundA()函数就可以实现循环播放背景音乐。
7.使用光标定位棋子：使用方向键控制光标移动方向，使用空格键来实现落子，带给玩家比坐标落子更高级的体验，更加方便快捷。（此处使用了以前没用到的，调用getch()函数，为了不需要键入回车。）
基本思路：
光标实现：使用缓冲器将棋盘交点的间隔都填充内容，光标用制表符表示，其余为空格。
方向键移动光标：
防止越界：
空格落子：
简单的人机对战：主要防御型的AI，主要针对对手的棋型来安排战术，有时会选择进攻。
基本思路：
判断对手是否有2,3,4子连珠，如果有，电脑会在两头下子；如果没有，若己方在一侧存在3子或4子连珠，电脑会在后面补子；如果以上情况均未出现，电脑会随机在对手单子周边落子。其余基本功能同人人对战，但是不支持保存和读取棋局功能。
按照奇偶数来判断是该电脑走子还是玩家走子。电脑执黑则会有不同的初始化方法。
正在加载中，请稍后...
63页64页23页29页24页12页12页32页17页35页查看: 23270|回复: 6
博弈树加上α-β剪枝算法做出来的五子棋AI往前推6步无压力
AI棋力已经非常叼了我反正是一次都赢不了它，所有棋类AI基本都是一个原理只需要根据游戏规则来改写自己的局面评分函数就欧了
以下代码是在博弈树加上α-β剪枝算法做出来的五子棋AI往前推6步无压力在DEV环境下编译的
#include &cstdlib&
#include &iostream.h&
#include&stdlib.h&
#include&string.h&
#include&time.h&
#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&GRID_NUM) && (y&=0 && y&GRID_NUM)
//定义了枚举型的数据类型，精确，下边界，上边界
enum ENTRY_TYPE{exact,lower_bound,upper_bound};
//哈希表中元素的结构定义
typedef struct HASHITEM
{
__int64& & & &&&//64位校验码
ENTRY_TYPE entry_//数据类型
& & & &&&//取得此值时的层次
& & & &&&//节点的值
}HashI
typedef struct Node
{
//用以表示棋子位置的结构
typedef struct _stoneposition
{
}STONEPOS;
typedef struct _movestone
{
unsigned char nRenjuID;
POINT ptMoveP
}MOVESTONE;
//这个结构用以表示走法
typedef struct _stonemove
{
STONEPOS StoneP//棋子位置
int S& & & &&&//走法的分数
}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 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 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;
& && &&&}
}
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
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;
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&GRID_NUM;i++)
for(j=0;j&GRID_NUM;j++)
{
nStoneType=position[i][j];
if(nStoneType!=NOSTONE)
if(nStoneType==BLACK)
BValue+=PosValue[i][j];
else
WValue+=PosValue[i][j];
}
//返回估值
if(!bIsWhiteTurn)
return BValue-WV
else
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];
int x,y;
if(i&j)
{
y=0;
x=j-i;
}
else
{
x=0;
y=i-j;
}
//将斜方向上的棋子转入一维数组
for(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];
int x,y,
if(14-i&j)
{
y=14;
x=j-14+i;
realnum=14-i;
}
else
{
x=0;
y=i+j;
realnum=j;
}
//将斜方向上的棋子转入一维数组
for(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);
return 0;
}
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;//活四
else
m_LineRecord[nAnalyPos]=SFOUR;//冲四
else
if(Leftfour==true)//如左边有气
m_LineRecord[nAnalyPos]=SFOUR;//冲四
else
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;
}
else
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;
}
else
if(LeftThree==true)//如左边有气
m_LineRecord[RightEdge]=THREE;//活三
else
m_LineRecord[RightEdge]=STHREE; //冲三
else
{
if(m_LineRecord[LeftEdge]==SFOUR)//如左冲四
return m_LineRecord[LeftEdge];//返回
if(LeftThree==true)//如左边有气
m_LineRecord[nAnalyPos]=STHREE;//眠三
}
else
{
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;//冲四
}
else
if(AnalyLine[LeftEdge-3]==NOSTONE)
{
//左边隔1个己方棋子
m_LineRecord[LeftEdge-2]=ANALSISED;
m_LineRecord[LeftEdge]=STHREE;//眠三
}
else
Lefttwo=
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;//冲四
}
else
if(AnalyLine[RightEdge+3]==NOSTONE)
{
//右边隔 1 个己方棋子
m_LineRecord[RightEdge+2]=ANALSISED;
m_LineRecord[RightEdge]=STHREE;//眠三
}
else
{
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;//返回活二
else
m_LineRecord[nAnalyPos]=STWO;//眠二
}
else
{
if(m_LineRecord[LeftEdge]==SFOUR)//冲四返回
return m_LineRecord[LeftEdge];
if(Lefttwo==true)//眠二
m_LineRecord[nAnalyPos]=STWO;
}
return m_LineRecord[nAnalyPos];
}
return 0;
}
//将历史记录表中所有项目全置为初值
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 i=l;
int j=m+1;
int k=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(int q=j;q&=r;q++)
target[k++]=source[q];
else
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 i=l;
int j=m+1;
int k=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(int q=j;q&=r;q++)
target[k++]=source[q];
else
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)
{
int i=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&n)//剩余的元素个数小于2s
{
if(direction)
Merge(source,target,i,i+s-1,n-1);
else
Merge_A(source,target,i,i+s-1,n-1);
}
else
for(int j=i;j&=n-1;j++)
target[j]=source[j];
}
void MergeSort(STONEMOVE* source,int n,bool direction)
{
int s=1;
while(s&n)
{
MergePass(source,m_TargetBuff,s,n,direction);
s+=s;
MergePass(m_TargetBuff,source,s,n,direction);
s+=s;
}
}
int CreatePossibleMove(unsigned char position[][GRID_NUM], int nPly, int nSide)
{
int i,j;
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)
{
int S
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);
if(i!=0)
&&//已分胜负，返回极值
}
*/
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;
& & a=
& & b=
& & 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]);
if(a&t)
{
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);
}
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);
unsigned char MakeMove(STONEMOVE* move,int type)
{
CurPosition[move-&StonePos.y][move-&StonePos.x]=
return 0;
}
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-&
else
case upper_bound://上边界
if (pht-&eval&=alpha)
return pht-&
else
& && &&&}
}
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(int argc, char *argv[])
{
SL=0;
char command[10]; //用于保存命令的字符串
for (int i = 0; i & GRID_NUM; i++)
for (int j = 0; j & GRID_NUM; j++)
m_RenjuBoard[i][j] = NOSTONE; //棋盘初始化
& & int XS;
& & printf(&请选择先手棋手：1表示AI先手 0表示棋手先手\n&);
cin && XS; //是否电脑先手
colour=BLACK;
m_nUserStoneColor=WHITE;
while (!SL)
& && &&&printf(&\n请输入落子坐标：\n&);
int rival_x, rival_y; //用于保存对手上一步落子点
cin && rival_x && rival_y; //读入对手上一步落子点&&
if(XS == 1 && rival_x == -1 && rival_y == -1) //如果己方执黑且是第一步，则占据棋盘中心位置
m_RenjuBoard[GRID_NUM / 2][GRID_NUM / 2] = //更新棋盘信息
//cout && GRID_NUM / 2 && ' ' && GRID_NUM / 2 && //输出
//cout && //刷新缓冲区&&
}
else
{
m_RenjuBoard[rival_x][rival_y] =m_nUserStoneC
//更新棋盘信息
& && & & & for (int i = 0; i & GRID_NUM; i++)
& && &{
for (int j = 0; j & GRID_NUM; j++)
{
& && && && &if(m_RenjuBoard[i][j]==WHITE)
printf(&O &); else&&if(m_RenjuBoard[i][j]==BLACK)printf(&X &); else printf(&+ &);
& && &&&}
& && && & printf(&\n&);
& && &&&}
m_nSearchDepth=4;//AI难度等级设置
//最大搜索深度& & & &
do
{
CNegaScout_TT_HH();& & & &&&//创建NegaScout_TT_HH搜索引擎
CTranspositionTable();
SearchAGoodMove(m_RenjuBoard,colour);
m_RenjuBoard[X][Y]=
printf(&\nAI落子坐标为：&);
cout && X && ' ' && Y && //输出
cout && //刷新缓冲区
_CTranspositionTable();
//结束循环
}
while (!SL);
//循环直至随机得到一个空位置
for (int i = 0; i & GRID_NUM; i++)
& & {
for (int j = 0; j & GRID_NUM; j++)
{
& && && && &if(m_RenjuBoard[i][j]==WHITE)
printf(&O &); else&&if(m_RenjuBoard[i][j]==BLACK)printf(&X &); else printf(&+ &);
& && &&&}
& && && & printf(&\n&);
& && &&&}
& && &&&
& && &&&if(SL==1)printf(&很遗憾AI胜利了继续努力吧少年！\n&);else if(SL==2)printf(&少年你太叼了居然打败了AI！\n&);
& && &&&
& && &&&
& &&&}
}
& &
& & system(&PAUSE&);
& & return EXIT_SUCCESS;
}
复制代码
本帖最后由
11:02 编辑
RE: 博弈树加上α-β剪枝算法做出来的五子棋AI往前推6步无压力
楼主的代码有个bug，ai不会防守眠4，胜局时也不会自己连5，希望改全，邮箱
**** 作者被禁止或删除 内容自动屏蔽 ****
兄弟，楼主有回复你吗，有的话，代码发我一下，
楼主真大佬，代码能跑起来，有4个错误，改了就好了
楼主真大佬，代码能跑起来，有4个错误，改了就好了
请问是哪四个错误啊
Powered by