五子棋人機對弈代碼——之博弈樹算法

#include

/*?Program?of?Game?--?wuziqi?Written?by?Zhang?shuai,?DEC.25th,?2010?*/

#define?GRID_NUM????15?//每一行(列)的棋盤交點數(shù)

#define?GRID_COUNT??225//棋盤上交點總數(shù)

#define?BLACK???????0??//黑棋用0表示

#define?WHITE???????1??//白棋用1表示

#define?NOSTONE?0xFF???//沒有棋子

//這組宏定義了用以代表幾種棋型的數(shù)字

#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??//已分析過的

//這個宏用以檢查某一坐標(biāo)是否是棋盤上的有效落子點

#define?IsValidPos(x,y)?((x>=0?&&?x=0?&&?y

//定義了枚舉型的數(shù)據(jù)類型，精確，下邊界丛版，上邊界

enumENTRY_TYPE{exact,lower_bound,upper_bound};

//哈希表中元素的結(jié)構(gòu)定義

typedefstructHASHITEM

{

__int64checksum;//64位校驗碼

ENTRY_TYPE?entry_type;//數(shù)據(jù)類型

shortdepth;//取得此值時的層次

shorteval;//節(jié)點的值

}HashItem;

typedefstructNode

{

intx;

inty;

}POINT;

//用以表示棋子位置的結(jié)構(gòu)

typedefstruct_stoneposition

{

unsignedcharx;

unsignedchary;

}STONEPOS;

typedefstruct_movestone

{

unsignedcharnRenjuID;

POINT?ptMovePoint;

}MOVESTONE;

//這個結(jié)構(gòu)用以表示走法

typedefstruct_stonemove

{

STONEPOS?StonePos;//棋子位置

intScore;//走法的分?jǐn)?shù)

}STONEMOVE;

//=================================================================//

intAnalysisLine(unsignedchar*?position,intGridNum,intStonePos);

intAnalysisRight(unsignedcharposition[][GRID_NUM],inti,intj);

intAnalysisLeft(unsignedcharposition[][GRID_NUM],inti,intj);

intAnalysisVertical(unsignedcharposition[][GRID_NUM],inti,intj);

intAnalysisHorizon(unsignedcharposition[][GRID_NUM],inti,intj);

intEveluate(unsignedintposition[][GRID_NUM],boolbIsWhiteTurn);

intAddMove(intnToX,intnToY,intnPly);

intCreatePossibleMove(unsignedcharposition[][GRID_NUM],intnPly,intnSide);

voidMergeSort(STONEMOVE*?source,intn,booldirection);

voidMergePass(STONEMOVE*?source,STONEMOVE*?target,constints,constintn,constbooldirection);

voidMerge_A(STONEMOVE*?source,STONEMOVE*?target,intl,intm,intr);

voidMerge(STONEMOVE*?source,STONEMOVE*?target,intl,intm,intr);

voidEnterHistoryScore(STONEMOVE*?move,intdepth);

intGetHistoryScore(STONEMOVE*?move);

voidResetHistoryTable();

intNegaScout(intdepth,intalpha,intbeta);

voidSearchAGoodMove(unsignedcharposition[][GRID_NUM],intType);

intIsGameOver(unsignedcharposition[][GRID_NUM],intnDepth);

voidUnMakeMove(STONEMOVE*?move);

unsignedcharMakeMove(STONEMOVE*?move,inttype);

void_CSearchEngine();

voidInitializeHashKey();

voidEnterHashTable(ENTRY_TYPE?entry_type,shorteval,shortdepth,intTableNo);

intLookUpHashTable(intalpha,intbeta,intdepth,intTableNo);

voidHash_UnMakeMove(STONEMOVE?*move,unsignedcharCurPosition[][GRID_NUM]);

voidHash_MakeMove(STONEMOVE?*move,unsignedcharCurPosition[][GRID_NUM]);

voidCalculateInitHashKey(unsignedcharCurPosition[][GRID_NUM]);

