# HG changeset patch
# User Oleksandr Gavenko <gavenkoa@gmail.com>
# Date 1411599948 -10800
# Node ID 4dde63ac0bb48ea6f0ed83d0166961d469cd3284
# Parent  23cd36180bf9f36240a6c65fe26c8e0c6d1c74ab
Make fast board cache.

diff -r 23cd36180bf9 -r 4dde63ac0bb4 ai.js
--- a/ai.js	Thu Sep 25 01:10:01 2014 +0300
+++ b/ai.js	Thu Sep 25 02:05:48 2014 +0300
@@ -22,6 +22,28 @@
     return to;
 }
 
+ai.brdCache = function() {
+    this.cache = [];
+}
+ai.brdCache.prototype.get = function(brd) {
+    var compr = brd.compress();
+    var subCache = this.cache[compr[0]];
+    if (subCache) {
+        return subCache[compr[1]];
+    }
+    return undefined;
+}
+ai.brdCache.prototype.put = function(brd, val) {
+    var compr = brd.compress();
+    var subCache = this.cache[compr[0]];
+    if (subCache) {
+        subCache[compr[1]] = val;
+    } else {
+        this.cache[compr[0]] = [];
+        this.cache[compr[0]][compr[1]] = val;
+    }
+}
+
 // Each strategy is a function that except current board position as 2d array and context from
 // previous call to share state/precomputed values between calls.
 
@@ -343,6 +365,7 @@
     return score;
 }
 ai.expectimax.prototype.analyse = function(brd) {
+    this.brdCache = new ai.brdCache();
     var origBrd = new this.brdEngine(brd);
     var nextBrd = new this.brdEngine();
     var maxW = -1;
@@ -368,15 +391,9 @@
 ai.expectimax.prototype.evalFn = function(brd, depth) {
     if (depth >= this.depthLimit)
         return this.weight(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 wCached = this.brdCache.get(brd);
+    if (wCached)
+        return wCached;
     var wMin = +Infinity;
     for (var i = 0; i < 3; i++) {
         for (var j = 0; j < 3; j++) {
@@ -402,11 +419,10 @@
             }
         }
     }
-    this.cache[depth].push({brd: brd, weight: wMin});
+    this.brdCache.put(brd, wMin);
     return wMin;
 }
 /* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */
 ai.expectimax.prototype.cleanup = function() {
-    this.cache = [];
 }
 
diff -r 23cd36180bf9 -r 4dde63ac0bb4 board.js
--- a/board.js	Thu Sep 25 01:10:01 2014 +0300
+++ b/board.js	Thu Sep 25 02:05:48 2014 +0300
@@ -119,6 +119,26 @@
 }
 /** Compare boards. */
 BoardArr2d.prototype.equals = BoardArr2d.prototype.equals_unrolled;
+BoardArr2d.prototype.compress = function() {
+    var brd = this.brd;
+    var h1 = brd[0][0];
+    h1 = (h1 << 4) | brd[0][1];
+    h1 = (h1 << 4) | brd[0][2];
+    h1 = (h1 << 4) | brd[0][3];
+    h1 = (h1 << 4) | brd[1][0];
+    h1 = (h1 << 4) | brd[1][1];
+    h1 = (h1 << 4) | brd[1][2];
+    h1 = (h1 << 4) | brd[1][3];
+    var h2 = brd[2][0];
+    h2 = (h2 << 4) | brd[2][1];
+    h2 = (h2 << 4) | brd[2][2];
+    h2 = (h2 << 4) | brd[2][3];
+    h2 = (h2 << 4) | brd[3][0];
+    h2 = (h2 << 4) | brd[3][1];
+    h2 = (h2 << 4) | brd[3][2];
+    h2 = (h2 << 4) | brd[3][3];
+    return [h1, h2];
+}
 
 /* Return and optionally fill 2d board. */
 BoardArr2d.prototype.exportTo = function(brd) {
@@ -812,6 +832,26 @@
         && self.db == brd.db && self.dc == brd.dc
         && self.bb == brd.bb && self.bc == brd.bc && self.cb == brd.cb && self.cc == brd.cc;
 };
+BoardObj.prototype.compress = function() {
+    var brd = this.brd;
+    var h1 = brd.aa;
+    h1 = (h1 << 4) | brd.ab;
+    h1 = (h1 << 4) | brd.ac;
+    h1 = (h1 << 4) | brd.ad;
+    h1 = (h1 << 4) | brd.ba;
+    h1 = (h1 << 4) | brd.bb;
+    h1 = (h1 << 4) | brd.bc;
+    h1 = (h1 << 4) | brd.bd;
+    var h2 = brd.ca;
+    h2 = (h2 << 4) | brd.cb;
+    h2 = (h2 << 4) | brd.cc;
+    h2 = (h2 << 4) | brd.cd;
+    h2 = (h2 << 4) | brd.da;
+    h2 = (h2 << 4) | brd.db;
+    h2 = (h2 << 4) | brd.dc;
+    h2 = (h2 << 4) | brd.dd;
+    return [h1, h2];
+}
 BoardObj.prototype.copy = function(brd) {
     var self = this.brd;
     if ( ! brd) {