Malay Keshav

Download Resume PDF

Malay Keshav

Netaji Subhas Institute of Technology

AI Script for 2048 to Run Directly on Chrome Console [Javascript]

March 24, 2014, by malay.keshav, category AI, All, Javascript

The following article explains the Game 2048, introduces Javascript and a basic Min-Max algorithm implemented in Javascipt and run on the Google Chrome Developer Tool's Console with an average success rate of ~60%.

The 2048  game is a single player 4x4 board game. Using the keyboard/mouse/touch we have to move the numbers to form bigger numbers and finally reaching the goal of making the number 2048. So 4 and 4 can be combined to form 8 , 2 and 2 can be combined to form 4 and so on. At every step a new number, either 2 or 4, is introduced in one of the unoccupied grid cells.

New Random Number Introduced


New
Random Number Introduced

Combine all Adjacent Numbers which   are equal and in the same direction.

Combine all Adjacent Numbers which are equal and in the same direction.

The game has been built on simple javascript. After numerous attempts on trying to reach 2048 but failing by a very small margin, I decided to  write an AI bot instead. I searched the internet for similar AI bots. I found a very good AI script on github that has been forked from the original GitHub repository.

But I wanted to run my bot on the original game instead of creating a forked clone for the same. This meant that somehow I had to read the current state of the game from the browser window, run my bot algorithm, and send back my 'move' to the game in the browser window.

This might sound simple but sending keyboard events to and from processes on MAC OSx is much harder than it looks like. After some digging I found that I had to use an Apple Script or Cocoa Objective C to simulate these keyboard events in a process. The only scripting language that I knew was Python.

Python has a library known as PyObjC. Which is a library implemented to run native Objective C code in Python. This solved the problem to send in events from one process to another. But due to some incompatibility with my version of xCode and the PyObjC library, I could go any further with this approach. I had to look for a more simpler and elegant approach to send in my 'move' to the game.

The game runs on Javascript. A language I am completely unfamiliar with. But this seemed like a good time to learn the most well known and used scritpting language out there. I went through the w3school tutorials and had a basic grasp of the language within a few hours. But how do I run my script on the game or how do you run a javascript on any webpage ? I had used it before where I copied a piece of JS and pasted it in the address bar of the browser to execute it. I also remember seeing a Javascript console in the Developer tools for Google Chrome.

Running javascript in the browser using the address bar meant copy-pasting the script into the browser address bar while the webpage (the game in this case) is open. I ran a sample code and it worked as expected :

javascript:alert("hello world!");

[ Notice how "javascript:" is very similar to "http:" that is written in webaddresses ]

The developer tools on the other hand included whats called the Javascript Console. So I tried running the same Javascript (JS) code in the console without the "javascript:" portion, and it worked in the same way.

So now that  I knew how to atleast execute my own JS on the webpage, the next step was to interact with the JS that was already on the page.

After going through all the Javascript files included on the game page, I found the script responsible for handling the keyboard events, keyboard_input_manager.js .

  <script src="js/bind_polyfill.js"></script>
  <script src="js/classlist_polyfill.js"></script>
  <script src="js/animframe_polyfill.js"></script>
  <script src="js/keyboard_input_manager.js"></script>
  <script src="js/html_actuator.js"></script>
  <script src="js/grid.js"></script>
  <script src="js/tile.js"></script>
  <script src="js/local_storage_manager.js"></script>
  <script src="js/game_manager.js"></script>
  <script src="js/application.js"></script>

I tried editing the script to display an alert box every time I pressed a key. It worked just as expected. I next tried to extract some information about the game using the script. Like the game score and the game grid (that contains the 4x4 grid of numbers). Again both of the tasks completed with a single lines of code. Now that I could extract information from the game, I needed to check how I could send my inputs to the game.

I looked at the script of keyboard_input_manager.js  , which was responsible for creating all the event handlers for the input. The script included event handlers for events from the keyboard, mouse and even touch. I only focussed on the keyboard events. A key press triggered an event named "keydown", which then was responsible for calling the function that handled the 'move' based on the direction key pressed.  The function that was being called after the "keydown" event was as follows :

self.emit("move", mapped);

KeyboardInputManager.prototype.emit = function (event, data) {
  var callbacks = this.events[event];
  if (callbacks) {
    callbacks.forEach(function (callback) {
      callback(data);
    });
  }
};

From what little I could understand from the code was that the emit function is being called with the parameters ("move", data : the key being pressed). The function  would then retreive the correct callback function for the event - "move" and inturn call it with the parameter (data). The callback function for a given event was stored in the array events[].

The callbacks array, events[], was being initialized by another function in the same JS file :

KeyboardInputManager.prototype.on = function (event, callback) {
  if (!this.events[event]) {
    this.events[event] = [];
  }
  this.events[event].push(callback);
};

The events and their respective callbacks were being added as follows from another JS file (game_manager.js) :

this.inputManager.on("move", this.move.bind(this));

which basically binds the method move with the scope of the object 'this' corresponds to. The following simple example taken from mozilla's developer website illustrates it properly :

this.x = 9; 
var module = {
  x: 81,
  getX: function() { return this.x; }
};

module.getX(); // 81 , since the scope is local to the object module

var getX = module.getX;
getX(); // 9, because in this case, "this" refers to the global object

// create a new function with 'this' bound to module
var boundGetX = getX.bind(module);
boundGetX(); // 81, since scope now binded to module.

Now that I knew what function was responsible for handling the move, I tried calling the module move manually, but I needed the object of the class "GameManager" that was nowehere to be found.

The game was initialized with a simple single line of code :

new GameManager(4, KeyboardInputManager, HTMLActuator, LocalStorageManager);

It does not return the newly created object and store it in any variable. I am yet to figure out how this works. But in the mean time I had to find a different way to interact with the Game. I knew that this elusive game object though cannot be called from the javascript console can atleast be called from the game object itself. So I tried calling the funciton move from within GameManager.prototype.move = function (direction); and yes it worked. I could call the object functions from within itself.

I now had the two main overhead requirements for making my AI Bot :

  1. A way to retrieve the Game state in the form of the contents of the grid.
  2. A way to send in my input to the Game.

The way to retrieve the contents of the grid was already provided in the JS files for the game.

Grid.prototype.cellContent = function (cell) {
  if (this.withinBounds(cell)) {
    return this.cells[cell.x][cell.y];
  } else {
    return null;
  }
};

The above code was already included in the grid.js file for the game. The above module returns the number contained in the cell (x,y).

Using the above module I created a function that returned the grid as a matrix that I could use as the input for my algorithm.

this.getMatrix = function(){
    var matrix = [];
    for (var i = 0 ; i <4 ; i++) {
      var row = [];
      for (var j = 0; j < 4; j++) {
        tile = self.grid.cellContent({x:j, y:i});
        if(tile == null)
          row.push(0);
        else 
          row.push(tile["value"]);
      };
      matrix.push(row);
    };
    return matrix;
  }

The above function had to be written in the move method. To create any new module or function that was global I had to write it inside another module that would be executed later on during the game play. I may be wrong, but I think this is because the Google Chrome Developer tools cannot update the entire static code of the JS , but only that portion of code that came in the line of execution. This would also explain why declaring any global variables did not work. Since the Game Object was already created, the global variable declaration line would not be executed again.

This meant I had to write my entire AI bot script inside the Game Object's move method.
 To run the game bot all on its own, the script needed to be called again and again. So I decided to write the Bot algorithm right at the end of the move method after all the game state modifications had been made. Once the algorithm came up with the next move , I recursively called the move method. And the process continued until the Game is Over.

To test things I wrote a random AI bot, that returned a random move based on the random number generator.

myMove = (Math.floor(Math.random()*100))%4;
self.move(myMove);

The above line generated a random number between [0,1,2,3], each number representing Up, Down, Left & Down respectively.

Result of   the Random Algorithm

Result of the Random Algorithm

The results of the random algorithm bot can be seen in the above image.
But the execution of the script was spontaneous. To prevent this and add a more natural look to it I added a timeout delay function.

setTimeout(function() {
    var moveval = (Math.floor(Math.random()*100))%4;
    self.move(myMove);
}, 100);

The above function calls the function move after a delay of 100ms.
The next step was to implement a very basic min-max algorithm. A very good explantion for the Min-Max Algorithm can be found here.
In short, the Min-Max algorithm enumerates the states of the game that can be reached from the current state, and assigns a score to each state recursively.

The scoring of each state is the critical section of the algorithm. I will be talking about the algorithm for this scoring as I improve it after each iteration.

My MinMax Function currently looked like :

this.minMax = function(matrix, move, depth){
  /* Run till depth 6 */
  if(depth == 6)
    return 0;
  /* Move the matrix in the given Direction */
  var rmatrix = self.moveCells(self.createCopy(matrix),move);
  /* Check if the move made any changes to the matrix */
  var areSame = self.isEqualMatrix(rmatrix, matrix);
  /* Evaluate the Game State and give it a score*/
  var score = self.evaluateMatrix(rmatrix);

  /* If the matrix before and after the move were the same, 
      then this move is invalid */
  if(areSame == true)
    return score-1;
  var maxVal=-1000,val,ret;
  for(var x = 0;x<4;x++)
  {
    val = this.minMax(self.createCopy(rmatrix), x, depth+1);
    if(val > maxVal)
      maxVal  = val;
  }
  return (score+maxVal);
}

