本文共 23823 字，大约阅读时间需要 79 分钟。

五子棋AI算法 Java实现（转载）

原始链接：

2013-04-01 15:42:33  阅读数 9845更多

分类专栏：  

五子棋AI算法 也算是一个典型的游戏AI算法，一些棋类的AI算法都可以参考实现，下面是Java实现代码

棋盘抽象接口

[java] 

1. import java.util.List;  
2.   
3.   
4. public interface IChessboard {  
5.     //取得棋盘最大横坐标  
6.     public int getMaxX();  
7.     //最大纵坐标  
8.     public int getMaxY();  
9.     //取得当前所有空白点，这些点才可以下棋  
10.     public List<Point> getFreePoints();  
11. }  

棋子类实现

[java] 

1. //棋子类  
2. public class Point {  
3.     // 这了性能，设成公有  
4.     public int x;  
5.     public int y;  
6.       
7.   
8.     public int getX() {  
9.         return x;  
10.     }  
11.   
12.     public Point setX(int x) {  
13.         this.x = x;  
14.         return this;  
15.     }  
16.   
17.     public int getY() {  
18.         return y;  
19.     }  
20.   
21.     public Point setY(int y) {  
22.         this.y = y;  
23.         return this;  
24.     }  
25.   
26.     public Point(int x, int y) {  
27.         this.x = x;  
28.         this.y = y;  
29.     }  
30.   
31.   
32.     @Override  
33.     public int hashCode() {  
34.         return x + y;  
35.     }  
36.   
37.     @Override  
38.     public boolean equals(Object obj) {  
39.         if (this == obj)  
40.             return true;  
41.         Point other = (Point) obj;  
42.         if (x != other.x)  
43.             return false;  
44.         if (y != other.y)  
45.             return false;  
46.         return true;  
47.     }  
48.   
49. }  

玩家抽象接口[java] 

1. import java.util.List;  
2.   
3. public interface IPlayer {  
4.     //下一步棋子，传入对手已经下的棋子集合  
5.     public void run(List<Point> enemyPoints, Point point);  
6.   
7.     public boolean hasWin();  
8.       
9.     public void setChessboard(IChessboard chessboard);  
10.       
11.     public List<Point> getMyPoints();  
12. }  

玩家基础抽象类

[java] 

1. import java.util.ArrayList;  
2. import java.util.List;  
3.   
4. public abstract class BasePlayer implements IPlayer {  
5.     //我已下的棋子  
6.     protected List<Point> myPoints = new ArrayList<Point>(200);  
7.     //棋盘  
8.     protected IChessboard chessboard;  
9.     //棋盘最大横坐标和纵标，  
10.     protected int maxX;  
11.     protected int maxY;  
12.       
13.     //所有空白棋子  
14.     protected List<Point> allFreePoints;  
15.   
16.     @Override  
17.     public final List<Point> getMyPoints() {  
18.         return myPoints;  
19.     }  
20.   
21.     @Override  
22.     public void setChessboard(IChessboard chessboard) {  
23.         this.chessboard = chessboard;  
24.         allFreePoints = chessboard.getFreePoints();  
25.         maxX = chessboard.getMaxX();  
26.         maxY = chessboard.getMaxY();  
27.         myPoints.clear();  
28.     }  
29.       
30.     private final Point temp = new Point(0, 0);  
31.     //我是否是否赢了  
32.     public final boolean hasWin(){  
33.         if(myPoints.size()<5){  
34.             return false;  
35.         }  
36.         Point point = myPoints.get(myPoints.size()-1);  
37.         int count = 1;  
38.         int x=point.getX(),y=point.getY();  
39.         //横向--  
40.         temp.setX(x).setY(y);  
41.         while (myPoints.contains(temp.setX(temp.getX()-1)) && temp.getX()>=0 && count<5) {  
42.             count ++;  
43.         }  
44.         if(count>=5){  
45.             return true;  
46.         }  
47.         temp.setX(x).setY(y);  
48.         while (myPoints.contains(temp.setX(temp.getX()+1)) && temp.getX()<maxX && count<5) {  
49.             count ++;  
50.         }  
51.         if(count>=5){  
52.             return true;  
53.         }  
54.         //纵向|  
55.         count = 1;  
56.         temp.setX(x).setY(y);  
57.         while (myPoints.contains(temp.setY(temp.getY()-1)) && temp.getY()>=0) {  
58.             count ++;  
59.         }  
60.         if(count>=5){  
61.             return true;  
62.         }  
63.         temp.setX(x).setY(y);  
64.         while (myPoints.contains(temp.setY(temp.getY()+1)) && temp.getY()<maxY && count<5) {  
65.             count ++;  
66.         }  
67.         if(count>=5){  
68.             return true;  
69.         }  
70.         //正斜向 /  
71.         count =1;  
72.         temp.setX(x).setY(y);  
73.         while (myPoints.contains(temp.setX(temp.getX()-1).setY(temp.getY()+1)) && temp.getX()>=0 && temp.getY()<maxY) {  
74.             count ++;  
75.         }  
76.         if(count>=5){  
77.             return true;  
78.         }  
79.         temp.setX(x).setY(y);  
80.         while (myPoints.contains(temp.setX(temp.getX()+1).setY(temp.getY()-1)) && temp.getX()<maxX && temp.getY()>=0 && count<6) {  
81.             count ++;  
82.         }  
83.         if(count>=5){  
84.             return true;  
85.         }  
86.         //反斜 \  
87.         count = 1;  
88.         temp.setX(x).setY(y);  
89.         while (myPoints.contains(temp.setX(temp.getX()-1).setY(temp.getY()-1)) && temp.getX()>=0 && temp.getY()>=0) {  
90.             count ++;  
91.         }  
92.         if(count>=5){  
93.             return true;  
94.         }  
95.         temp.setX(x).setY(y);  
96.         while (myPoints.contains(temp.setX(temp.getX()+1).setY(temp.getY()+1)) && temp.getX()<maxX && temp.getY()<maxY && count<5) {  
97.             count ++;  
98.         }  
99.         if(count>=5){  
100.             return true;  
101.         }  
102.         return false;  
103.     }  
104. }  

