"use strict";

/** @fileOverview AI modules. */

/** @module */
var ai = {};

/** Directions. @constant */
ai.dirs = ["up", "right", "down", "left"];
/** Directions in random order. */
ai.randDirs = function() {
    var idxs = [0, 1, 2, 3];
    for (var i = idxs.length - 1; i > 0; i--) {
        var j = Math.floor(Math.random()*(i+1));
        var swap = idxs[j]; idxs[j] = idxs[i]; idxs[i] = swap;
    }
    return [ai.dirs[idxs[0]], ai.dirs[idxs[1]], ai.dirs[idxs[2]], ai.dirs[idxs[3]]];
}

/** Possible direction check function names ordered by ai.dirs. @constant */
ai.canFn = ["canUp", "canRight", "canDown", "canLeft"];
/** Possible merge function names ordered by ai.dirs. @constant */
ai.mergeFn = ["upMerges", "rightMerges", "downMerges", "leftMerges"];

/** Create empty 'to' if argument missing. */
ai.copyObj = function(from, to) {
    if (to == null || typeof to !== "object")
        to = {};
    if (from == null || typeof from !== "object")
        return to;
    for (var attr in from) {
        if (from.hasOwnProperty(attr))
            to[attr] = from[attr];
    }
    return to;
}

ai.brdCache = function() {
    this.cache = [];
}
ai.brdCache.prototype.get = function(brd) {
    var compr = brd.compress();
    var subCache = this.cache[compr[0]];
    if (subCache) {
        return subCache[compr[1]];
    }
    return undefined;
}
ai.brdCache.prototype.put = function(brd, val) {
    var compr = brd.compress();
    var subCache = this.cache[compr[0]];
    if (subCache) {
        subCache[compr[1]] = val;
    } else {
        this.cache[compr[0]] = [];
        this.cache[compr[0]][compr[1]] = val;
    }
}

// Each strategy is a function that except current board position as 2d array and context from
// previous call to share state/precomputed values between calls.



////////////////////////////////////////////////////////////////
// Blind random AI.
////////////////////////////////////////////////////////////////

/** Blind random AI.
 * @param {Board} brd  board engine from board.js
 * @constructor */
ai.BlindRandom = function(brd) {
    this.brd = brd;
}
/** Select best direction for next step. */
ai.BlindRandom.prototype.analyse = function(brd2d) {
    var origBrd = new this.brd(brd2d);
    while (true) {
        var rnd = Math.floor(Math.random()*4);
        if (origBrd[ai.canFn[rnd]]())
            return ai.dirs[rnd];
    }
}
/* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */
ai.BlindRandom.prototype.cleanup = function() { }



////////////////////////////////////////////////////////////////
// Always up AI.
////////////////////////////////////////////////////////////////

/** Always up AI.
 * @param {Board} brd  board engine from board.js
 * @constructor */
ai.AlwaysUp = function(brd) {
    this.brd = brd;
}
/** Select best direction for next step. */
ai.AlwaysUp.prototype.analyse = function(brd2d) {
    var origBrd = new this.brd(brd2d);
    var nextBrd = new this.brd();
    var tmpBrd = new this.brd();
    if (origBrd.canUp())
        return "up";
    var canRight = origBrd.right(nextBrd);
    if (canRight) {
        var canRightUp = nextBrd.up(tmpBrd);
        var rightScore = tmpBrd.score();
    }
    var canLeft = origBrd.left(nextBrd);
    if (canLeft) {
        var canLeftUp = nextBrd.up(tmpBrd);
        var leftScore = tmpBrd.score();
    }
    if (canRight && canLeft) {
        if (canRightUp && canLeftUp)
            return (rightScore > leftScore) ? "right": "left";
        else if (canRightUp)
            return "right";
        else
            return "left";
    } else if (canRight)
        return "right";
    else if (canLeft)
        return "left";
    return "down";
}
/* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */
ai.AlwaysUp.prototype.cleanup = function() { }



////////////////////////////////////////////////////////////////
// Blind weight random AI.
////////////////////////////////////////////////////////////////

