/*
 * Copyright © 2009 Bjoern Guenzel
 *
 */
/*
 * scheduler has no effect yet
 */
function HalmaAI(halmaClone, scheduler){
    this.halma = halmaClone;
    this.scheduler = scheduler;
    this.nodeCount = 0;
    this.lastTime = 0;
}	

HalmaAI.MAX_DEPTH = 3;
HalmaAI.MAX_BACKWARDS_STEP = 0;//don't consider moves that move farther back than that.
HalmaAI.CUTOFF_DELTA = 0;//if a move gives less than CUTOFF_DELTA points than another move, don't evaluate that move further
HalmaAI.RANDOMIZE_EQUAL_MOVES = true;//add random number to deltaHoma, so that moves with equal delta and deltaHome don't end up the same every time


HalmaAI.LOG_TIME = false;
HalmaAI.DONT_VALIDATE = true;//scary, submit moves without validating them again

HalmaAI.prototype.computeMove = function() {

	//log("compute move for player "+this.halma.activePlayer);

	var timeBefore = this.getTime();

	var best = this.evaluateBestMove(HalmaAI.MAX_DEPTH, new Array(this.halma.playersCount));

	var move = best[0];

	//log("best move: "+repr(move)+", score: "+repr(best[1])+", nodes Evaluated: "+this.nodeCount+", time: "+(this.getTime()-timeBefore));

	return move;
}


HalmaAI.prototype.getTime = function() {
	return (new Date()).getTime();
}

HalmaAI.prototype.getLastTimeDelta = function() {
	var newTime = (new Date()).getTime();
	var delta = newTime-this.lastTime;
	this.lastTime = newTime;
	return delta;
}

/*
 * return [bestMove, scores]
 */
