五子棋AI算法也算是一個(gè)典型的游戲AI算法，一些棋類的AI算法都可以參考實(shí)現(xiàn)，下面是Java實(shí)現(xiàn)代碼
棋盤抽象接口
|
1
2
3
4
5
6
7
8
9
10
11
|
import java.util.List; public interface IChessboard { //取得棋盤最大橫坐標(biāo) public int getMaxX(); //最大縱坐標(biāo) public int getMaxY(); //取得當(dāng)前所有空白點(diǎn)，這些點(diǎn)才可以下棋 public List<Point> getFreePoints(); } |
棋子類實(shí)現(xiàn)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
//棋子類 public class Point { // 這了性能，設(shè)成公有 public int x; public int y; public int getX() { return x; } public Point setX(int x) { this.x = x; return this; } public int getY() { return y; } public Point setY(int y) { this.y = y; return this; } public Point(int x, int y) { this.x = x; this.y = y; } @Override public int hashCode() { return x + y; } @Override public boolean equals(Object obj) { if (this == obj) return true; Point other = (Point) obj; if (x != other.x) return false; if (y != other.y) return false; return true; } } |
玩家抽象接口
|
1
2
3
4
5
6
7
8
9
10
11
12
|
import java.util.List; public interface IPlayer { //下一步棋子，傳入對(duì)手已經(jīng)下的棋子集合 public void run(List<Point> enemyPoints, Point point); public boolean hasWin(); public void setChessboard(IChessboard chessboard); public List<Point> getMyPoints(); } |
玩家基礎(chǔ)抽象類
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
import java.util.ArrayList; import java.util.List; public abstract class BasePlayer implements IPlayer { //我已下的棋子 protected List<Point> myPoints = new ArrayList<Point>(200); //棋盤 protected IChessboard chessboard; //棋盤最大橫坐標(biāo)和縱標(biāo)， protected int maxX; protected int maxY; //所有空白棋子 protected List<Point> allFreePoints; @Override public final List<Point> getMyPoints() { return myPoints; } @Override public void setChessboard(IChessboard chessboard) { this.chessboard = chessboard; allFreePoints = chessboard.getFreePoints(); maxX = chessboard.getMaxX(); maxY = chessboard.getMaxY(); myPoints.clear(); } private final Point temp = new Point(0, 0); //我是否是否贏了 public final boolean hasWin(){ if(myPoints.size()<5){ return false; } Point point = myPoints.get(myPoints.size()-1); int count = 1; int x=point.getX(),y=point.getY(); //橫向-- temp.setX(x).setY(y); while (myPoints.contains(temp.setX(temp.getX()-1)) && temp.getX()>=0 && count<5) { count ++; } if(count>=5){ return true; } temp.setX(x).setY(y); while (myPoints.contains(temp.setX(temp.getX()+1)) && temp.getX()<maxX && count<5) { count ++; } if(count>=5){ return true; } //縱向| count = 1; temp.setX(x).setY(y); while (myPoints.contains(temp.setY(temp.getY()-1)) && temp.getY()>=0) { count ++; } if(count>=5){ return true; } temp.setX(x).setY(y); while (myPoints.contains(temp.setY(temp.getY()+1)) && temp.getY()<maxY && count<5) { count ++; } if(count>=5){ return true; } //正斜向 / count =1; temp.setX(x).setY(y); while (myPoints.contains(temp.setX(temp.getX()-1).setY(temp.getY()+1)) && temp.getX()>=0 && temp.getY()<maxY) { count ++; } if(count>=5){ return true; } temp.setX(x).setY(y); while (myPoints.contains(temp.setX(temp.getX()+1).setY(temp.getY()-1)) && temp.getX()<maxX && temp.getY()>=0 && count<6) { count ++; } if(count>=5){ return true; } //反斜 \ count = 1; temp.setX(x).setY(y); while (myPoints.contains(temp.setX(temp.getX()-1).setY(temp.getY()-1)) && temp.getX()>=0 && temp.getY()>=0) { count ++; } if(count>=5){ return true; } temp.setX(x).setY(y); while (myPoints.contains(temp.setX(temp.getX()+1).setY(temp.getY()+1)) && temp.getX()<maxX && temp.getY()<maxY && count<5) { count ++; } if(count>=5){ return true; } return false; } } |
電腦AI類實(shí)現(xiàn)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
|
import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; //算法核心類，算法的主體思想分三個(gè)步驟， //第一步：根據(jù)雙方的當(dāng)前的形勢(shì)循環(huán)地假設(shè)性的分別給自己和對(duì)方下一子（在某個(gè)范圍內(nèi)下子），并判斷此棋子能帶來(lái)的形勢(shì)上的變化，如能不能沖4，能不能形成我方或敵方雙3等， //第二步：根據(jù)上一步結(jié)果，組合每一步棋子所帶來(lái)的所有結(jié)果（如某一步棋子可能形成我方1個(gè)活3，1個(gè)沖4（我叫它半活4）等），包括敵方和我方的。 //第三步：根據(jù)用戶給的規(guī)則對(duì)上一步結(jié)果進(jìn)行排序，并選子（有進(jìn)攻形、防守形規(guī)則） public class BaseComputerAi extends BasePlayer { // 四個(gè)方向，橫- 、縱| 、正斜/ 、反斜\ private static final int HENG = 0; private static final int ZHONG = 1; private static final int ZHENG_XIE = 2; private static final int FAN_XIE = 3; //往前往后 private static final boolean FORWARD = true; private static final boolean BACKWARD = false; //標(biāo)示分析結(jié)果當(dāng)前點(diǎn)位是兩頭通（ALIVE）還是只有一頭通（HALF_ALIVE），封死的棋子分析過(guò)程自動(dòng)屏蔽，不作為待選棋子 private static final int ALIVE = 1; private static final int HALF_ALIVE = 0; //private static final int DEAD = -1; //計(jì)算范圍，太大的范圍會(huì)有性能問(wèn)題 private class CalcuteRange{ int xStart,yStart,xStop,yStop; private CalcuteRange(int xStart, int yStart, int xStop, int yStop) { this.xStart = xStart; this.yStart = yStart; this.xStop = xStop; this.yStop = yStop; } } //限定電腦計(jì)算范圍，如果整個(gè)棋盤計(jì)算，性能太差，目前是根據(jù)所有已下的棋子的邊界值加RANGE_STEP值形成，目前為1 private static final int RANGE_STEP = 1; CalcuteRange currentRange = new CalcuteRange(0, 0, 0, 0); private void initRange(List<Point> comuters, List<Point> humans){ currentRange.xStart = humans.get(0).getX()-RANGE_STEP; currentRange.yStart = humans.get(0).getY()-RANGE_STEP; currentRange.xStop = humans.get(0).getX()+RANGE_STEP; currentRange.yStop = humans.get(0).getY()+RANGE_STEP; for (Point point : humans) { if(point.getX()-RANGE_STEP<currentRange.xStart){ currentRange.xStart = point.getX()-RANGE_STEP; }else if(point.getX()+RANGE_STEP>currentRange.xStop){ currentRange.xStop = point.getX()+RANGE_STEP; } if(point.getY()-RANGE_STEP<currentRange.yStart){ currentRange.yStart = point.getY()-RANGE_STEP; }else if(point.getY()+RANGE_STEP>currentRange.yStop){ currentRange.yStop = point.getY()+RANGE_STEP; } } for (Point point : comuters) { if(point.getX()-RANGE_STEP<currentRange.xStart){ currentRange.xStart = point.getX()-RANGE_STEP; }else if(point.getX()+RANGE_STEP>currentRange.xStop){ currentRange.xStop = point.getX()+RANGE_STEP; } if(point.getY()-RANGE_STEP<currentRange.yStart){ currentRange.yStart = point.getY()-RANGE_STEP; }else if(point.getY()+RANGE_STEP>currentRange.yStop){ currentRange.yStop = point.getY()+RANGE_STEP; } } //如果范圍擴(kuò)大后超過(guò)了棋盤，則等于棋盤 currentRange.xStart=currentRange.xStart<0?0:currentRange.xStart; currentRange.yStart=currentRange.yStart<0?0:currentRange.yStart; currentRange.xStop=currentRange.xStop>=maxX?maxX-1:currentRange.xStop; currentRange.yStop=currentRange.yStop>=maxY?maxY-1:currentRange.yStop; } // 分析當(dāng)前形式的入口方法，分析總共分三個(gè)步驟，第三步驟可由子類干預(yù)以作難度控制 private Point doAnalysis(List<Point> comuters, List<Point> humans) { if(humans.size()==1){//第一步 return getFirstPoint(humans); } //初始化計(jì)算范圍 initRange(comuters, humans); //清除以前的結(jié)果 initAnalysisResults(); // 開(kāi)始分析，掃描所有空白點(diǎn)，形成第一次分析結(jié)果 Point bestPoint = doFirstAnalysis(comuters, humans); if(bestPoint!=null){ //System.out.println("這個(gè)棋子最重要，只能下這個(gè)棋子"); return bestPoint; } // 分析第一次結(jié)果，找到自己的最佳點(diǎn)位 bestPoint = doComputerSencondAnalysis(computerFirstResults,computerSencodResults); if(bestPoint!=null){ //System.out.println("快要贏了，就下這個(gè)棋子"); return bestPoint; } computerFirstResults.clear(); System.gc(); // 分析第一次結(jié)果，找到敵人的最佳點(diǎn)位 bestPoint = doHumanSencondAnalysis(humanFirstResults,humanSencodResults); if(bestPoint!=null){ //System.out.println("再不下這個(gè)棋子就輸了"); return bestPoint; } humanFirstResults.clear(); System.gc(); //沒(méi)找到絕殺點(diǎn)，第三次結(jié)果分析 return doThirdAnalysis(); } //下第一步棋子，不需要復(fù)雜的計(jì)算，根據(jù)人類第一步棋子X(jué)值減1完成 private Point getFirstPoint(List<Point> humans) { Point point = humans.get(0); if(point.getX()==0 || point.getY()==0 || point.getX()==maxX && point.getY()==maxY) return new Point(maxX/2, maxY/2); else{ return new Point(point.getX()-1,point.getY()); } } // private int debugx,debugy;//用于DEBUG // 開(kāi)始分析，掃描所有空白點(diǎn)，形成第一次分析結(jié)果 private Point doFirstAnalysis(List<Point> comuters, List<Point> humans){ int size = allFreePoints.size(); Point computerPoint = null; Point humanPoint = null; int x,y; FirstAnalysisResult firstAnalysisResult; for (int i = 0; i < size; i++) { computerPoint = allFreePoints.get(i); //先把X、Y坐標(biāo)記下來(lái)，因?yàn)樵诜治鲞^(guò)程中會(huì)改變?cè)瓉?lái)的對(duì)象 x = computerPoint.getX(); y = computerPoint.getY(); if(x<currentRange.xStart || x>currentRange.xStop || y<currentRange.yStart || y>currentRange.yStop){ continue; } // if(x==debugx && y==debugy){ // System.out.println("sssssssssssss"); // } //嘗試在此位置上下一個(gè)棋子，并分析在“橫向”這個(gè)方向上我方可形成的狀態(tài)，如活4，活3，半活4，活2等所有狀態(tài) firstAnalysisResult = tryAndCountResult(comuters,humans, computerPoint, HENG); computerPoint.setX(x).setY(y);//回復(fù)點(diǎn)位的原值，以供下次分析 if(firstAnalysisResult!=null){//無(wú)返回結(jié)果此方向上不可能達(dá)到五個(gè)棋子， if(firstAnalysisResult.count==5)//等于5表示在此點(diǎn)上下棋子即可連成5個(gè)，勝利了，不再往下進(jìn)行分析 return computerPoint; //記錄第一次分析結(jié)果 addToFirstAnalysisResult(firstAnalysisResult,computerFirstResults); } //在“縱向”這個(gè)方向上重復(fù)上面的步驟 firstAnalysisResult = tryAndCountResult(comuters,humans, computerPoint, ZHONG); computerPoint.setX(x).setY(y); if(firstAnalysisResult!=null){//死棋，不下 if(firstAnalysisResult.count==5) return computerPoint; addToFirstAnalysisResult(firstAnalysisResult,computerFirstResults); } //正斜向 firstAnalysisResult = tryAndCountResult(comuters,humans, computerPoint, ZHENG_XIE); computerPoint.setX(x).setY(y); if(firstAnalysisResult!=null){//死棋，不下 if(firstAnalysisResult.count==5) return computerPoint; addToFirstAnalysisResult(firstAnalysisResult,computerFirstResults); } //反斜向 firstAnalysisResult = tryAndCountResult(comuters,humans, computerPoint, FAN_XIE); computerPoint.setX(x).setY(y); if(firstAnalysisResult!=null){//死棋，不下 if(firstAnalysisResult.count==5) return computerPoint; addToFirstAnalysisResult(firstAnalysisResult,computerFirstResults); } //在“橫向”上分析此棋子可在敵方形成如何狀態(tài)，如敵方的活3、半活4等 firstAnalysisResult = tryAndCountResult(humans,comuters, computerPoint, HENG); computerPoint.setX(x).setY(y); if(firstAnalysisResult!=null){//死棋，不下 if(firstAnalysisResult.count==5) humanPoint = computerPoint; addToFirstAnalysisResult(firstAnalysisResult,humanFirstResults); } //“縱向” firstAnalysisResult = tryAndCountResult(humans,comuters, computerPoint, ZHONG); computerPoint.setX(x).setY(y); if(firstAnalysisResult!=null){//死棋，不下 if(firstAnalysisResult.count==5) humanPoint = computerPoint; addToFirstAnalysisResult(firstAnalysisResult,humanFirstResults); } //“正斜” firstAnalysisResult = tryAndCountResult(humans,comuters, computerPoint, ZHENG_XIE); computerPoint.setX(x).setY(y); if(firstAnalysisResult!=null){//死棋，不下 if(firstAnalysisResult.count==5) humanPoint = computerPoint; addToFirstAnalysisResult(firstAnalysisResult,humanFirstResults); } //“反斜” firstAnalysisResult = tryAndCountResult(humans,comuters, computerPoint, FAN_XIE); computerPoint.setX(x).setY(y); if(firstAnalysisResult!=null){//死棋，不下 if(firstAnalysisResult.count==5) humanPoint = computerPoint; addToFirstAnalysisResult(firstAnalysisResult,humanFirstResults); } } //如果沒(méi)有絕殺棋子，第一次分析不需要返回結(jié)果 return humanPoint; } //第二次分析，分析第一次形成的結(jié)果，第一次分析結(jié)果會(huì)把一步棋在四個(gè)方向上可形成的結(jié)果生成最多四個(gè)FirstAnalysisResult對(duì)象（敵我各四） //這里要把這四個(gè)對(duì)象組合成一個(gè)SencondAnalysisResult對(duì)象， private Point doComputerSencondAnalysis(Map<Point,List<FirstAnalysisResult>> firstResults,List<SencondAnalysisResult> sencodResults) { List<FirstAnalysisResult> list = null; SencondAnalysisResult sr = null; for (Point p : firstResults.keySet()) { sr = new SencondAnalysisResult(p); list = firstResults.get(p); for (FirstAnalysisResult result : list) { if(result.count==4){ if(result.aliveState==ALIVE){//經(jīng)過(guò)前面的過(guò)濾，雙方都排除了絕殺棋，有活4就下這一步了，再下一步就贏了 return result.point;//如果有絕殺，第一輪已返回，在此輪活4已經(jīng)是好的棋子，直接返回，不再往下分析 }else{ sr.halfAlive4 ++; computer4HalfAlives.add(sr); } }else if(result.count==3){ if(result.aliveState==ALIVE){ sr.alive3++; if(sr.alive3==1){ computer3Alives.add(sr); }else{ computerDouble3Alives.add(sr); } }else{ sr.halfAlive3++; computer3HalfAlives.add(sr); } }else{//半活2在第一階段已被排除，不再處理 sr.alive2++; if(sr.alive2==1){ computer2Alives.add(sr); }else{ computerDouble2Alives.add(sr); } } } sencodResults.add(sr); } //沒(méi)有找到活4 return null; } //這個(gè)方法和上面的基本一樣，但為了性能，少作幾次判斷，將人類和電腦的分開(kāi)了 private Point doHumanSencondAnalysis(Map<Point,List<FirstAnalysisResult>> firstResults,List<SencondAnalysisResult> sencodResults) { List<FirstAnalysisResult> list = null; SencondAnalysisResult sr = null; for (Point p : firstResults.keySet()) { sr = new SencondAnalysisResult(p); list = firstResults.get(p); for (FirstAnalysisResult result : list) { if(result.count==4){ if(result.aliveState==ALIVE){ human4Alives.add(sr); }else{ sr.halfAlive4 ++; human4HalfAlives.add(sr); } }else if(result.count==3){ if(result.aliveState==ALIVE){ sr.alive3++; if(sr.alive3==1){ human3Alives.add(sr); }else{ humanDouble3Alives.add(sr); } }else{ sr.halfAlive3++; human3HalfAlives.add(sr); } }else{ sr.alive2++; if(sr.alive2==1){ human2Alives.add(sr); }else{ humanDouble2Alives.add(sr); } } } sencodResults.add(sr); } //沒(méi)有找到活4 return null; } private void sleep(int miniSecond){ try { Thread.sleep(miniSecond); } catch (InterruptedException e) { } } //第三次分析，雙方都不可以制造活4，找雙活3棋子，不行就找半活4，再不行就找單活3，雙活2 private Point doThirdAnalysis() { if(!computer4HalfAlives.isEmpty()){ return computer4HalfAlives.get(0).point; } System.gc(); sleep(300); Collections.sort(computerSencodResults); System.gc(); //即將單活4，且我沒(méi)有半活4以上的，只能堵 Point mostBest = getBestPoint(human4Alives, computerSencodResults); if(mostBest!=null) return mostBest; Collections.sort(humanSencodResults); System.gc(); mostBest = getBestPoint(); if(mostBest!=null) return mostBest; //拿出各自排第一的，誰(shuí)好就下誰(shuí) return computerSencodResults.get(0).point; } //子類實(shí)現(xiàn)這個(gè)方法，并改變其順序可以實(shí)現(xiàn)防守為主還是猛攻 protected Point getBestPoint(){ //即將單活4，且我沒(méi)有半活4以上的，只能堵 Point mostBest = getBestPoint(computerDouble3Alives, humanSencodResults); if(mostBest!=null) return mostBest; mostBest = getBestPoint(computer3Alives, humanSencodResults); if(mostBest!=null) return mostBest; mostBest = getBestPoint(humanDouble3Alives, computerSencodResults); if(mostBest!=null) return mostBest; mostBest = getBestPoint(human3Alives, computerSencodResults); if(mostBest!=null) return mostBest; mostBest = getBestPoint(computerDouble2Alives, humanSencodResults); if(mostBest!=null) return mostBest; mostBest = getBestPoint(computer2Alives, humanSencodResults); if(mostBest!=null) return mostBest; mostBest = getBestPoint(computer3HalfAlives, humanSencodResults); if(mostBest!=null) return mostBest; mostBest = getBestPoint(human4HalfAlives, computerSencodResults); if(mostBest!=null) return mostBest; mostBest = getBestPoint(humanDouble2Alives, computerSencodResults); if(mostBest!=null) return mostBest; mostBest = getBestPoint(human2Alives, computerSencodResults); if(mostBest!=null) return mostBest; mostBest = getBestPoint(human3HalfAlives, computerSencodResults); return mostBest; } //第三次分析的最后一步，第二次結(jié)果已經(jīng)過(guò)排序，在此可以從前面選出最好的棋子 protected Point getBestPoint(List<SencondAnalysisResult> myBest,List<SencondAnalysisResult> yourSencodResults){ if(!myBest.isEmpty()){ if(myBest.size()>1){ for (SencondAnalysisResult your : yourSencodResults) { if(myBest.contains(your)){ return your.point; } } return myBest.get(0).point; }else{ return myBest.get(0).point; } } return null; } //第一次分析結(jié)果 private final Map<Point,List<FirstAnalysisResult>> computerFirstResults = new HashMap<Point,List<FirstAnalysisResult>>(); private final Map<Point,List<FirstAnalysisResult>> humanFirstResults = new HashMap<Point,List<FirstAnalysisResult>>(); //第二次總結(jié)果 protected final List<SencondAnalysisResult> computerSencodResults = new ArrayList<SencondAnalysisResult>(); protected final List<SencondAnalysisResult> humanSencodResults = new ArrayList<SencondAnalysisResult>(); //第二次分結(jié)果，電腦 protected final List<SencondAnalysisResult> computer4HalfAlives = new ArrayList<SencondAnalysisResult>(2); protected final List<SencondAnalysisResult> computerDouble3Alives = new ArrayList<SencondAnalysisResult>(4); protected final List<SencondAnalysisResult> computer3Alives = new ArrayList<SencondAnalysisResult>(5); protected final List<SencondAnalysisResult> computerDouble2Alives = new ArrayList<SencondAnalysisResult>(); protected final List<SencondAnalysisResult> computer2Alives = new ArrayList<SencondAnalysisResult>(); protected final List<SencondAnalysisResult> computer3HalfAlives = new ArrayList<SencondAnalysisResult>(); //第二次分結(jié)果，人類 protected final List<SencondAnalysisResult> human4Alives = new ArrayList<SencondAnalysisResult>(2); protected final List<SencondAnalysisResult> human4HalfAlives = new ArrayList<SencondAnalysisResult>(5); protected final List<SencondAnalysisResult> humanDouble3Alives = new ArrayList<SencondAnalysisResult>(2); protected final List<SencondAnalysisResult> human3Alives = new ArrayList<SencondAnalysisResult>(10); protected final List<SencondAnalysisResult> humanDouble2Alives = new ArrayList<SencondAnalysisResult>(3); protected final List<SencondAnalysisResult> human2Alives = new ArrayList<SencondAnalysisResult>(); protected final List<SencondAnalysisResult> human3HalfAlives = new ArrayList<SencondAnalysisResult>(); //第一次分析前清空上一步棋子的分析結(jié)果 private void initAnalysisResults(){ computerFirstResults.clear(); humanFirstResults.clear(); //第二次總結(jié)果 computerSencodResults.clear(); humanSencodResults.clear(); //第二次分結(jié)果 computer4HalfAlives.clear(); computerDouble3Alives.clear(); computer3Alives.clear(); computerDouble2Alives.clear(); computer2Alives.clear(); computer3HalfAlives.clear(); //第二次分結(jié)果，人類 human4Alives.clear(); human4HalfAlives.clear(); humanDouble3Alives.clear(); human3Alives.clear(); humanDouble2Alives.clear(); human2Alives.clear(); human3HalfAlives.clear(); System.gc(); } //加入到第一次分析結(jié)果中 private void addToFirstAnalysisResult(FirstAnalysisResult result,Map<Point,List<FirstAnalysisResult>> dest){ if(dest.containsKey(result.point)){ dest.get(result.point).add(result); }else{ List<FirstAnalysisResult> list = new ArrayList<FirstAnalysisResult>(1); list.add(result); dest.put(result.point, list); } } //第一次分析結(jié)果類 private class FirstAnalysisResult{ //連續(xù)數(shù) int count; //點(diǎn)位 Point point; //方向 int direction; //狀態(tài) int aliveState; private FirstAnalysisResult(int count, Point point, int direction) { this(count, point, direction, ALIVE); } private FirstAnalysisResult(int count, Point point, int direction,int aliveState) { this.count = count; this.point = point; this.direction = direction; this.aliveState = aliveState; } private FirstAnalysisResult init(Point point,int direction,int aliveState){ this.count = 1; this.point = point; this.direction = direction; this.aliveState = aliveState; return this; } private FirstAnalysisResult cloneMe(){ return new FirstAnalysisResult(count, point, direction,aliveState); } } //第二次分析結(jié)果類 class SencondAnalysisResult implements Comparable<SencondAnalysisResult>{ int alive4 = 0; //活3數(shù)量 int alive3 = 0; //半活4，一頭封的 int halfAlive4 = 0; //半活3，一頭封的 int halfAlive3 = 0; //活2數(shù)量 int alive2 = 0; //點(diǎn)位 Point point; @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + ((point == null) ? 0 : point.hashCode()); return result; } @Override public boolean equals(Object obj) { SencondAnalysisResult other = (SencondAnalysisResult) obj; if (point == null) { if (other.point != null) return false; } else if (!point.equals(other.point)) return false; return true; } private SencondAnalysisResult(Point point) { this.point = point; } //第三次分析時(shí)，對(duì)第二次分析結(jié)果進(jìn)行排序，此為排序回調(diào)函數(shù) @Override public int compareTo(SencondAnalysisResult another) { return compareTowResult(this, another); } } //返加-1則第一個(gè)參數(shù)優(yōu)先，1則第二個(gè)參數(shù)優(yōu)先，0則按原來(lái)順序 private int compareTowResult(SencondAnalysisResult oneResult,SencondAnalysisResult another){ if(oneResult.alive4>another.alive4){ return -1; } if(oneResult.alive4<another.alive4){ return 1; } if(oneResult.halfAlive4>another.halfAlive4){ return -1; } if(oneResult.halfAlive4<another.halfAlive4){ return 1; } if(oneResult.alive3>another.alive3){ return -1; } if(oneResult.alive3<another.alive3){ return 1; } if(oneResult.alive2>another.alive2){ return -1; } if(oneResult.alive2<another.alive2){ return 1; } if(oneResult.halfAlive3>another.halfAlive3){ return -1; } if(oneResult.halfAlive3>another.halfAlive3){ return 1; } return 0; } //一個(gè)臨時(shí)對(duì)象，供第一次分析時(shí)臨時(shí)存放分析結(jié)果使用，如果分析出有活1以上（不含）的結(jié)果，則調(diào)用其cloneMe方法獲得結(jié)果，否則拋棄此結(jié)果 private final FirstAnalysisResult far = new FirstAnalysisResult(1, null, HENG); // 分析如果在當(dāng)前位下一子，會(huì)形成某個(gè)方向上多少個(gè)子，參數(shù)：當(dāng)前己方已下的所有點(diǎn)，當(dāng)前要假設(shè)的點(diǎn)，需要判斷的方向 private FirstAnalysisResult tryAndCountResult(List<Point> myPoints,List<Point> enemyPoints, Point point,int direction) { int x = point.getX(); int y = point.getY(); FirstAnalysisResult fr = null; int maxCountOnThisDirection = maxCountOnThisDirection(point, enemyPoints, direction, 1); if(maxCountOnThisDirection<5){ //無(wú)意義的棋子 return null;//此方向不足五個(gè)空位，已排除己方已下的棋子 }else if(maxCountOnThisDirection==5){ //半死狀態(tài)，當(dāng)是一頭通 fr = far.init(point, direction,HALF_ALIVE); }else{ //兩頭皆通 fr = far.init(point, direction,ALIVE); } //在前和后的方向上計(jì)算一次 countPoint(myPoints,enemyPoints,point.setX(x).setY(y),fr,direction,FORWARD); countPoint(myPoints,enemyPoints,point.setX(x).setY(y),fr,direction,BACKWARD); if(fr.count<=1 || (fr.count==2 && fr.aliveState==HALF_ALIVE)){//活1，半活2及其以下結(jié)果，拋棄 return null; } //返回復(fù)制的結(jié)果 return fr.cloneMe(); } //棋子出了墻 private boolean isOutSideOfWall(Point point,int direction){ if(direction==HENG){ return point.getX()<0 || point.getX()>=maxX;//最大的X和Y值均在墻外所以用等號(hào) }else if(direction==ZHONG){ return point.getY()<0 || point.getY()>=maxY; }else{//這里可能有問(wèn)題 return point.getX()<0 || point.getY()<0 || point.getX()>=maxX || point.getY()>=maxY; } } private Point pointToNext(Point point,int direction,boolean forward){ switch (direction) { case HENG: if(forward) point.x++; else point.x--; break; case ZHONG: if(forward) point.y++; else point.y--; break; case ZHENG_XIE: if(forward){ point.x++; point.y--; }else{ point.x--; point.y++; } break; case FAN_XIE: if(forward){ point.x++; point.y++; }else{ point.x--; point.y--; } break; } return point; } //在某個(gè)方向（八個(gè)中的一個(gè)）可下多少棋子，這個(gè)方法是第一分析中的核心方法 private void countPoint(List<Point> myPoints, List<Point> enemyPoints, Point point, FirstAnalysisResult fr,int direction,boolean forward) { if(myPoints.contains(pointToNext(point,direction,forward))){ fr.count ++; if(myPoints.contains(pointToNext(point,direction,forward))){ fr.count ++; if(myPoints.contains(pointToNext(point,direction,forward))){ fr.count ++; if(myPoints.contains(pointToNext(point,direction,forward))){ fr.count ++; }else if(enemyPoints.contains(point) || isOutSideOfWall(point,direction)){ fr.aliveState=HALF_ALIVE; } }else if(enemyPoints.contains(point) || isOutSideOfWall(point,direction)){ fr.aliveState=HALF_ALIVE; } }else if(enemyPoints.contains(point) || isOutSideOfWall(point,direction)){ fr.aliveState=HALF_ALIVE; } }else if(enemyPoints.contains(point) || isOutSideOfWall(point,direction)){ fr.aliveState=HALF_ALIVE; } } //在某個(gè)方向上是否還能下到滿五個(gè)棋子 private int maxCountOnThisDirection(Point point,List<Point> enemyPoints,int direction,int count){ int x=point.getX(),y=point.getY(); switch (direction) { //橫向 case HENG: while (!enemyPoints.contains(point.setX(point.getX()-1)) && point.getX()>=0 && count<6) { count ++; } point.setX(x); while (!enemyPoints.contains(point.setX(point.getX()+1)) && point.getX()<maxX && count<6) { count ++; } break; //縱向 case ZHONG: while (!enemyPoints.contains(point.setY(point.getY()-1)) && point.getY()>=0) { count ++; } point.setY(y); while (!enemyPoints.contains(point.setY(point.getY()+1)) && point.getY()<maxY && count<6) { count ++; } break; //正斜向 / case ZHENG_XIE: while (!enemyPoints.contains(point.setX(point.getX()-1).setY(point.getY()+1)) && point.getX()>=0 && point.getY()<maxY) { count ++; } point.setX(x).setY(y); while (!enemyPoints.contains(point.setX(point.getX()+1).setY(point.getY()-1)) && point.getX()<maxX && point.getY()>=0 && count<6) { count ++; } break; //反斜 / case FAN_XIE: while (!enemyPoints.contains(point.setX(point.getX()-1).setY(point.getY()-1)) && point.getX()>=0 && point.getY()>=0) { count ++; } point.setX(x).setY(y); while (!enemyPoints.contains(point.setX(point.getX()+1).setY(point.getY()+1)) && point.getX()<maxX && point.getY()<maxY && count<6) { count ++; } break; } return count; } //下棋子，對(duì)外接口 @Override public void run(List<Point> humans,Point p) { //把人類下的最后一步棋子去除 allFreePoints.remove(humans.get(humans.size()-1)); //電腦可以下的一步棋子 Point result = doAnalysis(myPoints, humans); //去除電腦下的棋子 allFreePoints.remove(result); //加入到電腦棋子中，下棋了 myPoints.add(result); } } |
人類玩家實(shí)現(xiàn)起來(lái)就非常簡(jiǎn)單
|
1
2
3
4
5
6
7
8
9
10
|
import java.util.List; public class HumanPlayer extends BasePlayer { @Override public void run(List<Point> enemyPoints,Point p) { getMyPoints().add(p); allFreePoints.remove(p); } } |
總結(jié)：雖然是Java寫的但算法已被抽象可以方便的修改成各種平臺(tái)的實(shí)現(xiàn)。
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：https://blog.csdn.net/xiaoyu714543065/article/details/8746876