/**
 * @name ai.BlindWeightRandom.cfg
 * @namespace
 * @property {number} left   weight
 * @property {number} right  weight
 * @property {number} up     weight
 * @property {number} down   weight
 */

/** Blind weight random AI.
 * @param {Board} brd  board engine from board.js
 * @param {ai.BlindWeightRandom.cfg} cfg  configuration settings
 * @constructor */
ai.BlindWeightRandom = function(brd, cfg) {
    this.brd = brd;
    this.cfg = ai.copyObj(ai.BlindWeightRandom.bestCfg);
    ai.copyObj(cfg, this.cfg);
    var total = this.cfg.left + this.cfg.right + this.cfg.up + this.cfg.down;
    this.threshold1 = this.cfg.left/total;
    this.threshold2 = (this.cfg.left + this.cfg.down)/total;
    this.threshold3 = (this.cfg.left + this.cfg.down + this.cfg.right)/total;
}
ai.BlindWeightRandom.bestCfg = { left: 1, right: 16, up: 4, down: 8 };
/** Select best direction for next step. */
ai.BlindWeightRandom.prototype.analyse = function(brd2d) {
    var origBrd = new this.brd(brd2d);
    while (true) {
        var rnd = Math.random();
        if (rnd < this.threshold1)
            var dir = 0;
        else if (rnd < this.threshold2)
            var dir = 1;
        else if (rnd < this.threshold3)
            var dir = 2;
        else
            var dir = 3;
        if (origBrd[ai.canFn[dir]]())
            return ai.dirs[dir];
    }
}
/* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */
ai.BlindWeightRandom.prototype.cleanup = function() { }



////////////////////////////////////////////////////////////////
// Blind cycle AI.
////////////////////////////////////////////////////////////////

/**
 * @name ai.BlindCycle.cfg
 * @namespace
 * @property {boolean} whilePossible  move in one direction while possible
 * @property {boolean} down           switch direction clockwise
 */

/** Blind cycle AI.
 * @param {Board} brd  board engine from board.js
 * @param {ai.BlindCycle.cfg} cfg  configuration settings
 * @constructor */
ai.BlindCycle = function(brd, cfg) {
    this.brd = brd;
    this.cfg = cfg || {};
    this.cfg.whilePossible = this.cfg.whilePossible || false;
    this.cfg.clockwise = this.cfg.clockwise || false;
}
ai.BlindCycle.dirs = ["left", "down", "right", "up"];
ai.BlindCycle.canFn = ["canLeft", "canDown", "canRight", "canUp"];
ai.BlindCycle.prototype.nextDir = function(dir) {
    if (this.cfg.clockwise)
        return (dir + (4-1)) % 4;
    else
        return (dir + 1) % 4;
}
/** Select best direction for next step. */
ai.BlindCycle.prototype.analyse = function(brd2d) {
    var origBrd = new this.brd(brd2d);
    this.prevDir = this.prevDir || 0;
    if (!this.cfg.whilePossible)
        this.prevDir = this.nextDir(this.prevDir);
    while (true) {
        if (origBrd[ai.BlindCycle.canFn[this.prevDir]]())
            return ai.BlindCycle.dirs[this.prevDir];
        this.prevDir = this.nextDir(this.prevDir);
    }
}
/* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */
ai.BlindCycle.prototype.cleanup = function() {
    delete this.prevDir;
}



////////////////////////////////////////////////////////////////
// 1 step deep with linear utility function on score, max value,
// bonuses for max value stay at corner or edge and bonuses
// for each free field.
////////////////////////////////////////////////////////////////

/**
 * Defines coefficient for linear resulted utility function.
 * @name ai.OneStepAhead.cfg
 * @namespace
 * @property {number} scoreCoef    multiplicator for score
 * @property {number} maxValCoef   multiplicator for max value
 * @property {number} cornerBonus  bonus for max value at board corner
 * @property {number} edgeBonus    bonus for max value at board edge
 * @property {number} freeBonus    bonus for each free cell
 */

