minimaxplayer.java

source code about game desktop

// MinimaxPlayer.java

 
/** 
 *
 * @author  Sean Bridges
 * @version 1.0
 *
 * The MinimaxPlayer uses the minimax algorithm to determine what move it should 
 * make.  Looks ahead depth moves.  The number of moves will be on the order
 * of n^depth, where n is the number of moves possible, and depth is the number
 * of moves the engine is searching.  Because of this the minimax player periodically
 * polls the thread that calls getMove(..) to see if it was interrupted.  It the thread
 * is intertupted, the player returns null after it checks.  
 */
public class MinimaxPlayer extends DefaultPlayer
{
	
//----------------------------------------------
	//instance variables
	
	//the number of levels minimax will look ahead
	private int depth = 1;
	private Player minPlayer;

//----------------------------------------------
	//constructors

  /** Creates new MinimaxPlayer */
	public MinimaxPlayer(String name, int number, Player minPlayer) 
	{
		super(name, number);
		
		this.minPlayer = minPlayer;
	}

//----------------------------------------------
	//instance methods
	
	/**
	 * Get the number of levels that the Minimax Player is currently looking 
	 * ahead.
	 */
	public int getDepth()
	{
		return depth;
	}
	
	/**
	 * Set the number of levels that the Minimax Player will look ahead 
	 * when getMove is next called
	 */
	public void setDepth(int anInt)
	{
		depth = anInt;
	}
	
	/** Passed a copy of the board, asked what move it would like to make.
	 *
	 * The MinimaxPlayer periodically polls the thread that makes this call to 
	 * see if it is interrupted.  If it is the player returns null.
	 *
	 * Looks ahead depth moves.
 	 */
	public Move getMove(Board b)
	{
		MinimaxCalculator calc = new MinimaxCalculator(b,this,minPlayer);
		return calc.calculateMove(depth);
	}
	
	
}//end MinimaxPlayer

/**
 * The MinimaxCalculator does the actual work of finding the minimax move.
 * A new calculator should be created each time a move is to be made.
 * A calculator should only be used once.
 */
final class MinimaxCalculator
{

//-------------------------------------------------------
	//instance variables
	
	//the number of moves we have tried
	private int moveCount = 0;
	private long startTime;
	
	private Player minPlayer;
	private Player maxPlayer;
	private Board board;
	
	private final int MAX_POSSIBLE_STRENGTH;
	private final int MIN_POSSIBLE_STRENGTH;

//-------------------------------------------------------
	//constructors
	MinimaxCalculator(Board b, Player max, Player min)
	{
		board = b;
		maxPlayer = max;
		minPlayer = min;
		
		MAX_POSSIBLE_STRENGTH = board.getBoardStats().getMaxStrength();
		MIN_POSSIBLE_STRENGTH = board.getBoardStats().getMinStrength();
	}
	
//-------------------------------------------------------
	//instance methods
	
	/** 
	 * Calculate the move to be made.
	 */
	public Move calculateMove(int depth)
	{
		startTime = System.currentTimeMillis();
		
		if(depth == 0)
		{
			System.out.println("Error, 0 depth in minumax player");
			Thread.dumpStack();
			return null;
		}
		
		Move[] moves = board.getPossibleMoves(maxPlayer);
		int maxStrength = MIN_POSSIBLE_STRENGTH;
		int maxIndex = 0;
		
		for(int i = 0; i < moves.length; i++)
		{
			if(board.move(moves[i]))
			{
				moveCount++;
				
				int strength = expandMinNode(depth -1, maxStrength);
				if(strength > maxStrength)
				{
					maxStrength = strength;
					maxIndex = i;
				}
				board.undoLastMove();
			}//end if move made
			
			//if the thread has been interrupted, return immediately.
			if(Thread.currentThread().isInterrupted())
			{
				return null;
			}
			
		}//end for all moves
		
		long stopTime = System.currentTimeMillis();
		System.out.print("MINIMAX: Number of moves tried:" + moveCount);
		System.out.println(" Time:" + (stopTime -  startTime) + " milliseconds");
		
		return moves[maxIndex];
		
	}
	
	/**
	 * A max node returns the max score of its descendents.
	 * parentMinimum is the minumum score that the parent has already encountered.
	 * if we find a score that is higher than this, we will return that score
	 * immediately rather than continue to expand the tree, since
	 * the min node above us only cares if we are lower than its current 
	 * min score.
	 */
	private int expandMaxNode(int depth, int parentMinimum)
	{
		//base step
		if(depth == 0 || board.isGameOver())
		{
			return board.getBoardStats().getStrength(maxPlayer);
		}
		
		//recursive step
		Move[] moves = board.getPossibleMoves(maxPlayer);
		int maxStrength = MIN_POSSIBLE_STRENGTH;
		
		for(int i = 0; i < moves.length; i++)
		{
			if(board.move(moves[i]))
			{
				moveCount++;
				int strength = expandMinNode(depth -1, maxStrength);

				if(strength > parentMinimum)
				{
					board.undoLastMove();
					return strength;
				}
				if(strength > maxStrength)
				{
					maxStrength = strength;
				}
				board.undoLastMove();
			}//end if move made
			
		}//end for all moves
		
		return maxStrength;
	
	}//end expandMaxNode
	
	
	/**
	 * The min node chooses the smallest of its descendents.
	 * parentMaximum is the maximum that the parent max node has already found,
	 * if we find something smaller than this, return immediatly, since the
	 * parent max node will choose the greatest value it can find.
	 */
	private int expandMinNode(int depth, int parentMaximum)
	{
		//base step
		if(depth == 0 || board.isGameOver())
		{
			return board.getBoardStats().getStrength(maxPlayer);
		}
		
		//recursive step
		Move[] moves = board.getPossibleMoves(minPlayer);
		int minStrength = MAX_POSSIBLE_STRENGTH;
		
		for(int i = 0; i < moves.length; i++)
		{
			if(board.move(moves[i]))
			{
				moveCount++;
				int strength = expandMaxNode(depth -1, minStrength);
				
				if(strength < parentMaximum)
				{
					board.undoLastMove();
					return strength;
				}
				if(strength < minStrength)
				{
					minStrength = strength;
				}
				board.undoLastMove();
			}//end if move made
			
		}//end for all moves
		
		return minStrength;
	
	}//end expandMaxNode
	
}