searchengine.java

Java五子棋 支持本地游戏

import java.util.*;

class ChessPos
{
	int x = 0;
	int y = 0;
}

/**
 * 
 * this class is an abstract class it provides interface for a effective engine
 *
 */
abstract class SearchEngine  
{
	//the board information
	ChessMan CurPosition[][];
	//record the move calculated
	ChessPos bestMove;
	//a move generator generates possible move
	MoveGenerator moveGen;
	//evaluate the board
	Evaluation eval;
	//the current depth
	int searchDepth;
	//max depth of one search
	int maxDepth;
	//the board size
	int gridNum;
	//computer's chess
	ChessMan myChess;
	
	abstract void searchAGoodMove(ChessMan position[][], ChessMan c);
	
	/**
	 * 
	 * @param n			n is the board size
	 * @param depth		depth is the max depth
	 */
	SearchEngine(int n, int depth)
	{
		gridNum = n;
		maxDepth = depth;
		eval = new Evaluation(gridNum);
		moveGen = new MoveGenerator(gridNum);
		CurPosition = new ChessMan[n][n];
	}
	
	/**
	 * 
	 * put one chess on board
	 * 
	 * @param move		the position of one move
	 * @param c			the chess of the move
	 */
	void makeMove(ChessPos move, ChessMan c)
	{
		CurPosition[move.x][move.y] = c;
	}
	
	/**
	 * 
	 * retrieve the previous board
	 * 
	 * @param move the position of one move
	 */
	void unMakeMove(ChessPos move)
	{
		CurPosition[move.x][move.y] = ChessMan.Empty;		
	}
	
}

/**
 * 
 * this class generates possible moves
 *
 */
class MoveGenerator
{
	public int moveCount;	
	public ChessPos[][] moveList = new ChessPos[10][225];
	int size;
	
	/**
	 * 
	 * @param n		n is the board size
	 */
	MoveGenerator(int n)
	{
		size = n;		
		moveList = new ChessPos[5][n * n];
		for(int i = 0; i < 5; i++)
			for(int j = 0; j < n * n; j++)
				moveList[i][j] = new ChessPos();
	}

	/**
	 * this method create possible moves in one board
	 * 
	 * @param board		the board information
	 * @param depth		the current search depth
	 * @return			the count of possible move
	 */
	int createPossibleMove(ChessMan[][] board, int depth)
	{
		int	i,j;
		moveCount = 0;
		for (i = 0; i < size; i++)
			for (j = 0; j < size; j++)
			{
				if (board[i][j] == ChessMan.Empty)
				{
					moveList[depth][moveCount].x = i;
					moveList[depth][moveCount++].y = j;
				}
			}

		return moveCount;		
	}

}

/**
 * 
 * This class uses alpha-beta cutting algorithm and search a good move for computer 
 *
 */
class AlphaBetaEngine extends SearchEngine
{
	AlphaBetaEngine(int n, int depth)
	{
		super(n, depth);
	}
	
	/**
	 * this method search a good move for computer
	 * 
	 * @param position		the board information
	 * @param c				the chessman hold by computer
	 * 
	 */
	void searchAGoodMove(ChessMan position[][], ChessMan c)
	{
		//copy the board information
		for(int i = 0; i < gridNum; i++)
			for(int j = 0; j < gridNum; j++)
			{
				CurPosition[i][j] = position[i][j];
			}
		boolean isWhiteTurn = (c == ChessMan.White)?true:false;
		
		//use Alpha-Beta pruning search algorithm to find a good step 
		AB(maxDepth, -20000, 20000, isWhiteTurn);
		
		//System.out.println("x:" + bestMove.y + " y:" + bestMove.x);
		//makeMove(bestMove, c);
	}
	
	/**
	 * This method uses alpha-beta pruning algorithm and search for a good move
	 * 
	 * @param depth			the current depth
	 * @param alpha			the alpha value
	 * @param beta			the beta value
	 * @param isWhiteTurn	whether the current player is white
	 * @return				the score
	 */
	int AB(int depth, int alpha, int beta, boolean isWhiteTurn)
	{
		int Count,i;
		int score;
		ChessMan chessMan;
		int current = -20000;
		
		chessMan = (isWhiteTurn)?ChessMan.White:ChessMan.Black;
		
		//if it's a leaf node, return the evalution value
		if (depth <= 0)	
		{
			score = eval.evaluate(CurPosition, isWhiteTurn);
			score = (isWhiteTurn)?-score:score;
			return score;
		}
		
		//create possible move
		Count = moveGen.createPossibleMove(CurPosition, depth);
		
		//search among these moves
	    for ( i = 0; i < Count; i++ ) 
		{
	    	ChessPos t = moveGen.moveList[depth][i];
			makeMove(t, chessMan);
			if(ChessGame.judge(t.x, t.y, CurPosition))
			{	
				if(depth == maxDepth)
					bestMove = moveGen.moveList[depth][i];				
				return 10000;
			}
			
			//search the value in a recursive way
			score = -AB(depth - 1 , -beta, -alpha, !isWhiteTurn);
			
/*			if(depth == maxDepth)
				System.out.println("x:" + t.x + " " + "y:" + t.y + "score:" + score);
*/			
			unMakeMove(t);
			
			//judge if it's better
			if(score > current)
			{	
				current = score;
				if(score > alpha)
					alpha = score;
				if(score >= beta)
					break;
				if(depth == maxDepth)
					bestMove = moveGen.moveList[depth][i];
			}

		}
	    //return the value
		return current;

	}
}