Advertisement
Guest User

Untitled

a guest
May 25th, 2019
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 10.17 KB | None | 0 0
  1.  
  2. #include<math.h>
  3.  
  4. #include<stdlib.h>
  5.  
  6. #include<time.h>
  7.  
  8. #include<iostream>
  9.  
  10. #include<cstdio>
  11.  
  12. #include "jsoncpp/json.h" // C++编译时默认包含此库
  13.  
  14. #define N 8 //每个节点的分支数
  15.  
  16. //以下为各棋型的识别码  //权重
  17.  
  18. using namespace std;
  19. using namespace Json;
  20.  
  21. char board[15][15]; //当前棋盘
  22.  
  23. void placeAt(int x,int y,int d) {
  24.     if(x>=0&&y>=0)
  25.         board[x][y]=d;
  26. }
  27.  
  28. int put_board()
  29. {
  30.     for(int i=0;i<15;i++)
  31.     {
  32.         for(int j=0;j<15;j++)
  33.         {
  34.             if(board[i][j]==1)
  35.             {
  36.                 cout<<"x ";
  37.             }
  38.             else if(board[i][j]==2)
  39.             {
  40.                 cout<<"o ";
  41.             }
  42.             else
  43.             {
  44.                 cout<<". ";
  45.             }
  46.         }
  47.         cout<<endl;
  48.     }
  49. }
  50.  
  51. //复制棋盘A到B
  52. int copy_board(char A[][15],char B[][15])
  53. {
  54.     int i,j;
  55.    
  56.     for(i=0;i<15;i++)
  57.     {
  58.         for(j=0;j<15;j++)
  59.         {
  60.             B[i][j]=A[i][j];
  61.         }
  62.     }
  63.     return 0;
  64. }
  65.  
  66. //复制取反后的棋盘A到B
  67. int inv_board(char A[][15],char B[][15])
  68. {
  69.     int i,j;
  70.    
  71.     int INV[3]={0,2,1};
  72.    
  73.     for(i=0;i<15;i++)
  74.     {
  75.         for(j=0;j<15;j++)
  76.         {
  77.             B[i][j]=INV[A[i][j]];
  78.         }
  79.     }
  80.     return 0;
  81. }
  82.  
  83. 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};
  84.  
  85.  
  86. struct evaluation
  87. {
  88.     int score;
  89.     int result;
  90. };
  91. bool flag ;
  92. //对棋盘A的局势进行评分
  93. struct evaluation evaluate(char A[][15] , bool flag , int x , int y)
  94. {
  95.     //各棋型权重
  96.     int weight[17]={0,4000,-4000,2000,-2000,1000,-1000,1000,-1000,400,-600,400,-600,100,-150,100,-150};
  97.    
  98.     int i,j,s;
  99.    
  100.     int stat[4][17]={0};
  101.  
  102.     int STAT[17];
  103.    
  104.     struct evaluation EVALUATION;
  105.    
  106.     //棋型统计
  107.     if(flag == true){
  108.     for(i=0;i<15;i++)
  109.     {
  110.         for(j=0;j<10;j++)
  111.         {
  112.             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]];
  113.            
  114.             stat[1][s]++;
  115.         }
  116.     }
  117.    
  118.     for(j=0;j<15;j++)
  119.     {
  120.         for(i=0;i<10;i++)
  121.         {
  122.             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]];
  123.            
  124.             stat[2][s]++;
  125.         }
  126.     }
  127.    
  128.     for(i=0;i<10;i++)
  129.     {
  130.         for(j=0;j<10;j++)
  131.         {
  132.             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]];
  133.            
  134.             stat[3][s]++;
  135.         }
  136.     }
  137.    
  138.     for(i=5;i<15;i++)
  139.     {
  140.         for(j=0;j<10;j++)
  141.         {
  142.             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]];
  143.            
  144.             stat[0][s]++;
  145.         }
  146.     }
  147.     }
  148.     else {
  149.         int he=1/0;
  150.     /*      for(int i=max(0,x-5) ; i <= x && (i+5<15); ++i){
  151.                 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]];
  152.                 stat[0][s]++;
  153.             }
  154.             for(int i=max(0,y-5) ; i<= y && (i+5<15); ++i){
  155.                 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]];
  156.                 stat[0][s]++;
  157.             }
  158.             int i=x,j=y;
  159.             while(i > 0 && j > 0){ i--;j--;}
  160.             for(; i<= x && (i+5) < 15 && (j+5) < 15 ; ++i,++j){
  161.                 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]];
  162.                 stat[0][s]++;
  163.             }
  164.             i = x , j = y;
  165.             while(i > 0 && j < 14){
  166.                 i--;j++;
  167.             }
  168.             for(; i<= x && (i+5) < 15 && (j-5) >= 0 ; ++i,--j ){
  169.                 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]];
  170.                 stat[0][s]++;
  171.             }*/
  172.         }
  173.    
  174.     s=0;
  175.    
  176.     //初步评分累加
  177.     for(i=1;i<17;i++)
  178.     {
  179.         s+=(stat[1][i]+stat[2][i]+stat[3][i]+stat[0][i])*weight[i];
  180.        
  181.         STAT[i]=(stat[1][i]>0)+(stat[2][i]>0)+(stat[3][i]>0)+(stat[0][i]>0);
  182.     }
  183.    
  184.     EVALUATION.result=0;
  185.    
  186.     //胜
  187.     if(STAT[1]>0)
  188.     {
  189.         s+=100000;
  190.         flag = true;
  191.         EVALUATION.result=1;
  192.     }
  193.    
  194.     //负
  195.     else if(STAT[2]>0)
  196.     {
  197.         s-=100000;
  198.         flag = true;
  199.         EVALUATION.result=2;
  200.     }
  201.    
  202.     //对手冲四、活四
  203.     else if(STAT[4]>0||STAT[6]>0)
  204.     {
  205.         s-=30000;
  206.     }
  207.    
  208.     //对手无冲四、活四
  209.     else if(STAT[4]==0&&STAT[6]==0)
  210.     {
  211.         int k=0;
  212.        
  213.         //检验 冲四活三
  214.         for(i=0;i<4;i++)
  215.         {
  216.             for(j=0;j<4;j++)
  217.             {
  218.                 if(i!=j)
  219.                 {
  220.                     k+=stat[i][5]*stat[j][7];
  221.                 }
  222.             }
  223.         }
  224.        
  225.         //活四
  226.         if(STAT[3]>0)
  227.         {
  228.             s+=20000;
  229.         }
  230.        
  231.         //双冲四
  232.         else if(STAT[5]>=2)
  233.         {
  234.             s+=20000;
  235.         }
  236.        
  237.         //冲四活三
  238.         else if(k>0)
  239.         {
  240.             s+=20000;
  241.         }
  242.        
  243.         //对手有活三
  244.         else if(STAT[8]>0&&STAT[5]==0)
  245.         {
  246.             s-=20000;
  247.         }
  248.        
  249.         //双活三
  250.         else if(STAT[7]>=2&&STAT[8]==0)
  251.         {
  252.             s+=10000;
  253.         }
  254.     }
  255.     EVALUATION.score=s;
  256.        
  257.     return EVALUATION;
  258. }
  259.  
  260. struct points
  261. {
  262.     int coo_x[N]; //横坐标
  263.    
  264.     int coo_y[N]; //纵坐标
  265.    
  266.     int eva[N]; //评估值
  267.    
  268.     int exi[N]; //存在性
  269. };
  270.  
  271. //评估出最佳的N个待定落子点
  272. struct points seek_points(char A[][15])
  273. {
  274.     struct points best_points;
  275.    
  276.     struct evaluation EVA, temp;
  277.    
  278.     int i,j,k;
  279.    
  280.     int worth[15][15];
  281.    
  282.     int B[15][15]={0};
  283.    
  284.     for(k=0;k<N;k++)
  285.     {
  286.         best_points.exi[k]=0;
  287.     }
  288.    
  289.     EVA=evaluate(A,1,-1,-1);
  290.    
  291.     if(EVA.result>0)
  292.     {
  293.         best_points.exi[0]=1;
  294.        
  295.         best_points.eva[0]=EVA.score;
  296.                    
  297.                     goto the_end;
  298.            
  299.     }
  300.    
  301.     for(i=0;i<15;i++)
  302.     {
  303.         for(j=0;j<15;j++)
  304.         {
  305.             if(A[i][j]!=0)
  306.             {
  307.                 for(k=-3;k<=3;k++)
  308.                 {
  309.                     if(i+k>=0&&i+k<15)
  310.                     {
  311.                         B[i+k][j]=1;
  312.                        
  313.                         if(j+k>=0&&j+k<15)
  314.                         {
  315.                             B[i+k][j+k]=1;
  316.                         }
  317.                         if(j-k>=0&&j-k<15)
  318.                         {
  319.                             B[i+k][j-k]=1;
  320.                         }
  321.                     }
  322.                     if(j+k>=0&&j+k<15)
  323.                     {
  324.                         B[i][j+k]=1;
  325.                     }
  326.                 }
  327.             }
  328.         }
  329.     }
  330.    
  331.     //对于棋盘A上的空点,评估在该处落子后的局势
  332.     for(i=0;i<15;i++)
  333.     {
  334.         for(j=0;j<15;j++)
  335.         {
  336.             worth[i][j]=-1000000;
  337.            
  338.             if(A[i][j]==0&&B[i][j]==1)
  339.             {
  340.                 A[i][j]=1;
  341.                
  342.                 EVA=evaluate(A,1,i,j);
  343.                
  344.                 worth[i][j]=EVA.score;
  345.                
  346.                 A[i][j]=0;
  347.             }
  348.         }
  349.     }
  350.  
  351.     int w;
  352.  
  353.     //筛选最佳的N个点
  354.     for(k=0;k<N;k++)
  355.     {
  356.         w=-1000000;
  357.        
  358.         for(i=0;i<15;i++)
  359.         {
  360.             for(j=0;j<15;j++)
  361.             {
  362.                 if(worth[i][j]>w)
  363.                 {
  364.                     w=worth[i][j];
  365.                    
  366.                     best_points.coo_x[k]=i;
  367.                    
  368.                     best_points.coo_y[k]=j;
  369.                 }
  370.             }
  371.         }
  372.         if( (k>0) && ((best_points.eva[0]-w)>3000) ) break;
  373.        
  374.         best_points.eva[k]=w;
  375.        
  376.         best_points.exi[k]=1;
  377.        
  378.         worth[best_points.coo_x[k]][best_points.coo_y[k]]=-1000000;
  379.     }
  380.    
  381.     the_end:
  382.    
  383.     return best_points;
  384. }
  385.  
  386. struct decision
  387. {
  388.     int coo_x;
  389.    
  390.     int coo_y;
  391.    
  392.     int eva;
  393. };
  394.  
  395. struct decision DECISION;
  396.  
  397. int level_limit=6;
  398.  
  399. //博弈树MinMax递归分析 AlphaBeta剪枝 不明白的参看维基百科
  400. int analyse(char A[][15],int level,int alpha,int beta)
  401. {  
  402.     if(level==level_limit)
  403.     {
  404.         struct points P;
  405.        
  406.         P=seek_points(A);
  407.        
  408.         alpha=P.eva[0];
  409.        
  410.         return alpha;
  411.     }
  412.    
  413.     else if(level%2==0)
  414.     {
  415.         struct points P;
  416.        
  417.         P=seek_points(A);
  418.        
  419.        
  420.        
  421.         for(int i=0;i<N;i++)
  422.         {
  423.             if(P.exi[i]==1)
  424.             {
  425.                 char buff[15][15];
  426.                
  427.                 copy_board(A,buff);
  428.                
  429.                 buff[P.coo_x[i]][P.coo_y[i]]=1;
  430.                
  431.                 int a;
  432.                
  433.                 a=analyse(buff,level+1,alpha,beta);
  434.                
  435.                 if(a>alpha)
  436.                 {
  437.                     alpha=a;
  438.                    
  439.                     if(level==0)
  440.                     {
  441.                         DECISION.coo_x=P.coo_x[i];
  442.                        
  443.                         DECISION.coo_y=P.coo_y[i];
  444.                        
  445.                         DECISION.eva=a;
  446.                     }
  447.                 }
  448.             }
  449.             if(beta<=alpha) break;
  450.         }
  451.         return alpha;
  452.     }
  453.    
  454.     else if(level%2==1)
  455.     {
  456.         char BUFF[15][15];
  457.        
  458.         inv_board(A,BUFF);
  459.        
  460.         struct points P;
  461.        
  462.         P=seek_points(BUFF);
  463.        
  464.        
  465.        
  466.         for(int i=0;i<N;i++)
  467.         {
  468.             if(P.exi[i]==1)
  469.             {
  470.                 char buff[15][15];
  471.                
  472.                 copy_board(A,buff);
  473.                
  474.                 buff[P.coo_x[i]][P.coo_y[i]]=2;
  475.                
  476.                 int a;
  477.                
  478.                 a=analyse(buff,level+1,alpha,beta);
  479.                
  480.                 if(a<beta)
  481.                 {
  482.                     beta=a;
  483.                 }
  484.             }
  485.             if(beta<=alpha) break;
  486.         }
  487.         return beta;
  488.     }
  489. }
  490.  
  491. bool start() {
  492.     for(int i=0;i<15;i++)
  493.         for(int j=0;j<15;j++)
  494.             if(board[i][j]!=0) return 0;
  495.     return 1;
  496. }
  497.  
  498. Value pushout(int x,int y) {
  499.     Json::Value action;
  500.     action["x"]=x;
  501.     action["y"]=y;
  502.     return action;
  503. }
  504.  
  505. //图形界面写法请无视吧。。。
  506. int main()
  507. {
  508.     flag = false;
  509.     string str;
  510.     getline(cin, str);
  511.     Reader reader;
  512.     Value input;
  513.     reader.parse(str, input);
  514.     int turnID = input["responses"].size();
  515.     for (int i = 0; i < turnID; i++) {
  516.         placeAt(input["requests"][i]["x"].asInt(),input["requests"][i]["y"].asInt(),2);
  517.         placeAt(input["responses"][i]["x"].asInt(),input["responses"][i]["y"].asInt(),1);
  518.     }
  519.     placeAt(input["requests"][turnID]["x"].asInt(),input["requests"][turnID]["y"].asInt(),2);
  520.     Value ret;
  521.     int id = 2;
  522.     if(turnID>=2 && input["requests"][id]["x"].asInt()== -1 && input["requests"][id]["y"].asInt()==-1){
  523.         int rq = 1, rp = 0 , rp2 = 1;
  524.         placeAt(input["requests"][rq]["x"].asInt(), input["requests"][rq]["y"].asInt(),1);
  525.         placeAt(input["responses"][rp]["x"].asInt(), input["responses"][rp]["y"].asInt(),2);
  526.         placeAt(input["responses"][rp2]["x"].asInt(), input["responses"][rp2]["y"].asInt(),2);
  527.     }
  528.     if(start()) {
  529.         ret["response"]=pushout(0,0);
  530.     } else {
  531.         analyse(board,0,-1000000,1000000);
  532.         board[DECISION.coo_x][DECISION.coo_y]=1;
  533.         ret["response"]=pushout(DECISION.coo_x,DECISION.coo_y);
  534.     }
  535.     FastWriter writer;
  536.     cout<<writer.write(ret)<<endl;
  537.    
  538.     return 0;
  539. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement