Java實(shí)現(xiàn)五子棋AI算法
更新時間：2018年03月26日 15:04:52 作者：彷徨的石頭
這篇文章主要為大家詳細(xì)介紹了Java實(shí)現(xiàn)五子棋AI算法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下
五子棋AI算法也算是一個典型的游戲AI算法，一些棋類的AI算法都可以參考實(shí)現(xiàn)，下面是Java實(shí)現(xiàn)代碼
棋盤抽象接口
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)
//棋子類
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;
}
}
玩家抽象接口
import java.util.List;
public interface IPlayer {
//下一步棋子，傳入對手已經(jīng)下的棋子集合
public void run(List<Point> enemyPoints, Point point);
public boolean hasWin();
public void setChessboard(IChessboard chessboard);
public List<Point> getMyPoints();
}
玩家基礎(chǔ)抽象類
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)
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
//算法核心類，算法的主體思想分三個步驟，
//第一步：根據(jù)雙方的當(dāng)前的形勢循環(huán)地假設(shè)性的分別給自己和對方下一子（在某個范圍內(nèi)下子），并判斷此棋子能帶來的形勢上的變化，如能不能沖4，能不能形成我方或敵方雙3等，
//第二步：根據(jù)上一步結(jié)果，組合每一步棋子所帶來的所有結(jié)果（如某一步棋子可能形成我方1個活3，1個沖4（我叫它半活4）等），包括敵方和我方的。
//第三步：根據(jù)用戶給的規(guī)則對上一步結(jié)果進(jìn)行排序，并選子（有進(jìn)攻形、防守形規(guī)則）
public class BaseComputerAi extends BasePlayer {
// 四個方向，橫- 、縱| 、正斜/ 、反斜\
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），封死的棋子分析過程自動屏蔽，不作為待選棋子
private static final int ALIVE = 1;
private static final int HALF_ALIVE = 0;
//private static final int DEAD = -1;
//計(jì)算范圍，太大的范圍會有性能問題
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ì)算范圍，如果整個棋盤計(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ò)大后超過了棋盤，則等于棋盤
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)前形式的入口方法，分析總共分三個步驟，第三步驟可由子類干預(yù)以作難度控制
private Point doAnalysis(List<Point> comuters, List<Point> humans) {
if(humans.size()==1){//第一步
return getFirstPoint(humans);
}
//初始化計(jì)算范圍
initRange(comuters, humans);
//清除以前的結(jié)果
initAnalysisResults();
// 開始分析，掃描所有空白點(diǎn)，形成第一次分析結(jié)果
Point bestPoint = doFirstAnalysis(comuters, humans);
if(bestPoint!=null){
//System.out.println("這個棋子最重要，只能下這個棋子");
return bestPoint;
}
// 分析第一次結(jié)果，找到自己的最佳點(diǎn)位
bestPoint = doComputerSencondAnalysis(computerFirstResults,computerSencodResults);
if(bestPoint!=null){
//System.out.println("快要贏了，就下這個棋子");
return bestPoint;
}
computerFirstResults.clear();
System.gc();
// 分析第一次結(jié)果，找到敵人的最佳點(diǎn)位
bestPoint = doHumanSencondAnalysis(humanFirstResults,humanSencodResults);
if(bestPoint!=null){
//System.out.println("再不下這個棋子就輸了");
return bestPoint;
}
humanFirstResults.clear();
System.gc();
//沒找到絕殺點(diǎn)，第三次結(jié)果分析
return doThirdAnalysis();
}
//下第一步棋子，不需要復(fù)雜的計(jì)算，根據(jù)人類第一步棋子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
// 開始分析，掃描所有空白點(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)記下來，因?yàn)樵诜治鲞^程中會改變原來的對象
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");
// }
//嘗試在此位置上下一個棋子，并分析在“橫向”這個方向上我方可形成的狀態(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){//無返回結(jié)果此方向上不可能達(dá)到五個棋子，
if(firstAnalysisResult.count==5)//等于5表示在此點(diǎn)上下棋子即可連成5個，勝利了，不再往下進(jìn)行分析
return computerPoint;
//記錄第一次分析結(jié)果
addToFirstAnalysisResult(firstAnalysisResult,computerFirstResults);
}
//在“縱向”這個方向上重復(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);
}
}
//如果沒有絕殺棋子，第一次分析不需要返回結(jié)果
return humanPoint;
}
//第二次分析，分析第一次形成的結(jié)果，第一次分析結(jié)果會把一步棋在四個方向上可形成的結(jié)果生成最多四個FirstAnalysisResult對象（敵我各四）
//這里要把這四個對象組合成一個SencondAnalysisResult對象，
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)過前面的過濾，雙方都排除了絕殺棋，有活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);
}
//沒有找到活4
return null;
}
//這個方法和上面的基本一樣，但為了性能，少作幾次判斷，將人類和電腦的分開了
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);
}
//沒有找到活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，且我沒有半活4以上的，只能堵
Point mostBest = getBestPoint(human4Alives, computerSencodResults);
if(mostBest!=null)
return mostBest;
Collections.sort(humanSencodResults);
System.gc();
mostBest = getBestPoint();
if(mostBest!=null)
return mostBest;
//拿出各自排第一的，誰好就下誰
return computerSencodResults.get(0).point;
}
//子類實(shí)現(xiàn)這個方法，并改變其順序可以實(shí)現(xiàn)防守為主還是猛攻
protected Point getBestPoint(){
//即將單活4，且我沒有半活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)過排序，在此可以從前面選出最好的棋子
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;
}
//第三次分析時，對第二次分析結(jié)果進(jìn)行排序，此為排序回調(diào)函數(shù)
@Override
public int compareTo(SencondAnalysisResult another) {
return compareTowResult(this, another);
}
}
//返加-1則第一個參數(shù)優(yōu)先，1則第二個參數(shù)優(yōu)先，0則按原來順序
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;
}
//一個臨時對象，供第一次分析時臨時存放分析結(jié)果使用，如果分析出有活1以上（不含）的結(jié)果，則調(diào)用其cloneMe方法獲得結(jié)果，否則拋棄此結(jié)果
private final FirstAnalysisResult far = new FirstAnalysisResult(1, null, HENG);
// 分析如果在當(dāng)前位下一子，會形成某個方向上多少個子，參數(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){
//無意義的棋子
return null;//此方向不足五個空位，已排除己方已下的棋子
}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值均在墻外所以用等號
}else if(direction==ZHONG){
return point.getY()<0 || point.getY()>=maxY;
}else{//這里可能有問題
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;
}
//在某個方向（八個中的一個）可下多少棋子，這個方法是第一分析中的核心方法
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;
}
}
//在某個方向上是否還能下到滿五個棋子
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;
}
//下棋子，對外接口
@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)起來就非常簡單
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寫的但算法已被抽象可以方便的修改成各種平臺的實(shí)現(xiàn)。
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
EasyExcel是阿里巴巴開源poi插件之一，主要解決了poi框架使用復(fù)雜，sax解析模式不容易操作，數(shù)據(jù)量大起來容易OOM，解決了POI并發(fā)造成的報錯。主要解決方式：通過解壓文件的方式加載，一行一行的加載，并且拋棄樣式字體等不重要的數(shù)據(jù)，降低內(nèi)存的占用。2021-06-06
這篇文章主要介紹了線程啟動為什么要用start()而不是run()?下面文章圍繞start()與run()的相關(guān)資料展開詳細(xì)內(nèi)容，具有一定的參考價值，西藥的小火熬版可以參考一下，希望對你有所幫助2021-12-12
之前一個朋友問我，如何判斷字符串中是否包含中文，其實(shí)解決的方法很簡單，但覺著有必要寫出給不知道的朋友們以參考，所以下面這篇文章主要介紹了利用Java正則表達(dá)式判斷字符串中是否包含中文的方法，需要的朋友可以參考。2017-03-03
Springboot pom項(xiàng)目間接依賴包版本與預(yù)期不符原因解決分析
這篇文章主要介紹了Springboot pom項(xiàng)目間接依賴包版本與預(yù)期不符原因解決分析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-08-08
這篇文章主要介紹了Java 鎖粗化與循環(huán)的相關(guān)知識，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，具有一定的參考借鑒價值,需要的朋友可以參考下2019-04-04
spring boot hutool整合email的詳細(xì)過程
這篇文章主要介紹了spring boot hutool整合email的相關(guān)知識，本文介紹兩種方式發(fā)送email文件，結(jié)合實(shí)例代碼給大家介紹的非常詳細(xì),需要的朋友可以參考下2023-03-03
這篇文章主要介紹了使用jar包反編譯形成pom工程，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-06-06
IDEA是JetBrains公司推出一個集成開發(fā)工具，是Java開發(fā)工具中的翹楚，基于這個開發(fā)工具可以快速開發(fā)我們的Java相關(guān)項(xiàng)目，本文重點(diǎn)給大家介紹IDEA2022.2的簡介、下載與安裝、初步配置，感興趣的朋友一起看看吧2022-11-11
關(guān)于Spring MVC框架中攔截器Interceptor的使用解讀
這篇文章主要介紹了關(guān)于Spring MVC框架中攔截器Interceptor的使用，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-07-07
這篇文章主要介紹了Java8新特性之Optional使用詳解,為了解決空指針異常更加優(yōu)雅,Java8?提供了?Optional?類庫,Optional?實(shí)際上是個容器,它可以保存類型T的值,或者僅僅保存null,,需要的朋友可以參考下2023-08-08