Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<math.h>
- #include<stdlib.h>
- #include<time.h>
- #include<iostream>
- #include<cstdio>
- #include "jsoncpp/json.h" // C++编译时默认包含此库
- #define N 8 //每个节点的分支数
- //以下为各棋型的识别码 //权重
- using namespace std;
- using namespace Json;
- char board[15][15]; //当前棋盘
- void placeAt(int x,int y,int d) {
- if(x>=0&&y>=0)
- board[x][y]=d;
- }
- int put_board()
- {
- for(int i=0;i<15;i++)
- {
- for(int j=0;j<15;j++)
- {
- if(board[i][j]==1)
- {
- cout<<"x ";
- }
- else if(board[i][j]==2)
- {
- cout<<"o ";
- }
- else
- {
- cout<<". ";
- }
- }
- cout<<endl;
- }
- }
- //复制棋盘A到B
- int copy_board(char A[][15],char B[][15])
- {
- int i,j;
- for(i=0;i<15;i++)
- {
- for(j=0;j<15;j++)
- {
- B[i][j]=A[i][j];
- }
- }
- return 0;
- }
- //复制取反后的棋盘A到B
- int inv_board(char A[][15],char B[][15])
- {
- int i,j;
- int INV[3]={0,2,1};
- for(i=0;i<15;i++)
- {
- for(j=0;j<15;j++)
- {
- B[i][j]=INV[A[i][j]];
- }
- }
- return 0;
- }
- int score[3][3][3][3][3][3] = {0,0,0,15,13,0,16,0,14,15,13,0,11,9,13,0,0,0,16,0,14,0,0,0,12,14,10,15,13,0,11,9,13,0,0,0,11,9,13,7,5,9,0,0,0,0,0,0,0,0,0,0,0,0,16,0,14,0,0,0,12,14,10,0,0,0,0,0,0,0,0,0,12,14,10,0,0,0,8,10,6,15,13,0,11,9,13,0,0,0,11,9,13,7,5,9,0,0,0,0,0,0,0,0,0,0,0,0,11,9,13,7,5,9,0,0,0,7,5,9,3,1,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,16,0,14,0,0,0,12,14,10,0,0,0,0,0,0,0,0,0,12,14,10,0,0,0,8,10,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,12,14,10,0,0,0,8,10,6,0,0,0,0,0,0,0,0,0,8,10,6,0,0,0,4,6,2,0,0,0,13,13,13,0,0,14,13,13,13,9,9,9,0,0,0,0,0,14,0,0,0,14,0,10,13,13,13,9,9,9,0,0,0,9,9,9,5,5,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,14,0,0,0,14,0,10,0,0,0,0,0,0,0,0,0,14,0,10,0,0,0,10,0,6,13,13,13,9,9,9,0,0,0,9,9,9,5,5,5,0,0,0,0,0,0,0,0,0,0,0,0,9,9,9,5,5,5,0,0,0,5,5,5,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,14,0,0,0,14,0,10,0,0,0,0,0,0,0,0,0,14,0,10,0,0,0,10,0,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,14,0,10,0,0,0,10,0,6,0,0,0,0,0,0,0,0,0,10,0,6,0,0,0,6,0,2,0,0,0,0,13,0,14,14,14,0,13,0,13,9,0,0,0,0,14,14,14,0,0,0,10,10,10,0,13,0,13,9,0,0,0,0,13,9,0,9,5,0,0,0,0,0,0,0,0,0,0,0,0,0,14,14,14,0,0,0,10,10,10,0,0,0,0,0,0,0,0,0,10,10,10,0,0,0,6,6,6,0,13,0,13,9,0,0,0,0,13,9,0,9,5,0,0,0,0,0,0,0,0,0,0,0,0,0,13,9,0,9,5,0,0,0,0,9,5,0,5,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,14,14,14,0,0,0,10,10,10,0,0,0,0,0,0,0,0,0,10,10,10,0,0,0,6,6,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,10,10,0,0,0,6,6,6,0,0,0,0,0,0,0,0,0,6,6,6,0,0,0,2,2,2};
- struct evaluation
- {
- int score;
- int result;
- };
- bool flag ;
- //对棋盘A的局势进行评分
- struct evaluation evaluate(char A[][15] , bool flag , int x , int y)
- {
- //各棋型权重
- int weight[17]={0,4000,-4000,2000,-2000,1000,-1000,1000,-1000,400,-600,400,-600,100,-150,100,-150};
- int i,j,s;
- int stat[4][17]={0};
- int STAT[17];
- struct evaluation EVALUATION;
- //棋型统计
- if(flag == true){
- for(i=0;i<15;i++)
- {
- for(j=0;j<10;j++)
- {
- s=score[A[i][j]][A[i][j+1]][A[i][j+2]][A[i][j+3]][A[i][j+4]][A[i][j+5]];
- stat[1][s]++;
- }
- }
- for(j=0;j<15;j++)
- {
- for(i=0;i<10;i++)
- {
- s=score[A[i][j]][A[i+1][j]][A[i+2][j]][A[i+3][j]][A[i+4][j]][A[i+5][j]];
- stat[2][s]++;
- }
- }
- for(i=0;i<10;i++)
- {
- for(j=0;j<10;j++)
- {
- s=score[A[i][j]][A[i+1][j+1]][A[i+2][j+2]][A[i+3][j+3]][A[i+4][j+4]][A[i+5][j+5]];
- stat[3][s]++;
- }
- }
- for(i=5;i<15;i++)
- {
- for(j=0;j<10;j++)
- {
- s=score[A[i][j]][A[i-1][j+1]][A[i-2][j+2]][A[i-3][j+3]][A[i-4][j+4]][A[i-5][j+5]];
- stat[0][s]++;
- }
- }
- }
- else {
- int he=1/0;
- /* for(int i=max(0,x-5) ; i <= x && (i+5<15); ++i){
- s = score[A[i][y]][A[i+1][y]][A[i+2][y]][A[i+3][y]][A[i+4][y]][A[i+5][y]];
- stat[0][s]++;
- }
- for(int i=max(0,y-5) ; i<= y && (i+5<15); ++i){
- s = score[A[x][i]][A[x][i+1]][A[x][i+2]][A[x][i+3]][A[x][i+4]][A[x][i+5]];
- stat[0][s]++;
- }
- int i=x,j=y;
- while(i > 0 && j > 0){ i--;j--;}
- for(; i<= x && (i+5) < 15 && (j+5) < 15 ; ++i,++j){
- s = score[A[i][j]][A[i+1][j+1]][A[i+2][j+2]][A[i+3][j+3]][A[i+4][j+4]][A[i+5][j+5]];
- stat[0][s]++;
- }
- i = x , j = y;
- while(i > 0 && j < 14){
- i--;j++;
- }
- for(; i<= x && (i+5) < 15 && (j-5) >= 0 ; ++i,--j ){
- s = score[A[i][j]][A[i+1][j-1]][A[i+2][j-2]][A[i+3][j-3]][A[i+4][j-4]][A[i+5][j-5]];
- stat[0][s]++;
- }*/
- }
- s=0;
- //初步评分累加
- for(i=1;i<17;i++)
- {
- s+=(stat[1][i]+stat[2][i]+stat[3][i]+stat[0][i])*weight[i];
- STAT[i]=(stat[1][i]>0)+(stat[2][i]>0)+(stat[3][i]>0)+(stat[0][i]>0);
- }
- EVALUATION.result=0;
- //胜
- if(STAT[1]>0)
- {
- s+=100000;
- flag = true;
- EVALUATION.result=1;
- }
- //负
- else if(STAT[2]>0)
- {
- s-=100000;
- flag = true;
- EVALUATION.result=2;
- }
- //对手冲四、活四
- else if(STAT[4]>0||STAT[6]>0)
- {
- s-=30000;
- }
- //对手无冲四、活四
- else if(STAT[4]==0&&STAT[6]==0)
- {
- int k=0;
- //检验 冲四活三
- for(i=0;i<4;i++)
- {
- for(j=0;j<4;j++)
- {
- if(i!=j)
- {
- k+=stat[i][5]*stat[j][7];
- }
- }
- }
- //活四
- if(STAT[3]>0)
- {
- s+=20000;
- }
- //双冲四
- else if(STAT[5]>=2)
- {
- s+=20000;
- }
- //冲四活三
- else if(k>0)
- {
- s+=20000;
- }
- //对手有活三
- else if(STAT[8]>0&&STAT[5]==0)
- {
- s-=20000;
- }
- //双活三
- else if(STAT[7]>=2&&STAT[8]==0)
- {
- s+=10000;
- }
- }
- EVALUATION.score=s;
- return EVALUATION;
- }
- struct points
- {
- int coo_x[N]; //横坐标
- int coo_y[N]; //纵坐标
- int eva[N]; //评估值
- int exi[N]; //存在性
- };
- //评估出最佳的N个待定落子点
- struct points seek_points(char A[][15])
- {
- struct points best_points;
- struct evaluation EVA, temp;
- int i,j,k;
- int worth[15][15];
- int B[15][15]={0};
- for(k=0;k<N;k++)
- {
- best_points.exi[k]=0;
- }
- EVA=evaluate(A,1,-1,-1);
- if(EVA.result>0)
- {
- best_points.exi[0]=1;
- best_points.eva[0]=EVA.score;
- goto the_end;
- }
- for(i=0;i<15;i++)
- {
- for(j=0;j<15;j++)
- {
- if(A[i][j]!=0)
- {
- for(k=-3;k<=3;k++)
- {
- if(i+k>=0&&i+k<15)
- {
- B[i+k][j]=1;
- if(j+k>=0&&j+k<15)
- {
- B[i+k][j+k]=1;
- }
- if(j-k>=0&&j-k<15)
- {
- B[i+k][j-k]=1;
- }
- }
- if(j+k>=0&&j+k<15)
- {
- B[i][j+k]=1;
- }
- }
- }
- }
- }
- //对于棋盘A上的空点,评估在该处落子后的局势
- for(i=0;i<15;i++)
- {
- for(j=0;j<15;j++)
- {
- worth[i][j]=-1000000;
- if(A[i][j]==0&&B[i][j]==1)
- {
- A[i][j]=1;
- EVA=evaluate(A,1,i,j);
- worth[i][j]=EVA.score;
- A[i][j]=0;
- }
- }
- }
- int w;
- //筛选最佳的N个点
- for(k=0;k<N;k++)
- {
- w=-1000000;
- for(i=0;i<15;i++)
- {
- for(j=0;j<15;j++)
- {
- if(worth[i][j]>w)
- {
- w=worth[i][j];
- best_points.coo_x[k]=i;
- best_points.coo_y[k]=j;
- }
- }
- }
- if( (k>0) && ((best_points.eva[0]-w)>3000) ) break;
- best_points.eva[k]=w;
- best_points.exi[k]=1;
- worth[best_points.coo_x[k]][best_points.coo_y[k]]=-1000000;
- }
- the_end:
- return best_points;
- }
- struct decision
- {
- int coo_x;
- int coo_y;
- int eva;
- };
- struct decision DECISION;
- int level_limit=6;
- //博弈树MinMax递归分析 AlphaBeta剪枝 不明白的参看维基百科
- int analyse(char A[][15],int level,int alpha,int beta)
- {
- if(level==level_limit)
- {
- struct points P;
- P=seek_points(A);
- alpha=P.eva[0];
- return alpha;
- }
- else if(level%2==0)
- {
- struct points P;
- P=seek_points(A);
- for(int i=0;i<N;i++)
- {
- if(P.exi[i]==1)
- {
- char buff[15][15];
- copy_board(A,buff);
- buff[P.coo_x[i]][P.coo_y[i]]=1;
- int a;
- a=analyse(buff,level+1,alpha,beta);
- if(a>alpha)
- {
- alpha=a;
- if(level==0)
- {
- DECISION.coo_x=P.coo_x[i];
- DECISION.coo_y=P.coo_y[i];
- DECISION.eva=a;
- }
- }
- }
- if(beta<=alpha) break;
- }
- return alpha;
- }
- else if(level%2==1)
- {
- char BUFF[15][15];
- inv_board(A,BUFF);
- struct points P;
- P=seek_points(BUFF);
- for(int i=0;i<N;i++)
- {
- if(P.exi[i]==1)
- {
- char buff[15][15];
- copy_board(A,buff);
- buff[P.coo_x[i]][P.coo_y[i]]=2;
- int a;
- a=analyse(buff,level+1,alpha,beta);
- if(a<beta)
- {
- beta=a;
- }
- }
- if(beta<=alpha) break;
- }
- return beta;
- }
- }
- bool start() {
- for(int i=0;i<15;i++)
- for(int j=0;j<15;j++)
- if(board[i][j]!=0) return 0;
- return 1;
- }
- Value pushout(int x,int y) {
- Json::Value action;
- action["x"]=x;
- action["y"]=y;
- return action;
- }
- //图形界面写法请无视吧。。。
- int main()
- {
- flag = false;
- string str;
- getline(cin, str);
- Reader reader;
- Value input;
- reader.parse(str, input);
- int turnID = input["responses"].size();
- for (int i = 0; i < turnID; i++) {
- placeAt(input["requests"][i]["x"].asInt(),input["requests"][i]["y"].asInt(),2);
- placeAt(input["responses"][i]["x"].asInt(),input["responses"][i]["y"].asInt(),1);
- }
- placeAt(input["requests"][turnID]["x"].asInt(),input["requests"][turnID]["y"].asInt(),2);
- Value ret;
- int id = 2;
- if(turnID>=2 && input["requests"][id]["x"].asInt()== -1 && input["requests"][id]["y"].asInt()==-1){
- int rq = 1, rp = 0 , rp2 = 1;
- placeAt(input["requests"][rq]["x"].asInt(), input["requests"][rq]["y"].asInt(),1);
- placeAt(input["responses"][rp]["x"].asInt(), input["responses"][rp]["y"].asInt(),2);
- placeAt(input["responses"][rp2]["x"].asInt(), input["responses"][rp2]["y"].asInt(),2);
- }
- if(start()) {
- ret["response"]=pushout(0,0);
- } else {
- analyse(board,0,-1000000,1000000);
- board[DECISION.coo_x][DECISION.coo_y]=1;
- ret["response"]=pushout(DECISION.coo_x,DECISION.coo_y);
- }
- FastWriter writer;
- cout<<writer.write(ret)<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement