package edu.dartmouth.cs.kalah;

/**
 * Implements a computer player that chooses moves using
 *   game tree search with alpha-beta pruning
 * @author Scot Drysdale, 2011
 */
public class ComputerKalahPlayerAB extends KalahPlayer {
  private int depth;    // Look-ahead depth
  
  /**
   * Constructs a computer player that uses alpha-beta pruning
   * @param name
   * @param maxDepth
   */
	public ComputerKalahPlayerAB(String name, int maxDepth) {
		super(name);
		depth = maxDepth;
	}

	@Override
	public int getMove(KalahGame state, KalahView view) {
		// Returns the computer play's choice using alpha-beta  search

		int move = pickMove(state, depth, -Integer.MAX_VALUE, Integer.MAX_VALUE).move;
		view.reportMove((move - state.getPlayerNum() * 7), state.getPlayerToMove().getName());

		return move;
	}

	/**
	 * Uses game tree search with alpha-beta pruning to pick player's move
	 * low and high define the current range for the best move.
	 * The current player has another move choice which will get him at least low,
	 * and his opponent has another choice that will hold his losses to high.
	 * 
	 * @param state current state of the game
	 * @param depth number of moves to look ahead in game tree search
	 * @param low a value that the player can achieve by some other move
	 * @param high a value that the opponent can force by a different line of play
	 * @return the move chosen
	 */
	private KalahMove pickMove (KalahGame state, int depth, int low, int high) {
		KalahMove currentMove;      // Hold current move and its value
		KalahMove bestMove;         // Hold best move found and its value
		int playerKalah, opponentKalah;   // Keep track of whose kalah is whose
		int [] board = state.getBoard();
		int playerToMove = state.getPlayerNum();

		playerKalah = state.getPlayerNum() * KalahGame.HALFPITS;
		opponentKalah = KalahGame.HALFPITS - playerKalah;

		// A dummy move that will be replaced when a real move is evaluated, 
		// so the pit number is irrelevant.
		bestMove = new KalahMove(Integer.MIN_VALUE, 0);   

		// Run through possible moves 
		for (int pit = playerKalah + 1; 
				bestMove.value < high && pit <= playerKalah + KalahGame.SIDEPITS; 
				pit++)   
			if (board[pit] > 0)               // See if legal move
			{
				// Make a scratch copy of state
				KalahGame copy = new KalahGame(playerToMove, state.getPlayers(), board);   
				copy.makeMove(pit);             // Make the move

				// Find the value of this board by evaluating if game over or looking ahead if not

				if (copy.gameIsOver())
					// Evaluate the true score, and multiply it by a huge constant so that the 
					// program will choose a sure win over a potentially larger speculative win 
					// and a possible loss over a sure loss.  
					currentMove = new KalahMove(100 * copy.score(), pit);
				else if (playerToMove == copy.getPlayerNum())    // Did current player change?
				{
					currentMove = pickMove(copy, depth, low, high);  // No, so no depth change
					currentMove.move = pit;              // Remember move made
				}
				else if (depth > 0)               // Player changed, so reduce search depth 
				{
					currentMove = pickMove(copy, depth - 1, -high, -low);
					currentMove.value = -currentMove.value;   // Good for opponent is bad for me 
					currentMove.move = pit;                   // Remember move made
				}
				else    // Depth exhausted, so estimate who is winning by comparing kalahs 
					currentMove = new KalahMove(copy.getBoard()[playerKalah] - 
							copy.getBoard()[opponentKalah], pit);

				if (currentMove.value > bestMove.value)  {  // Found a new best move?
					bestMove = currentMove;
					low = Math.max(low, bestMove.value);   // Update the low value, also
				}
			}
		return bestMove;
	}
}