2048.html
author Oleksandr Gavenko <gavenkoa@gmail.com>
Tue, 02 Sep 2014 18:47:33 +0300
changeset 3 96a50cb300cc
parent 2 11da0a8fabf3
child 4 732aef931a9e
permissions -rw-r--r--
Enable score cache.

<!DOCTYPE html>
<html>
<head>
  <title>2048 AI</title>
  <meta name="viewport" content="width=device-width; initial-scale=1.0"/>
  <meta charset="utf-8"/>

  <style>
    body {
      width: 100%;
    }
    h1, .score-area, .control-area, #message-area {
      text-align: center;
    }
    #board {
      margin: 10px auto;
    }
    #board td {
      width: 40px;
      height: 40px;
      border: 1px solid red;
      margin: 0;
      text-align: center;
    }
  </style>
</head>
<body>

  <h1>2048</h1>

  <div class="score-area">Score: <span id="score">0</span>, Max: <span id="max">0</span>, Speed: <span id="speed">0</span> t/s, Turn: <span id="turn">0</span></div>

  <div id="message-area"></div>

  <table id="board">
    <tr>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
  </table>

  <div class="control-area">
    <div>
      <button id="start">Start</button>
      <button id="step">Step</button>
      <button id="loop">Loop</button>
      <button id="finish">Finish</button>
    </div>
    <div>
      <button id="left">left</button>
      <button id="up">up</button>
      <button id="down">down</button>
      <button id="right">right</button>
    </div>
    <h1>AI</h1>
    <div>
      <button id="ai-random">random</button>
      <button id="ai-next-max-score">next max score</button>
      <button id="ai-next-max-value">next max value</button>
    </div>
  </div>

  <script>
    "use strict";

    var board = {};
    board.create = function() {
      var brd = [];
      for (var i = 0; i < 4; i++) {
        brd[i] = [];
        for (var j = 0; j < 4; j++) {
          brd[i][j] = 0;
        }
      }
      return brd;
    }
    board.copy = function(from, to) {
      for (var i = 0; i < 4; i++) {
        for (var j = 0; j < 4; j++) {
          to[i][j] = from[i][j];
        }
      }
    }
    board.freeCnt = function(brd) {
      var cnt = 0;
      for (var i = 0; i < 4; i++) {
        for (var j = 0; j < 4; j++) {
          if (brd[i][j] === 0)
            cnt++;
        }
      }
      return cnt;
    }
    board.gameOver = function(brd) {
      if (board.freeCnt(brd) > 0)
        return false;
      for (var i = 0; i < 4; i++) {
        for (var j = 0; j < 3; j++) {
          if (brd[i][j] === brd[i][j+1])
            return false;
        }
      }
      for (var j = 0; j < 4; j++) {
        for (var i = 0; i < 3; i++) {
          if (brd[i][j] === brd[i+1][j])
            return false;
        }
      }
      return true;
    }
    board.random = function(brd) {
      var cnt = board.freeCnt(brd);
      cnt = Math.floor(Math.random() * cnt)+1;
      for (var i = 0; i < 4 && cnt > 0; i++) {
        for (var j = 0; j < 4 && cnt > 0; j++) {
          if (brd[i][j] !== 0)
            continue;
          if (cnt === 1)
            brd[i][j] = 2;
          cnt--;
        }
      }
    }
    /* http://www.reddit.com/r/2048/comments/214njx/highest_possible_score_for_2048_warning_math */
    var boardScoreTbl = {"0": 0};
    for (var i = 1, exp = 2; i < 16; i++, exp *= 2) {
      boardScoreTbl[exp] = (i-1)*exp;
    }
    board.score = function(brd) {
      var score = 0;
      var max = 0;
      for (var i = 0; i < 4; i++) {
        for (var j = 0; j < 4; j++) {
          var val = brd[i][j];
          score += boardScoreTbl[val];
          if (max < val)
            max = val;
        }
      }
      return {score: score, max: max};
    }

    board.row = {};
    board.row.init = function() {
      return {stack: [], curr: 0};
    }
    board.row.push = function(state, val) {
      if (val === 0)
        return;
      if (state.curr === 0) {
        state.curr = val;
        return;
      }
      if (state.curr === val) {
        state.stack.push(state.curr*2);
        state.curr = 0;
      } else {
        state.stack.push(state.curr);
        state.curr = val;
      }
    }
    board.row.finish = function(state) {
      if (state.curr !== 0)
        state.stack.push(state.curr);
    }
    board.move = {};
    board.move.up = function(brd) {
      var updated = false;
      for (var j = 0; j < 4; j++) {
        var state = board.row.init();
        for (var i = 0; i < 4; i++) {
          board.row.push(state, brd[i][j]);
        }
        board.row.finish(state);
        for (var i = 0; i < state.stack.length; i++) {
          if (brd[i][j] !== state.stack[i])
            updated = true;
          brd[i][j] = state.stack[i];
        }
        for (; i < 4; i++) {
          if (brd[i][j] !== 0)
            updated = true;
          brd[i][j] = 0;
        }
      }
      return updated;
    };
    board.move.down = function(brd) {
      var updated = false;
      for (var j = 0; j < 4; j++) {
        var state = board.row.init();
        for (var i = 3; i >= 0; i--) {
          board.row.push(state, brd[i][j]);
        }
        board.row.finish(state);
        for (var i = 0; i < state.stack.length; i++) {
          if (brd[3-i][j] !== state.stack[i])
            updated = true;
          brd[3-i][j] = state.stack[i];
        }
        for (; i < 4; i++) {
          if (brd[3-i][j] !== 0)
            updated = true;
          brd[3-i][j] = 0;
        }
      }
      return updated;
    };
    board.move.left = function(brd) {
      var updated = false;
      for (var i = 0; i < 4; i++) {
        var state = board.row.init();
        for (var j = 0; j < 4; j++) {
          board.row.push(state, brd[i][j]);
        }
        board.row.finish(state);
        for (var j = 0; j < state.stack.length; j++) {
          if (brd[i][j] !== state.stack[j])
            updated = true;
          brd[i][j] = state.stack[j];
        }
        for (; j < 4; j++) {
          if (brd[i][j] !== 0)
            updated = true;
          brd[i][j] = 0;
        }
      }
      return updated;
    };
    board.move.right = function(brd) {
      var updated = false;
      for (var i = 0; i < 4; i++) {
        var state = board.row.init();
        for (var j = 3; j >= 0; j--) {
          board.row.push(state, brd[i][j]);
        }
        board.row.finish(state);
        for (var j = 0; j < state.stack.length; j++) {
          if (brd[i][3-j] !== state.stack[j])
            updated = true;
          brd[i][3-j] = state.stack[j];
        }
        for (; j < 4; j++) {
          if (brd[i][3-j] !== 0)
            updated = true;
          brd[i][3-j] = 0;
        }
      }
      return updated;
    };

    var boardDom = document.getElementById("board");
    var ui = {};
    ui.board = {};
    ui.board.set = function(i, j, val) {
      boardDom.querySelectorAll("tr")[i].querySelectorAll("td")[j].innerHTML = val;
    }
    ui.board.update = function(brd) {
      for (var i = 0; i < 4; i++) {
        for (var j = 0; j < 4; j++) {
          ui.board.set(i, j, (brd[i][j] >= 2) ? brd[i][j] : "");
        }
      }
    }
    ui.score = {};
    var scoreDom = document.getElementById("score");
    var maxDom = document.getElementById("max");
    var speedDom = document.getElementById("speed");
    var turnDom = document.getElementById("turn");
    ui.score.clear = function(brd) {
      scoreDom.innerHTML = '0';
      maxDom.innerHTML = '0';
      speedDom.innerHTML = '0';
      turnDom.innerHTML = '0';
    }
    ui.score.update = function(brd) {
      var score = board.score(brd);
      scoreDom.innerHTML = '' + score.score;
      maxDom.innerHTML = '' + score.max;
    }
    ui.score.speed = function(speed, turn) {
      speedDom.innerHTML = '' + speed;
      turnDom.innerHTML = '' + turn;
    }

    function start() {
      ui.score.clear();
      ui.message.clear();
      board.current = board.create();
      board.random(board.current);
      ui.board.update(board.current);
    }
    document.getElementById("start").addEventListener("click", start);

    function up() {
      var updated = board.move.up(board.current);
      if (updated) {
        board.random(board.current);
        ui.board.update(board.current);
        ui.score.update(board.current);
      }
    }
    document.getElementById("up").addEventListener("click", up);
    function down() {
      var updated = board.move.down(board.current);
      if (updated) {
        board.random(board.current);
        ui.board.update(board.current);
        ui.score.update(board.current);
      }
    }
    document.getElementById("down").addEventListener("click", down);
    function left() {
      var updated = board.move.left(board.current);
      if (updated) {
        board.random(board.current);
        ui.board.update(board.current);
        ui.score.update(board.current);
      }
    }
    document.getElementById("left").addEventListener("click", left);
    function right() {
      var updated = board.move.right(board.current);
      if (updated) {
        board.random(board.current);
        ui.board.update(board.current);
        ui.score.update(board.current);
      }
    }
    document.getElementById("right").addEventListener("click", right);

    document.body.addEventListener("keydown", function(event) {
      var key = event.keyCode || event.which;
      switch (key) {
          case 38: up(); break;
          case 40: down(); break;
          case 37: left(); break;
          case 39: right(); break;
      }
      return false;
    });
    
    ui.message = {};
    var messageDom = document.getElementById("message-area");
    ui.message.clear = function() {
      messageDom.innerHTML = "";
    }
    ui.message.set = function(msg) {
      messageDom.innerHTML = msg;
    }

    function step() {
      ui.message.clear();
      if (board.gameOver(board.current)) {
        ui.message.set("Game over!");
        return;
      }
      var tmpBrd = board.create();
      board.copy(board.current, tmpBrd);
      var fn = ai.current(tmpBrd);
      if (typeof fn === 'undefined') {
        ui.message.set("I don't know how to move!");
        return;
      }
      var updated = board.move[fn].call(null, board.current);
      if (updated) {
        board.random(board.current);
        ui.board.update(board.current);
        ui.score.update(board.current);
      } else {
        ui.message.set("Wrong move!");
      }
    }
    document.getElementById("step").addEventListener("click", step);

    function finish() {
      ui.message.clear();
      var step = 0;
      var tsFrom = new Date().getTime();
      while (!board.gameOver(board.current)) {
        var tmpBrd = board.create();
        board.copy(board.current, tmpBrd);
        var fn = ai.current(tmpBrd);
        if (typeof fn === 'undefined') {
          ui.message.set("I don't know how to move!");
          return;
        }
        var updated = board.move[fn].call(null, board.current);
        if (updated) {
          board.random(board.current);
        } else {
          ui.board.update(board.current);
          ui.score.update(board.current);
          ui.message.set("Wrong move!");
          return;
        }
        step++; 
      }
      var tsTo = new Date().getTime();
      ui.board.update(board.current);
      ui.score.update(board.current);
      ui.score.speed(step*1000.0/(tsTo-tsFrom), step);
      ui.message.set("Game over!");
    }
    document.getElementById("finish").addEventListener("click", finish);

    var ai = {};

    ai.random = function(brd) {
      var tmpBrd = board.create();
      do {
        var action = ["up", "down", "left", "right"][Math.floor(Math.random()*4)];
        board.copy(brd, tmpBrd);
      } while (!board.move[action](tmpBrd));
      return action;
    }
    document.getElementById("ai-random").addEventListener("click", function() {
      ai.current = ai.random;
    });

    ai.nextMaxScore = function(brd) {
      var tmpBrd = board.create();
      board.copy(brd, tmpBrd);
      var maxScore = -1;
      var action;
      if (board.move.up(tmpBrd)) {
        maxScore = board.score(tmpBrd).score;
        action = "up";
      }
      board.copy(brd, tmpBrd);
      if (board.move.left(tmpBrd)) {
        var score = board.score(tmpBrd).score;
        if (maxScore < score) {
          action = "left";
          maxScore = score;
        }
      }
      board.copy(brd, tmpBrd);
      if (board.move.down(tmpBrd)) {
        var score = board.score(tmpBrd).score;
        if (maxScore < score) {
          action = "down";
          maxScore = score;
        }
      }
      board.copy(brd, tmpBrd);
      if (board.move.right(tmpBrd)) {
        var score = board.score(tmpBrd).score;
        if (maxScore < score) {
          action = "right";
          maxScore = score;
        }
      }
      return action;
    }
    document.getElementById("ai-next-max-score").addEventListener("click", function() {
      ai.current = ai.nextMaxScore;
    });


    ai.nextMaxValue = function(brd) {
      var tmpBrd = board.create();
      board.copy(brd, tmpBrd);
      var maxMax = -1;
      var action;
      if (board.move.up(tmpBrd)) {
        maxMax = board.score(tmpBrd).max;
        action = "up";
      }
      board.copy(brd, tmpBrd);
      if (board.move.left(tmpBrd)) {
        var max = board.score(tmpBrd).max;
        if (maxMax < max) {
          action = "left";
          maxMax = max;
        }
      }
      board.copy(brd, tmpBrd);
      if (board.move.down(tmpBrd)) {
        var max = board.score(tmpBrd).max;
        if (maxMax < max) {
          action = "down";
          maxMax = max;
        }
      }
      board.copy(brd, tmpBrd);
      if (board.move.right(tmpBrd)) {
        var max = board.score(tmpBrd).max;
        if (maxMax < max) {
          action = "right";
          maxMax = max;
        }
      }
      return action;
    }
    document.getElementById("ai-next-max-value").addEventListener("click", function() {
      ai.current = ai.nextMaxValue;
    });

  </script>
  
</body>
</html>