--- a/2048.html Sat Jun 27 00:07:18 2015 -0500
+++ b/2048.html Fri Jul 03 22:31:58 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 Sat Jun 27 00:07:18 2015 -0500
+++ b/ai.js Fri Jul 03 22:31:58 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 */
@@ -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 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);
+ }
+ 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) {
+ var utility = 0;
+ if (this.cfg.freeBonus > 0)
+ utility += this.cfg.freeBonus * brd.freeCnt();
+ var max = brd.maxVal();
+ if (max > 7) {
+ if (this.cfg.cornerBonus > 0 && brd.atCorner(max))
+ utility += this.cfg.cornerBonus;
+ if (this.cfg.edgeBonus > 0 && brd.atEdge(max))
+ utility += this.cfg.edgeBonus;
+ }
+ return utility;
+}
+/* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */
+ai.MonteCarlo.prototype.cleanup = function() {
+}
+
--- a/board.js Sat Jun 27 00:07:18 2015 -0500
+++ b/board.js Fri Jul 03 22:31:58 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++)