• API
• FAQ
• Tools
• Archive
SHARE
TWEET

Untitled

a guest May 25th, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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);
512.     Value 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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top