Expectimax implementation.
"use strict";
var ai = {};
ai.dirs = ["up", "down", "left", "right"];
// 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.
////////////////////////////////////////////////////////////////
// Random AI.
////////////////////////////////////////////////////////////////
ai.random = function(brdEngine) {
this.brdEngine = brdEngine;
}
ai.random.prototype.analyse = function(brd) {
var origBrd = new this.brdEngine(brd);
while (true) {
var rnd = Math.floor(Math.random()*4);
if (origBrd[["canUp", "canDown", "canLeft", "canRight"][rnd]]())
return ["up", "down", "left", "right"][rnd];
}
}
/* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */
ai.random.prototype.cleanup = function() { }
////////////////////////////////////////////////////////////////
// 1 level deep on max scores.
////////////////////////////////////////////////////////////////
ai.nextMaxScore = function(brdEngine) {
this.brdEngine = brdEngine;
}
ai.nextMaxScore.prototype.analyse = function(brd) {
var origBrd = new this.brdEngine(brd);
var nextBrd = new this.brdEngine();
var maxScore = -1;
var bestDir;
for (var i = 0; i < ai.dirs.length; i++) {
var dir = ai.dirs[i];
if (origBrd[dir](nextBrd)) {
var score = nextBrd.score();
if (maxScore < score) {
bestDir = dir;
maxScore = score;
}
}
}
return bestDir;
}
/* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */
ai.nextMaxScore.prototype.cleanup = function() { }
////////////////////////////////////////////////////////////////
// 1 level deep on max value.
////////////////////////////////////////////////////////////////
ai.nextMaxValue = function(brdEngine) {
this.brdEngine = brdEngine;
}
ai.nextMaxValue.prototype.analyse = function(brd) {
var origBrd = new this.brdEngine(brd);
var nextBrd = new this.brdEngine();
var maxMax = -1;
var bestDir;
for (var i = 0; i < ai.dirs.length; i++) {
var dir = ai.dirs[i];
if (origBrd[dir](nextBrd)) {
var max = nextBrd.score();
if (maxMax < max) {
maxMax = max;
bestDir = dir;
}
}
}
return bestDir;
}
/* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */
ai.nextMaxScore.prototype.cleanup = function() { }
////////////////////////////////////////////////////////////////
// N level deep on score value without random simulation.
////////////////////////////////////////////////////////////////
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.
////////////////////////////////////////////////////////////////
/* cfg.cornerBonus - value to add if max value at corner. */
/* cfg.edgeBonus - value to add if max value at edge. */
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.
////////////////////////////////////////////////////////////////
/* cfg.cornerBonus - value to add if max value at corner. */
/* cfg.edgeBonus - value to add if max value at edge. */
ai.expectimax = function(brdEngine, cfg) {
this.brdEngine = brdEngine;
this.cfg = cfg || {};
this.cfg.balance = this.cfg.balance || .9;
if (!this.cfg.depth || this.cfg.depth < 0 || 8 <= this.cfg.depth)
this.cfg.depth = 5;
this.cfg.cornerBonus = this.cfg.cornerBonus || 20000;
this.cfg.edgeBonus = this.cfg.edgeBonus || 100;
this.cfg.freeBonus = this.cfg.edgeBonus || 100;
this.cfg.weightPriority = this.cfg.weightPriority || 10;
}
ai.expectimax.prototype.lvl1Score = 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.expectimax.prototype.lvlnScore = 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.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)) {
nextScore = this.lvl1Score(nextBrd);
var weight = this.weight(nextBrd, 0);
// console.log("dir: %o, prevScore: %o, nextScore: %o, maxWeight: %o, weight: %o", dir, prevScore, nextScore, maxWeight, weight);
if (maxWeight + this.cfg.weightPriority < weight || (maxWeight <= weight && prevScore < nextScore)) {
prevScore = nextScore;
maxWeight = weight;
bestDir = dir;
}
}
}
this.cleanup();
return bestDir;
}
ai.expectimax.prototype.weight = function(brd, depth) {
if (depth === this.cfg.depth)
return this.lvlnScore(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.weight(nextBrd, depth+1);
n++;
}
}
if (n > 0)
w = w / n;
weight += this.cfg.balance * w;
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.weight(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 = [];
}