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

• 200_success: Note that Math.sign() is currently not supported in many browsers.
• 200_success: I've taken the liberty of copying the little bit of HTML and CSS from your jsFiddle into the question as a Stack Snippet, changing just the cell size from 50px to 35px to make it fit better.
• rolfl: See: What you may and may not do after receiving answers In this case, a follow-up question is the right way to go.
• caub: ok, thanks, done

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:

enter image description here

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.

• caub: thanks, I'm trying hard to improve it, I've tried to force descending high values into a kind of 'snake' jsfiddle.net/crl/hmthq78t/57 but it's inefficient, I'll try to make the highest values stick to an edge, because this post's version of the AI is too erratic
• user34073: No problem. Glad to help.

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);

• caub: thanks, the stats function is indeed the most ugly, it's still in dev, I've factorized like you suggest the code, by concatenating grid and tgrid's rows in a same array jsfiddle.net/crl/hmthq78t/52, but I changed other things and I'm getting worse results... anyway the AI part is definitely not ready