电脑AI类实现

[java] 

1. import java.util.ArrayList;  
2. import java.util.Collections;  
3. import java.util.HashMap;  
4. import java.util.List;  
5. import java.util.Map;  
6.   
7. //算法核心类，算法的主体思想分三个步骤，  
8. //第一步：根据双方的当前的形势循环地假设性的分别给自己和对方下一子（在某个范围内下子），并判断此棋子能带来的形势上的变化，如能不能冲4，能不能形成我方或敌方双3等，  
9. //第二步：根据上一步结果，组合每一步棋子所带来的所有结果（如某一步棋子可能形成我方1个活3，1个冲4（我叫它半活4）等），包括敌方和我方的。  
10. //第三步：根据用户给的规则对上一步结果进行排序，并选子（有进攻形、防守形规则）  
11. public class BaseComputerAi extends BasePlayer {  
12.   
13.     // 四个方向，横- 、纵| 、正斜/ 、反斜\  
14.     private static final int HENG = 0;  
15.     private static final int ZHONG = 1;  
16.     private static final int ZHENG_XIE = 2;  
17.     private static final int FAN_XIE = 3;  
18.     //往前往后  
19.     private static final boolean FORWARD = true;  
20.     private static final boolean BACKWARD = false;  
21.       
22.       
23.       
24.     //标示分析结果当前点位是两头通（ALIVE）还是只有一头通（HALF_ALIVE），封死的棋子分析过程自动屏蔽，不作为待选棋子  
25.     private static final int ALIVE = 1;  
26.     private static final int HALF_ALIVE = 0;  
27.     //private static final int DEAD = -1;  
28.       
29.     //计算范围，太大的范围会有性能问题  
30.     private class CalcuteRange{  
31.         int xStart,yStart,xStop,yStop;  
32.         private CalcuteRange(int xStart, int yStart, int xStop, int yStop) {  
33.             this.xStart = xStart;  
34.             this.yStart = yStart;  
35.             this.xStop = xStop;  
36.             this.yStop = yStop;  
37.         }  
38.     }  
39.       
40.       
41.     //限定电脑计算范围，如果整个棋盘计算，性能太差，目前是根据所有已下的棋子的边界值加RANGE_STEP值形成，目前为1  
42.     private static final int RANGE_STEP = 1;  
43.     CalcuteRange currentRange = new CalcuteRange(0, 0, 0, 0);  
44.     private void initRange(List<Point> comuters, List<Point> humans){  
45.         currentRange.xStart = humans.get(0).getX()-RANGE_STEP;  
46.         currentRange.yStart = humans.get(0).getY()-RANGE_STEP;  
47.         currentRange.xStop = humans.get(0).getX()+RANGE_STEP;  
48.         currentRange.yStop = humans.get(0).getY()+RANGE_STEP;  
49.         for (Point point : humans) {  
50.             if(point.getX()-RANGE_STEP<currentRange.xStart){  
51.                 currentRange.xStart = point.getX()-RANGE_STEP;  
52.             }else if(point.getX()+RANGE_STEP>currentRange.xStop){  
53.                 currentRange.xStop = point.getX()+RANGE_STEP;  
54.             }  
55.             if(point.getY()-RANGE_STEP<currentRange.yStart){  
56.                 currentRange.yStart = point.getY()-RANGE_STEP;  
57.             }else if(point.getY()+RANGE_STEP>currentRange.yStop){  
58.                 currentRange.yStop = point.getY()+RANGE_STEP;  
59.             }  
60.         }  
61.         for (Point point : comuters) {  
62.             if(point.getX()-RANGE_STEP<currentRange.xStart){  
63.                 currentRange.xStart = point.getX()-RANGE_STEP;  
64.             }else if(point.getX()+RANGE_STEP>currentRange.xStop){  
65.                 currentRange.xStop = point.getX()+RANGE_STEP;  
66.             }  
67.             if(point.getY()-RANGE_STEP<currentRange.yStart){  
68.                 currentRange.yStart = point.getY()-RANGE_STEP;  
69.             }else if(point.getY()+RANGE_STEP>currentRange.yStop){  
70.                 currentRange.yStop = point.getY()+RANGE_STEP;  
71.             }  
72.         }  
73.           
74.         //如果范围扩大后超过了棋盘，则等于棋盘  
75.         currentRange.xStart=currentRange.xStart<0?0:currentRange.xStart;  
76.         currentRange.yStart=currentRange.yStart<0?0:currentRange.yStart;  
77.         currentRange.xStop=currentRange.xStop>=maxX?maxX-1:currentRange.xStop;  
78.         currentRange.yStop=currentRange.yStop>=maxY?maxY-1:currentRange.yStop;  
79.     }  
80.   
81.     // 分析当前形式的入口方法，分析总共分三个步骤，第三步骤可由子类干预以作难度控制  
82.     private Point doAnalysis(List<Point> comuters, List<Point> humans) {  
83.         if(humans.size()==1){//第一步  
84.             return getFirstPoint(humans);  
85.         }  
86.           
87.         //初始化计算范围  
88.         initRange(comuters, humans);  
89.           
90.         //清除以前的结果  
91.         initAnalysisResults();  
92.         // 开始分析，扫描所有空白点，形成第一次分析结果  
93.         Point bestPoint = doFirstAnalysis(comuters, humans);  
94.         if(bestPoint!=null){  
95.             //System.out.println("这个棋子最重要，只能下这个棋子");  
96.             return bestPoint;  
97.         }  
98.         // 分析第一次结果，找到自己的最佳点位  
99.         bestPoint = doComputerSencondAnalysis(computerFirstResults,computerSencodResults);  
100.         if(bestPoint!=null){  
101.             //System.out.println("快要赢了，就下这个棋子");  
102.             return bestPoint;  
103.         }  
104.         computerFirstResults.clear();  
105.         System.gc();  
106.         // 分析第一次结果，找到敌人的最佳点位  
107.         bestPoint = doHumanSencondAnalysis(humanFirstResults,humanSencodResults);  
108.         if(bestPoint!=null){  
109.             //System.out.println("再不下这个棋子就输了");  
110.             return bestPoint;  
111.         }  
112.         humanFirstResults.clear();  
113.         System.gc();  
114.         //没找到绝杀点，第三次结果分析  
115.         return doThirdAnalysis();  
116.     }  
117.       
118.   
119.     //下第一步棋子，不需要复杂的计算，根据人类第一步棋子X值减1完成  
120.     private Point getFirstPoint(List<Point> humans) {  
121.         Point point = humans.get(0);  
122.         if(point.getX()==0 || point.getY()==0 || point.getX()==maxX && point.getY()==maxY)  
123.             return new Point(maxX/2, maxY/2);  
124.         else{  
125.             return new Point(point.getX()-1,point.getY());  
126.         }  
127.     }  
128.   
129. //  private int debugx,debugy;//用于DEBUG  
130.   
131.     // 开始分析，扫描所有空白点，形成第一次分析结果  
132.     private Point doFirstAnalysis(List<Point> comuters, List<Point> humans){  
133.         int size = allFreePoints.size();  
134.         Point computerPoint = null;  
135.         Point humanPoint = null;  
136.         int x,y;  
137.         FirstAnalysisResult firstAnalysisResult;  
138.         for (int i = 0; i < size; i++) {  
139.             computerPoint = allFreePoints.get(i);  
140.             //先把X、Y坐标记下来，因为在分析过程中会改变原来的对象  
141.             x = computerPoint.getX();  
142.             y = computerPoint.getY();  
143.             if(x<currentRange.xStart || x>currentRange.xStop || y<currentRange.yStart || y>currentRange.yStop){  
144.                 continue;  
145.             }  
146.               
147. //          if(x==debugx && y==debugy){  
148. //              System.out.println("sssssssssssss");  
149. //          }  
150.               
151.             //尝试在此位置上下一个棋子，并分析在“横向”这个方向上我方可形成的状态，如活4，活3，半活4，活2等所有状态  
152.             firstAnalysisResult = tryAndCountResult(comuters,humans, computerPoint, HENG);  
153.             computerPoint.setX(x).setY(y);//回复点位的原值，以供下次分析  
154.             if(firstAnalysisResult!=null){//无返回结果此方向上不可能达到五个棋子，  
155.                 if(firstAnalysisResult.count==5)//等于5表示在此点上下棋子即可连成5个，胜利了，不再往下进行分析  
156.                     return computerPoint;  
157.                 //记录第一次分析结果  
158.                 addToFirstAnalysisResult(firstAnalysisResult,computerFirstResults);  
159.             }  
160.               
161.             //在“纵向”这个方向上重复上面的步骤  
162.             firstAnalysisResult = tryAndCountResult(comuters,humans, computerPoint, ZHONG);  
163.             computerPoint.setX(x).setY(y);  
164.             if(firstAnalysisResult!=null){//死棋，不下  
165.                 if(firstAnalysisResult.count==5)  
166.                     return computerPoint;  
167.                   
168.                 addToFirstAnalysisResult(firstAnalysisResult,computerFirstResults);  
169.             }  
170.               
171.             //正斜向  
172.             firstAnalysisResult = tryAndCountResult(comuters,humans, computerPoint, ZHENG_XIE);  
173.             computerPoint.setX(x).setY(y);  
174.             if(firstAnalysisResult!=null){//死棋，不下  
175.                 if(firstAnalysisResult.count==5)  
176.                     return computerPoint;  
177.                   
178.                 addToFirstAnalysisResult(firstAnalysisResult,computerFirstResults);  
179.             }  
180.               
181.             //反斜向  
182.             firstAnalysisResult = tryAndCountResult(comuters,humans, computerPoint, FAN_XIE);  
183.             computerPoint.setX(x).setY(y);  
184.             if(firstAnalysisResult!=null){//死棋，不下  
185.                 if(firstAnalysisResult.count==5)  
186.                     return computerPoint;  
187.                   
188.                 addToFirstAnalysisResult(firstAnalysisResult,computerFirstResults);  
189.             }  
190.               
191.             //在“横向”上分析此棋子可在敌方形成如何状态，如敌方的活3、半活4等  
192.             firstAnalysisResult = tryAndCountResult(humans,comuters, computerPoint, HENG);  
193.             computerPoint.setX(x).setY(y);  
194.             if(firstAnalysisResult!=null){//死棋，不下  
195.                 if(firstAnalysisResult.count==5)  
196.                     humanPoint = computerPoint;  
197.                   
198.                 addToFirstAnalysisResult(firstAnalysisResult,humanFirstResults);  
199.             }  
200.               
201.             //“纵向”  
202.             firstAnalysisResult = tryAndCountResult(humans,comuters, computerPoint, ZHONG);  
203.             computerPoint.setX(x).setY(y);  
204.             if(firstAnalysisResult!=null){//死棋，不下  
205.                 if(firstAnalysisResult.count==5)  
206.                     humanPoint = computerPoint;  
207.                   
208.                 addToFirstAnalysisResult(firstAnalysisResult,humanFirstResults);  
209.             }  
210.               
211.             //“正斜”  
212.             firstAnalysisResult = tryAndCountResult(humans,comuters, computerPoint, ZHENG_XIE);  
213.             computerPoint.setX(x).setY(y);  
214.             if(firstAnalysisResult!=null){//死棋，不下  
215.                 if(firstAnalysisResult.count==5)  
216.                     humanPoint = computerPoint;  
217.                   
218.                 addToFirstAnalysisResult(firstAnalysisResult,humanFirstResults);  
219.             }  
220.               
221.             //“反斜”  
222.             firstAnalysisResult = tryAndCountResult(humans,comuters, computerPoint, FAN_XIE);  
223.             computerPoint.setX(x).setY(y);  
224.             if(firstAnalysisResult!=null){//死棋，不下  
225.                 if(firstAnalysisResult.count==5)  
226.                     humanPoint = computerPoint;  
227.                   
228.                 addToFirstAnalysisResult(firstAnalysisResult,humanFirstResults);  
229.             }  
230.         }  
231.         //如果没有绝杀棋子，第一次分析不需要返回结果  
232.         return humanPoint;  
233.     }  
234.       
235.     //第二次分析，分析第一次形成的结果，第一次分析结果会把一步棋在四个方向上可形成的结果生成最多四个FirstAnalysisResult对象（敌我各四）  
236.     //这里要把这四个对象组合成一个SencondAnalysisResult对象，  
237.     private Point doComputerSencondAnalysis(Map<Point,List<FirstAnalysisResult>> firstResults,List<SencondAnalysisResult> sencodResults) {  
238.         List<FirstAnalysisResult> list = null;  
239.         SencondAnalysisResult sr = null;  
240.         for (Point p : firstResults.keySet()) {  
241.             sr = new SencondAnalysisResult(p);  
242.             list = firstResults.get(p);  
243.             for (FirstAnalysisResult result : list) {  
244.                 if(result.count==4){  
245.                     if(result.aliveState==ALIVE){//经过前面的过滤，双方都排除了绝杀棋，有活4就下这一步了，再下一步就赢了  
246.                         return result.point;//如果有绝杀，第一轮已返回，在此轮活4已经是好的棋子，直接返回，不再往下分析  
247.                     }else{  
248.                         sr.halfAlive4 ++;  
249.                         computer4HalfAlives.add(sr);  
250.                     }  
251.                 }else if(result.count==3){  
252.                     if(result.aliveState==ALIVE){  
253.                         sr.alive3++;  
254.                         if(sr.alive3==1){  
255.                             computer3Alives.add(sr);  
256.                         }else{  
257.                             computerDouble3Alives.add(sr);  
258.                         }  
259.                     }else{  
260.                         sr.halfAlive3++;  
261.                         computer3HalfAlives.add(sr);  
262.                     }  
263.                 }else{//半活2在第一阶段已被排除，不再处理  
264.                     sr.alive2++;  
265.                     if(sr.alive2==1){  
266.                         computer2Alives.add(sr);  
267.                     }else{  
268.                         computerDouble2Alives.add(sr);  
269.                     }  
270.                 }  
271.             }  
272.             sencodResults.add(sr);  
273.         }  
274.         //没有找到活4  
275.         return null;  
276.     }  
277.       
278.     //这个方法和上面的基本一样，但为了性能，少作几次判断，将人类和电脑的分开了  
279.     private Point doHumanSencondAnalysis(Map<Point,List<FirstAnalysisResult>> firstResults,List<SencondAnalysisResult> sencodResults) {  
280.         List<FirstAnalysisResult> list = null;  
281.         SencondAnalysisResult sr = null;  
282.         for (Point p : firstResults.keySet()) {  
283.             sr = new SencondAnalysisResult(p);  
284.             list = firstResults.get(p);  
285.             for (FirstAnalysisResult result : list) {  
286.                 if(result.count==4){  
287.                     if(result.aliveState==ALIVE){  
288.                         human4Alives.add(sr);  
289.                     }else{  
290.                         sr.halfAlive4 ++;  
291.                         human4HalfAlives.add(sr);  
292.                     }  
293.                 }else if(result.count==3){  
294.                     if(result.aliveState==ALIVE){  
295.                         sr.alive3++;  
296.                         if(sr.alive3==1){  
297.                             human3Alives.add(sr);  
298.                         }else{  
299.                             humanDouble3Alives.add(sr);  
300.                         }  
301.                     }else{  
302.                         sr.halfAlive3++;  
303.                         human3HalfAlives.add(sr);  
304.                     }  
305.                 }else{  
306.                     sr.alive2++;  
307.                     if(sr.alive2==1){  
308.                         human2Alives.add(sr);  
309.                     }else{  
310.                         humanDouble2Alives.add(sr);  
311.                     }  
312.                 }  
313.             }  
314.             sencodResults.add(sr);  
315.         }  
316.         //没有找到活4  
317.         return null;  
318.     }  
319.       
320.     private void sleep(int miniSecond){  
321.         try {  
322.             Thread.sleep(miniSecond);  
323.         } catch (InterruptedException e) {  
324.         }  
325.     }  
326.       
327.       
328.     //第三次分析，双方都不可以制造活4，找双活3棋子，不行就找半活4，再不行就找单活3，双活2  
329.     private Point doThirdAnalysis() {  
330.         if(!computer4HalfAlives.isEmpty()){  
331.             return computer4HalfAlives.get(0).point;  
332.         }  
333.         System.gc();  
334.         sleep(300);  
335.         Collections.sort(computerSencodResults);  
336.         System.gc();  
337.           
338.         //即将单活4，且我没有半活4以上的，只能堵  
339.         Point mostBest = getBestPoint(human4Alives, computerSencodResults);  
340.         if(mostBest!=null)  
341.             return mostBest;  
342.           
343.         Collections.sort(humanSencodResults);  
344.         System.gc();  
345.           
346.         mostBest = getBestPoint();  
347.         if(mostBest!=null)  
348.             return mostBest;  
349.           
350.         //拿出各自排第一的，谁好就下谁  
351.         return computerSencodResults.get(0).point;  
352.     }  
353.       
354.     //子类实现这个方法，并改变其顺序可以实现防守为主还是猛攻  
355.     protected Point getBestPoint(){  
356.         //即将单活4，且我没有半活4以上的，只能堵  
357.         Point mostBest = getBestPoint(computerDouble3Alives, humanSencodResults);  
358.         if(mostBest!=null)  
359.             return mostBest;  
360.           
361.         mostBest = getBestPoint(computer3Alives, humanSencodResults);  
362.         if(mostBest!=null)  
363.             return mostBest;  
364.           
365.         mostBest = getBestPoint(humanDouble3Alives, computerSencodResults);  
366.         if(mostBest!=null)  
367.             return mostBest;  
368.           
369.         mostBest = getBestPoint(human3Alives, computerSencodResults);  
370.         if(mostBest!=null)  
371.             return mostBest;  
372.   
373.         mostBest = getBestPoint(computerDouble2Alives, humanSencodResults);  
374.         if(mostBest!=null)  
375.             return mostBest;  
376.           
377.         mostBest = getBestPoint(computer2Alives, humanSencodResults);  
378.         if(mostBest!=null)  
379.             return mostBest;  
380.           
381.         mostBest = getBestPoint(computer3HalfAlives, humanSencodResults);  
382.         if(mostBest!=null)  
383.             return mostBest;  
384.           
385.         mostBest = getBestPoint(human4HalfAlives, computerSencodResults);  
386.         if(mostBest!=null)  
387.             return mostBest;  
388.           
389.         mostBest = getBestPoint(humanDouble2Alives, computerSencodResults);  
390.         if(mostBest!=null)  
391.             return mostBest;  
392.           
393.         mostBest = getBestPoint(human2Alives, computerSencodResults);  
394.         if(mostBest!=null)  
395.             return mostBest;  
396.           
397.         mostBest = getBestPoint(human3HalfAlives, computerSencodResults);  
398.         return mostBest;  
399.     }  
400.       
401.       
402.     //第三次分析的最后一步，第二次结果已经过排序，在此可以从前面选出最好的棋子  
403.     protected Point getBestPoint(List<SencondAnalysisResult> myBest,List<SencondAnalysisResult> yourSencodResults){  
404.         if(!myBest.isEmpty()){  
405.             if(myBest.size()>1){  
406.                 for (SencondAnalysisResult your : yourSencodResults) {  
407.                     if(myBest.contains(your)){  
408.                         return your.point;  
409.                     }  
410.                 }  
411.                 return myBest.get(0).point;  
412.             }else{  
413.                 return myBest.get(0).point;  
414.             }  
415.         }  
416.         return null;  
417.     }  
418.       
419.       
420.     //第一次分析结果  
421.     private final Map<Point,List<FirstAnalysisResult>> computerFirstResults = new HashMap<Point,List<FirstAnalysisResult>>();  
422.     private final Map<Point,List<FirstAnalysisResult>> humanFirstResults = new HashMap<Point,List<FirstAnalysisResult>>();  
423.     //第二次总结果  
424.     protected final List<SencondAnalysisResult> computerSencodResults = new ArrayList<SencondAnalysisResult>();  
425.     protected final List<SencondAnalysisResult> humanSencodResults = new ArrayList<SencondAnalysisResult>();  
426.     //第二次分结果，电脑  
427.     protected final List<SencondAnalysisResult> computer4HalfAlives = new ArrayList<SencondAnalysisResult>(2);  
428.     protected final List<SencondAnalysisResult> computerDouble3Alives = new ArrayList<SencondAnalysisResult>(4);  
429.     protected final List<SencondAnalysisResult> computer3Alives = new ArrayList<SencondAnalysisResult>(5);  
430.     protected final List<SencondAnalysisResult> computerDouble2Alives = new ArrayList<SencondAnalysisResult>();  
431.     protected final List<SencondAnalysisResult> computer2Alives = new ArrayList<SencondAnalysisResult>();  
432.     protected final List<SencondAnalysisResult> computer3HalfAlives = new ArrayList<SencondAnalysisResult>();  
433.       
434.     //第二次分结果，人类  
435.     protected final List<SencondAnalysisResult> human4Alives = new ArrayList<SencondAnalysisResult>(2);  
436.     protected final List<SencondAnalysisResult> human4HalfAlives = new ArrayList<SencondAnalysisResult>(5);  
437.     protected final List<SencondAnalysisResult> humanDouble3Alives = new ArrayList<SencondAnalysisResult>(2);  
438.     protected final List<SencondAnalysisResult> human3Alives = new ArrayList<SencondAnalysisResult>(10);  
439.     protected final List<SencondAnalysisResult> humanDouble2Alives = new ArrayList<SencondAnalysisResult>(3);  
440.     protected final List<SencondAnalysisResult> human2Alives = new ArrayList<SencondAnalysisResult>();  
441.     protected final List<SencondAnalysisResult> human3HalfAlives = new ArrayList<SencondAnalysisResult>();  
442.       
443.     //第一次分析前清空上一步棋子的分析结果  
444.     private void initAnalysisResults(){  
445.         computerFirstResults.clear();  
446.         humanFirstResults.clear();  
447.         //第二次总结果  
448.         computerSencodResults.clear();  
449.         humanSencodResults.clear();  
450.         //第二次分结果  
451.         computer4HalfAlives.clear();  
452.         computerDouble3Alives.clear();  
453.         computer3Alives.clear();  
454.         computerDouble2Alives.clear();  
455.         computer2Alives.clear();  
456.         computer3HalfAlives.clear();  
457.           
458.         //第二次分结果，人类  
459.         human4Alives.clear();  
460.         human4HalfAlives.clear();  
461.         humanDouble3Alives.clear();  
462.         human3Alives.clear();  
463.         humanDouble2Alives.clear();  
464.         human2Alives.clear();  
465.         human3HalfAlives.clear();  
466.         System.gc();  
467.     }  
468.       
469.     //加入到第一次分析结果中  
470.     private void addToFirstAnalysisResult(FirstAnalysisResult result,Map<Point,List<FirstAnalysisResult>> dest){  
471.         if(dest.containsKey(result.point)){  
472.             dest.get(result.point).add(result);  
473.         }else{  
474.             List<FirstAnalysisResult> list = new ArrayList<FirstAnalysisResult>(1);  
475.             list.add(result);  
476.             dest.put(result.point, list);  
477.         }  
478.     }  
479.       
480.       
481.     //第一次分析结果类  
482.     private class FirstAnalysisResult{  
483.         //连续数  
484.         int count;  
485.         //点位  
486.         Point point;  
487.         //方向  
488.         int direction;  
489.         //状态  
490.         int aliveState;  
491.         private FirstAnalysisResult(int count, Point point, int direction) {  
492.             this(count, point, direction, ALIVE);  
493.         }  
494.           
495.         private FirstAnalysisResult(int count, Point point, int direction,int aliveState) {  
496.             this.count = count;  
497.             this.point = point;  
498.             this.direction = direction;  
499.             this.aliveState = aliveState;  
500.         }  
501.           
502.   
503.           
504.         private FirstAnalysisResult init(Point point,int direction,int aliveState){  
505.             this.count = 1;  
506.             this.point = point;  
507.             this.direction = direction;  
508.             this.aliveState = aliveState;  
509.             return this;  
510.         }  
511.           
512.         private FirstAnalysisResult cloneMe(){  
513.             return new FirstAnalysisResult(count, point, direction,aliveState);  
514.         }  
515.           
516.     }  
517.       
518.     //第二次分析结果类  
519.     class SencondAnalysisResult implements Comparable<SencondAnalysisResult>{  
520.         int alive4 = 0;  
521.         //活3数量  
522.         int alive3 = 0;  
523.         //半活4，一头封的  
524.         int halfAlive4 = 0;  
525.         //半活3，一头封的  
526.         int halfAlive3 = 0;  
527.         //活2数量  
528.         int alive2 = 0;  
529.         //点位  
530.         Point point;  
531.           
532.         @Override  
533.         public int hashCode() {  
534.             final int prime = 31;  
535.             int result = 1;  
536.             result = prime * result + ((point == null) ? 0 : point.hashCode());  
537.             return result;  
538.         }  
539.         @Override  
540.         public boolean equals(Object obj) {  
541.             SencondAnalysisResult other = (SencondAnalysisResult) obj;  
542.             if (point == null) {  
543.                 if (other.point != null)  
544.                     return false;  
545.             } else if (!point.equals(other.point))  
546.                 return false;  
547.             return true;  
548.         }  
549.   
550.         private SencondAnalysisResult(Point point) {  
551.             this.point = point;  
552.         }  
553.           
554.           
555.         //第三次分析时，对第二次分析结果进行排序，此为排序回调函数  
556.         @Override  
557.         public int compareTo(SencondAnalysisResult another) {  
558.             return compareTowResult(this, another);  
559.         }  
560.               
561.     }  
562.       
563.     //返加-1则第一个参数优先，1则第二个参数优先，0则按原来顺序  
564.     private int compareTowResult(SencondAnalysisResult oneResult,SencondAnalysisResult another){  
565.         if(oneResult.alive4>another.alive4){  
566.             return -1;  
567.         }  
568.         if(oneResult.alive4<another.alive4){  
569.             return 1;  
570.         }  
571.         if(oneResult.halfAlive4>another.halfAlive4){  
572.             return -1;  
573.         }  
574.         if(oneResult.halfAlive4<another.halfAlive4){  
575.             return 1;  
576.         }  
577.         if(oneResult.alive3>another.alive3){  
578.             return -1;  
579.         }  
580.         if(oneResult.alive3<another.alive3){  
581.             return 1;  
582.         }  
583.         if(oneResult.alive2>another.alive2){  
584.             return -1;  
585.         }  
586.         if(oneResult.alive2<another.alive2){  
587.             return 1;  
588.         }  
589.         if(oneResult.halfAlive3>another.halfAlive3){  
590.             return -1;  
591.         }  
592.         if(oneResult.halfAlive3>another.halfAlive3){  
593.             return 1;  
594.         }  
595.         return 0;  
596.     }  
597.       
598.       
599.     //一个临时对象，供第一次分析时临时存放分析结果使用，如果分析出有活1以上（不含）的结果，则调用其cloneMe方法获得结果，否则抛弃此结果  
600.     private final FirstAnalysisResult far = new FirstAnalysisResult(1, null, HENG);  
601.     // 分析如果在当前位下一子，会形成某个方向上多少个子，参数：当前己方已下的所有点，当前要假设的点，需要判断的方向  
602.     private FirstAnalysisResult tryAndCountResult(List<Point> myPoints,List<Point> enemyPoints, Point point,int direction) {  
603.         int x = point.getX();  
604.         int y = point.getY();  
605.         FirstAnalysisResult fr = null;  
606.           
607.         int maxCountOnThisDirection = maxCountOnThisDirection(point, enemyPoints, direction, 1);  
608.         if(maxCountOnThisDirection<5){  
609.             //无意义的棋子  
610.             return null;//此方向不足五个空位，已排除己方已下的棋子  
611.         }else if(maxCountOnThisDirection==5){  
612.             //半死状态，当是一头通  
613.             fr = far.init(point, direction,HALF_ALIVE);  
614.         }else{  
615.             //两头皆通  
616.             fr = far.init(point, direction,ALIVE);  
617.         }  
618.           
619.         //在前和后的方向上计算一次  
620.         countPoint(myPoints,enemyPoints,point.setX(x).setY(y),fr,direction,FORWARD);  
621.         countPoint(myPoints,enemyPoints,point.setX(x).setY(y),fr,direction,BACKWARD);  
622.           
623.           
624.         if(fr.count<=1 || (fr.count==2 && fr.aliveState==HALF_ALIVE)){//活1，半活2及其以下结果，抛弃  
625.             return null;  
626.         }  
627.         //返回复制的结果  
628.         return fr.cloneMe();  
629.     }  
630.       
631.     //棋子出了墙  
632.     private boolean isOutSideOfWall(Point point,int direction){  
633.         if(direction==HENG){  
634.             return point.getX()<0 || point.getX()>=maxX;//最大的X和Y值均在墙外所以用等号  
635.         }else if(direction==ZHONG){  
636.             return point.getY()<0 || point.getY()>=maxY;  
637.         }else{//这里可能有问题  
638.             return point.getX()<0 || point.getY()<0 || point.getX()>=maxX || point.getY()>=maxY;  
639.         }  
640.     }  
641.       
642.     private Point pointToNext(Point point,int direction,boolean forward){  
643.         switch (direction) {  
644.             case HENG:  
645.                 if(forward)  
646.                     point.x++;  
647.                 else  
648.                     point.x--;  
649.                 break;  
650.             case ZHONG:  
651.                 if(forward)  
652.                     point.y++;  
653.                 else  
654.                     point.y--;  
655.                 break;  
656.             case ZHENG_XIE:  
657.                 if(forward){  
658.                     point.x++;  
659.                     point.y--;  
660.                 }else{  
661.                     point.x--;  
662.                     point.y++;  
663.                 }  
664.                 break;  
665.             case FAN_XIE:  
666.                 if(forward){  
667.                     point.x++;  
668.                     point.y++;  
669.                 }else{  
670.                     point.x--;  
671.                     point.y--;  
672.                 }  
673.                 break;  
674.         }  
675.         return point;  
676.     }  
677.       
678.     //在某个方向（八个中的一个）可下多少棋子，这个方法是第一分析中的核心方法  
679.     private void countPoint(List<Point> myPoints, List<Point> enemyPoints, Point point, FirstAnalysisResult fr,int direction,boolean forward) {  
680.         if(myPoints.contains(pointToNext(point,direction,forward))){  
681.             fr.count ++;  
682.             if(myPoints.contains(pointToNext(point,direction,forward))){  
683.                 fr.count ++;  
684.                 if(myPoints.contains(pointToNext(point,direction,forward))){  
685.                     fr.count ++;  
686.                     if(myPoints.contains(pointToNext(point,direction,forward))){  
687.                         fr.count ++;  
688.                     }else if(enemyPoints.contains(point) || isOutSideOfWall(point,direction)){  
689.                         fr.aliveState=HALF_ALIVE;  
690.                     }  
691.                 }else if(enemyPoints.contains(point) || isOutSideOfWall(point,direction)){  
692.                     fr.aliveState=HALF_ALIVE;  
693.                 }  
694.             }else if(enemyPoints.contains(point) || isOutSideOfWall(point,direction)){  
695.                 fr.aliveState=HALF_ALIVE;  
696.             }  
697.         }else if(enemyPoints.contains(point) || isOutSideOfWall(point,direction)){  
698.             fr.aliveState=HALF_ALIVE;  
699.         }  
700.     }  
701.       
702.       
703.   
704.     //在某个方向上是否还能下到满五个棋子  
705.     private int maxCountOnThisDirection(Point point,List<Point> enemyPoints,int direction,int count){  
706.         int x=point.getX(),y=point.getY();  
707.         switch (direction) {  
708.         //横向  
709.         case HENG:  
710.             while (!enemyPoints.contains(point.setX(point.getX()-1)) && point.getX()>=0 && count<6) {  
711.                 count ++;  
712.             }  
713.             point.setX(x);  
714.             while (!enemyPoints.contains(point.setX(point.getX()+1)) && point.getX()<maxX && count<6) {  
715.                 count ++;  
716.             }  
717.             break;  
718.         //纵向  
719.         case ZHONG:  
720.             while (!enemyPoints.contains(point.setY(point.getY()-1)) && point.getY()>=0) {  
721.                 count ++;  
722.             }  
723.             point.setY(y);  
724.             while (!enemyPoints.contains(point.setY(point.getY()+1)) && point.getY()<maxY && count<6) {  
725.                 count ++;  
726.             }  
727.             break;  
728.         //正斜向 /  
729.         case ZHENG_XIE:  
730.             while (!enemyPoints.contains(point.setX(point.getX()-1).setY(point.getY()+1)) && point.getX()>=0 && point.getY()<maxY) {  
731.                 count ++;  
732.             }  
733.             point.setX(x).setY(y);  
734.             while (!enemyPoints.contains(point.setX(point.getX()+1).setY(point.getY()-1)) && point.getX()<maxX && point.getY()>=0 && count<6) {  
735.                 count ++;  
736.             }  
737.             break;  
738.         //反斜 /  
739.         case FAN_XIE:  
740.             while (!enemyPoints.contains(point.setX(point.getX()-1).setY(point.getY()-1)) && point.getX()>=0 && point.getY()>=0) {  
741.                 count ++;  
742.             }  
743.             point.setX(x).setY(y);  
744.             while (!enemyPoints.contains(point.setX(point.getX()+1).setY(point.getY()+1)) && point.getX()<maxX && point.getY()<maxY && count<6) {  
745.                 count ++;  
746.             }  
747.             break;  
748.         }  
749.         return count;  
750.     }  
751.       
752.     //下棋子，对外接口  
753.     @Override  
754.     public void run(List<Point> humans,Point p) {  
755.         //把人类下的最后一步棋子去除  
756.         allFreePoints.remove(humans.get(humans.size()-1));  
757.         //电脑可以下的一步棋子  
758.         Point result = doAnalysis(myPoints, humans);  
759.         //去除电脑下的棋子  
760.         allFreePoints.remove(result);  
761.         //加入到电脑棋子中，下棋了  
762.         myPoints.add(result);  
763.     }  
764. }  

人类玩家实现起来就非常简单

[java] 

1. import java.util.List;  
2.   
3. public class HumanPlayer extends BasePlayer {  
4.   
5.     @Override  
6.     public void run(List<Point> enemyPoints,Point p) {  
7.         getMyPoints().add(p);  
8.         allFreePoints.remove(p);  
9.     }  
10. }