# HG changeset patch
# User Oleksandr Gavenko <gavenkoa@gmail.com>
# Date 1435795390 -10800
# Node ID 87479ae5688963d6314cf36d515e3f3ef2574de3
# Parent  f2c55c5744abed3427d844588cf1609738602cb4
Basic Monte Carlo AI.

diff -r f2c55c5744ab -r 87479ae56889 2048.html
--- a/2048.html	Thu Jul 02 03:02:38 2015 +0300
+++ b/2048.html	Thu Jul 02 03:03:10 2015 +0300
@@ -291,6 +291,16 @@
           <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="100"/> simulations
+        </div>
+      </div>
     </div>
   </div>
 
@@ -799,6 +809,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 f2c55c5744ab -r 87479ae56889 ai.js
--- a/ai.js	Thu Jul 02 03:02:38 2015 +0300
+++ b/ai.js	Thu Jul 02 03:03:10 2015 +0300
@@ -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,73 @@
 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};
+/** 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 brd.freeCnt();
+    }
+    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;
+}
+/* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */
+ai.MonteCarlo.prototype.cleanup = function() {
+}
+