/** 1 step deep with * AI.
 * @param {Board} brd  board engine from board.js
 * @param {ai.OneStepAhead.cfg} cfg  configuration settings
 * @constructor */
ai.OneStepAhead = function(brd, cfg) {
    this.brd = brd;
    this.cfg = ai.copyObj(ai.OneStepAhead.bestCfg);
    ai.copyObj(cfg, this.cfg);
}
ai.OneStepAhead.bestCfg = {scoreCoef: 1, maxValCoef: 0, cornerBonus: 0, edgeBonus: 0, freeBonus: 0};
ai.OneStepAhead.prototype.utility = function(brd) {
    var utility = 0;
    if (this.cfg.scoreCoef > 0)
        utility += this.cfg.scoreCoef * brd.score();
    var max = brd.maxVal();
    if (this.cfg.maxValCoef > 0)
        utility += this.cfg.maxValCoef * max;
    if (this.cfg.cornerBonus > 0 && brd.atCorner(max))
        utility += this.cfg.cornerBonus;
    if (this.cfg.edgeBonus > 0 && brd.atEdge(max))
        utility += this.cfg.edgeBonus;
    if (this.cfg.freeBonus > 0)
        utility += this.cfg.freeBonus * brd.freeCnt();
    return utility;
}
/** Select best direction for next step. */
ai.OneStepAhead.prototype.analyse = function(brd2d) {
    var origBrd = new this.brd(brd2d);
    var nextBrd = new this.brd();
    var maxUtility = -1;
    var bestDir;
    for (var i = 0; i < ai.dirs.length; i++) {
        var dir = ai.dirs[i];
        if (origBrd[dir](nextBrd)) {
            var utility = this.utility(nextBrd);
            if (maxUtility < utility) {
                bestDir = dir;
                maxUtility = utility;
            }
        }
    }
    return bestDir;
}
/* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */
ai.OneStepAhead.prototype.cleanup = function() { }



////////////////////////////////////////////////////////////////
// N level deep on score value without random simulation.
////////////////////////////////////////////////////////////////

/**
 * Defines coefficient for linear resulted utility function.
 * @name ai.StaticDeepMerges.cfg
 * @namespace
 * @property {number} scoreCoef    multiplicator for score
 * @property {number} maxValCoef   multiplicator for max value
 * @property {number} cornerBonus  bonus for max value at board corner
 * @property {number} edgeBonus    bonus for max value at board edge
 * @property {number} freeBonus    bonus for each free cell
 */

/** Deep merges AI without random simulation.
 * @param {Board} brd  board engine from board.js
 * @param {Object} cfg  configuration settings
 * @constructor */
ai.StaticDeepMerges = function(brd, cfg) {
    this.brd = brd;
    this.cfg = ai.copyObj(ai.OneStepAhead.bestCfg);
    ai.copyObj(cfg, this.cfg);
}
ai.StaticDeepMerges.bestCfg = {scoreCoef: 1, maxValCoef: 0, cornerBonus: 0, edgeBonus: 0, freeBonus: 0, utilityThreshold: 10};
ai.StaticDeepMerges.prototype.utility = function(brd) {
    var utility = 0;
    if (this.cfg.scoreCoef > 0)
        utility += this.cfg.scoreCoef * brd.score();
    var max = brd.maxVal();
    if (this.cfg.maxValCoef > 0)
        utility += this.cfg.maxValCoef * max;
    if (this.cfg.cornerBonus > 0 && brd.atCorner(max))
        utility += this.cfg.cornerBonus;
    if (this.cfg.edgeBonus > 0 && brd.atEdge(max))
        utility += this.cfg.edgeBonus;
    if (this.cfg.freeBonus > 0)
        utility += this.cfg.freeBonus * brd.freeCnt();
    return utility;
}
/** Select best direction for next step. */
ai.StaticDeepMerges.prototype.analyse = function(brd2d) {
    var origBrd = new this.brd(brd2d);
    var nextBrd = new this.brd();
    var prevScore = -1, nextScore = -1;
    var maxUtility = -1;
    var bestDir;
    for (var i = 0; i < ai.dirs.length; i++) {
        var dir = ai.dirs[i];
        if (origBrd[dir](nextBrd)) {
            var utility = this.evalFn(nextBrd);
            var ok = (utility - maxUtility) > this.cfg.utilityThreshold;
            if ( ! ok && maxUtility <= utility) {
                nextScore = this.utility(nextBrd);
                ok = prevScore < nextScore;
            }
            if (ok) {
                prevScore = nextScore;
                maxUtility = utility;
                bestDir = dir;
            }
        }
    }
    return bestDir;
}
ai.StaticDeepMerges.prototype.evalFn = function(brd) {
    var currScore = brd.score();
    var maxUtility = currScore;
    var nextBrd = new this.brd();
    for (var i = 0; i < ai.dirs.length; i++) {
        if (brd[ai.dirs[i]](nextBrd)) {
            var score = nextBrd.score();
            if (score > currScore)
                maxUtility = Math.max(maxUtility, this.evalFn(nextBrd));
        }
    }
    return maxUtility;
}
/* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */
ai.StaticDeepMerges.prototype.cleanup = function() { }



