board.java

Game Caro 4 user begginer

	default:		
	    switch (getGameAction(keyCode)) {
	    case Canvas.UP:
		   if(nsy -1 >= 0) nsy -= 1;
		   break;
	    case Canvas.DOWN:
		   if(nsy+1 < rows) nsy +=1;
		   break;
	    case Canvas.LEFT:
		   if(nsx-1 >= 0) nsx -= 1;		
		   break;
	    case Canvas.RIGHT:
		    if(nsx+1 < colums) nsx += 1;
		    break;
	    case Canvas.FIRE:			
			if(grid[nsy][nsx].IsSelect() == 1){
			  if(grid[nsy][nsx].getColor() == EMPTY){
				humanGo(nsy,nsx);
				return;
			  }
			}
		     break; 
		default:
			 return;
		}
		break;       
	}
	if(selectUndo == true)	selectUndo = false;	//user don't choise undo
    updateSelect(nsy,nsx);
	repaint();

}
//key release 
public void keyReleased(int keycode){
	if(gameState == COMPUTERTHINK){ ComGo();}
}
//update message from game state
public String IsMSG(int code){
	 String s = " ";
	 switch (code) {
		case INITIALIZED:
		s = s + "Select New Game from menu";
		break;
		case HUMANTHINK:
		s = s + "You Turn...";
		break;
		case COMPUTERTHINK:
		s = s + "I'm Thinking, Wait ...";
		break;
		case HUMANWIN:
		s = s + "Game Over !.. You Win !..";
		break;
		case COMPUTERWIN:
		s = s + "Game Over !.. You Lose ...";
		break;
	 default:
		s = "Unknow ...";
		break;
	 }
	 return s;
}

public void humanGo(int newy,int newx){
     newmove.set(newy,newx,0);
     int win = UpdateNewMove(newmove);
	 if(win > 0) setState(HUMANWIN);
	 else setState(COMPUTERTHINK);
	 repaint();
}

public void updateSelect(int newy,int newx){
	if(grid[newy][newx].IsSelect() == 1) return;
	osx = sx; osy = sy;
	sx = newx; sy = newy;
	grid[osy][osx].setSelect(NOSELECT);
	grid[sy][sx].setSelect(SELECT);
}
// reset game 
public void resetGrid(){
	for (int i = 0; i < rows; i++) {
		for (int j = 0; j < colums; j++) {
		  grid[i][j].setColor(EMPTY);
		}
	}

	updateSelect(rows/2,colums/2);
	clipRect.setAll(rows/2-1,colums/2-1,rows/2+1,colums/2+1);	
	hp = 0; 
	side = 3 - side; xside = 3 - side;	
	gameState = side; // fisrt state is side turn;
}

public void initboard(int nside){
	
	int i;
	clipRect = new ClipRect(0,0,0,0); //create clip rect
	cRect = new ClipRect(0,0,0,0);
	newmove  = new Move(0,0,0); // create newmove	
	histmove = new Move[(rows*colums)+1]; // create the histmove arrays	
	for(i=0;i<(rows*colums)+1;i++){
		histmove[i] = new Move(0,0,0);
	}
	Gen_dat = new Move[(rows*colums)*10];
	for(i=0;i<(rows*colums)*10;i++){
		Gen_dat[i] = new Move(0,0,0);
	}
    Gen_begin = new int[rows*colums + 1];
	Gen_end = new int[rows*colums + 1];
	for(i=0;i<(rows*colums)+1;i++){
		Gen_begin[i] = (int)0;
		Gen_end[i] = (int)0;
	}
	osx = 0; osy = 0; sx = 0; sy =0;
	side = nside; xside = 3 - nside;
	hp = 0; 
	gameState = side; // fisrt state is side turn;
}

