# HG changeset patch
# User Oleksandr Gavenko <gavenkoa@gmail.com>
# Date 1410121811 -10800
# Node ID 9b49e710f5a747a2bad6e399ab085d16bd5c06ce
# Parent  b3bfa9d1b53723905288cd9676374a0cd2a00a04
Add "N level deep on score value without random" AI.
Fix nextMaxScore and nextMaxValue AI.

diff -r b3bfa9d1b537 -r 9b49e710f5a7 2048.html
--- a/2048.html	Sun Sep 07 14:16:26 2014 +0300
+++ b/2048.html	Sun Sep 07 23:30:11 2014 +0300
@@ -87,6 +87,7 @@
       <button id="ai-random">random</button>
       <button id="ai-next-max-score">next max score</button>
       <button id="ai-next-max-value">next max value</button>
+      <button id="ai-deep-max-score">deep max score</button>
     </div>
   </div>
 
@@ -293,6 +294,9 @@
     document.getElementById("ai-next-max-value").addEventListener("click", function() {
       ui.ai = new ai.nextMaxValue(ui.brdEngine);
     });
+    document.getElementById("ai-deep-max-score").addEventListener("click", function() {
+      ui.ai = new ai.deepMaxScore(ui.brdEngine);
+    });
 
   </script>
   
diff -r b3bfa9d1b537 -r 9b49e710f5a7 ai.js
--- a/ai.js	Sun Sep 07 14:16:26 2014 +0300
+++ b/ai.js	Sun Sep 07 23:30:11 2014 +0300
@@ -40,28 +40,25 @@
     var maxScore = -1;
     var action;
     if (origBrd.up(nextBrd)) {
-        maxScore = board.score(tmpBrd).score;
+        maxScore = nextBrd.score();
         action = "up";
     }