////////////////////////////////////////////////////////////////
// N level deep with random simulation.
////////////////////////////////////////////////////////////////

/**
 * Defines coefficient for linear resulted utility function.
 * @name ai.expectimax.cfg
 * @namespace
 * @property {number} scoreCoef    multiplicator for score
 * @property {number} maxValCoef   multiplicator for max value
 * @property {number} cornerBonus  bonus for max value at board corner
 * @property {number} edgeBonus    bonus for max value at board edge
 * @property {number} freeBonus    bonus for each free cell
 */

/** N level deep with random simulation.
 * @param {Board} brd  board engine from board.js
 * @param {ai.expectimax.cfg} cfg  configuration settings
 * @constructor */
ai.expectimax = function(brd, cfg) {
    this.brd = brd;
    this.cfg = ai.copyObj(ai.expectimax.bestCfg);
    ai.copyObj(cfg, this.cfg);
    if (this.cfg.balance <= 0)
        this.cfg.balance = ai.expectimax.bestCfg.balance;
    if ( this.cfg.balance > 1)
        this.cfg.balance = 1;
    if (!this.cfg.depth || this.cfg.depth < 0 || 9 <= this.cfg.depth)
        this.cfg.depth = ai.expectimax.bestCfg.depth;
}
ai.expectimax.bestCfg = {balance: .9, depth: 5, scoreCoef: 1, maxValCoef: 0, cornerBonus: 0, edgeBonus: 0, freeBonus: 0};
ai.expectimax.prototype.utility = function(brd) {
    var score = 0;
    var cfg = this.cfg;
    if (cfg.scoreCoef > 0)
        score += cfg.scoreCoef * brd.score();
    if (cfg.maxValCoef > 0 || cfg.cornerBonus > 0 || cfg.edgeBonus > 0) {
        var max = brd.maxVal();
        if (cfg.maxValCoef > 0)
            score += cfg.maxValCoef * max;
        if (cfg.cornerBonus > 0)
            if (brd.atCorner(max))
                score += cfg.cornerBonus;
        if (cfg.edgeBonus > 0)
            if (brd.atEdge(max))
                score += cfg.edgeBonus;
    }
    if (cfg.freeBonus > 0)
        score += cfg.freeBonus * brd.freeCnt();
    return score;
}
/** Select best direction for next step. */
ai.expectimax.prototype.analyse = function(brd2d) {
    this.brdCache = new ai.brdCache();
    var origBrd = new this.brd(brd2d);
    var nextBrd = new this.brd();
    var maxW = -1;
    var bestDir;
    this.cleanup();
    this.depthLimit = this.cfg.depth;
    var freeCnt = origBrd.freeCnt();
    if (freeCnt >= 6)
        this.depthLimit = Math.min(this.depthLimit, 6 - freeCnt/3);
    for (var i = 0; i < ai.dirs.length; i++) {
        var dir = ai.dirs[i];
        if (origBrd[dir](nextBrd)) {
            var w = this.evalFn(nextBrd, 1);
            if (w > maxW) {
                maxW = w;
                bestDir = dir;
            }
        }
    }
    this.cleanup();
    return bestDir;
}
ai.expectimax.prototype.evalFn = function(brd, depth) {
    if (depth >= this.depthLimit)
        return this.utility(brd);
    var wCached = this.brdCache.get(brd);
    if (wCached)
        return wCached;
    var wMin = +Infinity;
    var randBoard = new this.brd();
    var nextBrd = new this.brd();
    for (var i = 0; i < 3; i++) {
        for (var j = 0; j < 3; j++) {
            if (brd.get(i, j) === 0) {
                brd.copy(randBoard);
                randBoard.set(i, j, 1);
                var wMax2 = 0;
                for (var diri = 0; diri < ai.dirs.length; diri++) {
                    if (randBoard[ai.dirs[diri]](nextBrd))
                        wMax2 = Math.max(wMax2, this.evalFn(nextBrd, depth+1));
                }
                var wMax4 = 0;
                var balance = this.cfg.balance;
                if (balance < 1) {
                    randBoard.set(i, j, 2);
                    for (var diri = 0; diri < ai.dirs.length; diri++) {
                        if (randBoard[ai.dirs[diri]](nextBrd))
                            wMax4 = Math.max(wMax4, this.evalFn(nextBrd, depth+1));
                    }
                }
                wMin = Math.min(wMin, balance * wMax2 + (1 - balance) * wMax4);
            }
        }
    }
    this.brdCache.put(brd, wMin);
    return wMin;
}
/* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */
ai.expectimax.prototype.cleanup = function() {
}



