--- a/2048.html Wed Jun 10 21:57:38 2015 -0500
+++ b/2048.html Fri Jul 03 22:21:05 2015 -0500
@@ -291,6 +291,25 @@
<input type="text" name="freeCells" class="positive" pattern="[1-9][0-9]?" value="8"/> free cells
</div>
</div>
+ <div class="ai wide control" id="ai-monte-carlo">
+ <button class="ai">enable</button>
+ <h5>Monte Carlo</h5>
+ <div class="option">
+ <input type="text" name="maxDepth" class="positive" pattern="[0-9]*" value="5"/> depth limit
+ </div>
+ <div class="option">
+ <input type="text" name="simulations" class="positive" pattern="[0-9]*" value="20"/> simulations
+ </div>
+ <div class="option">
+ <input type="text" name="cornerBonus" class="positive" pattern="[0-9]*[.]?[0-9]*" value="0"/> max value at corner bonus
+ </div>
+ <div class="option">
+ <input type="text" name="edgeBonus" class="positive" pattern="[0-9]*[.]?[0-9]*" value="0"/> max value at edge bonus
+ </div>
+ <div class="option">
+ <input type="text" name="freeBonus" class="positive" pattern="[0-9]*[.]?[0-9]*" value="1"/> free cell coefficient
+ </div>
+ </div>
</div>
</div>
@@ -799,6 +818,10 @@
var cfg = ui.ai.parseCfg(aiDom);
return new ai.survive(ui.brdEngine, cfg);
},
+ "ai-monte-carlo": function(aiDom) {
+ var cfg = ui.ai.parseCfg(aiDom);
+ return new ai.MonteCarlo(ui.brdEngine, cfg);
+ },
// "": function() {
// return new ai.(ui.brdEngine);
// },
--- a/ai.js Wed Jun 10 21:57:38 2015 -0500
+++ b/ai.js Fri Jul 03 22:21:05 2015 -0500
@@ -4,8 +4,19 @@
/** @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 */
@@ -56,14 +67,14 @@
////////////////////////////////////////////////////////////////
/** Blind random AI.
- * @param {Board} brdEngine board engine from board.js
+ * @param {Board} brd board engine from board.js
* @constructor */
-ai.BlindRandom = function(brdEngine) {
- this.brdEngine = brdEngine;
+ai.BlindRandom = function(brd) {
+ this.brd = brd;
}
/** Select best direction for next step. */
ai.BlindRandom.prototype.analyse = function(brd2d) {
- var origBrd = new this.brdEngine(brd2d);
+ var origBrd = new this.brd(brd2d);
while (true) {
var rnd = Math.floor(Math.random()*4);
if (origBrd[ai.canFn[rnd]]())
@@ -89,11 +100,11 @@
*/
/** Blind weight random AI.
- * @param {Board} brdEngine board engine from board.js
+ * @param {Board} brd board engine from board.js
* @param {ai.BlindWeightRandom.cfg} cfg configuration settings
* @constructor */
-ai.BlindWeightRandom = function(brdEngine, cfg) {
- this.brdEngine = brdEngine;
+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;
@@ -104,7 +115,7 @@
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.brdEngine(brd2d);
+ var origBrd = new this.brd(brd2d);
while (true) {
var rnd = Math.random();
if (rnd < this.threshold1)
@@ -136,11 +147,11 @@
*/
/** Blind cycle AI.
- * @param {Board} brdEngine board engine from board.js
+ * @param {Board} brd board engine from board.js
* @param {ai.BlindCycle.cfg} cfg configuration settings
* @constructor */
-ai.BlindCycle = function(brdEngine, cfg) {
- this.brdEngine = brdEngine;
+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;
@@ -155,7 +166,7 @@
}
/** Select best direction for next step. */
ai.BlindCycle.prototype.analyse = function(brd2d) {
- var origBrd = new this.brdEngine(brd2d);
+ var origBrd = new this.brd(brd2d);
this.prevDir = this.prevDir || 0;
if (!this.cfg.whilePossible)
this.prevDir = this.nextDir(this.prevDir);
@@ -190,11 +201,11 @@
*/
/** 1 step deep with * AI.
- * @param {Board} brdEngine board engine from board.js
+ * @param {Board} brd board engine from board.js
* @param {ai.OneStepAhead.cfg} cfg configuration settings
* @constructor */
-ai.OneStepAhead = function(brdEngine, cfg) {
- this.brdEngine = brdEngine;
+ai.OneStepAhead = function(brd, cfg) {
+ this.brd = brd;
this.cfg = ai.copyObj(ai.OneStepAhead.bestCfg);
ai.copyObj(cfg, this.cfg);
}
@@ -216,8 +227,8 @@
}
/** Select best direction for next step. */
ai.OneStepAhead.prototype.analyse = function(brd2d) {
- var origBrd = new this.brdEngine(brd2d);
- var nextBrd = new this.brdEngine();
+ var origBrd = new this.brd(brd2d);
+ var nextBrd = new this.brd();
var maxWeight = -1;
var bestDir;
for (var i = 0; i < ai.dirs.length; i++) {
@@ -253,11 +264,11 @@
*/
/** Deep merges AI without random simulation.
- * @param {Board} brdEngine board engine from board.js
+ * @param {Board} brd board engine from board.js
* @param {Object} cfg configuration settings
* @constructor */
-ai.StaticDeepMerges = function(brdEngine, cfg) {
- this.brdEngine = brdEngine;
+ai.StaticDeepMerges = function(brd, cfg) {
+ this.brd = brd;
this.cfg = ai.copyObj(ai.OneStepAhead.bestCfg);
ai.copyObj(cfg, this.cfg);
}
@@ -279,8 +290,8 @@
}
/** Select best direction for next step. */
ai.StaticDeepMerges.prototype.analyse = function(brd2d) {
- var origBrd = new this.brdEngine(brd2d);
- var nextBrd = new this.brdEngine();
+ var origBrd = new this.brd(brd2d);
+ var nextBrd = new this.brd();
var prevScore = -1, nextScore = -1;
var maxWeight = -1;
var bestDir;
@@ -305,7 +316,7 @@
ai.StaticDeepMerges.prototype.evalFn = function(brd) {
var currScore = brd.score();
var maxWeight = currScore;
- var nextBrd = new this.brdEngine();
+ var nextBrd = new this.brd();
for (var i = 0; i < ai.dirs.length; i++) {
if (brd[ai.dirs[i]](nextBrd)) {
var score = nextBrd.score();
@@ -336,11 +347,11 @@
*/
/** N level deep with random simulation.
- * @param {Board} brdEngine board engine from board.js
+ * @param {Board} brd board engine from board.js
* @param {ai.expectimax.cfg} cfg configuration settings
* @constructor */
-ai.expectimax = function(brdEngine, cfg) {
- this.brdEngine = brdEngine;
+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)
@@ -374,8 +385,8 @@
/** Select best direction for next step. */
ai.expectimax.prototype.analyse = function(brd2d) {
this.brdCache = new ai.brdCache();
- var origBrd = new this.brdEngine(brd2d);
- var nextBrd = new this.brdEngine();
+ var origBrd = new this.brd(brd2d);
+ var nextBrd = new this.brd();
var maxW = -1;
var bestDir;
this.cleanup();
@@ -403,8 +414,8 @@
if (wCached)
return wCached;
var wMin = +Infinity;
- var randBoard = new this.brdEngine();
- var nextBrd = new this.brdEngine();
+ 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) {
@@ -453,25 +464,25 @@
*/
/** N level deep with random simulation.
- * @param {Board} brdEngine board engine from board.js
+ * @param {Board} brd board engine from board.js
* @param {ai.survive.cfg} cfg configuration settings
* @constructor */
-ai.survive = function(brdEngine, cfg) {
- this.brdEngine = brdEngine;
+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(brdEngine, ai.survive.altAICfg);
+ 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, weightThreshold: 0};
/** Select best direction for next step. */
ai.survive.prototype.analyse = function(brd2d) {
- var origBrd = new this.brdEngine(brd2d);
- var nextBrd = new this.brdEngine();
+ var origBrd = new this.brd(brd2d);
+ var nextBrd = new this.brd();
var bestW = -2;
var bestDir;
var freeCnt = origBrd.freeCnt();
@@ -495,8 +506,8 @@
if (depth >= this.cfg.maxDepth)
return 0;
var wMin = +Infinity;
- var randBoard = new this.brdEngine();
- var nextBrd = new this.brdEngine();
+ 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++) {
@@ -530,3 +541,86 @@
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 bestW = - 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 w = 0;
+ for (var gameCnt = this.cfg.simulations; gameCnt > 0; gameCnt--) {
+ var tmpBrd = nextBrd.copy();
+ w += this.play(tmpBrd, this.cfg.maxDepth);
+ }
+ if (w > bestW) {
+ bestW = w;
+ 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) {
+ var w = 0;
+ if (this.cfg.freeBonus > 0)
+ w += this.cfg.freeBonus * brd.freeCnt();
+ var max = brd.maxVal();
+ if (max > 7) {
+ if (this.cfg.cornerBonus > 0 && brd.atCorner(max))
+ w += this.cfg.cornerBonus;
+ if (this.cfg.edgeBonus > 0 && brd.atEdge(max))
+ w += this.cfg.edgeBonus;
+ }
+ return w;
+}
+/* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */
+ai.MonteCarlo.prototype.cleanup = function() {
+}
+
--- a/board.js Wed Jun 10 21:57:38 2015 -0500
+++ b/board.js Fri Jul 03 22:21:05 2015 -0500
@@ -915,14 +915,14 @@
ca: 0, cb: 0, cc: 0, cd: 0,
da: 0, db: 0, dc: 0, dd: 0 };
}
-BoardObj.arrMap = [["aa", "ab", "ac", "ad"], ["ba", "bb", "bc", "bd"], ["ca", "cb", "cc", "cd"], ["da", "db", "dc", "dd"]];
+BoardObj.dim2Map = [["aa", "ab", "ac", "ad"], ["ba", "bb", "bc", "bd"], ["ca", "cb", "cc", "cd"], ["da", "db", "dc", "dd"]];
/** Get [i][j] element. */
BoardObj.prototype.get = function(i, j) {
- return this.brd[BoardObj.arrMap[i][j]];
+ return this.brd[BoardObj.dim2Map[i][j]];
}
/** Set [i][j] element. */
BoardObj.prototype.set = function(i, j, val) {
- this.brd[BoardObj.arrMap[i][j]] = val;
+ this.brd[BoardObj.dim2Map[i][j]] = val;
}
/* Return and optionally fill 2d board.
* Doesn't designed to be efficient. */
@@ -989,6 +989,25 @@
if (brd.da === 0) cnt++; if (brd.db === 0) cnt++; if (brd.dc === 0) cnt++; if (brd.dd === 0) cnt++;
return cnt;
}
+BoardObj.indexes = ["aa", "ab", "ac", "ad", "ba", "bb", "bc", "bd", "ca", "cb", "cc", "cd", "da", "db", "dc", "dd"];
+/** Put random value to free cell uniformly. */
+BoardObj.prototype.rnd = function(val) {
+ var brd = this.brd;
+ var idx;
+ var free = 0;
+ for (var i = BoardObj.indexes.length-1; i >= 0; i--) {
+ var idx = BoardObj.indexes[i];
+ if (brd[idx] === 0) {
+ free++;
+ if (Math.random()*free < 1)
+ idx = i;
+ }
+ }
+ if (free === 0)
+ throw new Error('There are no free space...');
+ brd[idx] = val;
+}
+
BoardObj.scoreLookup = [0]; // [ 0, 4, 16, 48, 128, 320, 768, 1792, 4096, 9216, 20480, 45056, 98304];
(function() {
for (var i = 1; i < 16; i++)