__int64rand64();

longrand32();

voidCTranspositionTable();

void_CTranspositionTable();

boolOnInitDialog();

//=================================================================//

intm_HistoryTable[GRID_NUM][GRID_NUM];//歷史得分表

STONEMOVE?m_TargetBuff[225];//排序用的緩沖隊列

unsignedintm_nHashKey32[15][10][9];//32位隨機樹組溶弟，用以生成32位哈希值

unsigned__int64m_ulHashKey64[15][10][9];//64位隨機樹組，用以生成64位哈希值

HashItem?*m_pTT[10];//置換表頭指針

unsignedintm_HashKey32;//32位哈希值

__int64m_HashKey64;//64?位哈希值

STONEMOVE?m_MoveList[10][225];//用以記錄走法的數(shù)組

unsignedcharm_LineRecord[30];//存放AnalysisLine分析結(jié)果的數(shù)組

intTypeRecord[GRID_NUM?][GRID_NUM][4];//存放全部分析結(jié)果的數(shù)組,有三個維度,用于存放水平、垂直、左斜、右斜?4?個方向上所有棋型分析結(jié)果

intTypeCount[2][20];//存放統(tǒng)記過的分析結(jié)果的數(shù)組

intm_nMoveCount;//此變量用以記錄走法的總數(shù)

unsignedcharCurPosition[GRID_NUM][GRID_NUM];//搜索時用于當(dāng)前節(jié)點棋盤狀態(tài)的數(shù)組

STONEMOVE?m_cmBestMove;//記錄最佳走法的變量

//CMoveGenerator*?m_pMG;?????????????????//走法產(chǎn)生器指針

//CEveluation*?m_pEval;??????????????//估值核心指針

intm_nSearchDepth;//最大搜索深度

intm_nMaxDepth;//當(dāng)前搜索的最大搜索深度

unsignedcharm_RenjuBoard[GRID_NUM][GRID_NUM];//棋盤數(shù)組比庄，用于顯示棋盤

intm_nUserStoneColor;//用戶棋子的顏色

//CSearchEngine*?m_pSE;???????????????//搜索引擎指針

intX,Y;

//位置重要性價值表,此表從中間向外,越往外價值越低

intPosValue[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}

};

//全局變量,用以統(tǒng)計估值函數(shù)的執(zhí)行遍數(shù)

intcount=0;

intEveluate(unsignedcharposition[][GRID_NUM],boolbIsWhiteTurn)

{

inti,j,k;

unsignedcharnStoneType;

count++;//計數(shù)器累加

//清空棋型分析結(jié)果

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);

//如果右斜方向上沒有分析過

if(TypeRecord[i][j][3]==TOBEANALSIS)

AnalysisRight(position,i,j);

}

//對分析結(jié)果進(jìn)行統(tǒng)計,得到每種棋型的數(shù)量

