2048 (game) solver

Question

The code contains an AI function, that searches breadth-first all possible moves and get the score of their grids, a depth of 6 is used which makes at most \$4+4^2+...+4^6\$ computed grids. The highest scores (and their associated moves) are kept for each level of depth, the most redundant one is chosen.

This function uses a 4x4 grid, and other functions to make it move in the 4 directions, so it can run in the background and return the final grid (when no more moves are possible). You also see a visualization of it as an HTML table, whose cells are in the cells variable and updated after each turn. You can also play directly with no solver, with keyboard's arrow keys.

Some remarks on the code either on the form, or on the design of the game solver would be great.

var n= 4; // grid size
var demoAI = new AI({maxDepth:6, minDepth:3, monoWeight:20, smoothWeight:0, freeWeight:40, maxWeight:60})


function AI(o){
    this.init=function(){
        this.grid = [];
        for(var i=0;i<n;i++){
           this.grid[i]=[]
            for(var j=0;j<n;j++){
                this.grid[i][j]='';
            }
        }
        rand(2, this.grid)
        rand(2, this.grid)
        this.steps=0;
    }
    this.init();

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

    this.predict = function(){
        var root={path:[], grid:this.grid};
        var levels = [[root]];
        for (var depth=1; depth<o.maxDepth; depth++){
            levels[depth] = [];
            for (var node of levels[depth-1])
                levels[depth] = levels[depth].concat(expand(node))
        }
        var best = []; //best first moves by level
        levels.map(maxScore).forEach(function(x){if (!!x.path) best.push(x.path[0])});
        if (!best.length) return null;

        var votedBest=[];
        var votes=[0,0,0,0]; //votes for each direction
        for (var i=best.length-1; i>=o.minDepth; i--){ // avoid votes of low depth
            votes[best[i]]++;
            votedBest.push(maxIndex(votes))
        }
        //pick the latest non-null winner
        for (var i=votedBest.length-1; i>=0; i--)
            if (votedBest[i]!=null)
                return votedBest[i]
        return null;
    }

    this.run=function(){
        var p = this.predict();
        if (p!=null) {
            this.move(p);
            this.steps++;
            this.run()
        }
    }
    this.test=function(){//run 10 times and average
        var s=0;
        for (var i=0; i<10; i++){
            this.init();
            this.run()
            s+=maxValue(this.grid)
        }
        return s/10;
    }

    function expand(node){ // mode={grid,score,path}
        var children= [];
        for (var move of [0,1,2,3]){
            var g = mv(move, node.grid);
            if (!equal(g, node.grid)) {
                try{
                    rand(2, g)
                    children.push({grid:g, score:score(g), path:node.path.concat([move])});
                }catch(e){
                     console.log('no more room', e)   
                }
            }
        }
        return children;
    }

    function score(grid){
        var s = stats(grid);
        //console.log(s)
        return o.monoWeight*s.monotonicity+
            o.smoothWeight*s.smoothness+
            o.freeWeight*s.freeCells+
            o.maxWeight*s.maxValue;
    }

}

var g = [];// transformation matrix in the 4 directions g[i][j] = [up, right, down, left]
var ig= [];// the inverse tranformations
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]];
        ig[i][j]=[[j,i], [i,n-1-j], [n-1-j,i], [i,j]];
    }
}
function transform(g, k, grid){
    var newgrid=[];
    for(var i=0;i<grid.length;i++){
        newgrid[i]=[];
        for(var j=0;j<grid.length;j++)
            newgrid[i][j] = grid[ g[i][j][k][0] ][ g[i][j][k][1] ];
    }
    return newgrid;
}
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);
//var flatCells = cells.reduce(function(v,a){return v.concat(a)},[])

cells.forEach(function(a, i){a.forEach(function(el,j){el.innerHTML=demoAI.grid[i][j]})});

function runAI(){
    var p = demoAI.predict();
    if (p!=null && ai.run) {
        demoAI.move(p)
        cells.forEach(function(a, i){a.forEach(function(el,j){el.innerHTML=demoAI.grid[i][j]})});
        requestAnimationFrame(runAI)
    }
}
ai.onclick = function(){
    if (!ai.run){
        this.innerHTML='stop AI';
        ai.run=true;
        runAI();
    }else{
        this.innerHTML='run AI';
        ai.run=false;
    }   
}


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


