井字棋_小游戏_人人对战_人工智能

import java.util.*; class jidajixiao { public List<jiedian> close=new LinkedList<jiedian>(); public jidajixiao(jiedian open) { } int dep=0; int DEP=4; public void xiayibu(jiedian xxx,int dep)//生成整个树 通过father和son来联系各个节点 { int h=0; for(int i=0;i<9;i++) { if(xxx.ar[i]==0) { h++; } } if(h!=0 &&dep<DEP ) { for (int i = 0; i < 9; i++) { if (xxx.ar[i] == 0) { xxx.ar[i] = xxx.gs; int[] a = new int[9]; for (int j = 0; j < 9; j++) { a[j] = xxx.ar[j]; } jiedian xin = new jiedian(a, -xxx.gs); xin.father = xxx; xxx.son.add(xin); close.add(xin); xxx.ar[i] = 0; if(this.checkWin(xin.ar,xxx.gs)==1) { xin.dt=1000; xin.getar(); System.out.println("dt="+xin.dt); } else if(this.checkWin(xin.ar,xxx.gs)==-1) { xin.dt=-1000; xin.getar(); System.out.println("dt="+xin.dt); } else if(dep==DEP) { xin.getdt(); } else { dep++; xiayibu(xin,dep); } } } } /* int h=0; for(int i=0;i<9;i++) { if(xxx.ar[i]==0) { h++; } } if(h!=0 &&dep<1 ) { for (int i = 0; i < 9; i++) { if (xxx.ar[i] == 0) { xxx.ar[i] = xxx.gs; int[] a = new int[9]; for (int j = 0; j < 9; j++) { a[j] = xxx.ar[j]; } jiedian xin = new jiedian(a, -xxx.gs); xin.father = xxx; xxx.son.add(xin); close.add(xin); xxx.ar[i] = 0; if(checkWin(xin.ar,xxx.gs) == 0 ||dep<1) { xin.getdt();//计算新节点的dt值 xiayibu(xin,dep++); } else { xxx.dt=-checkWin(xin.ar,xxx.gs)*1000; } } } }*/ } public jiedian MAXorMIN(List<jiedian> a)//在同父亲的儿子节点中挑出此时需要的dt最大或最小节点 { jiedian res; if(a.size()==0) {} res=a.get(0); if (a.get(0).gs == -1)//找一个dt最大的 { for (int i = 1; i < a.size(); i++) { if (a.get(0).dt >= res.dt) { res = a.get(i); //Console.WriteLine("WO LAIGU2"); } } return res; } else//找一个dt最小的 { for (int i = 1; i < a.size(); i++) { if (a.get(i).dt < res.dt) { res = a.get(i); } } return res; } } public void showclose()//写代码的时候用来观察，后来就木有用了 { for (int i = 0; i < close.size(); i++) { System.out.println(); close.get(i).getar(); System.out.println("DT=MAX-MIN=:"+close.get(i).max+"-"+close.get(i).min+"="+close.get(i).dt+" GSL="+close.get(i).gs); } } public int getgoodnext(jiedian old)//输入初始节点，通过最大最小值法，求得最优步骤 { int temp=9; int h=0; dep=0; if(this.pandun2zi(old)!=9 )//先判断是否有此时能够胜利的位置 { return this.pandun2zi(old);//胜利 } else//胜利 { if(this.pandun2zi2(old)!=9 )//再判断是否此时对手有能够胜利的位置 { return this.pandun2zi2(old );//围堵 } else//围堵 { //只剩下一个位置了么？ for(int i=0;i<9;i++) { if(old.ar[i]==0) {h++;} } if(h==1) { for(int i=0;i<9;i++) { if(old.ar[i]==0) temp=i; } return temp; } ////极大极小算法用一个递归出应该下的位置 else { if (old.son.size()== 1) { old.father.dt=this.MAXorMIN(old.father.son).dt;//在倒数第二层的这个old节点的兄弟找出来 求出MINorMAX（）的dt复制给old的父亲 } else { for (int i = 0; i < old.son.size(); i++) { getgoodnext(old.son.get(i)); } } if(old.son.size()!=0) { jiedian new_01=MAXorMIN(old.son); for(int i=0;i<9;i++) { if(old.ar[i]!=new_01.ar[i]) { temp=i; } } } return temp; }//判断剩1格 }//围堵 }//胜利 } public int pandun2zi(jiedian a)//判断是否有2字连线能赢的情况 { int[] t = a.ar; int p = a.gs; int i, k = 9; for (i = 0; i < 9; i++) { if (t[i] == 0) { t[i] = p; if (checkWin(t, p) == p) { t[i] = 0; k = i; } t[i] = 0; } } return k; } public int pandun2zi2(jiedian a)//判断是否有2字连线会输的情况 { int[] t = a.ar; int p = -a.gs; int i, k = 9; for (i = 0; i < 9; i++) { if (t[i] == 0) { t[i] = p; if (checkWin(t, p) == p) { t[i] = 0; k = i; } t[i] = 0; } } return k; } int checkWin(int[] t,int p)//盘算局势是否胜利了 用来和那个panduan2zi 联系起来 { if (t[0]==p && t[0]==t[1] && t[1]==t[2]) return(p); if (t[3]==p && t[3]==t[4] && t[4]==t[5]) return(p); if (t[6]==p && t[6]==t[7] && t[7]==t[8]) return(p); if (t[0]==p && t[0]==t[3] && t[3]==t[6]) return(p); if (t[1]==p && t[1]==t[4] && t[4]==t[7]) return(p); if (t[2]==p && t[2]==t[5] && t[5]==t[8]) return(p); if (t[0]==p && t[0]==t[4] && t[4]==t[8]) return(p); if (t[2]==p && t[2]==t[4] && t[4]==t[6]) return(p); return(0); } public static void main(String[] args) { int[] a ={0,1,1,0,-1,0,-1,0,0}; //int[] a ={ 1,0,0,-1,-1,1,0,0,0};//第三步 jiedian text = new jiedian(a,-1); text.getdt(); jidajixiao test2 =new jidajixiao(text); test2.xiayibu(text,0); //System.out.println(text.son.size()); //test2.getgoodnext(text).getar(); System.out.println("应该下="+test2.getgoodnext(text)); System.out.println(test2.close.size()); } }