ITERATION 1

The very basic approach that I used was to maximize the number of free grids in the game. A game state with higher number of free grids was given a higher score than the game with lower number of free grids. Just by using this simple approach I was able to reach the 2048 grid in the 5th test run.

this.evaluateMatrix = function(matrix){
  var cc = 0;
  for(var i = 0;i<4;i++)
    for(var j = 0;j<4;j++)
      if(matrix[i][j] == 0)
        cc += 100;    
  return cc;
}

ITERATION 2

The next approach that I tried was to raise all the grid numbers equally. To do this, I tried to keep all the filled grid closer to the average using the following code :

this.evaluateMatrix = function(matrix){
  var cc = 0;
  var sum = 0;
  for(var i = 0;i<4;i++)
    for(var j = 0;j<4;j++){
      if(matrix[i][j] == 0)
        cc += 50;
      else 
        sum += matrix[i][j];
    }
  sum = sum/(((50*16) - cc)/50);
  for(var i = 0;i<4;i++)
    for(var j = 0;j<4;j++)
      if(matrix[i][j] != 0)
        cc -= Math.abs(matrix[i][j]-sum);
  return cc;
}

ITERATION 3

The previous approach failed because even though equal valued cells were present in the given game state, they were not combined. And hence very few free cells were left in the grid for moving around the other cells. To remove this, I gave the gamestate with larger size cells a better score. So if two different game states had the same number of free cells, the one with the higher numbered cells would be given a better score. The focus now shifted from creating a flat gamestate (one where all the cell numbers were closer to the average) to one with the highest peak (Maximizing the highest cell number).

this.evaluateMatrix = function(matrix){
  var cc = 0;
  for(var i = 0;i<4;i++)
    for(var j = 0;j<4;j++){
      if(matrix[i][j] == 0)
        cc += 100; /* Score for Free Spaces */
      else 
        cc += matrix[i][j]*matrix[i][j]; /* Score for higher numbers */
    }
  return cc;
}

ITERATION 4

The above approach reached 2048 more than twice in every three tests. The next step was to try and reach 4096 as well as further improve on the accuracy. Once the game reachs higher numbered cells such as 1024, 512 & 2048, the amount of free space in the gamestate is reduced. This meant that the translation of the cells had fewer space to work with. So my next approach was to keep the grids with smaller differences closer than the once with larger difference. So a gamestate with 1024 being more close to 512 than 64 would be given a higher score than 1024 being more closer to 64 than 512. This was achieved using the following game state evaluation code :

this.evaluateMatrix = function(matrix){
  var cc = 0;
  var sum = 0;
  for(var i = 0;i<4;i++)
    for(var j = 0;j<4;j++){
      sum += matrix[i][j];
      if(matrix[i][j] == 0)
          cc += 100;    
      else 
          cc += matrix[i][j]*matrix[i][j]*matrix[i][j]*matrix[i][j];
    }

    /* Code to evalute the distance component of the game state */
    var dist;
    var dx = [-1,0,1,0,1,1,-1,-1];
    var dy = [0,1,0,-1,1,-1,1,-1];
    var LIMIT = 64;
    var nx,ny;
    var map = {
      2: 1, 
      4: 2, 
      8: 3, 
      16: 4,
      32: 5,
      64: 6,
      128: 7,
      256: 8, 
      512: 9, 
      1024: 10,
      2048: 11,
      4096: 12 
  };

    var powLIMIT;
    for(var i = 0;i<4;i++){
      for(var j = 0;j<4;j++){
        for(var ii = i; ii<4;ii++){
          for(var jj = 0;jj<4;jj++){
            if(ii == i && jj < j)
              continue;
            if(matrix[i][j] <= 2 || matrix[ii][jj] <= 4)
              continue;
            dist = Math.abs(i-ii) + Math.abs(j-jj);
            powLIMIT = Math.max(map[matrix[i][j]], map[matrix[ii][jj]])+1;
            dist = Math.pow(2, (powLIMIT - Math.abs(map[matrix[i][j]]
                    - map[matrix[ii][jj]]))+ (dist*2));
            cc -= dist;
          }
        }
      }
    }
    return cc;
}

The score given for two grids at position (i,j) and (ii,jj) with values M[i][j] and M[ii][jj], is given by :


d = |i-ii| + |j-jj|
score = - 2^{max(\log_2(M_{i,j}),\log_2(M_{ii,jj}))\ -\ |\log_2(M_{i,j}) - \log_2(M_{ii,jj})| + 2\cdot d}

ITERATION 5