HalmaAI.prototype.evaluateBestMove = function(depth, maxOverallScores) {

	//log("evaluateBestMove, depth: "+depth+", maxOverallScores: "+repr(maxOverallScores)+", nodeCount: "+this.nodeCount);

	//collect all possible moves for active player
	//OPTIMIZE why collect in array, just evaluate directly
	var allPossibleMoves = [];		

	myMaxOverallScores = map(operator.identity, maxOverallScores);//copy for further evaluation, pruning data for THIS node

	//this.getLastTimeDelta();

	var activePlayer = this.halma.activePlayer;

	var pieces = this.halma.playerConstellation[activePlayer];

	//iterate over all pieces and compute the possible moves...
	for(var p = 0;p< pieces.length; p++) {
		forEach(this.halma.pieceCoordinates[pieces[p]], method(this, function(coords) {
			var x = coords[0];
			var y = coords[1];

			var origin = [x,y];

			var stone = this.halma.getPosition(x,y);
			
			var possibleMoves = [];

			var timeBeforePossible = this.getTime();

			this.halma.collectPossibleMoves([origin], 0, 0, possibleMoves, []);//OPTIMIZE collects too much, maybe could be pruned sooner
			
			//if(HalmaAI.LOG_TIME)log("possible moves for "+repr(origin)+" took "+(this.getTime()-timeBeforePossible));
				//log("possible moves for stone "+repr([x,y])+": "+possibleMoves.length);

			//precalculate distance gain and distance to home base
			//filter some moves already
			forEach(possibleMoves, method(this, function(pMove){
				var extractedMoved = pMove[1];	
				var origin = extractedMoved[0];
				var target = extractedMoved[extractedMoved.length-1];
				
				//estimate score improvement
				var dh = this.halma.getDistanceToDestination(origin[0], origin[1], stone);
				var d = dh - this.halma.getDistanceToDestination(target[0],target[1], stone);
				
				if(HalmaAI.RANDOMIZE_EQUAL_MOVES) {
					dh += Math.random();
				}
					//log("move "+repr(extractedMoved)+", d: "+d);
				if(d >= HalmaAI.MAX_BACKWARDS_STEP){//only consider moves that don't step too far in the wrong direction
					allPossibleMoves.push({move : extractedMoved, delta : d, dHome : dh});
				}
			}));
		}));

	}

	//if no moves found, take a shortcut
	if(allPossibleMoves.length == 0) {
		return [[],this.evaluatePosition()];
	}

	//if(HalmaAI.LOG_TIME)log("finding "+allPossibleMoves.length+" moves took "+this.getLastTimeDelta());

	//logDebug("possibleMoves found: "+allPossibleMoves.length);

	//OPTIMIZE maybe sort the moves to try more promising moves first, as is recommended for alpha/beta pruning
	//sort so that higher delta is first, and stones farther away from home base are listed first
	allPossibleMoves.sort(function(a,b){
		var deltaA = a["delta"];
		var deltaB = b["delta"];
		
		if(deltaA == deltaB){
			//check distance from home
			var dhA = a["dHome"];
			var dhB = b["dHome"];
			
			return dhB - dhA;
		} else {
			return deltaB - deltaA;
		}
	});
	
	//if(HalmaAI.LOG_TIME)log("sorting took "+this.getLastTimeDelta());

	//log("sorted: "+repr(map(function(x){return [x.delta,x.dHome];}, allPossibleMoves)));
	
	var activePlayer = this.halma.activePlayer;

	var bestMove = null;
	var bestScores = null;
	var bestEvaluation;

	//TODO mabe better scores for moves from "far behind"?

	var bestDelta = 0;

	

	loop : for(var i = 0;i < allPossibleMoves.length;i++) {

		var possibleMove = allPossibleMoves[i]; 
		var move = possibleMove["move"];
		var d = possibleMove["delta"];
		var dh = possibleMove["dHome"];
		this.nodeCount++;

		//log("evaluating move "+i+" of "+allPossibleMoves.length+" at depth "+depth+": "+repr(move)+", d: "+d+", dh: "+dh);		

		if(this.nodeCount%100 == 0){
			//log("node count: "+this.nodeCount+", depth: "+depth);
		}

		if(d > bestDelta) {
			bestDelta = d;
		} else if(bestDelta - d >= HalmaAI.CUTOFF_DELTA && HalmaAI.CUTOFF_DELTA > 0) {//prune if some moves MUCH better than others. don't do this if HalmaAI.CUTOFF_DELTA <= 0
			//log("stopped evaluating moves at move "+i+" of "+allPossibleMoves.length+" because of max cutoff delta, difference: "+(bestDelta - d)+", depth: "+depth);
			break loop;
		}

		//var beforeMoveTime = this.getTime();

		this.halma.doMove(move, HalmaAI.DONT_VALIDATE);
		
		var scores;

		if(depth > 0 && this.halma.winner == null){
			scores = this.evaluateBestMove(depth-1, myMaxOverallScores)[1];
		} else {
			scores = this.evaluatePosition();
		}

		//if(scores == null) {
		//	logDebug("scores: "+scores+", depth: "+depth+", halma: "+this.halma+", winner: "+this.halma.winner+", halma.scores: "+this.halma.scores+", last Move: "+repr(this.halma.history[this.halma.history.length-1]));
		//}

		var evaluation = scores[activePlayer];//TODO maybe better evaluate score of each player, useful in parent node?

		//TODO better evaluation function;

		//subtract distance to next best player from evaluation - distance to competition is most important...

		//var differences = map(function(x){return evaluation-x;},scores);

		//for(var j = 0;j< scores.length;j++){
			
		//}

		if(bestMove == null || evaluation > bestEvaluation) {
			//log("new best move: "+repr(move)+", evaluation: "+evaluation+" at depth "+depth);
			bestMove = move;
			bestEvaluation = evaluation;
			bestScores = scores;
		}

		this.halma.undoLastMove();

		//if(HalmaAI.LOG_TIME)log("evaluating move "+i+" at depth "+depth+" took "+(this.getTime()-beforeMoveTime));

		//pruning
		//theory: remember best evaluation for current player from other branches
		//stop looking if branch is worse...

		if(maxOverallScores[activePlayer] && maxOverallScores[activePlayer] >= evaluation) {
			//prune - can it really be that simple??
			//log("pruned at depth "+depth+" (player "+activePlayer+"), nodeCount: "+this.nodeCount+", maxScores: "+repr(maxOverallScores)+", current eval: "+evaluation);
			break loop;
		}

		if(!myMaxOverallScores[activePlayer] || evaluation > myMaxOverallScores[activePlayer]){
			myMaxOverallScores[activePlayer] = evaluation;
			//log("updated myMaxOVerallScores: "+repr(myMaxOverallScores)+", maxOverallScores: "+repr(maxOverallScores));
		} 

		
	}

	return [bestMove, bestScores];
}

HalmaAI.prototype.evaluatePosition = function() {
	var s = map(partial(operator.mul,-1), this.halma.scores);
	//if(s == null) {
	//	logDebug("s null, this.halma.scores: "+repr(this.halma.scores)+", this: "+this);
	//}
	return s;
}