public void changeSide(){
	int temp = side;
	 side = xside;	 xside = temp; 
}
public int UpdateNewMove(Move m){
	updateSelect(m.y,m.x);
	grid[m.y][m.x].setColor(side);	
	histmove[hp].set(m.y,m.x,m.prior);
	updateClip(m,clipRect);
	hp++;
	int ret = WinFive(m.y,m.x,side);
	changeSide();	
	//repaint();
	return ret;
}
public void updateClip(Move m,ClipRect c){
	if(m.y == c.y1 && m.y-1 >= 0) c.y1 = m.y - 1; //set top clip
	if(m.x == c.x1 && m.x-1 >= 0) c.x1 = m.x - 1; //set left clip
	if(m.y == c.y2 && m.y+1 < rows) c.y2 = m.y + 1; //set bottom clip
	if(m.x == c.x2 && m.x+1 < colums) c.x2 = m.x + 1; //set right clip
}
public void UnDoMove(){
	if(hp-2 <= 0){
		msg = "Don't Undo !...";
		repaint();	return;
	}
	for(int u=0;u<2;u++){
	    hp--;
	    int hy = histmove[hp].gety();   
	    int hx = histmove[hp].getx();
	    updateSelect(hy,hx);
	    grid[hy][hx].setColor(EMPTY);	  	
        repaint();	  
	    changeSide();
	    setState(side);
	}
}
public void InitGen(){
    Gen_begin[0]=0; 
	newmove.set(0,0,0);
	ply=0; m_hp = hp; 
	cRect.setAll(clipRect.y1,clipRect.x1,clipRect.y2,clipRect.x2);
}
public void ComGo(){
	if(hp == (rows*colums) - (rows+colums)){
	   msg = "I Don't Move, Draw A Game ?";
	   repaint(); return;
	}
	ComThink();
	int win = UpdateNewMove(newmove);
	if(win > 0) setState(COMPUTERWIN);
	else setState(HUMANTHINK);
	repaint();
}
public void ComThink(){
	if(hp == 0){ newmove.y = rows/2; newmove.x =colums/2; return;}
	if( hp == 1){		
		int mr[] = {-1,0,1};	
	    int input = mr[rand.nextInt(3)];	
	    newmove.y = newmove.y + input; newmove.x = newmove.x + input;
	    return;
	}
	maskwin = 0;
	InitGen();
	int bestPoint = 0;
	switch(Level){
	case 1: bestPoint = AlphaBeta1(-MAXPOINT,MAXPOINT,4); break;
	case 2: bestPoint = AlphaBeta2(-MAXPOINT,MAXPOINT,2); break;
	case 3:
			int r = rand.nextInt(2);	
			if( r == 0) bestPoint = AlphaBeta1(-MAXPOINT,MAXPOINT,4); 
			else bestPoint = AlphaBeta2(-MAXPOINT,MAXPOINT,3);
			break;
	}
}
// algothm AlphaBeta search
public int AlphaBeta1(int alpha, int beta, int depth) //search with level 1
{
    int i,n, value, best;
	int k = max[ply]; 
    if(ply > 0){
		value = Better(side) - ply*10;
		if(value > beta) return value;
		if(value > alpha) alpha = value;
	    if (depth == 0) return value;
	}	
	
	n = QuickGen(side,true);	if(n==0) return -MAXPOINT;
	Sort();
    best=-MAXPOINT;
	
    i=Gen_begin[ply];
    while(Gen_dat[i++].prior>160)
	  //reject
	if(i-Gen_begin[ply]> k) k = i-Gen_begin[ply];
    if(n>k) 
	Gen_end[ply] = Gen_begin[ply] + k;
	
	for (i=Gen_begin[ply]; i<Gen_end[ply] ; i++) {
		if (best > alpha) alpha = best;        
		int val = MakeMove(Gen_dat[i],Gen_dat[i].prior);
		if (val > 0){
			value = (20-ply)*1000 + (5-val)*500; 
			if(ply==1) maskwin = 1;
			//if(val >= WIN_LINE4B3) value = -AlphaBeta1(-beta, -alpha, 4);
		}
		else{ 		
		    value =  - AlphaBeta1(-beta, -alpha, depth-1);			
		}				
		UnMakeMove();
        if(ply == 0) cRect.setAll(clipRect.y1,clipRect.x1,clipRect.y2,clipRect.x2);
		if (value > best) {
			best = value; 
			if (ply == 0) newmove = Gen_dat[i];
		}
		if(best>beta || maskwin == 1) break;	
	}

	return best;
}

int AlphaBeta2(int alpha,int beta,int depth) //search with level 2
{
    int i,n,value, best=-MAXPOINT,maxxside;
    int k = max[ply];
	if(ply == 2) return AlphaBeta1(alpha,beta,2);
    maxxside = GetMaxLine(xside);	
	if(ply > 0){
	  value = TryOfMaxSide(side) - Better(xside);
	  if(value > beta) return value;
	  if(value > alpha) alpha = value;
      if(depth == 0) return value;
	}

    n = Gen(side); if(n==0) return best;
	Sort();	
    if(n>k){ 
      i=Gen_begin[ply];
	  while(Gen_dat[i++].prior > maxxside)
	  //reject
	  if(i-Gen_begin[ply]> k) k = i-Gen_begin[ply];
      Gen_end[ply] = Gen_begin[ply] + k;
	}

	for (i=Gen_begin[ply]; i<Gen_end[ply] && (maskwin == 0) && (best <= beta); i++) {
		if (best > alpha) alpha = best;        
		int val = MakeMove(Gen_dat[i],Gen_dat[i].prior);
		if (val > 0){
			value = (20-ply)*1000  -(10-val)*50; 
			if(ply==1) maskwin = 1;
			//if(val >= WIN_LINE4B3) value = value - AlphaBeta2(-beta, -alpha, 2);
		}
		else{ 
			value = - AlphaBeta2(-beta, -alpha, depth-1);			
		}
		UnMakeMove();
		if(ply == 0) cRect.setAll(clipRect.y1,clipRect.x1,clipRect.y2,clipRect.x2);
		if (value > best) {
			best = value; 
			if(ply == 0) newmove = Gen_dat[i];
		}		
	}
	return best; 
}

