8
\$\begingroup\$

Follow-up of 2048 (game) solver

I improved the script, using standard search methods like expectimax. Now it goes easily to 2048, but not really further, the difference with the highly efficient answer is that they represent the whole board in an integer, then they can go to further depth in the search (10 million of moves, likely they can go to depth=5). While I can't go above depth=3 (~104 moves) it's already deadly slow with depth=3. I use it only when there is 2 or less free tiles left, and depth=2 with 6 or less free tiles, otherwise, depth=1.

var n = 4, M=new MatrixTransform(n);

var ai = { weights: [1, 1], depth: 1};// depth=1 by default, but we adjust it on every prediction according to the number of free tiles

initialize(ai)

function run(ai) {
  var p;
  while ((p = predict(ai)) != null) {
move(p, ai);
  }
  //console.log(ai.grid , maxValue(ai.grid))
  ai.maxValue = maxValue(ai.grid)
  console.log(ai)
}

function initialize(ai) {
  ai.grid = [];
  for (var i = 0; i < n; i++) {
ai.grid[i] = []
for (var j = 0; j < n; j++) {
  ai.grid[i][j] = 0;
}
  }
  rand(ai.grid)
  rand(ai.grid)
  ai.steps = 0;
}

function move(p, ai) { //0:up, 1:right, 2:down, 3:left
  var newgrid = mv(p, ai.grid);
  if (!equal(newgrid, ai.grid)) {
//console.log(stats(newgrid, ai.grid))
ai.grid = newgrid;
try {
  rand(ai.grid)
  ai.steps++;
} catch (e) {
  console.log('no room', e)
}
  }
}

function predict(ai) {
  var free=freeCells(ai.grid);
  ai.depth=free>4?1:(free>2?2:3);
  var root = { path: [], prob:1, grid: ai.grid, score: -Infinity, children:[]};
  var x=expandMove(root, ai)
  //console.log("number of leaves", x)
  //console.log("number of leaves2", countLeaves(root))
  if (!root.children.length)
return null
  var values = root.children.map(expectimax);
  var mx = max(values);
  return root.children[mx[1]].path[0]
  
}

function countLeaves(node){
  var x=0;
  if (!node.children.length) return 1;
  for(var n of node.children)
x+=countLeaves(n);
  return x;
}

function expectimax(node){
  if (!node.children.length){
return node.score
  }else{
var values = node.children.map(expectimax);
if(node.prob){ //we are at a max node
  return Math.max.apply(null, values)
}else{ // we are at a random node
  var avg=0;
  for(var i=0;i<values.length;i++)
    avg+=node.children[i].prob*values[i]
  return avg/(values.length/2)
}
  }
}

function expandRandom(node, ai) {
  var x=0;
  for (var i = 0; i < node.grid.length; i++)
for (var j = 0; j < node.grid.length; j++)
  if (!node.grid[i][j]){
    var grid2=M.copy(node.grid), grid4=M.copy(node.grid);
    grid2[i][j]=2;
    grid4[i][j]=4;
    var child2 = {grid:grid2, prob:.9, path:node.path, children:[]};
    var child4 = {grid:grid4, prob:.1, path:node.path, children:[]}
    node.children.push(child2)
    node.children.push(child4)
    x+=expandMove(child2, ai)
    x+=expandMove(child4, ai)
  }
  return x;
}

function expandMove(node, ai) { // node={grid,path,score}
  var isLeaf=true, x=0;
  if(node.path.length<ai.depth){
for (var move of[0, 1, 2, 3]) {
  var grid = mv(move, node.grid);
  if (!equal(grid, node.grid)) {
    isLeaf=false;
    var child = {grid: grid, path: node.path.concat([move]), children:[]}
    node.children.push(child)
    x+=expandRandom(child, ai)
  }
}
  }
  if(isLeaf) node.score = dot(ai.weights, stats(node.grid))
  return isLeaf?1:x;
}



var cells = []
var table = document.createElement("table");
for (var i = 0; i < n; i++) {
  var tr = document.createElement("tr");
  cells[i] = [];
  for (var j = 0; j < n; j++) {
cells[i][j] = document.createElement("td");
tr.appendChild(cells[i][j])
  }
  table.appendChild(tr);
}
document.querySelector('div').appendChild(table);

function updateUI(ai) {
  cells.forEach(function(a, i) {
a.forEach(function(el, j) {
  el.innerHTML = ai.grid[i][j] || ''
})
  });
}
updateUI(ai)

function runAI() {
  var p = predict(ai);
  if (p != null && ai.running) {
move(p, ai)
updateUI(ai)
requestAnimationFrame(runAI)
  }
}
runai.onclick = function() {
  if (!ai.running) {
this.innerHTML = 'stop AI';
ai.running = true;
runAI();
  } else {
this.innerHTML = 'run AI';
ai.running = false;
  }
}


hint.onclick = function() {
  hintvalue.innerHTML = ['up', 'right', 'down', 'left'][predict(ai)]
}
document.addEventListener("keydown", function(event) {
  if (event.which in map) {
move(map[event.which], ai)
console.log(stats(ai.grid))
updateUI(ai)
  }
})
var map = {
  38: 0, // Up
  39: 1, // Right
  40: 2, // Down
  37: 3, // Left
};
init.onclick = function() {
  initialize(ai);
  updateUI(ai)
}


function stats(grid, previousGrid) {

  var free = freeCells(grid);

  var c = -conv44valid(grid, [[3,2,1,0],[2,1,0,-1],[1,0,-1,-2],[0,-1,-2,-3]]);
  
  return [c, free * free];
}

