# HG changeset patch
# User Oleksandr Gavenko <gavenkoa@gmail.com>
# Date 1435980718 18000
# Node ID 5a17638f0dca96f11b885102fee9799f8cfefdd7
# Parent  cde69b258e85a4626f3557565691e3bb82ccb4ea# Parent  df8e645c3f366c787f345fdacfd78210c9b362c3
merged

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