public void QuickSort(int q, int r)
{
	int 	i, j;
	int x;
	Move g;

	  i = q; j = r; x = Gen_dat[(q+r)/2].getprior();
	  do {
		while (Gen_dat[i].prior > x) i++;
		while (Gen_dat[j].prior < x) j--;
		if (i <= j) {
			g = Gen_dat[i]; Gen_dat[i] = Gen_dat[j];
			Gen_dat[j] = g; i++; j--;
		}
	  } while (i<=j);

	  if (q < j) QuickSort(q, j); if (i < r) QuickSort(i, r);
	
}
public void Sort()
{	
	QuickSort(Gen_begin[ply], Gen_end[ply]-1);
}

public int Gen(int nside)
{
    int i,j; 
	int Prior=0;
    //begin gen
    Gen_end[ply] = Gen_begin[ply];
	  for(i=cRect.y1;i<=cRect.y2;i++){
	    for(j=cRect.x1;j<=cRect.x2;j++)	{
	  //for(i=0;i<rows;i++){
	    //for(j=0;j<colums;j++){
			if(grid[i][j].getColor() == EMPTY){	
				Prior = CalcPoints(i,j,side,-1); 
				if(Prior>5000) {
                   grid[i][j].setColor(side);
                   if(WinFive(i,j,side) == 0) Prior -= 5300;
		           grid[i][j].setColor(EMPTY);
				}
				else Prior *= 2;
				//Prior += CalcPoints(i,j,side,5);
				Prior += CalcPoints(i,j,xside,-1);
				Gen_dat[Gen_end[ply]].set(i,j,Prior);
                Gen_end[ply] = Gen_end[ply] + 1 ;
			}
		}
	  }	

     Gen_end[ply + 1] = Gen_end[ply];
     Gen_begin[ply + 1] = Gen_end[ply];     
	 return (Gen_end[ply]-Gen_begin[ply]);
}
public int QuickGen(int nside,boolean scanxside)
{
    int i,j; 
	int Prior=0;
    //begin gen
    Gen_end[ply] = Gen_begin[ply];
	  for(i=cRect.y1;i<=cRect.y2;i++){
	    for(j=cRect.x1;j<=cRect.x2;j++)	{
			if(grid[i][j].getColor() == EMPTY){	
				Prior = CalcPoints(i,j,side,-1); 
				if(Prior>5000) {
                   grid[i][j].setColor(side);
                   if(WinFive(i,j,side) == 0) Prior -= 5300;
		           grid[i][j].setColor(EMPTY);
				}
				else Prior *= 2;
				if(scanxside == true) Prior += CalcPoints(i,j,xside,-1);
				if(Prior>0){
				   Gen_dat[Gen_end[ply]].set(i,j,Prior);
                   Gen_end[ply] = Gen_end[ply] + 1 ;
				}
			}
		}
	  }	

     Gen_end[ply + 1] = Gen_end[ply];
     Gen_begin[ply + 1] = Gen_end[ply];     
	 return (Gen_end[ply]-Gen_begin[ply]);
}

public int MakeMove(Move m,int withprior){
  
    grid[m.y][m.x].setColor(side);
	histmove[m_hp].set(m.y,m.x,withprior);
	updateClip(m,cRect);
	m_hp++;	ply++;    
	int ret = NOWON;
	if(withprior > 2100) ret =  WinFive(m.y,m.x,side);
	changeSide();	
	if(ret == 0){
		if(FindSideWin(side,false) == NOWON){ 
		    ret = WinLine4(m.y,m.x,xside);		 
		}
	}    
	return ret;
}

public void UnMakeMove()
{
   	int y,x;
    m_hp--;
	ply--;	
	y = histmove[m_hp].gety();	x = histmove[m_hp].getx();
    grid[y][x].setColor(EMPTY);
	changeSide();
}

public int WinFive(int mi, int mj, int nside)
{
   int i=0,j=0;
   int left=0, right=0;

   // vertical