package game.training;

import java.util.Collections;

import game.logic.GameBoard;
import game.logic.Vector;

public class MiniMax {
	public static final boolean MAX = true;
	public static final boolean MIN = false;
	
	
	/**
	 * The recursive implementation of the MiniMax algorithm,
	 * with alpha-beta pruning. First call should be with alpha==-inf and beta==+inf.
	 * We implemented some sort of randomization by shuffling the moves before each
	 * iteration over them. This should give us some randomization if we reach two
	 * equally good moves.
	 * 
	 * @param side a MIN player or a MAX player
	 * @param alpha the alpha value.
	 * @param beta the beta value.
	 * @param board the current state of the board.
	 * @param depth the depth of the current tree or subtree.
	 * @param player the player that initialized the whole process.
	 * @param weights the player's weight vector.
	 * 
	 * @return a Best data structure which holds the best possible move and score for
	 * the current player.
	 */
	public static Best chooseMove(boolean side, double alpha, double beta, GameBoard board,
			int depth, int player, Vector weights){
		Best myBest = new Best();
		Best reply;
		
		/* Stop condition - if the game is over or the maximal depth has been reached, return
		 * the score, with no move. */
		if (depth == 0 || board.isOver()){
			
			if (board.isOver()){
				/* A tie game */
				if (board.getTotalDiscs() == GameBoard.NumOfRows * GameBoard.NumOfColumns &&
						board.player1Four == 0 && board.player2Four == 0){
					myBest.setScore(0);
				} else {
					/* If side is MAX, then MIN placed the winning move, so give it -inf. */
					if (side == MAX){
						myBest.setScore(Double.NEGATIVE_INFINITY);
					}
					/* Else, MAX made the winning move. */
					else if (side == MIN){
						myBest.setScore(Double.POSITIVE_INFINITY);
					}
				}
			}
			/* Else, depth must be zero, so return the state*weights of the board. */
			else {
				double boardScore;
				
				boardScore = Vector.dotProduct(board.getStateVector(), weights);
				
				myBest.setScore(boardScore);
			}
			
			return myBest;
		}
		
		/* Initialize score values that will guarantee a move */
		if (side == MAX){
			myBest.setScore(alpha);
		} else {
			myBest.setScore(beta);
		}
		
		/* Get all possible moves, and shuffle them into an array. */
		int[] possibleMoves = new int[board.getPossibleMoves().size()];
		Collections.shuffle(board.getPossibleMoves());
		
		for (int i = 0; i < board.getPossibleMoves().size(); i++){
			possibleMoves[i] = board.getPossibleMoves().get(i);
		}
		
		/* for each possible move */
		for (int nextMove : possibleMoves){
			
			/* Make the move and modify board */
			board.insertDisc(nextMove, board.getCurrentPlayer());
			board.switchPlayer();
			
			/* The recursive call */
			reply = chooseMove(!side, alpha, beta, board, depth-1, player, weights);
			board.removeDisc(nextMove); /* Restore board */
			board.switchPlayer();
			
			/* If side is MAX and the reply score is higher than what we achieved so far,
			 * then make it the new best score (reversed image for MIN player). */
			if (side == MAX && reply.getScore() > myBest.getScore()){
				myBest.setMove(nextMove);
				myBest.setScore(reply.getScore());
				alpha = reply.getScore();
			} else if (side == MIN && reply.getScore() < myBest.getScore()){
				myBest.setMove(nextMove);
				myBest.setScore(reply.getScore());
				beta = reply.getScore();
			}
			
			/* Alpha or Beta cutoffs - no need to search the rest of the tree */
			if (alpha >= beta){
				return myBest;
			}
			
		}
		
		return myBest;
	}
}
