# HG changeset patch
# User Oleksandr Gavenko <gavenkoa@gmail.com>
# Date 1410194552 -10800
# Node ID ed0292f0c7c66ba6de86a8b083df52fc6107247b
# Parent  ab294e8db00cdd106a29d229994443dd866e8cff
Expectimax implementation.

diff -r ab294e8db00c -r ed0292f0c7c6 2048.html
--- a/2048.html	Mon Sep 08 17:43:10 2014 +0300
+++ b/2048.html	Mon Sep 08 19:42:32 2014 +0300
@@ -89,6 +89,7 @@
       <button id="ai-next-max-value">next max value</button>
       <button id="ai-deep-max-score">deep max score</button>
       <button id="ai-deep-max-score-corner">deep max score corner</button>
+      <button id="ai-expectimax">expectimax</button>
     </div>
   </div>
 
@@ -358,6 +359,9 @@
     document.getElementById("ai-deep-max-score-corner").addEventListener("click", function() {
       ui.ai = new ai.deepMaxScoreCorner(ui.brdEngine);
     });
+    document.getElementById("ai-expectimax").addEventListener("click", function() {
+      ui.ai = new ai.expectimax(ui.brdEngine);
+    });
 
   </script>
   
diff -r ab294e8db00c -r ed0292f0c7c6 ai.js
--- a/ai.js	Mon Sep 08 17:43:10 2014 +0300
+++ b/ai.js	Mon Sep 08 19:42:32 2014 +0300
@@ -215,3 +215,119 @@
 /* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */
 ai.deepMaxScoreCorner.prototype.cleanup = function() { }
 
+
+////////////////////////////////////////////////////////////////
+// N level deep with random simulation.
+////////////////////////////////////////////////////////////////
+
+/* cfg.cornerBonus - value to add if max value at corner. */
+/* cfg.edgeBonus - value to add if max value at edge. */
+ai.expectimax = function(brdEngine, cfg) {
+    this.brdEngine = brdEngine;
+    this.cfg = cfg || {};
+    this.cfg.balance = this.cfg.balance || .9;
+    if (!this.cfg.depth || this.cfg.depth < 0 || 8 <= this.cfg.depth)
+        this.cfg.depth = 5;
+    this.cfg.cornerBonus = this.cfg.cornerBonus || 20000;
+    this.cfg.edgeBonus = this.cfg.edgeBonus || 100;
+    this.cfg.freeBonus = this.cfg.edgeBonus || 100;
+    this.cfg.weightPriority = this.cfg.weightPriority || 10;
+}
+ai.expectimax.prototype.lvl1Score = function(brd) {
+    var score = brd.score();
+    var max = brd.max();
+    if (brd.atCorner(max))
+        score += this.cfg.cornerBonus;
+    else if (brd.atEdge(max))
+        score += this.cfg.edgeBonus;
+    score += brd.free() * this.cfg.freeBonus;
+    return score;
+}
+ai.expectimax.prototype.lvlnScore = function(brd) {
+    var score = brd.score();
+    // var max = brd.max();
+    // if (brd.atCorner(max))
+    //     score += this.cfg.cornerBonus;
+    // else if (brd.atEdge(max))
+    //     score += this.cfg.edgeBonus;
+    // score += brd.free() * this.cfg.freeBonus;
+    return score;
+}
+ai.expectimax.prototype.analyse = function(brd) {
+    var origBrd = new this.brdEngine(brd);
+    var nextBrd = new this.brdEngine();
+    var prevScore = -1, nextScore = -1;
+    var maxWeight = -1;
+    var bestDir;
+    this.cleanup();
+    for (var i = 0; i < ai.dirs.length; i++) {
+        var dir = ai.dirs[i];
+        if (origBrd[dir](nextBrd)) {
+            nextScore = this.lvl1Score(nextBrd);
+            var weight = this.weight(nextBrd, 0);
+            // console.log("dir: %o, prevScore: %o, nextScore: %o, maxWeight: %o, weight: %o", dir, prevScore, nextScore, maxWeight, weight);
+            if (maxWeight + this.cfg.weightPriority < weight || (maxWeight <= weight && prevScore < nextScore)) {
+                prevScore = nextScore;
+                maxWeight = weight;
+                bestDir = dir;
+            }
+        }
+    }
+    this.cleanup();
+    return bestDir;
+}
+ai.expectimax.prototype.weight = function(brd, depth) {
+    if (depth === this.cfg.depth)
+        return this.lvlnScore(brd);
+    if (this.cache[depth]) {
+        var cache = this.cache[depth];
+        for (var i = cache.length-1; i >= 0; i--) {
+            if (brd.equals(cache[i].brd))
+                return cache[i].weight;
+        }
+    } else {
+        this.cache[depth] = [];
+    }
+    var weight = 0;
+    var free = 0;
+    for (var i = 0; i < 3; i++) {
+        for (var j = 0; j < 3; j++) {
+            if (brd.get(i, j) === 0) {
+                var randBoard = brd.copy();
+                randBoard.set(i, j, 1);
+                var nextBrd = new this.brdEngine();
+                var n = 0, w = 0;
+                for (var diri = 0; diri < ai.dirs.length; diri++) {
+                    if (randBoard[ai.dirs[diri]](nextBrd)) {
+                        w += this.weight(nextBrd, depth+1);
+                        n++;
+                    }
+                }
+                if (n > 0)
+                    w = w / n;
+                weight += this.cfg.balance * w;
+                randBoard.set(i, j, 2);
+                var n = 0, w = 0;
+                for (var diri = 0; diri < ai.dirs.length; diri++) {
+                    if (randBoard[ai.dirs[diri]](nextBrd)) {
+                        w += this.weight(nextBrd, depth+1);
+                        n++;
+                    }
+                }
+                if (n > 0)
+                    w = w / n;
+                weight += this.cfg.balance * w;
+                free++;
+            }
+        }
+    }
+    if (free > 0)
+        weight = weight / free;
+    this.cache[depth].push({brd: brd, weight: weight});
+    return weight;
+}
+/* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */
+ai.expectimax.prototype.cleanup = function() {
+    this.cache = [];
+}
+