2048 AI

I was actually thinking a new game AI competition.

When playing against a random opponent, sometimes it will "accidentally" make the best possible move. In chess, this might be extremely unlikely, as there are so many possible moves: the probability that, of all the pieces on the board, with all of the positions it could have made, that it would stumble upon a move that devastates your position--especially considering that often multiple correct moves must be performed in specific sequence to take advantage of what "should be" a winning position--is vanishingly small.

Further: the potential for gain (trivial mate against a stupid opponent in a handful of moves) is great. If you are thereby playing for "fastest win over time", taking advantage of random's suboptimality seems sane. In 2048, the bottleneck on your score seems best approximated by how long you survive: pulling stunts won't get you to 2048 all that faster as you need to have worked through enough tiles to arrive at that point: I'd imagine the difference would be at best a tiny fraction of the "required" moves.

Meanwhile, the computer has only a few possible moves, increasing the probability of doing something accidentally optimal. As you approach the end, needing over half the board just for unbuilt path up to 1024 and thereby not having as much scratch space, the probability of it hitting a problematic (even if not "devastating", one that suddenly requires you to reorganize things to "clean up the mess") move seems more more of a problem than when playing chess.

In summary: I just don't think comparing this game to chess is leading to useful intuitions.

I'm running some trials here and keeping track of the results with this AI. I'll edit this when I have the data to provide the information.

Something that occurred to me is that "score" and "winning" can have different optimizations. Score is based upon combining blocks, where as winning is based upon reaching the 2048 block. This means the game can be optimzed in two different ways: 1) To maximize score, wherein your goal is to delay reaching 2048 until the last possible moment to allow yourself time to rack up score, and 2) to reach 2048 in the optimal number of moves, which means a lower score.

You're scored on what you combine in a move. So, if you combine two "4" tiles to yield and "8" tile, you'll get 8 points, and so on. To maximize score, the idea would be to basically waste space on the board building up tiles you don't need, while avoiding getting to 2048. In theory, one could build up many 1024 tiles, and maybe even combine several at once to yield multiple 2048 tiles.

To minimize moves in order to reach the fastest would basically be a game of golf. You'd need to reach 2048, but the lowest score in doing so would, by default, mean you've completed the game more efficiently. There's probably some absolute minimum score, but I'm too lazy to figure that out right now...

Back in college I implemented a checker AI that used minimax and a neural network that was trained with a genetic algorithm. After 4 days of tournament on a 400mhz box the resulting AI would almost always beat me. It was always fascinating to me that it used a 4 ply minimax with a 50 hidden nodes and 90 inputs to handily kick my ass.

I always wanted to re-implement it in node and for a cooler game. Alas! I have too many side projects.

The source is here: https://github.com/mkoryak/Evolutionary-Neural-Net-Checker-A...

and you can play against it here: http://mkoryak.github.io/checkers/nn_checker_ai_demo.html (requires java, might also require a 7 year old computer)

I won with using basically this strategy. I was forced to use the other direction exactly once.

http://i.imgur.com/4Ig74Q9.jpg