for(i=0;i

for(j=0;j

for(k?=0;k<4;k++)

{

nStoneType=position[i][j];

if(nStoneType!=NOSTONE)

{

switch(TypeRecord[i][j][k])

{

caseFIVE://五連

TypeCount[nStoneType][FIVE]++;

break;

caseFOUR://活四

TypeCount[nStoneType][FOUR]++;

break;

caseSFOUR://沖四

TypeCount[nStoneType][SFOUR]++;

break;

caseTHREE://活三

TypeCount[nStoneType][THREE]++;

break;

caseSTHREE://眠三

TypeCount[nStoneType][STHREE]++;

break;

caseTWO://活二

TypeCount[nStoneType][TWO]++;

break;

caseSTWO://眠二

TypeCount[nStoneType][STWO]++;

break;

default:

break;

}

//如果已五連,返回極值

if(bIsWhiteTurn)

{

if(TypeCount[BLACK][FIVE])

return-9999;

if(TypeCount[WHITE][FIVE])

return9999;

}

else

{

if(TypeCount[BLACK][FIVE])

return9999;

if(TypeCount[WHITE][FIVE])

return-9999;

}

//兩個沖四等于一個活四

if(TypeCount[WHITE][SFOUR]>1)

TypeCount[WHITE][FOUR]++;

if(TypeCount[BLACK][SFOUR]>1)

TypeCount[BLACK][FOUR]++;

intWValue=0,BValue=0;

if(bIsWhiteTurn)//輪到白棋走

{

if(TypeCount[WHITE][FOUR])

return9990;//活四,白勝返回極值

if(TypeCount[WHITE][SFOUR])

return9980;//沖四,白勝返回極值

if(TypeCount[BLACK][FOUR])

return-9970;//白無沖四活四,而黑有活四,黑勝返回極值

if(TypeCount[BLACK][SFOUR]?&&?TypeCount[BLACK][THREE])

return-9960;//而黑有沖四和活三,黑勝返回極值

if(TypeCount[WHITE][THREE]?&&?TypeCount[BLACK][SFOUR]==?0)

return9950;//白有活三而黑沒有四,白勝返回極值

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])

return9990;//活四,黑勝返回極值

if(TypeCount[BLACK][SFOUR])

return9980;//沖四,黑勝返回極值

if(TypeCount[WHITE][FOUR])

return-9970;//活四,白勝返回極值

if(TypeCount[WHITE][SFOUR]?&&?TypeCount[WHITE][THREE])

return-9960;//沖四并活三,白勝返回極值

if(TypeCount[BLACK][THREE]?&&?TypeCount[WHITE][SFOUR]==0)

return9950;//黑活三,白無四求妹。黑勝返回極值

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

for(j=0;j

{

nStoneType=position[i][j];

if(nStoneType!=NOSTONE)

if(nStoneType==BLACK)

BValue+=PosValue[i][j];

else

WValue+=PosValue[i][j];

}

//返回估值

if(!bIsWhiteTurn)

returnBValue-WValue;

else

returnWValue-BValue;

}

//分析棋盤上某點在水平方向上的棋型

intAnalysisHorizon(unsignedcharposition[][GRID_NUM],inti,intj)

{

//調(diào)用直線分析函數(shù)分析

AnalysisLine(position[i],15,j);

//拾取分析結(jié)果

for(ints=0;s<15;s++)

if(m_LineRecord[s]!=TOBEANALSIS)

TypeRecord[i][s][0]=?m_LineRecord[s];

returnTypeRecord[i][j][0];

}

//分析棋盤上某點在垂直方向上的棋型

intAnalysisVertical(unsignedcharposition[][GRID_NUM],inti,intj)

{

unsignedchartempArray[GRID_NUM];

//將垂直方向上的棋子轉(zhuǎn)入一維數(shù)組

for(intk=0;k

tempArray[k]=position[k][j];

//調(diào)用直線分析函數(shù)分析

AnalysisLine(tempArray,GRID_NUM,i);

//拾取分析結(jié)果

for(ints=0;s

if(m_LineRecord[s]!=TOBEANALSIS)

TypeRecord[s][j][1]=m_LineRecord[s];

returnTypeRecord[i][j][1];

}

//分析棋盤上某點在左斜方向上的棋型

intAnalysisLeft(unsignedcharposition[][GRID_NUM],inti,intj)

{

unsignedchartempArray[GRID_NUM];

intx,y;

if(i

{

y=0;

x=j-i;

}

else

{

x=0;

y=i-j;

}

//將斜方向上的棋子轉(zhuǎn)入一維數(shù)組

for(intk=0;k

{

if(x+k>14?||?y+k>14)

break;

tempArray[k]=position[y+k][x+k];

}

//調(diào)用直線分析函數(shù)分析

AnalysisLine(tempArray,k,j-x);

//拾取分析結(jié)果

for(ints=0;s

if(m_LineRecord[s]!=TOBEANALSIS)

TypeRecord[y+s][x+s][2]=m_LineRecord[s];

returnTypeRecord[i][j][2];

}

//分析棋盤上某點在右斜方向上的棋型

intAnalysisRight(unsignedcharposition[][GRID_NUM],inti,intj)

{

unsignedchartempArray[GRID_NUM];

intx,y,realnum;

if(14-i

{

y=14;

x=j-14+i;

realnum=14-i;

}

else

{

x=0;

y=i+j;

realnum=j;

}

//將斜方向上的棋子轉(zhuǎn)入一維數(shù)組

for(intk=0;k

{

if(x+k>14?||?y-k<0)

break;

tempArray[k]=position[y-k][x+k];

}

//調(diào)用直線分析函數(shù)分析

AnalysisLine(tempArray,k,j-x);

//拾取分析結(jié)果

for(ints=0;s

if(m_LineRecord[s]!=TOBEANALSIS)

TypeRecord[y-s][x+s][3]=m_LineRecord[s];

returnTypeRecord[i][j][3];

}

intAnalysisLine(unsignedchar*?position,intGridNum,intStonePos)

{

unsignedcharStoneType;

unsignedcharAnalyLine[30];

intnAnalyPos;

intLeftEdge,RightEdge;

intLeftRange,RightRange;

if(GridNum<5)

{

//數(shù)組長度小于5沒有意義

memset(m_LineRecord,ANALSISED,GridNum);

return0;

}

nAnalyPos=StonePos;

memset(m_LineRecord,TOBEANALSIS,30);

memset(AnalyLine,0x0F,30);

//將傳入數(shù)組裝入AnalyLine;

memcpy(&AnalyLine,position,GridNum);

GridNum--;

StoneType=AnalyLine[nAnalyPos];

LeftEdge=nAnalyPos;

RightEdge=nAnalyPos;

//算連續(xù)棋子左邊界

while(LeftEdge>0)

{

if(AnalyLine[LeftEdge-1]!=StoneType)

break;

LeftEdge--;

}

//算連續(xù)棋子右邊界

while(RightEdge

{

if(AnalyLine[RightEdge+1]!=StoneType)

break;

RightEdge++;

}

LeftRange=LeftEdge;

RightRange=RightEdge;

//下面兩個循環(huán)算出棋子可下的范圍

while(LeftRange>0)

{

if(AnalyLine[LeftRange?-1]==!StoneType)

break;

LeftRange--;

}

while(RightRange

{

if(AnalyLine[RightRange+1]==!StoneType)

break;

RightRange++;

}

//如果此范圍小于4則分析沒有意義

if(RightRange-LeftRange<4)

{

for(intk=LeftRange;k<=RightRange;k++)

m_LineRecord[k]=ANALSISED;

returnfalse;

}

//將連續(xù)區(qū)域設(shè)為分析過的,防止重復(fù)分析此一區(qū)域

for(intk=LeftEdge;k<=RightEdge;k++)

m_LineRecord[k]=ANALSISED;

if(RightEdge-LeftEdge>3)

{

//如待分析棋子棋型為五連

m_LineRecord[nAnalyPos]=FIVE;

returnFIVE;

}

if(RightEdge-LeftEdge==?3)

{

//如待分析棋子棋型為四連

boolLeftfour=false;

if(LeftEdge>0)

if(AnalyLine[LeftEdge-1]==NOSTONE)

Leftfour=true;//左邊有氣

if(RightEdge

//右邊未到邊界

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;//沖四

returnm_LineRecord[nAnalyPos];

}

if(RightEdge-LeftEdge==2)

{

//如待分析棋子棋型為三連

boolLeftThree=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

if(AnalyLine[RightEdge+1]==NOSTONE)

//右邊有氣

if(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)//如左沖四

returnm_LineRecord[LeftEdge];//返回

if(LeftThree==true)//如左邊有氣

m_LineRecord[nAnalyPos]=STHREE;//眠三

}

else

{

if(m_LineRecord[LeftEdge]==SFOUR)//如左沖四

returnm_LineRecord[LeftEdge];//返回

if(LeftThree==true)//如左邊有氣

m_LineRecord[nAnalyPos]=STHREE;//眠三

}

returnm_LineRecord[nAnalyPos];

}

if(RightEdge-LeftEdge==1)

{

//如待分析棋子棋型為二連

boolLefttwo=false;

boolLeftthree=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

if(AnalyLine[RightEdge+1]==NOSTONE)

//右邊有氣

if(RightEdge+1

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)//左邊沖四

returnm_LineRecord[LeftEdge];//返回

if(m_LineRecord[LeftEdge]==STHREE)//左邊眠三

returnm_LineRecord[LeftEdge];

if(Lefttwo==true)

m_LineRecord[nAnalyPos]=TWO;//返回活二

else

m_LineRecord[nAnalyPos]=STWO;//眠二

}

else

{

if(m_LineRecord[LeftEdge]==SFOUR)//沖四返回

returnm_LineRecord[LeftEdge];

if(Lefttwo==true)//眠二

m_LineRecord[nAnalyPos]=STWO;

}

returnm_LineRecord[nAnalyPos];

}

return0;

}

//將歷史記錄表中所有項目全置為初值

voidResetHistoryTable()

{

memset(m_HistoryTable,10,GRID_COUNT*sizeof(int));

}

//從歷史得分表中取給定走法的歷史得分

intGetHistoryScore(STONEMOVE*?move)

{

returnm_HistoryTable[move->StonePos.x][move->StonePos.y];

}

//將一最佳走法匯入歷史記錄

voidEnterHistoryScore(STONEMOVE*?move,intdepth)

{

m_HistoryTable[move->StonePos.x][move->StonePos.y]+=2<

}

//對走法隊列從小到大排序

//STONEMOVE*?source原始隊列

//STONEMOVE*?target目標(biāo)隊列

//合并source[l…m]和?source[m?+1…r]至target[l…r]

voidMerge(STONEMOVE*?source,STONEMOVE*?target,intl,intm,intr)

{

//從小到大排序

inti=l;

intj=m+1;

intk=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(intq=j;q<=r;q++)

target[k++]=source[q];

else

for(intq=i;q<=m;q++)

target[k++]=source[q];

}

voidMerge_A(STONEMOVE*?source,STONEMOVE*?target,intl,intm,intr)

{

//從大到小排序

inti=l;

intj=m+1;

intk=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(intq=j;q<=r;q++)

target[k++]=source[q];

else

for(intq=i;q<=m;q++)

target[k++]=source[q];

}

//合并大小為?S?的相鄰子數(shù)組

//direction?是標(biāo)志,指明是從大到小還是從小到大排序

voidMergePass(STONEMOVE*?source,STONEMOVE*?target,constints,constintn,constbooldirection)

{

inti=0;

while(i<=n-2*s)

{

//合并大小為?s的相鄰二段子數(shù)組

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

{

if(direction)

Merge(source,target,i,i+s-1,n-1);

else

Merge_A(source,target,i,i+s-1,n-1);

}

else

for(intj=i;j<=n-1;j++)

target[j]=source[j];

}

voidMergeSort(STONEMOVE*?source,intn,booldirection)

{

ints=1;

while(s

{

MergePass(source,m_TargetBuff,s,n,direction);

s+=s;

MergePass(m_TargetBuff,source,s,n,direction);

s+=s;

}

intCreatePossibleMove(unsignedcharposition[][GRID_NUM],intnPly,intnSide)

{

inti,j;

m_nMoveCount=0;

for(i=0;i

for(j=0;j

{

if(position[i][j]==(unsignedchar)NOSTONE)

AddMove(j,i,nPly);

}

//使用歷史啟發(fā)類中的靜態(tài)歸并排序函數(shù)對走法隊列進(jìn)行排序

//這是為了提高剪枝效率

//??CHistoryHeuristic?history;

MergeSort(m_MoveList[nPly],m_nMoveCount,0);

returnm_nMoveCount;//返回合法走法個數(shù)

}

//在m_MoveList中插入一個走法

//nToX是目標(biāo)位置橫坐標(biāo)

//nToY是目標(biāo)位置縱坐標(biāo)

//nPly是此走法所在的層次

intAddMove(intnToX,intnToY,intnPly)

{

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];//使用位置價值表評估當(dāng)前走法的價值

returnm_nMoveCount;

}

voidCNegaScout_TT_HH()

{

ResetHistoryTable();

//??m_pThinkProgress=NULL;

}

voidSearchAGoodMove(unsignedcharposition[][GRID_NUM],intType)

{

intScore;

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);

}

intIsGameOver(unsignedcharposition[][GRID_NUM],intnDepth)

{

intscore,i;//計算要下的棋子顏色

i=(m_nMaxDepth-nDepth)%2;

score=Eveluate(position,i);//調(diào)用估值函數(shù)

if(abs(score)>8000)//如果估值函數(shù)返回極值，給定局面游戲結(jié)束

returnscore;//返回極值

return0;//返回未結(jié)束

}

intNegaScout(intdepth,intalpha,intbeta)

{

intCount,i;

unsignedchartype;

inta,b,t;

intside;

intscore;

/*??if(depth>0)

{

i=?IsGameOver(CurPosition,depth);

if(i!=0)

return?i;??//已分勝負(fù)佳窑，返回極值

}

side=(m_nMaxDepth-depth)%2;//計算當(dāng)前節(jié)點的類型,極大0/極小1

score=LookUpHashTable(alpha,beta,depth,side);

if(score!=66666)

returnscore;

if(depth<=0)//葉子節(jié)點取估值

{

score=Eveluate(CurPosition,side);

EnterHashTable(exact,score,depth,side);//將估值存入置換表

returnscore;

}

Count=CreatePossibleMove(CurPosition,depth,side);

for(i=0;i

m_MoveList[depth][i].Score=GetHistoryScore(&m_MoveList[depth][i]);

MergeSort(m_MoveList[depth],Count,0);

intbestmove=-1;

a=alpha;

b=beta;

inteval_is_exact=0;

for(i=0;i

{

type=MakeMove(&m_MoveList[depth][i],side);

Hash_MakeMove(&m_MoveList[depth][i],CurPosition);

t=-NegaScout(depth-1,-b,-a);//遞歸搜索子節(jié)點制恍，對第?1?個節(jié)點是全窗口，其后是空窗探測

if(t>a?&&?t0)

{

//對于第一個后的節(jié)點,如果上面的搜索failhigh

a=-NegaScout(depth-1,-beta,-t);//re-search

eval_is_exact=1;//設(shè)數(shù)據(jù)類型為精確值

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

{

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);

returna;

}

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);

returna;

}

unsignedcharMakeMove(STONEMOVE*?move,inttype)

{

CurPosition[move->StonePos.y][move->StonePos.x]=type;

return0;

}

voidUnMakeMove(STONEMOVE*?move)

{

CurPosition[move->StonePos.y][move->StonePos.x]=NOSTONE;

}

__int64rand64(void)

{

returnrand()^((__int64)rand()<<15)^((__int64)rand()<<30)^

((__int64)rand()<<45)^((__int64)rand()<<60);

}

//生成32位隨機數(shù)

longrand32(void)

{

returnrand()^((long)rand()<<15)^((long)rand()<<30);

}

voidCTranspositionTable()

{

InitializeHashKey();//建立哈希表神凑，創(chuàng)建隨機數(shù)組

}

void_CTranspositionTable()

{

//釋放哈希表所用空間

deletem_pTT[0];

deletem_pTT[1];

}

voidCalculateInitHashKey(unsignedcharCurPosition[][GRID_NUM])

{

intj,k,nStoneType;

m_HashKey32=0;

//將所有棋子對應(yīng)的哈希數(shù)加總

for(j=0;j

for(k=0;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];

}

voidHash_MakeMove(STONEMOVE?*move,unsignedcharCurPosition[][GRID_NUM])

{

inttype;

type=CurPosition[move->StonePos.y][move->StonePos.x];//將棋子在目標(biāo)位置的隨機數(shù)添入

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];

}

voidHash_UnMakeMove(STONEMOVE?*move,unsignedcharCurPosition[][GRID_NUM])

{

inttype;

type=CurPosition[move->StonePos.y][move->StonePos.x];//將棋子現(xiàn)在位置上的隨機數(shù)從哈希值當(dāng)中去除

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];

}

intLookUpHashTable(intalpha,intbeta,intdepth,intTableNo)

{

intx;

HashItem*?pht;

//計算二十位哈希地址净神，如果讀者設(shè)定的哈希表大小不是?1M*2?的,

//而是?TableSize*2，TableSize為讀者設(shè)定的大小

//則需要修改這一句為m_HashKey32%?TableSize

//下一個函數(shù)中這一句也一樣

x=m_HashKey32?&?0xFFFFF;

pht=&m_pTT[TableNo][x];//取到具體的表項指針

if(pht->depth>=depth?&&?pht->checksum==m_HashKey64)

{

switch(pht->entry_type)//判斷數(shù)據(jù)類型

{

caseexact://確切值

returnpht->eval;

caselower_bound://下邊界

if(pht->eval>=beta)

returnpht->eval;

else

break;

caseupper_bound://上邊界

if(pht->eval<=alpha)

returnpht->eval;

else

break;

}

return66666;

}

voidEnterHashTable(ENTRY_TYPE?entry_type,shorteval,shortdepth,intTableNo)

{

intx;

HashItem*?pht;

x=m_HashKey32?&?0xFFFFF;//計算二十位哈希地址

pht=&m_pTT[TableNo][x];//取到具體的表項指針

//將數(shù)據(jù)寫入哈希表

pht->checksum=m_HashKey64;//64位校驗碼

pht->entry_type=entry_type;//表項類型

pht->eval=eval;//要保存的值

pht->depth=depth;//層次

}

voidInitializeHashKey()

{

inti,j,k;

srand((unsigned)time(NULL));

//填充隨機數(shù)組

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]=newHashItem[1024*1024];//用于存放取極大值的節(jié)點數(shù)據(jù)

m_pTT[1]=newHashItem[1024*1024];//用于存放取極小值的節(jié)點數(shù)據(jù)

}

intmain()

{

intcolour;

charcommand[10];//用于保存命令的字符串

for(inti?=?0;?i?<?GRID_NUM;?i++)

for(intj?=?0;?j?<?GRID_NUM;?j++)

m_RenjuBoard[i][j]?=?NOSTONE;//棋盤初始化

cin?>>?command;

if(strcmp(command,"[START]")?!=?0)//讀入第一條命令

{

return0;//如果不是[START]則停止程序

}

cin?>>?colour;//讀入己方顏色

colour=colour-1;

m_nUserStoneColor=1-colour;

while(true)

{

intrival_x,?rival_y;//用于保存對手上一步落子點

cin?>>?command;//讀入命令

if(strcmp(command,"[PUT]")?!=?0)

break;//如果不是[PUT]則停止程序

cin?>>?rival_x?>>?rival_y;//讀入對手上一步落子點

if(colour?==?0?&&?rival_x?==?-1?&&?rival_y?==?-1)//如果己方執(zhí)黑且是第一步，則占據(jù)棋盤中心位置

{

m_RenjuBoard[GRID_NUM?/?2][GRID_NUM?/?2]?=?colour;//更新棋盤信息

cout?<<?GRID_NUM?/?2?<<'?'<<?GRID_NUM?/?2?<<?endl;//輸出

cout?<<?flush;//刷新緩沖區(qū)

}

else

{

m_RenjuBoard[rival_x][rival_y]?=?1?-?colour;

//更新棋盤信息

m_nSearchDepth=3;

//最大搜索深度

{

CNegaScout_TT_HH();//創(chuàng)建NegaScout_TT_HH搜索引擎

CTranspositionTable();

SearchAGoodMove(m_RenjuBoard,colour);

m_RenjuBoard[X][Y]=colour;

cout?<<?X?<<'?'<<?Y?<<?endl;//輸出

cout?<<?flush;//刷新緩沖區(qū)

_CTranspositionTable();

break;//結(jié)束循環(huán)

}

while(true);

//循環(huán)直至隨機得到一個空位置

}

return0;

}

最后編輯于：2017.12.06 18:54:07

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末薛躬，一起剝皮案震驚了整個濱河市俯渤，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌型宝，老刑警劉巖八匠，帶你破解...
沈念sama閱讀 216,372評論 6贊 498
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異趴酣，居然都是意外死亡梨树，警方通過查閱死者的電腦和手機，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,368評論 3贊 392
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門岖寞，熙熙樓的掌柜王于貴愁眉苦臉地迎上來抡四，“玉大人，你說我怎么就攤上這事仗谆≈秆玻” “怎么了？”我有些...
開封第一講書人閱讀 162,415評論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵隶垮，是天一觀的道長藻雪。經(jīng)常有香客問我，道長狸吞，這世上最難降的妖魔是什么勉耀？我笑而不...
開封第一講書人閱讀 58,157評論 1贊 292
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮蹋偏，結(jié)果婚禮上便斥，老公的妹妹穿的比我還像新娘。我一直安慰自己威始，他們只是感情好椭住，可當(dāng)我...
茶點故事閱讀 67,171評論 6贊 388
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著字逗，像睡著了一般京郑。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上葫掉，一...
開封第一講書人閱讀 51,125評論 1贊 297
城市分裂傳說
那天些举，我揣著相機與錄音，去河邊找鬼俭厚。笑死户魏，一個胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的挪挤。我是一名探鬼主播叼丑，決...
沈念sama閱讀 40,028評論 3贊 417
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼扛门！你這毒婦竟也來了鸠信？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 38,887評論 0贊 274
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤论寨，失蹤者是張志新（化名）和其女友劉穎星立，沒想到半個月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體葬凳，經(jīng)...
沈念sama閱讀 45,310評論 1贊 310
?護(hù)林員之死
正文獨居荒郊野嶺守林人離奇死亡绰垂，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,533評論 2贊 332
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了火焰。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片劲装。...
茶點故事閱讀 39,690評論 1贊 348
活死人
序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖昌简，靈堂內(nèi)的尸體忽然破棺而出占业，到底是詐尸還是另有隱情，我是刑警寧澤江场，帶...
沈念sama閱讀 35,411評論 5贊 343
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布纺酸，位于F島的核電站，受9級特大地震影響址否，放射性物質(zhì)發(fā)生泄漏餐蔬。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點故事閱讀 41,004評論 3贊 325
男人毒藥：我在死后第九天來索命
文/蒙蒙一佑附、第九天我趴在偏房一處隱蔽的房頂上張望樊诺。院中可真熱鬧，春花似錦音同、人聲如沸词爬。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,659評論 0贊 22
一樁弒父案权均，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽顿膨。三九已至锅锨，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間恋沃，已是汗流浹背必搞。一陣腳步聲響...
開封第一講書人閱讀 32,812評論 1贊 268
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留囊咏，地道東北人恕洲。一個月前我還...
沈念sama閱讀 47,693評論 2贊 368
代替公主和親
正文我出身青樓，卻偏偏與公主長得像梅割，于是被迫代替她去往敵國和親霜第。傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 44,577評論 2贊 353

五子棋人機對弈代碼——之博弈樹算法

推薦閱讀更多精彩內(nèi)容