The only portion the minmax algorithm did not consider was the random addition of 2 and 4.
This was further added to the script by adding the following :

  var freeCellMatrix = self.findFreeCell(rmatrix);
  for(var i = 0;i<freeCellMatrix.length;i++)
    rmatrix[freeCellMatrix[i].x][freeCellMatrix[i].y] = freeCellMatrix[i].z;

The function findFreeCell returns an object with the location of the free cell in the grid and the value it should have. (75% - '2' , 25% - '4'). The function has been implemented in the following manner :

this.findFreeCell = function(matrix){
  var ret = [];
  var i,j,k=0;
  var xx = ((Math.floor(Math.random()*100))%4)==3?4:2;
  do{
    i =  (Math.floor(Math.random()*100))%4;
    j =  (Math.floor(Math.random()*100))%4;
    k++;
  }while(matrix[i][j] != 0 && k != 64);

  if(matrix[i][j] != 0)
    for(i = 0;i<4;i++)
      for(j = 0;j<4;j++)
        if(matrix[i][j] == 0){
          ret.push({x:i, y:j, z:xx});
          return ret;
        }
  ret.push({x:i, y:j, z:xx});
  return ret;
}

The AI script still hasnt reached 4096 and I am strill trying to further improve the code. The entire script for game_manager.js can be downloaded from here.

ITERATION 6 (4096)

Finally reached 4096. The problem earlier was that once 2048 was reached, the amount of free space if further reduced. Hence the remaining space needs to be used more judicially. One approach in doing this is to form decreasing sequence such that the largest tile is in the corner. Forming something like this :

 

Forming a linear sequence with the largest tile in one corner

Forming a linear sequence with the largest tile in one corner

The code for the above approach was to give an extra score for a decreasing sequence starting from any corner :

var linearSeq;
var jk = [1,2,1,2];
var dj = [1,-1,1,-1];
var cj = [-1,1,-1,1]
for(var k = 0;k<4;k++){
  for(var i = 0;i<4 && i >=0;i++){
    linearSeq = true;
    for(var j = jk[k];j >= 0 && j<4;j += dj[k]){
      if(k < 2){
        if(matrix[i][j+cj[k]]*2 != matrix[i][j])
          linearSeq = false;
      }
      else {
        if(matrix[j+cj[k]][i]*2 != matrix[j][i])
          linearSeq = false;
      }
    }
    if(linearSeq){
      var mul = 10;
      if(i == 0 || i == 3)
        mul = 70;
      if(k == 0){
        cc += matrix[i][3]*mul*Math.sqrt(matrix[i][3]);
        if(matrix[i][3] == largest)
          cc += largest*Math.sqrt(largest);
      }
      else if(k == 1){
        cc += matrix[i][0]*mul*Math.sqrt(matrix[i][0]);
        if(matrix[i][0] == largest)
          cc += largest*Math.sqrt(largest);
      } 
      else if(k == 2){
        cc += matrix[3][i]*mul*Math.sqrt(matrix[3][i]);
        if(matrix[3][i] == largest)
          cc += largest*Math.sqrt(largest);
      }
      else {
        cc += matrix[0][i]*mul*Math.sqrt(matrix[0][i]);
        if(matrix[0][i] == largest)
          cc += largest*Math.sqrt(largest);
      }
    }
  }
}
Maximum Score Achieved So far

Maximum Score Achieved So far

The final code for this can be found here.

7 Comments

    • malay.keshav |

      1) Load the game on chrome browser.
      2) Open the developer tools by right click and selecting "Inspect Element".
      3) Look for game_manager.js and open it within the developer tools.
      4) You can try and paste the entire ai script over this script and press Ctrl+s (cmd + s for Mac). But this might stop working as the original code is changed over time. In which case just copy the section from "AI code begins here" to "AI code ends here" from my AI script and paste it at the bottom of the "move" function (before the '}') in the game_manager.js script. And press Ctrl+s.
      5) Play the first move and the rest will be played by the ai script.

      Reply
      • Jesse |

        Just commenting to let you know that neither of the scripts is working in Chrome at the moment. The older script from the Youtube video worked until late last night but the final script never managed to run. Chrome returns an error that getBestScore is undefined when you attempt to start the program by making a move.

        Best wishes,

        Jesse

        Reply
        • malay.keshav |

          Yes, it seems some of the functions have been renamed in the game_manager.js script.
          But the core AI script is still working.
          Copy the Code from " /* AI CODE BEGINS */" to "/* AI CODE END */" .
          And paste it here :
          """
          this.actuate();
          }
          ->PASTE CODE HERE <- }; """ Hit Save and and try. Should work

          Reply
  1. Joseph |

    Can someone edit this code so it goes upto 16,384? If you can I'd be extremely grateful, thanks.

    Reply

So, what do you think ?