/*
 * This is an AI class based on the idea of Mini-Max and Aplha-Beta pruning. It creates a decision tree based on
 * the board and future moves. The best option for the next move is then chosen. The further it looks ahead, the
 * better the decisions it makes. However, it is possible to look far enough ahead to see that it can't win no
 * matter what, and just throw the game. Also, the further the AI looks ahead, the longer it takes to process a
 * given situation and the more CPU it will consume. The AI cannot process deeper than there are nodes available
 * from the game board. This doesn't mean it won't infinitely recurse if the current state never stops saying it
 * has more child nodes to process!
 *
 * This class was adapted from a Java project based around this class. This class was written by my project parter
 * and he is rightfully attributed as author. (I only fixed one teensy-tiny error in this class and "randomized"
 * the AI. I do understand how it works though!)
 *
 * Author: M. Butalla, 2007
 *
 * Constructor:
 * Param - The depth of the decision tree this AI is allowed to process (must be a number).
 */
function MiniMaxEngine(depth) {

	if(isNaN(Number(depth))) {
		throw ("Depth parameter: number expected, received: " + (typeof depth));
	}

	var maxLevel = Number(depth);
	var isBrainActive = false;

	const REL_MAX = Math.pow(2, 31);

	/*
	 * Returns a the state with the computer's next move.
	 */
	this.generateNextMove = function(currentProblem) {

		var currentLevel = 1;
		var bestResult = -REL_MAX;
		var bestMove = currentProblem;

		// Start thinking.
		isBrainActive = true;

		// For all of the problem children, find the best choice.
		while(currentProblem.hasMoreChildren()) {
			var problemChild = currentProblem.nextChild();
			var currentResult = recursiveMiniMaxAlphaBeta(problemChild, currentLevel, -REL_MAX, REL_MAX);

			// Keep the best choice. If the same, make life interesting! :)
			if(currentResult > bestResult || (currentResult === bestResult && Math.random() > .5)) {
				bestResult = currentResult;
				bestMove = problemChild;
			}
		}

		// Stop thinking. :P
		isBrainActive = false;

		return (bestMove);
	};

	/*
	 * Whether or not the AI is currently thinking.
	 */
	this.isThinking = function() {
		return (isBrainActive);
	};

	/*
	 * Calculates and returns the cost of the passed board state.
	 *
	 * Param - The board state to be evaluated.
	 * Param - The current depth in the decision tree.
	 * Param - The alpha bound, used when pruning the decision tree.
	 * Param - The beta bound, used when pruning the decision tree.
	 */
	function recursiveMiniMaxAlphaBeta(currentProblem, currentLevel, alpha, beta) {

		var cost = currentProblem.staticEvaluation();
		var newBound = 0.0;

		// Problem not solved
		if(cost == 0 && currentProblem.hasMoreChildren() && currentLevel < maxLevel) {

			// Mini Level
			if(currentLevel % 2 != 0) {

				// As long as we have more children and alpha is still smaller than beta
				while(currentProblem.hasMoreChildren() && alpha < beta) {

					// Evaluate the next child, passing it the current alpha and beta
					newBound = recursiveMiniMaxAlphaBeta(currentProblem.nextChild(), currentLevel + 1, alpha, beta);
					
					// If the value returned from the child is smaller than beta, replace beta
					if(newBound < beta) {
						beta = newBound;
					}
				}
				cost = beta; // Return beta as our cost
			}

			// Max Level
			if(currentLevel % 2 == 0) {

				// As long as we have more children and alpha is still smaller than beta
				while(currentProblem.hasMoreChildren() && alpha < beta) {

					//Evaluate the next child, passing it the current alpha and beta
					newBound = recursiveMiniMaxAlphaBeta(currentProblem.nextChild(), currentLevel + 1, alpha, beta);
					
					//If the value returned from the child is larger than alpha, replace alpha
					if(newBound > alpha) {
						alpha = newBound;
					}
				}
				cost = alpha;  // Return alpha as our cost
			}
		}
			
		return (cost);
	}
}