function stats(grid){ 
    var tgrid = transform(g, 0, grid); // transpose

    var cx = compact(grid), cy = compact(tgrid);
    // array of differences
    var dx = cx.map(function(a){ return a.map(function(_, i){return a[i]-a[i-1]}).slice(1, a.length) }),
        dy = cy.map(function(a){ return a.map(function(_, i){return a[i]-a[i-1]}).slice(1, a.length) }); 
    // sum abs(differences)
    var sx = dx.reduce(function(v,x){ return v+x.reduce(function(t,y){return t+(y==0?1:1/Math.abs(y))},0) },0), // Math.log2?
        sy = dy.reduce(function(v,x){ return v+x.reduce(function(t,y){return t+(y==0?1:1/Math.abs(y))},0) },0);

    // flatten differences and get their sign only
     var fx = dx.reduce(function(v, a){return v.concat(a)},[]).map(Math.sign),
         fy = dy.reduce(function(v, a){return v.concat(a)},[]).map(Math.sign);
    // count 1 and -1
    var mx = [fx.reduce(function(v,x){return x==1?v+1:v},0), fx.reduce(function(v,x){return x==-1?v+1:v},0)],
        my = [fy.reduce(function(v,x){return x==1?v+1:v},0), fy.reduce(function(v,x){return x==-1?v+1:v},0)];

    var Mx = Math.max.apply(null, mx)/Math.min.apply(null, mx),
        My = Math.max.apply(null, my)/Math.min.apply(null, my);

    if(Mx==Infinity || isNaN(Mx)) Mx=2*grid.length*grid.length;
    if(My==Infinity || isNaN(My)) My=2*grid.length*grid.length;

    var freeCells = grid.length*grid.length-filledCells(grid);

    return {monotonicity: Mx+My==0?0:Math.log2(Mx*Mx+My*My), smoothness: sx*sx+sy*sy, freeCells: freeCells*freeCells, maxValue: maxValue(grid)}
}

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

grid1 = [[2, '', '', ''],
         ['', '', 4, 2],
         ['', 8, 16, 4],
         [4, 2, 4, 8]];

grid2 = [[2, '', '', ''],
         ['', '', 4, 2],
         ['', 8, 16, 4],
         [4, 8, 16, 8]]

//console.log(stats(grid1), stats(grid2))

function filledCells(grid){
    return grid.reduce(function(v,a){
        return v+a.reduce(function(t,x){
            return t+Math.abs(Math.sign(x))
        },0)
    },0)
}

function maxIndex(arr){ // return the index of the max, or null if there are 2 equal max
    var max=[-1,null];
    for (var i=0;i<arr.length; i++){
        if (arr[i]>max[0]) max=[arr[i], i];
        else if (arr[i]==max[0]) max[1]=null;
    }
    return max[1]
}

function maxScore(nodes){
    var max={score:0};
    for (var node of nodes)
        if (node.score>max.score)
            max = node;
    return max;
}


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

function compact(grid){ // remove empty values [2, 4, '', 2] -> [2, 4, 2]
    var ngrid=[];
    for (var row of grid)
        ngrid.push(row.filter(Number))
    return ngrid;
}

function random(v){
    var free = $('td').filter(function(el){ return el.innerHTML==''});
    var r = Math.floor(Math.random()*free.length);
    free[r].innerHTML = v;
}
function rand(v, grid){
    var r = Math.floor(Math.random()*(grid.length*grid.length-filledCells(grid))), _r=0;
    for (var i = 0; i < grid.length; i++) {
        for (var j = 0; j < grid.length; j++) {
            if (!Number(grid[i][j])){
                if (_r==r) {grid[i][j]=v}
                _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 $(s) {
    return [].slice.apply(typeof s=="string"?document.querySelectorAll(s):s);
}

table, th, td {
    border: 1px solid black;
}
td {
    width: 35px;
    height: 35px;
    text-align: center;
}

<div></div>
<button id=init>init</button><button id=ai>run AI</button><button id=hint>hint</button><span id=hintvalue></span>

jsFiddle

edit: final version

Answer 1

First, you are usually good about naming your variables, but you still have a few single-letter variables in here, o, p, and v, to name a few. These should be more descriptive of what they are.

Second, your code would be a bit more readable if you put spaces around your operators, like for(var i = 0; i < n; i++) {. JSLint says you should do this too.

Third, I think your algorithm can be improved. The very highest number that can be created is 2^18, which can only happen when you have 2^17 in one of the corner squares, and 2^16, 2^15, and 2^14 along one of the edges. Then, you need to 2^13 above 2^14, 2^12 next to 2^13, and so on:

Given the nature of the game, the odds of this happening are extremely low, but your algorithm does not seem to weight the squares to follow this pattern.

Finally, once the board gets filled when playing with the keyboard, nothing happens. When you ask for a hint, it returns "undefined". Perhaps you should implement win/loss situations to cover this scenario.

Answer 2

Sloppy code

This code is extremely sloppy, making it very hard to review. Next time, before posting here, please paste it on http://jshint.com/ or http://jslint.com/ first, and make the suggested corrections.

Don't repeat yourself

Copy-pasting code is a very dangerous practice. Don't do it. For example:

var dx = cx.map(function(a){ return a.map(function(_, i){return a[i]-a[i-1]}).slice(1, a.length) }),
    dy = cy.map(function(a){ return a.map(function(_, i){return a[i]-a[i-1]}).slice(1, a.length) });

You do this in many other places too: you write the same anonymous function twice. Give the function a nice, descriptive name, make it nicely indented and readable, and rewrite the two map calls in terms of it. For example:

// note: try to give this a more descriptive name than "mapper"
function mapper(a) {
    return a.map(function(_, i) { return a[i] - a[i-1] }).slice(1, a.length)
}
var dx = cx.map(mapper),
    dy = cy.map(mapper);

---

On closer look, the entire stats method is about deriving Mx and My by applying the exact same sequence of operations on grid and tgrid, respectively. Instead of writing all those non-trivial steps twice, it would be better to move the common logic to a helper function with no duplicated code, so that you can rewrite as:

var Mx = helper(grid),
    My = helper(tgrid);