android MyChess

package com.player.base; import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; import com.chess.tools.Point; //算法核心类，算法的主体思想分三个步骤， //第一步：根据双方的当前的形势循环地假设性的分别给自己和对方下一子（在某个范围内下子），并判断此棋子能带来的形势上的变化，如能不能冲4，能不能形成我方或敌方双3等， //第二步：根据上一步结果，组合每一步棋子所带来的所有结果（如某一步棋子可能形成我方1个活3，1个冲4（我叫它半活4）等），包括敌方和我方的。 //第三步：根据用户给的规则对上一步结果进行排序，并选子（有进攻形、防守形规则） public class BaseComputerAi extends BasePlayer { // 四个方向，横- 、纵| 、正斜/ 、反斜\ private static final int HENG = 0; private static final int ZONG = 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; // 标示分析结果当前点位是两头通（ALIVE）还是只有一头通（HALF_ALIVE），封死的棋子分析过程自动屏蔽，不作为待选棋子 private static final int ALIVE = 1; private static final int HALF_ALIVE = 0; // private static final int DEAD = -1; // 计算范围，太大的范围会有性能问题 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; } } // 限定电脑计算范围，如果整个棋盘计算，性能太差，目前是根据所有已下的棋子的边界值加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; } } // 如果范围扩大后超过了棋盘，则等于棋盘 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; } // 分析当前形式的入口方法，分析总共分三个步骤，第三步骤可由子类干预以作难度控制 private Point doAnalysis(List<Point> computers, List<Point> humans) { if (humans.size() == 1) {// 第一步 return getFirstPoint(humans); } // 初始化计算范围 initRange(computers, humans); // 清除以前的结果 initAnalysisResults(); // 开始分析，扫描所有空白点，形成第一次分析结果 Point bestPoint = doFirstAnalysis(computers, humans); if (bestPoint != null) { // System.out.println("这个棋子最重要，只能下这个棋子"); return bestPoint; } // 分析第一次结果，找到自己的最佳点位 bestPoint = doComputerSencondAnalysis(computerFirstResults, computerSencodResults); if (bestPoint != null) { // System.out.println("快要赢了，就下这个棋子"); return bestPoint; } computerFirstResults.clear(); System.gc(); // 分析第一次结果，找到敌人的最佳点位 bestPoint = doHumanSencondAnalysis(humanFirstResults, humanSencodResults); if (bestPoint != null) { // System.out.println("再不下这个棋子就输了"); return bestPoint; } humanFirstResults.clear(); System.gc(); // 没找到绝杀点，第三次结果分析 return doThirdAnalysis(); } // 下第一步棋子，不需要复杂的计算，根据人类第一步棋子X值减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 // 开始分析，扫描所有空白点，形成第一次分析结果 private Point doFirstAnalysis(List<Point> computers, 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坐标记下来，因为在分析过程中会改变原来的对象 x = computerPoint.getX(); y = computerPoint.getY(); if (x < currentRange.xStart || x > currentRange.xStop || y < currentRange.yStart || y > currentRange.yStop) { continue; } // 尝试在此位置上下一个棋子，并分析在“横向”这个方向上我方可形成的状态，如活4，活3，半活4，活2等所有状态 firstAnalysisResult = tryAndCountResult(computers, humans, computerPoint, HENG); computerPoint.setX(x).setY(y);// 回复点位的原值，以供下次分析 if (firstAnalysisResult != null) {// 无返回结果此方向上不可能达到五个棋子， if (firstAnalysisResult.count == 5)// 等于5表示在此点上下棋子即可连成5个，胜利了，不再往下进行分析 return computerPoint; // 记录第一次分析结果 addToFirstAnalysisResult(firstAnalysisResult, computerFirstResults); } // 在“纵向”这个方向上重复上面的步骤 firstAnalysisResult = tryAndCountResult(computers, humans, computerPoint, ZONG); computerPoint.setX(x).setY(y); if (firstAnalysisResult != null) {// 死棋，不下 if (firstAnalysisResult.count == 5) return computerPoint; addToFirstAnalysisResult(firstAnalysisResult, computerFirstResults); } // 正斜向 firstAnalysisResult = tryAndCountResult(computers, humans, computerPoint, ZHENG_XIE); computerPoint.setX(x).setY(y); if (firstAnalysisResult != null) {// 死棋，不下 if (firstAnalysisResult.count == 5) return computerPoint; addToFirstAnalysisResult(firstAnalysisResult, computerFirstResults); } // 反斜向 firstAnalysisResult = tryAndCountResult(computers, humans, computerPoint, FAN_XIE); computerPoint.setX(x).setY(y); if (firstAnalysisResult != null) {// 死棋，不下 if (firstAnalysisResult.count == 5) return computerPoint; addToFirstAnalysisResult(firstAnalysisResult, computerFirstResults); } // 在“横向”上分析此棋子可在敌方形成如何状态，如敌方的活3、半活4等 firstAnalysisResult = tryAndCountResult(humans, computers, computerPoint, HENG); computerPoint.setX(x).setY(y); if (firstAnalysisResult != null) {// 死棋，不下 if (firstAnalysisResult.count == 5) humanPoint = computerPoint; addToFirstAnalysisResult(firstAnalysisResult, humanFirstResults); } // “纵向” firstAnalysisResult = tryAndCountResult(humans, computers, computerPoint, ZONG); computerPoint.setX(x).setY(y); if (firstAnalysisResult != null) {// 死棋，不下 if (firstAnalysisResult.count == 5) humanPoint