Rename AI.
"use strict";
/** @fileOverview AI modules. */
/** @module */
var ai = {};
/** Directions. @constant */
ai.dirs = ["up", "right", "down", "left"];
/** Possible direction function names. @constant */
ai.canDirs = ["canUp", "canRight", "canDown", "canLeft"];
/** 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;
}
// 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} brdEngine board engine from board.js
* @constructor */
ai.BlindRandom = function(brdEngine) {
this.brdEngine = brdEngine;
}
ai.BlindRandom.prototype.analyse = function(brd) {
var origBrd = new this.brdEngine(brd);
while (true) {
var rnd = Math.floor(Math.random()*4);
if (origBrd[ai.canDirs[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() { }
////////////////////////////////////////////////////////////////
// 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} brdEngine board engine from board.js
* @param {ai.BlindWeightRandom.cfg} cfg configuration settings
* @constructor */
ai.BlindWeightRandom = function(brdEngine, cfg) {
this.brdEngine = brdEngine;
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, down: 10, right: 5, up: 1 };
ai.BlindWeightRandom.prototype.analyse = function(brd) {
var origBrd = new this.brdEngine(brd);
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.canDirs[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} brdEngine board engine from board.js
* @param {ai.BlindCycle.cfg} cfg configuration settings
* @constructor */
ai.BlindCycle = function(brdEngine, cfg) {
this.brdEngine = brdEngine;
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.canDirs = ["canLeft", "canDown", "canRight", "canUp"];
ai.BlindCycle.prototype.nextDir = function(dir) {
if (this.cfg.clockwise)
return (dir + (4-1)) % 4;
else
return (dir + 1) % 4;
}
ai.BlindCycle.prototype.analyse = function(brd) {
var origBrd = new this.brdEngine(brd);
this.prevDir = this.prevDir || 0;
if (!this.cfg.whilePossible)
this.prevDir = this.nextDir(this.prevDir);
while (true) {
if (origBrd[ai.BlindCycle.canDirs[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 weight 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 weight 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 foe each free cell
*/
/** 1 step deep with * AI.
* @param {Board} brdEngine board engine from board.js
* @param {ai.OneStepAhead.cfg} cfg configuration settings
* @constructor */
ai.OneStepAhead = function(brdEngine, cfg) {
this.brdEngine = brdEngine;
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.weight = function(brd) {
var weight = 0;
if (this.cfg.scoreCoef > 0)
weight += this.cfg.scoreCoef * brd.score();
var max = brd.max();
if (this.cfg.maxValCoef > 0)
weight += this.cfg.maxValCoef * max;
if (this.cfg.cornerBonus > 0 && brd.atCorner(max))
weight += this.cfg.cornerBonus;
if (this.cfg.edgeBonus > 0 && brd.atEdge(max))
weight += this.cfg.edgeBonus;
if (this.cfg.freeBonus > 0)
weight += this.cfg.freeBonus * brd.free();
return weight;
}
ai.OneStepAhead.prototype.analyse = function(brd) {
var origBrd = new this.brdEngine(brd);
var nextBrd = new this.brdEngine();
var maxWeight = -1;
var bestDir;
for (var i = 0; i < ai.dirs.length; i++) {
var dir = ai.dirs[i];
if (origBrd[dir](nextBrd)) {
var weight = this.weight(nextBrd);
if (maxWeight < weight) {
bestDir = dir;
maxWeight = weight;
}
}
}
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.
////////////////////////////////////////////////////////////////
/** N level deep on score value without random simulation.
* @param {Board} brdEngine board engine from board.js
* @constructor */
ai.DeepMaxScore = function(brdEngine) {
this.brdEngine = brdEngine;
}
ai.DeepMaxScore.prototype.analyse = function(brd) {
var origBrd = new this.brdEngine(brd);
var nextBrd = new this.brdEngine();
var prevScore = -1, nextScore = -1;
var maxScore = -1;
var bestDir;
for (var i = 0; i < ai.dirs.length; i++) {
var dir = ai.dirs[i];
if (origBrd[dir](nextBrd)) {
nextScore = nextBrd.score();
var score = this.bestScore(nextBrd);
// console.log("dir: %o, prevScore: %o, nextScore: %o, maxScore: %o, score: %o", dir, prevScore, nextScore, maxScore, score);
if (maxScore < score || (maxScore === score && prevScore < nextScore)) {
prevScore = nextScore;
maxScore = score;
bestDir = dir;
}
}
}
return bestDir;
}
ai.DeepMaxScore.prototype.bestScore = function(brd, seenBrds) {
if (seenBrds) {
for (var i = 0; i < seenBrds.length; i++)
if (brd.equals(seenBrds[i]))
return 0;
} else {
seenBrds = [];
}
seenBrds.push(brd);
var currScore = brd.score();
var maxScore = currScore;
var nextBrd = new this.brdEngine();
for (var i = 0; i < ai.dirs.length; i++) {
if (brd[ai.dirs[i]](nextBrd)) {
var score = nextBrd.score();
if (score > currScore)
maxScore = Math.max(maxScore, this.bestScore(nextBrd, seenBrds));
}
}
return maxScore;
}
/* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */
ai.DeepMaxScore.prototype.cleanup = function() { }
////////////////////////////////////////////////////////////////
// N level deep on score value + max value prefer corner,
// without random simulation.
////////////////////////////////////////////////////////////////
/**
* Defines coefficient for linear resulted weight function.
* @name ai.DeepMaxScoreCorner.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 foe each free cell
*/
/** N level deep AI without random simulation.
* @param {Board} brdEngine board engine from board.js
* @param {Object} cfg configuration settings
* @constructor */
ai.DeepMaxScoreCorner = function(brdEngine, cfg) {
this.brdEngine = brdEngine;
this.cfg = cfg || {};
this.cfg.cornerBonus = this.cfg.cornerBonus || 20000;
this.cfg.edgeBonus = this.cfg.edgeBonus || 100;
this.cfg.freeBonus = this.cfg.edgeBonus || 100;
}
ai.DeepMaxScoreCorner.prototype.scoreCorner = function(brd) {
var score = brd.score();
var max = brd.max();
if (brd.atCorner(max))
score += this.cfg.cornerBonus;
else if (brd.atEdge(max))
score += this.cfg.edgeBonus;
score += brd.free() * this.cfg.freeBonus;
return score;
}
ai.DeepMaxScoreCorner.prototype.scoreEdge = function(brd) {
var score = brd.score();
var max = brd.max();
if (brd.atEdge(max))
score += this.cfg.edgeBonus;
score += brd.free() * this.cfg.freeBonus;
return score;
}
ai.DeepMaxScoreCorner.prototype.analyse = function(brd) {
var origBrd = new this.brdEngine(brd);
var nextBrd = new this.brdEngine();
var prevScore = -1, nextScore = -1;
var maxScore = -1;
var bestDir;
for (var i = 0; i < ai.dirs.length; i++) {
var dir = ai.dirs[i];
if (origBrd[dir](nextBrd)) {
nextScore = this.scoreCorner(nextBrd);
var score = this.bestScore(nextBrd);
// console.log("dir: %o, prevScore: %o, nextScore: %o, maxScore: %o, score: %o", dir, prevScore, nextScore, maxScore, score);
if (maxScore < score || (maxScore === score && prevScore < nextScore)) {
prevScore = nextScore;
maxScore = score;
bestDir = dir;
}
}
}
return bestDir;
}
ai.DeepMaxScoreCorner.prototype.bestScore = function(brd, seenBrds) {
if (seenBrds) {
for (var i = 0; i < seenBrds.length; i++)
if (brd.equals(seenBrds[i]))
return 0;
} else {
seenBrds = [];
}
seenBrds.push(brd);
var currScore = this.scoreEdge(brd);
var maxScore = currScore;
var nextBrd = new this.brdEngine();
for (var i = 0; i < ai.dirs.length; i++) {
if (brd[ai.dirs[i]](nextBrd)) {
var score = this.scoreEdge(nextBrd);
if (score > currScore)
maxScore = Math.max(maxScore, this.bestScore(nextBrd, seenBrds));
}
}
return maxScore;
}
/* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */
ai.DeepMaxScoreCorner.prototype.cleanup = function() { }
////////////////////////////////////////////////////////////////
// N level deep with random simulation.
////////////////////////////////////////////////////////////////
/**
* Defines coefficient for linear resulted weight 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 foe each free cell
*/
/** N level deep with random simulation.
* @param {Board} brdEngine board engine from board.js
* @param {ai.expectimax.cfg} cfg configuration settings
* @constructor */
ai.expectimax = function(brdEngine, cfg) {
this.brdEngine = brdEngine;
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 || 8 <= this.cfg.depth)
this.cfg.depth = ai.expectimax.bestCfg.depth;
}
ai.expectimax.bestCfg = {balance: .9, depth: 3, scoreCoef: 1, maxValCoef: 0, cornerBonus: 0, edgeBonus: 0, freeBonus: 0, weightPriority: 10};
ai.expectimax.prototype.weight = function(brd) {
var score = 0;
if (this.cfg.scoreCoef > 0)
score += this.cfg.scoreCoef * brd.score();
var max = brd.max();
if (this.cfg.maxValCoef > 0)
score += this.cfg.maxValCoef * max;
if (this.cfg.cornerBonus > 0)
if (brd.atCorner(max))
score += this.cfg.cornerBonus;
if (this.cfg.edgeBonus > 0)
if (brd.atEdge(max))
score += this.cfg.edgeBonus;
if (this.cfg.freeBonus > 0)
score += this.cfg.freeBonus * brd.free();
return score;
}
ai.expectimax.prototype.analyse = function(brd) {
var origBrd = new this.brdEngine(brd);
var nextBrd = new this.brdEngine();
var prevScore = -1, nextScore = -1;
var maxWeight = -1;
var bestDir;
this.cleanup();
for (var i = 0; i < ai.dirs.length; i++) {
var dir = ai.dirs[i];
if (origBrd[dir](nextBrd)) {
var weight = this.recWeight(nextBrd, 1);
var ok = (weight - maxWeight) > this.cfg.weightPriority;
if ( ! ok && maxWeight <= weight) {
nextScore = this.weight(nextBrd);
ok = prevScore < nextScore;
}
if (ok) {
prevScore = nextScore;
maxWeight = weight;
bestDir = dir;
}
}
}
this.cleanup();
return bestDir;
}
ai.expectimax.prototype.recWeight = function(brd, depth) {
if (depth >= this.cfg.depth)
return this.weight(brd);
if (this.cache[depth]) {
var cache = this.cache[depth];
for (var i = cache.length-1; i >= 0; i--) {
if (brd.equals(cache[i].brd))
return cache[i].weight;
}
} else {
this.cache[depth] = [];
}
var weight = 0;
var free = 0;
for (var i = 0; i < 3; i++) {
for (var j = 0; j < 3; j++) {
if (brd.get(i, j) === 0) {
var randBoard = brd.copy();
randBoard.set(i, j, 1);
var nextBrd = new this.brdEngine();
var n = 0, w = 0;
for (var diri = 0; diri < ai.dirs.length; diri++) {
if (randBoard[ai.dirs[diri]](nextBrd)) {
w += this.recWeight(nextBrd, depth+1);
n++;
}
}
if (n > 0)
w = w / n;
weight += this.cfg.balance * w;
if (this.cfg.balance < 1) {
randBoard.set(i, j, 2);
var n = 0, w = 0;
for (var diri = 0; diri < ai.dirs.length; diri++) {
if (randBoard[ai.dirs[diri]](nextBrd)) {
w += this.recWeight(nextBrd, depth+1);
n++;
}
}
if (n > 0)
w = w / n;
weight += this.cfg.balance * w;
}
free++;
}
}
}
if (free > 0)
weight = weight / free;
this.cache[depth].push({brd: brd, weight: weight});
return weight;
}
/* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */
ai.expectimax.prototype.cleanup = function() {
this.cache = [];
}