18 Mar 2014

2048-AI

written by hunter | Tags: , , , ,

You know those times when you jump cleanly out of your comfort zone, away from all the stuff you know, for the pure purpose of experimenting and exploring and trying to learn something new on your own? No? Well, regardless, this was one of those cases for me.
Back when 2048 was just getting big, I was busy maintaining that it was the stupidest thing. I didn’t see the playability at all, and I couldn’t comprehend why so many of my friends were trudging through English class, their heads glued to their laps as they endlessly swiped numbered blocks beneath both their desk and the gaze of the teacher. I didn’t get it. Though, just because I didn’t understand it as a game doesn’t mean I couldn’t appreciate it as a concept. And 2048 was, indeed, a really interesting concept. At the very least it posed a very interesting problem. And that’s what I saw it as. Not as a game to be played, but as a problem to be solved. 2048-AI was my attempt at solving it.
 
(If you just came for the sandbox and for the code, you can skip to the bottom. Before that, I just talk a lot about what I tried to do)
 
First and foremost, I’ll acknowledge readily that 2048-AI is a misnomer. It’s got to do with 2048, sure, but it’s in no ways an AI. It’s an assortment of algorithms attempting to maximize the score of the game, but I’d hardly call it artificial intelligence. Heck, I’ll spoil the story right now and admit it’s not even very intelligent. I wrote the program as a lowly Pre-calc student who’d never done any formal learning on artificial intelligence nor tried to solve a game before. The closest I’d come was with a dumb recursive solution for tic-tac-toe I’d written in Java the year before. Long story short, the best algorithm I came up with can play 2048 marginally better than I can, but I’ve got plenty of friends who can still blow it out of the water. The long version of the story is as follows:
For the uninitiated, 2048 is a game originally programmed by Gabriele Cirulli that focuses on moving numbered blocks across a grid to combine equal-numbered tiles (so 1 + 1 for 2, 2 + 2 for 4, 4 + 4 for 8) all the way up to the magic 2048 tile, and all without filling up the grid and running out of options and getting stuck. You can play it here if you haven’t already though, be forewarned, it’s actually rather difficult. The goal for 2048-AI was just to play around. I wanted to get a computer to analyze the state of a game of 2048 and then try to solve it, maximizing the number of points scored.
The first step, then, was to fork Cirulli’s code and hack my way into it, positioning myself to send game-input in the form of a Javascript function. That part wasn’t too bad. I ended up with very little modification of Cirulli’s code, mostly just adding a couple lines to let me access the game board from my own code. Additionally, I copied his gameboard code into a separate model.js file that let me model play of the game (for recursively testing movement options) without modifying the actual game being displayed. After that, I was ready to dive in.
I coded up a simple HTML UI on the page for selecting the algorithm that was to be applied to the game, and then spent a few days coding up new approaches in my idle time. I started with a simple ‘Random’ that, as its name would imply, just plays the game randomly. This was to get a baseline on how random play would affect score. Indeed, that script never scored particularly well.
In response to that, I tried a couple different approaches that manifested themselves through a few different iterations of the scripts themselves. The simple approach was to follow the maxim that most of my friends swore by: pick two directions and, unless otherwise impossible, ALWAYS move in one of those two directions. So for this approach, I had the computer attempt to pick between those directions, choosing based on which would immediately make the score higher (so that it would automatically attempt to combine tiles where possible). My alternative approach, which ended up scoring the best with a single caveat, was to recursively branch through the game and pick whichever path either (a) won the game or (b) increased the score the most.
The recursive algorithm seemed to do well, too. At least, compared to everything else that I’d tried. I even weighted the choices so that the computer would try to pick two directions over the other two (keeping with the victory maxim of my friends), and that proved to increase my scores slightly further. I never managed, however, to beat the game.
The main problem was probably in my approach. More recently I’ve read solutions to the game that focus on trying to achieve a certain pattern of numbers on the board. Whereas my approach tried to immediately maximize the score and the tile-numbers on the board, this winning approach (which I can’t seem to find at the moment) tried instead to achieve a certain state/arrangement of pieces on the board. This makes sense as an alternative approach because the key problem I found with my recursive solution was that the tiles would always tend to line up in this diagonal pattern. Always trying to score points, most games would end with the highest tile in the corner, then each successive diagonal radiating outwards would consist of the next tile down, until there were no more diagonals to fill and the game would end having no options for continued play. Clearly, my approach was sub-optimal.
But it was still, certainly, an exciting attempt. Certainly successful, in my opinion. It was something I’d never tried before, and yet I still managed to get the computer playing better than my (untrained) hand. Not bad for an unguided swing at it. And the aimless tinkering there kept me more than occupied for a good amount of time. Otherwise, with the story out of the way, here’s what actually went into the project.
 
The Basics:
Name: 2048-AI
Language: Javascript. HTML/CSS.
Source: Right here.
Tools: Cloud9 IDE, Github
 
The Link:
The game’s hosted on the Github page, so you can find a running copy at the link below:
http://huntrr.github.io/2048/