# HG changeset patch
# User Oleksandr Gavenko <gavenkoa@gmail.com>
# Date 1435980065 18000
# Node ID cde69b258e85a4626f3557565691e3bb82ccb4ea
# Parent  cdde490085008b672fcde33db7e407a886a85df4# Parent  4579c59e7e6b797eda799ac4fc9e6adbdf1c6b5b
merged

diff -r 4579c59e7e6b -r cde69b258e85 2048.html
--- 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);
       // },
diff -r 4579c59e7e6b -r cde69b258e85 ai.js
--- 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() {
+}
+
diff -r 4579c59e7e6b -r cde69b258e85 board.js
--- 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++)