gistfile1.js

/**
 * Copy paste in the console, then restart the game (space bar)
 *
 * Greedy Algorithm for : http://gabrielecirulli.github.io/2048/
 * Plays the game using a naive greedy method. i.e. Local maximum
 *
 * Azaan
 * 
 * ---
 * Added Simple Heuristics to the algorithm. Tuning ftw! And... it won! 
 * 
 */
(function () {
  var __restart = GameManager.prototype.restart;
  var GM;

  GameManager.prototype.restart = function () {
    GM = this;
    __restart.bind(this)();

    var strategy = new GreedyStrategy(GM);
    console.log('hi');
    setTimeout(function () {
      strategy.play(window.DELAY || 100);
    }, 0);
  };

  function GreedyStrategy(gm) {
    this.gm = gm;
  }

  GreedyStrategy.prototype.cloneGrid = function () {
    function cloneTile(tile) {
      var t = new Tile({x: tile.x, y: tile.y}, tile.value);
      t.previousPosition = tile.previousPosition;
      t.mergedFrom = tile.mergedFrom;
      return t;
    }

    var arr = [], i, j, len, len2;
    for (i = 0, len = this.gm.grid.size; i < len; i++) {
      arr[i] = this.gm.grid.cells[i].slice();

      for (j = 0, len2 = arr[i].length; j < len2; j++) {
        if (arr[i][j] !== null) {
          arr[i][j] = cloneTile(arr[i][j]);
        }
      }
    }

    var g = new Grid(this.gm.grid.size);
    g.cells = arr;
    return g;
  };
  GreedyStrategy.prototype.greedyScore = function (grid) {
    //some general guidelines for greediness:
    //reward pairs of numbers together
    //reward values that are higher in the leftmost column?
    //avoid bomb circumstance at all costs!!!
    //bomb happens when 3 rows are all filled, forcing you to move right. 
    //This usually causes a quick death.
    // x x _ _ 
    // x x x _
    // x x x _
    // x x x _
    //this is bomb2
    // x x _ _ 
    // x x _ _
    // x x _ _
    // x _ _ _
    
    var bomb = true;
    var bombcount = 0;
    var bomb2 = true;
    var bomb2count = 0;
    var greedyscore = 0;
    var arr = [], i, j, len, len2;
    //gather initial data
    var totalempty = 16;
    var numtwos = 0
    for (i = 0, len = grid.size; i < len; i++) {
      arr[i] = grid.cells[i].slice();
      for (j = 0, len2 = arr[i].length; j < len2; j++) {
        if(arr[i][j] !== null) {
          if(arr[i][j].value == 2) {
            numtwos++;
          }
          totalempty -= 1;
        }
      }
    }
    for (i = 0, len = grid.size; i < len; i++) {
      arr[i] = grid.cells[i].slice();
      for (j = 0, len2 = arr[i].length; j < len2; j++) {
        //check for bomb(s)
        if(bomb) {
          if(i<2) {
            if(arr[i][j] == null) {
              bomb = false;
            }
          } else if (i==2) {
            if(arr[i][j] !== null) {
              bombcount++;
            }
          }
          else {
            if(arr[i][i] !== null) {
              bomb = false;
            }
          }
        }
        if(bomb2) {
          if(i<1) {
            if(arr[i][j] == null) {
              bomb2 = false;
            }
          } else if (i==1) {
            if(arr[i][j] !== null) {
              bomb2count++;
            }
          } else {
            if(arr[i][i] !== null) {
              bomb2 = false;
            }
          }
        }
        
        if (arr[i][j] == null) { // if a tile is empty, that is a good thing! 
          greedyscore += 450;
        }
        if (arr[i][j] !== null) { 
          if(i+1 < len) {
            if(arr[i][j].value == 2 && arr[i+1][j] == null) { //bump a 2 with nothing on the right or bottom
              if(totalempty < 2) {
                greedyscore += 500;   
              } else {
                greedyscore += 50;   
              }
            } 
            if(arr[i+1][j] !== null) {
              if(arr[i][j].value == arr[i+1][j].value) { greedyscore += 180; } // if a tile is next to another tile of the same number, that is a good thing!!!
            }
          }
          if(j+1 < len2) {
            if(arr[i][j].value == 2 && arr[i][j+1] == null) {
              if(totalempty < 2) {
                greedyscore += 500;   
              } else {
                greedyscore += 50;   
              }
            }
            if(arr[i][j+1] !== null) {
              if(arr[i][j].value == arr[i][j+1].value) { greedyscore += 180; }
            }
          }
          if(j-1 >= 0) {
            if(arr[i][j].value == 2 && arr[i][j-1] == null) { //bump a 2 with nothing on the right or bottom & top
              if(totalempty < 2) {
                greedyscore += 500;   
              } else {
                greedyscore += 50;   
              }
            } 
          }
          if(i==0 && (j==0||j==3)) { //add value to having big numbers in the corners (helps very much at later stages of the game)
            if(arr[i][j] !== null) {
              greedyscore += arr[i][j].value*10;
            }
          }
        }
      }
    }
    if(bomb && bombcount == 3) {
      greedyscore = greedyscore/50;
    }
    if(bomb2 && bomb2count == 3) {
      greedyscore = greedyscore/50;
    }
    
    return greedyscore;
  }
  

  GreedyStrategy.prototype.freeze = function () {
    this._grid = this.gm.grid;
    this._act = this.gm.actuator;
    this._score = this.gm.score;
    this._over = this.gm.over;
    this._won = this.gm.won;

    this.gm.actuator = undefined;
    this.gm.grid = this.cloneGrid();
  };

  GreedyStrategy.prototype.restore = function () {
    this.gm.grid = this._grid;
    this.gm.actuator = this._act;
    this.gm.score = this._score;
    this.gm.won = this._won;
    this.gm.over = this._over;
  };

  GreedyStrategy.prototype.step = function () {
    var scores = [], i;

    for (i = 0; i < 4; i++) {
      this.freeze();

      try {
        this.gm.move(i);
        scores.push(-Infinity);
      } catch (e) {
        // add score only if something moved
        if(i == 1) { // right is a last resort!!!
          scores.push((this.greedyScore(this.gm.grid) + this.gm.score)/50);
        }
        else if (i == 3) { //left is a good move!!!
          scores.push(this.greedyScore(this.gm.grid) + this.gm.score + 50);
        } else { 
          scores.push(this.greedyScore(this.gm.grid) + this.gm.score);
        }
      }
      this.restore();
    }

    return scores;
  };

  GreedyStrategy.prototype.play = function (d) {
    var self = this, next;
    var delay = d || 0;

    next = function () {
      var maxI = 0, scores;

      scores = self.step();
      for (i = 0; i < 4; i++) {
        if (scores[i] > scores[0])
          maxI = i;
      }
      if(maxI == 1) {
        console.log('moved right!');
        console.log(scores);
        console.log(this);
      }
      window.requestAnimationFrame(function () {
        self.gm.move(maxI);
        
        
        if (!self.gm.over) {
          setTimeout(next, delay);
        }
      });
    };

    next();
  };

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