goBang.rar

#include "aiplayer.h" #include <algorithm rel='nofollow' onclick='return false;'> bool point::operator ==(const point& x)const { return x.row == this->row && x.col == this->col; } bool point::operator <(const point& another)const { return score>another.score; } AIPlayer::AIPlayer() { } void AIPlayer::setColor(CHESSCOLOR color) { myColor = color; } void AIPlayer::setName(QString name) { this->name =name; } double AIPlayer::alphaBeta(int depth,double alpha,double beta,CHESSCOLOR player,point& choose )//待补充 { CHESSCOLOR opp = (player==WHITE?BLACK:WHITE); CHESSCOLOR winner = isWin(); if(winner != NONE) if(winner == myColor) return DBL_MAX/10; else return -DBL_MAX/10; modifyScore(); if(depth<=1 && player==myColor){ return score; } point bestMove; std::vector<point> canMove; int canMoveNums = 0; posCanMove(canMove,player); //prune(canMove,player); canMoveNums = canMove.size(); double tempScore = score; if(player==myColor)//力求最大 { double temp = -DBL_MAX; for(int i(0);i<canMoveNums;i++) { addAChess(canMove[i],player); steps.push_back(canMove[i]); temp = std::max(temp,alphaBeta(depth-1,alpha,beta,opp,bestMove)); score = tempScore; removeAChess(canMove[i]); steps.pop_back(); if(temp>=beta) return temp; if(alpha < temp) { choose = canMove[i]; alpha = temp; } } return temp; } else//求最小 { double temp = DBL_MAX; for(int i(0);i<canMoveNums;i++) { addAChess(canMove[i],player); steps.push_back(canMove[i]); temp = std::min(temp,alphaBeta(depth-1,alpha,beta,opp,bestMove)); score = tempScore; steps.pop_back(); removeAChess(canMove[i]); if(temp<=alpha) return temp; beta = std::min(beta,temp); } return temp; } } bool AIPlayer::hasNeigh(int x,int y)//判断是否有有邻居 { return neighNums[x][y]>0; } void AIPlayer::posCanMove(std::vector<point>&canMove,CHESSCOLOR player)//下一步可以落子的点，仅仅考虑5*5邻域 { CHESSCOLOR opp = (player==BLACK?WHITE:BLACK); for(int i(0);i<15;i++) for(int j(0);j<15;j++) { if(myBoard[i][j]==NONE && hasNeigh(i,j)) { canMove.push_back(point(i,j,evaluate(i,j,player)+evaluate(i,j,opp))); } } sort(canMove.begin(),canMove.end()); while(canMove.size()>10) canMove.pop_back(); } void AIPlayer::initiallizeNeigh() { neighNums = QVector<QVector<int> >(15,QVector<int>(15,0)); for(int i(0);i<15;i++) for(int j(0);j<15;j++) { if(myBoard[i][j]!=NONE) { for(int k(-2);k<=2;k++) for(int l(-2);l<=2;l++) { if(legal(i+k,j+l)) { neighNums[i+k][j+l]++; } } } } } void AIPlayer::addAChess(const point &p, const CHESSCOLOR &color) { int x = p.row,y = p.col; myBoard[p.row][p.col] = color; int maxx = std::min(14,x+2),maxy = std::min(14,y+2); for(int i(std::max(0,x-2));i<=maxx;i++) for(int j(std::max(0,y-2));j<=maxy;j++) { neighNums[i][j]++; } } void AIPlayer::removeAChess(const point& p) { int x = p.row,y = p.col; myBoard[x][y]=NONE; for(int i(-2);i<=2;i++) for(int j(-2);j<=2;j++) { if(legal(x+i,y+j)) neighNums[x+i][y+j]--; } } void AIPlayer::myTurn(const QVector<QVector<CHESSCOLOR> >&board) { myBoard = board; initiallizeNeigh(); evaluate(); steps.clear(); alphaBeta(5,-DBL_MAX,DBL_MAX,myColor,bestMove); emit player::addAChess(myColor,bestMove.row,bestMove.col); } void AIPlayer::modifyScore()//走了一步，需要重新计算分数，只需要重新计算落子点附近的位置分数即可 { if(steps.size()==0) return; point lastStep = steps.back(); int x = lastStep.row,y = lastStep.col; CHESSCOLOR player = myBoard[x][y]; CHESSCOLOR opp = (player==WHITE?BLACK:WHITE); double temp = 0; temp = evaluate(x,y,player); myBoard[x][y]=NONE; temp -= evaluate(x,y,player); temp += evaluate(x,y,opp); myBoard[x][y]=player; if(player==myColor) score += temp*5; else score -= temp*5; } bool AIPlayer::legal(int x,int y) { return x>=0 && x<15&&y>=0&&y<15; } double AIPlayer::evaluate()//计算整个棋盘的分数 { score = 0; CHESSCOLOR opp; opp = (myColor==WHITE?BLACK:WHITE); for(int i(0);i<15;i++) for(int j(0);j<15;j++) { score += evaluate(i,j,myColor) - evaluate(i,j,opp); } return score; } double AIPlayer::evaluate(int x,int y,CHESSCOLOR player)//计算某一位置的分数 { static double scores[6]={0,1,20,600,4000,1000000}; static double combo[5][5]={ {0,0,0,0,0}, {0,0,0,0,0}, {0,0,100,400,800}, {0,0,400,2000,30000}, {0,0,800,30000,100000} }; static int dx[4]={1,1,1,0}; static int dy[4]={-1,1,0,1}; double result = 0; CHESSCOLOR opp; opp = (player==WHITE?BLACK:WHITE); int style[4]={0}; int lx,ly,hx,hy; int num,num0,temp; for(int i(0);i<4;i++) { lx = x-dx[i],ly = y-dy[i]; num = 0; while(legal(lx,ly)&&num<4 && myBoard[lx][ly]!=opp) { lx -= dx[i],ly-=dy[i]; num++; } lx += dx[i];ly+=dy[i]; hx = lx;hy = ly; num0 = num; temp = 0; num = 0; while((num<5)&&legal(hx,hy)&&(myBoard[hx][hy]!=opp)) { if(myBoard[hx][hy]==player) temp++; hx+=dx[i];hy+=dy[i]; num++; } if(num<5) continue; result += scores[temp]; while(num0>0 && legal(hx,hy) && myBoard[hx][hy]!=opp) { if(myBoard[lx][ly]==player) temp--; if(myBoard[hx][hy]==player) temp++; if(temp>style[i]) style[i]=temp; result += scores[temp]; lx+=dx[i];ly+=dy[i]; hx+=dx[i];hy+=dy[i]; num0 --; } /*for(int i(0);i<4;i++) for(int j(i+1);j<4;j++) { if(i!=j &&style[i]!=5 && style[j]!=5) { result += combo[style[i]][style[j]]; } }*/ } return result; } point::point(int x,int y,int score) { row = x,col = y; this->score = score; } void point::set(int x,int y) { row = x; col = y; } void AIPlayer::prune(std::vector<point> &canMove,CHESSCOLOR player) { CHESSCOLOR opp = (player==WHITE?BLACK:WHITE); std::vector<point> threats; for(size_t i(0);i<canMove.size();i++) { if(haveThreat(canMove[i],opp)) { threats.push_back(canMove[i]); } else if(haveThreat(canMove[i],player)) threats.push_back(canMove[i]); } if(threats.size()>=3) canMove = threats; return; } //判断是否有三个子，或者有两个活2，己方可以利用这些点来进攻 bool AIPlayer::havePotThreat(const point& step,CHESSCOLOR player) { static int dx[4]={1,1,1,0}; static int dy[