This is a writeup of the challenge 2048 from the 2014 Pwnium CTF.

I participated in this challenge together with Yoav Ben Shalom, Matan Mates, Itay Yona, and Gal Dor. This was the second CTF we participated in (as 0xAWES0ME) and this time we came in first place!

A few weeks have passed since the competition. Many writeups have been written for the competition, so I will focus my writeups on challenges that have no writeups written for them yet. These won’t necessarilly be the challenges we found hardest but they will be challenges that few other teams solved (at least other teams who post writeups).

The challenge

This challenge was to connect to a socket on a specific ip address on port 2048, and play and win a game of 2048 in less than 3:30 minutes.

When we first connect to the socket we are given instructions followed by the board. We can send back ‘l’, ‘r’, ‘u’, ‘d’ to move left, right, up, or down, and then we get a new board sent over the socket.

While some of our team members are quite skilled at 2048 (it’s part of our intense training regime), winning in 3:30 minutes is not doable even for them.

The solution, of course, is to solve the game using AI. But why write our own AI when we can use just find an open source one?

First AI

The first AI we examined is the first google result for “2048 AI”. This AI uses minimax with alpha-beta pruning to try to find the best move. You can see this AI in practice here

There were a few problems with this AI. First, it was really slow. When running on the example webpage, it did not complete the game within 3:30 minutes. At first we thought that the animations might be to blame but then noticed that the AI was utilizing the animations for processing time. So without the animations the AI will give a worse result.

The second, and more important problem, is that the AI lost. We left it running in a browser window for a few minutes and came back to a losing game that had only gotten to 1024.

The code is written in javascript. We could fix the first issue by reimplementing it in C, but there’s still no guarantee that it will win and rewriting the code is too much work. Especially when there’s a better solution.

Second AI

Discarding the first AI, we continue searching and come upon a better AI.

This AI uses expectimax instead of minimax. Minimax assumes you are playing against an adverserial opponent who will choose the best move for him at any moment. However, in 2048 the placement of new pieces is random and not adverserial. By using expectimax we can make moves that are probabilistically more likely to win faster that if we use the result of minimax.

More importantly, this implementation is written in C with a “highly-efficient bitboard representation to search upwards of 10 million moves per second on recent hardware”. Jibber jabber technobabble, faster is better.

The AI compiles to an .so and comes with an example python program to communicate with it. We just need to rewrite the input system so that it gets input from the socket instead of the browser and we can run it to play.

The code is below. It’s mostly copied from 2048.py in the repository, with the Game class written to communicate with the game over the socket.

Because it was written under time constraints, it’s ugly and ineffecient. We repeatedly convert between different representations of the board and don’t use Multithreading to make our life easier.

But it’s fast enough to beat this challenge, so it’s good enough.

Last important point: we didn’t know what the output would look like once we won, and so we didn’t properly handle it. This caused our code to throw an exception once we won, without printing the solution to the level.

Luckily, we had wireshark open in the background and so were able to see the password that had been sent to the program.

Moral of the story - keep wireshark open when solving challenges that work over sockets.