////////////////////////////////////////////////////////////////
// Survive as long as possible.
////////////////////////////////////////////////////////////////

/**
 * Defines coefficient for linear resulted utility function.
 * @name ai.survive.cfg
 * @namespace
 * @property {number} scoreCoef    multiplicator for score
 * @property {number} maxValCoef   multiplicator for max value
 * @property {number} cornerBonus  bonus for max value at board corner
 * @property {number} edgeBonus    bonus for max value at board edge
 * @property {number} freeBonus    bonus for each free cell
 */

/** N level deep with random simulation.
 * @param {Board} brd  board engine from board.js
 * @param {ai.survive.cfg} cfg  configuration settings
 * @constructor */
ai.survive = function(brd, cfg) {
    this.brd = brd;
    this.cfg = ai.copyObj(ai.survive.bestCfg);
    ai.copyObj(cfg, this.cfg);
    if (this.cfg.freeCells <= 0)
        this.cfg.freeCells = ai.survive.bestCfg.freeCells;
    if (!this.cfg.maxDepth || this.cfg.maxDepth < 0 || 20 <= this.cfg.maxDepth)
        this.cfg.maxDepth = ai.survive.bestCfg.maxDepth;
    this.cfg.altAI = new ai.StaticDeepMerges(brd, ai.survive.altAICfg);
}
ai.survive.bestCfg = {freeCells: 8, maxDepth: 5};
ai.survive.altAICfg = {scoreCoef: 1, maxValCoef: 0, cornerBonus: 0, edgeBonus: 0, freeBonus: 0, utilityThreshold: 0};
/** Select best direction for next step. */
ai.survive.prototype.analyse = function(brd2d) {
    var origBrd = new this.brd(brd2d);
    var nextBrd = new this.brd();
    var bestW = -2;
    var bestDir;
    var freeCnt = origBrd.freeCnt();
    if (freeCnt >= this.cfg.freeCells)
        return this.cfg.altAI.analyse(brd2d);
    for (var i = 0; i < ai.dirs.length; i++) {
        var dir = ai.dirs[i];
        if (origBrd[dir](nextBrd)) {
            var w = this.evalFn(nextBrd, 1);
            if (w > bestW) {
                bestW = w;
                bestDir = dir;
            }
        }
    }
    return bestDir;
}
ai.survive.prototype.evalFn = function(brd, depth) {
    if (brd.freeCnt() >= this.cfg.freeCells)
        return 1;
    if (depth >= this.cfg.maxDepth)
        return 0;
    var wMin = +Infinity;
    var randBoard = new this.brd();
    var nextBrd = new this.brd();
exit:
    for (var i = 0; i < 3; i++) {
        for (var j = 0; j < 3; j++) {
            if (brd.get(i, j) !== 0)
                continue;
            brd.copy(randBoard);
            randBoard.set(i, j, 1);
            var wMax = -1;
            for (var diri = 0; diri < ai.dirs.length; diri++) {
                if (randBoard[ai.dirs[diri]](nextBrd)) {
                    var w = this.evalFn(nextBrd, depth+1);
                    if (w === 1) {
                        wMax = 1;
                        break;
                    }
                    wMax = Math.max(wMax, w);
                }
            }
            if (wMax === -1) {
                wMin = -1;
                break exit;
            }
            wMin = Math.min(wMin, wMax);
        }
    }
    if (wMin === +Infinity)
        return -1;
    return wMin;
}
/* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */
ai.survive.prototype.cleanup = function() {
}



