博弈樹加上α-β剪枝算法做出來的五子棋AI往前推6步無壓力

ID:72008 · 發表于 2015-1-11 19:56

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 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<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
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-WValue;
else
return WValue-BValue;
}
//分析棋盤上某點在水平方向上的棋型
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;
int k;
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)
break;
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,realnum;
int k;
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)
break;
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 StoneType;
unsigned char AnalyLine[30];
int nAnalyPos;
int LeftEdge,RightEdge;
int LeftRange,RightRange;
if(GridNum<5)
{
//數組長度小于5沒有意義
memset(m_LineRecord,ANALSISED,GridNum);
return 0;
}
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<GridNum)
{
if(AnalyLine[RightEdge+1]!=StoneType)
break;
RightEdge++;
}
LeftRange=LeftEdge;
RightRange=RightEdge;
//下面兩個循環算出棋子可下的范圍
while(LeftRange>0)
{
if(AnalyLine[LeftRange -1]==!StoneType)
break;
LeftRange--;
}
while(RightRange<GridNum)
{
if(AnalyLine[RightRange+1]==!StoneType)
break;
RightRange++;
}
//如果此范圍小于4則分析沒有意義
if(RightRange-LeftRange<4)
{
for(int k=LeftRange;k<=RightRange;k++)
m_LineRecord[k]=ANALSISED;
return false;
}
//將連續區域設為分析過的,防止重復分析此一區域
for(int k=LeftEdge;k<=RightEdge;k++)
m_LineRecord[k]=ANALSISED;
if(RightEdge-LeftEdge>3)
{
//如待分析棋子棋型為五連
m_LineRecord[nAnalyPos]=FIVE;
return FIVE;
}
if(RightEdge-LeftEdge== 3)
{
//如待分析棋子棋型為四連
bool Leftfour=false;
if(LeftEdge>0)
if(AnalyLine[LeftEdge-1]==NOSTONE)
Leftfour=true;//左邊有氣
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=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<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=false;
bool Leftthree=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<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<<depth;
}
//對走法隊列從小到大排序
//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);
}
//使用歷史啟發類中的靜態歸并排序函數對走法隊列進行排序
//這是為了提高剪枝效率
// CHistoryHeuristic history;
MergeSort(m_MoveList[nPly],m_nMoveCount,0);
return m_nMoveCount;//返回合法走法個數
}
//在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_nMoveCount;
}
void CNegaScout_TT_HH()
{
ResetHistoryTable();
// m_pThinkProgress=NULL;
}
void SearchAGoodMove(unsigned char position[][GRID_NUM],int Type)
{
int Score;
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);
}
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 score;//返回極值
return 0;//返回未結束
}
int NegaScout(int depth,int alpha,int beta)
{
int Count,i;
unsigned char type;
int a,b,t;
int side;
int score;
/* 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)
return score;
if(depth<=0)//葉子節點取估值
{
score=Eveluate(CurPosition,side);
EnterHashTable(exact,score,depth,side);//將估值存入置換表
return score;
}
Count=CreatePossibleMove(CurPosition,depth,side);
for(i=0;i<Count;i++)
m_MoveList[depth][i].Score=GetHistoryScore(&m_MoveList[depth][i]);
MergeSort(m_MoveList[depth],Count,0);
int bestmove=-1;
a=alpha;
b=beta;
int eval_is_exact=0;
for(i=0;i<Count;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 && 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);
return a;
}
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);
return a;
}
unsigned char MakeMove(STONEMOVE* move,int type)
{
CurPosition[move->StonePos.y][move->StonePos.x]=type;
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,nStoneType;
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])
{
int type;
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])
{
int type;
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)
{
int x;
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)//判斷數據類型
{
case exact://確切值
return pht->eval;
case lower_bound://下邊界
if(pht->eval>=beta)
return pht->eval;
else
break;
case upper_bound://上邊界
if (pht->eval<=alpha)
return pht->eval;
else
break;
}
}
return 66666;
}
void EnterHashTable(ENTRY_TYPE entry_type, short eval, short depth, int TableNo)
{
int x;
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; //層次
}
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[1024*1024];//用于存放取極大值的節點數據
m_pTT[1]=new HashItem[1024*1024];//用于存放取極小值的節點數據
}
//using namespace std;
int main(int argc, char *argv[])
{
SL=0;
int colour;
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] = colour; //更新棋盤信息
//cout << GRID_NUM / 2 << ' ' << GRID_NUM / 2 << endl; //輸出
//cout << flush; //刷新緩沖區
}
else
{
m_RenjuBoard[rival_x][rival_y] =m_nUserStoneColor;
//更新棋盤信息
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]=colour;
printf("\nAI落子坐標為：");
cout << X << ' ' << Y << endl; //輸出
cout << flush; //刷新緩沖區
_CTranspositionTable();
break; //結束循環
}
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;
}