-    board.copy(brd, tmpBrd);
-    if (board.move.left(tmpBrd)) {
-        var score = board.score(tmpBrd).score;
+    if (origBrd.left(nextBrd)) {
+        var score = nextBrd.score();
         if (maxScore < score) {
             action = "left";
             maxScore = score;
         }
     }
-    board.copy(brd, tmpBrd);
-    if (board.move.down(tmpBrd)) {
-        var score = board.score(tmpBrd).score;
+    if (origBrd.down(nextBrd)) {
+        var score = nextBrd.score();
         if (maxScore < score) {
             action = "down";
             maxScore = score;
         }
     }
-    board.copy(brd, tmpBrd);
-    if (board.move.right(tmpBrd)) {
-        var score = board.score(tmpBrd).score;
+    if (origBrd.right(nextBrd)) {
+        var score = nextBrd.score();
         if (maxScore < score) {
             action = "right";
             maxScore = score;
@@ -82,33 +79,30 @@
     this.brdEngine = brdEngine;
 }
 ai.nextMaxValue.prototype.analyse = function(brd) {
-    var tmpBrd = board.create();
-    board.copy(brd, tmpBrd);
+    var origBrd = new this.brdEngine(brd);
+    var nextBrd = new this.brdEngine();
     var maxMax = -1;
     var action;
-    if (board.move.up(tmpBrd)) {
-        maxMax = board.score(tmpBrd).max;
+    if (origBrd.up(nextBrd)) {
+        maxMax = nextBrd.max();
         action = "up";
     }
-    board.copy(brd, tmpBrd);
-    if (board.move.left(tmpBrd)) {
-        var max = board.score(tmpBrd).max;
+    if (origBrd.left(nextBrd)) {
+        var max = nextBrd.score();
         if (maxMax < max) {
             action = "left";
             maxMax = max;
         }
     }
-    board.copy(brd, tmpBrd);
-    if (board.move.down(tmpBrd)) {
-        var max = board.score(tmpBrd).max;
+    if (origBrd.down(nextBrd)) {
+        var max = nextBrd.max();
         if (maxMax < max) {
             action = "down";
             maxMax = max;
         }
     }
-    board.copy(brd, tmpBrd);
-    if (board.move.right(tmpBrd)) {
-        var max = board.score(tmpBrd).max;
+    if (origBrd.right(nextBrd)) {
+        var max = nextBrd.max();
         if (maxMax < max) {
             action = "right";
             maxMax = max;
@@ -119,3 +113,65 @@
 /* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */
 ai.nextMaxScore.prototype.cleanup = function() { }
 
+
+////////////////////////////////////////////////////////////////
+// N level deep on score value without random.
+////////////////////////////////////////////////////////////////
+
+ai.deepMaxScore = function(brdEngine) {
+    this.brdEngine = brdEngine;
+}
+ai.deepMaxScore.prototype.analyse = function(brd) {
+    var origBrd = new this.brdEngine(brd);
+    var nextBrd = new this.brdEngine();
+    var maxScore = -1;
+    var action;
+    if (origBrd.up(nextBrd)) {
+        maxScore = this.bestScore(nextBrd);
+        action = "up";
+    }
+    if (origBrd.left(nextBrd)) {
+        var score = this.bestScore(nextBrd);
+        if (maxScore < score) {
+            action = "left";
+            maxScore = score;
+        }
+    }
+    if (origBrd.down(nextBrd)) {
+        var score = this.bestScore(nextBrd);
+        if (maxScore < score) {
+            action = "down";
+            maxScore = score;
+        }
+    }
+    if (origBrd.right(nextBrd)) {
+        var score = this.bestScore(nextBrd);
+        if (maxScore < score) {
+            action = "right";
+            maxScore = score;
+        }
+    }
+    return action;
+}
+ai.deepMaxScore.prototype.bestScore = function(brd, seenBrds) {
+    if (seenBrds) {
+        for (var i = 0; i < seenBrds.length; i++)
+            if (brd.equals(seenBrds[i]))
+                return 0;
+    } else {
+        seenBrds = [];
+    }
+    seenBrds.push(brd);
+    var maxScore = brd.score();
+    var nextBrd = new this.brdEngine();
+    if (brd.up(nextBrd))
+        maxScore = Math.max(maxScore, this.bestScore(nextBrd, seenBrds) - 1);
+    if (brd.down(nextBrd))
+        maxScore = Math.max(maxScore, this.bestScore(nextBrd, seenBrds) - 1);
+    if (brd.left(nextBrd))
+        maxScore = Math.max(maxScore, this.bestScore(nextBrd, seenBrds) - 1);
+    if (brd.right(nextBrd))
+        maxScore = Math.max(maxScore, this.bestScore(nextBrd, seenBrds) - 1);
+    return maxScore;
+}
+
diff -r b3bfa9d1b537 -r 9b49e710f5a7 board.js
--- a/board.js	Sun Sep 07 14:16:26 2014 +0300
+++ b/board.js	Sun Sep 07 23:30:11 2014 +0300
@@ -59,6 +59,13 @@
 BoardArr2d.prototype.set = function(i, j, val) {
     this.brd[i][j] = val;
 }
+BoardArr2d.prototype.equals = function(brd) {
+    for (var i = 0; i < 4; i++)
+        for (var j = 0; j < 4; j++)
+            if (this.brd[i][j] !== brd.brd[i][j])
+                return false;
+    return true;
+}
 /* Return and optionally fill 2d board. */
 BoardArr2d.prototype.exportTo = function(brd) {
     brd = brd || [[],[],[],[]];
@@ -85,6 +92,15 @@
     }
     return score;
 }
+BoardArr2d.prototype.max = function() {
+    var max = 0;
+    for (var i = 0; i < 4; i++) {
+        for (var j = 0; j < 4; j++) {
+            max = Math.max(max, this.brd[i][j]);
+        }
+    }
+    return max;
+}
 
 BoardArr2d.prototype.canRight = function() {
     for (var i = 0; i < 4; i++) {