////////////////////////////////////////////////////////////////
// MonteCarlo simulations.
////////////////////////////////////////////////////////////////

/**
 * Defines coefficient for linear resulted weight function.
 * @name ai.MonteCarlo.cfg
 * @namespace
 * @property {number} maxDepth     depth limit
 * @property {number} simulations  simulation count limit
 */

/** MonteCarlo simulations.
 * @param {Board} brd  board engine from board.js
 * @param {ai.MonteCarlo.cfg} cfg  configuration settings
 * @constructor */
ai.MonteCarlo = function(brd, cfg) {
    this.brd = brd;
    this.cfg = ai.copyObj(ai.MonteCarlo.bestCfg);
    ai.copyObj(cfg, this.cfg);
    if (this.cfg.simulations <= 0)
        this.cfg.simulations = ai.MonteCarlo.bestCfg.simulations;
    if (!this.cfg.maxDepth || this.cfg.maxDepth <= 0 || 20 <= this.cfg.maxDepth)
        this.cfg.maxDepth = ai.MonteCarlo.bestCfg.maxDepth;
}
ai.MonteCarlo.bestCfg = {simulations: 1000, maxDepth: 20, cornerBonus: 0, edgeBonus: 0, freeBonus: 0};
/** Select best direction for next step. */
ai.MonteCarlo.prototype.analyse = function(brd2d) {
    var origBrd = new this.brd(brd2d);
    var nextBrd = new this.brd();
    var bestUtility = - this.cfg.simulations;
    var bestDir;
    var freeCnt = origBrd.freeCnt();
    for (var i = 0; i < ai.dirs.length; i++) {
        var dir = ai.dirs[i];
        if (origBrd[dir](nextBrd)) {
            var utility = 0;
            for (var gameCnt = this.cfg.simulations; gameCnt > 0; gameCnt--) {
                var tmpBrd = nextBrd.copy();
                utility += this.play(tmpBrd, this.cfg.maxDepth);
            }
            utility /= this.cfg.simulations;

            var max = nextBrd.maxVal();
            if (this.cfg.cornerBonus > 0 && nextBrd.atCorner(max))
                utility += this.cfg.cornerBonus;
            if (this.cfg.edgeBonus > 0 && nextBrd.atEdge(max))
                utility += this.cfg.edgeBonus;

            if (utility > bestUtility) {
                bestUtility = utility;
                bestDir = dir;
            }
        }
    }
    return bestDir;
}
ai.MonteCarlo.prototype.play = function(brd, depth) {
    if (depth <= 0) {
        return this.evalFn(brd);
    }
    brd.rnd(1);
    var dirs = ai.randDirs();
    for (var i = 0; i < 4; i++) {
        var dir = dirs[i];
        var nextBrd = new brd.constructor();
        if (brd[dir](nextBrd)) {
            return this.play(nextBrd, depth-1);
        }
    }
    return -1;
}
ai.MonteCarlo.prototype.evalFn = function(brd) {
    return this.cfg.freeBonus * brd.freeCnt();
}
/* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */
ai.MonteCarlo.prototype.cleanup = function() {
}