{
 "metadata": {
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Outline of post"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Let's try to implement the 2048 game in Python, based on my experience playing it as well as the [sources](). We'll do this with a class, that will have the following methods :\n",
      "\n",
      "- an `__init__` method that will initialize a board with two numbers\n",
      "- a `move` method that will apply a move (up, down, right or left) to the board and randomly add a new number to the board\n",
      "- a `is_game_over` method that determines if the game is finished or not"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import numpy as np\n",
      "from numpy import zeros\n",
      "\n",
      "class board_game_2048():\n",
      "    def __init__(self):\n",
      "        self.board = zeros((4, 4), dtype=np.int)\n",
      "        self.game_over = False\n",
      "        \n",
      "    def move(self, direction):\n",
      "        pass\n",
      "    \n",
      "    def is_game_over(self):\n",
      "        pass"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "game = board_game_2048()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "game.board"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 3,
       "text": [
        "array([[0, 0, 0, 0],\n",
        "       [0, 0, 0, 0],\n",
        "       [0, 0, 0, 0],\n",
        "       [0, 0, 0, 0]])"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Randomly filling a cell of the board"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "So far, so good. The first thing I want to do is to fill a cell randomly with a 2 or a 4. The way to do this would be:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from random import randint, random\n",
      "\n",
      "def fill_cell(board):\n",
      "    i, j = (board == 0).nonzero()\n",
      "    if i.size != 0:\n",
      "        rnd = randint(0, i.size - 1) \n",
      "        board[i[rnd], j[rnd]] = 2 * ((random() > .9) + 1)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "fill_cell(game.board)\n",
      "game.board"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 5,
       "text": [
        "array([[0, 0, 0, 0],\n",
        "       [0, 0, 0, 0],\n",
        "       [0, 2, 0, 0],\n",
        "       [0, 0, 0, 0]])"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Moving a vector to the left"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Next step would be to address the moving of the tiles. To do this, we'll start by moving just a single column, seen as a 4 vector and we'll implement the move to the left."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from numpy import array, zeros"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def move_left(col):\n",
      "    new_col = zeros((4), dtype=col.dtype)\n",
      "    j = 0\n",
      "    previous = None\n",
      "    for i in range(col.size):\n",
      "        if col[i] != 0: # number different from zero\n",
      "            if previous == None:\n",
      "                previous = col[i]\n",
      "            else:\n",
      "                if previous == col[i]:\n",
      "                    new_col[j] = 2 * col[i]\n",
      "                    j += 1\n",
      "                    previous = None\n",
      "                else:\n",
      "                    new_col[j] = previous\n",
      "                    j += 1\n",
      "                    previous = col[i]\n",
      "    if previous != None:\n",
      "        new_col[j] = previous\n",
      "    return new_col"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 7
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "col = array([0, 2, 2, 0])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print col\n",
      "print move_left(col)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[0 2 2 0]\n",
        "[4 0 0 0]\n"
       ]
      }
     ],
     "prompt_number": 9
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "In the next cell, we're building a couple of test cases to check that we implemented the right algorithm."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for col in [array([0, 2, 2, 0]),\n",
      "            array([2, 2, 2, 8]),\n",
      "            array([0, 2, 2, 4]),\n",
      "            array([2, 2, 2, 2]),\n",
      "            array([256, 256, 2, 4]),\n",
      "            array([256, 128, 64, 32]),\n",
      "            array([2, 0, 2, 0])]: # the last one doesn't work yet!\n",
      "    print col, '->', move_left(col)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[0 2 2 0] -> [4 0 0 0]\n",
        "[2 2 2 8] -> [4 2 8 0]\n",
        "[0 2 2 4] -> [4 4 0 0]\n",
        "[2 2 2 2] -> [4 4 0 0]\n",
        "[256 256   2   4] -> [512   2   4   0]\n",
        "[256 128  64  32] -> [256 128  64  32]\n",
        "[2 0 2 0] -> [4 0 0 0]\n"
       ]
      }
     ],
     "prompt_number": 10
    },
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Putting it all together: moving the grid"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Since this seems to work like the real game, we can now go on to the main algorithm for moving the board along the four directions. This is done using the algorithm from the previous section but taking into account the symmetries of the board: individual moves are just a couple rotations away from the move to the left we have implemented above."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from numpy import rot90\n",
      "\n",
      "def move(board, direction):\n",
      "    # 0: left, 1: up, 2: right, 3: down\n",
      "    rotated_board = rot90(board, direction)\n",
      "    cols = [rotated_board[i, :] for i in range(4)]\n",
      "    new_board = array([move_left(col) for col in cols])\n",
      "    return rot90(new_board, -direction)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 11
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "game.board"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 14,
       "text": [
        "array([[0, 0, 0, 0],\n",
        "       [0, 0, 0, 0],\n",
        "       [0, 2, 0, 0],\n",
        "       [0, 0, 0, 0]])"
       ]
      }
     ],
     "prompt_number": 14
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for i in range(4):\n",
      "    print move(game.board, i), '\\n' "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[[0 0 0 0]\n",
        " [0 0 0 0]\n",
        " [2 0 0 0]\n",
        " [0 0 0 0]] \n",
        "\n",
        "[[0 2 0 0]\n",
        " [0 0 0 0]\n",
        " [0 0 0 0]\n",
        " [0 0 0 0]] \n",
        "\n",
        "[[0 0 0 0]\n",
        " [0 0 0 0]\n",
        " [0 0 0 2]\n",
        " [0 0 0 0]] \n",
        "\n",
        "[[0 0 0 0]\n",
        " [0 0 0 0]\n",
        " [0 0 0 0]\n",
        " [0 2 0 0]] \n",
        "\n"
       ]
      }
     ],
     "prompt_number": 15
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "As this seems to work, we can complete the class design. At every move step, we apply the movement to the existing grid. If the returned grid is the same as before, then it's not a valid move. If the move was valid, we add a random tile."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def main_loop(board, direction):\n",
      "    new_board = move(board, direction)\n",
      "    moved = False\n",
      "    if (new_board == board).all():\n",
      "        # move is invalid\n",
      "        pass\n",
      "    else:\n",
      "        moved = True\n",
      "        fill_cell(new_board)\n",
      "        \n",
      "    return (moved, new_board)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 20
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "main_loop(game.board, 2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 24,
       "text": [
        "(True,\n",
        " array([[0, 0, 0, 0],\n",
        "       [0, 0, 0, 0],\n",
        "       [0, 2, 0, 2],\n",
        "       [0, 0, 0, 0]]))"
       ]
      }
     ],
     "prompt_number": 24
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}