function dist2(a, b) { //squared 2D distance
  return Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2)
}

function dot(a, b) {
  var r = 0;
  for (var i = 0; i < a.length; i++)
r += a[i] * b[i];
  return r
}

function product(a) {
  return a.reduce(function(v, x) {
return v * x
  }, 1)
}

function maxValue(grid) {
  return Math.max.apply(null, grid.map(function(a) {
return Math.max.apply(null, a)
  }));
}

function freeCells(grid) {
  return grid.reduce(function(v, a) {
return v + a.reduce(function(t, x) {
  return t + (x==0)
}, 0)
  }, 0)
}

function max(arr) { // return [value, index] of the max
  var m = [-Infinity, null];
  for (var i = 0; i < arr.length; i++) {
if (arr[i] > m[0]) m = [arr[i], i];
  }
  return m
}

function min(arr) { // return [value, index] of the min
  var m = [Infinity, null];
  for (var i = 0; i < arr.length; i++) {
if (arr[i] < m[0]) m = [arr[i], i];
  }
  return m
}

function maxScore(nodes) {
  var min = {
score: -Infinity,
path: []
  };
  for (var node of nodes) {
if (node.score > min.score)
  min = node;
  }
  return min;
}


function mv(k, grid) {
  var tgrid = M.itransform(k, grid);
  for (var i = 0; i < tgrid.length; i++) {
var a = tgrid[i];
for (var j = 0, jj = 0; j < a.length; j++)
  if (a[j]) a[jj++] = (j < a.length - 1 && a[j] == a[j + 1]) ? 2 * a[j++] : a[j]
for (; jj < a.length; jj++)
  a[jj] = 0;
  }
  return M.transform(k, tgrid);
}

function rand(grid) {
  var r = Math.floor(Math.random() * freeCells(grid)),
_r = 0;
  for (var i = 0; i < grid.length; i++) {
for (var j = 0; j < grid.length; j++) {
  if (!grid[i][j]) {
    if (_r == r) {
      grid[i][j] = Math.random() < .9 ? 2 : 4
    }
    _r++;
  }
}
  }
}

function equal(grid1, grid2) {
  for (var i = 0; i < grid1.length; i++)
for (var j = 0; j < grid1.length; j++)
  if (grid1[i][j] != grid2[i][j]) return false;
  return true;
}

function conv44valid(a,b){
  var r=0;
  for(var i=0;i<4;i++)
for(var j=0;j<4;j++)
  r+=a[i][j]*b[3-i][3-j]
  return r
}

function MatrixTransform(n){
  var g = [], ig = [];
  for (var i = 0; i < n; i++) {
g[i] = [];ig[i] = [];
for (var j = 0; j < n; j++) {
  g[i][j] = [[j, i], [i, n-1-j], [j, n-1-i], [i, j]]; // transformation matrix in the 4 directions g[i][j] = [up, right, down, left]
  ig[i][j] = [[j, i], [i, n-1-j], [n-1-j, i], [i, j]]; // the inverse tranformations
}
  }
  this.transform = function(k, grid){
return this.transformer(k, grid, g)
  }
  this.itransform = function(k, grid){ // inverse transform
return this.transformer(k, grid, ig)
  }
  this.transformer = function(k, grid, mat){
var newgrid = [];
for (var i = 0; i < grid.length; i++) {
  newgrid[i] = [];
  for (var j = 0; j < grid.length; j++)
    newgrid[i][j] = grid[mat[i][j][k][0]][mat[i][j][k][1]];
}
return newgrid;
  }
  this.copy = function(grid){
return this.transform(3, grid)
  }
}
table, th, td {
    border: 1px solid black;
}
td {
    width: 35px;
    height: 35px;
    text-align: center;
}
<div></div>
<button id=init>init</button><button id=runai>run AI</button><button id=hint>hint</button><span id=hintvalue></span>

jsbin

Edit: code improved: http://jsbin.com/yawewe/4

edit: final version

\$\endgroup\$
5
\$\begingroup\$

First, your algorithm looks a little better, but it still can be improved. It appears that it weights the higher values so they always drift to the left side of the board instead of wrapping around in a snake pattern:

2048 game image

Second, you should always have spaces around your operators, not just sometimes.

Third, you should use the correct levels of indentation, usually 4 spaces per level:

function freeCells(grid) {
  return grid.reduce(function(v, a) {
return v + a.reduce(function(t, x) {
  return t + (x==0)
}, 0)
  }, 0)
}

This should be:

function freeCells(grid) {
    return grid.reduce(function(v, a) {
        return v + a.reduce(function(t, x) {
            return t + (x == 0)
        }, 0)
    }, 0)
}

Fourth, when you attempt to get a hint after the game is over, it still returns "undefined".

Fifth, when I was playing it with my keyboard, sometimes when I would press down to merge some numbers and there was a space between them, the numbers would just stack next to each other instead of merging. I'm not sure why this happens.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your remarks, formatted the code and making it snake jsbin.com/yawewe/4, it goes to 4096 \$\endgroup\$ – caub Feb 21 '15 at 19:50
  • \$\begingroup\$ Are you sure about the merging issue? I didn't have it \$\endgroup\$ – caub Feb 22 '15 at 19:43
  • \$\begingroup\$ @kwak Yes, I check it several times, and it happened continually. \$\endgroup\$ – Hosch250 Feb 22 '15 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.