Letterpress is a word game. I wrote a solver for it, called LetterPwn.

Try it out by hitting the ‘random board’ button. It creates a random board, makes an API request to the server, and shows you the best possible moves for the blue player at right.

It will probably do this in a fraction of a second, even if there are tens of thousands of possible moves to consider. You can pop open the “stats” link beneath the recommended words to see how much work it’s doing.

Hover over the suggested words to see the moves highlighted. Try using the tools at the bottom of the board to change letters, or simulate an ongoing game where red and blue already control some of the board, to see what LetterPwn recommends as the next move for blue. Also try the Vocabulary slider at the top right.

One of my favorite things is to create what seems like an overwhelming position for red, and then see how LetterPwn usually manages to gain the upper hand, or at least ruin the red player’s strategy.

Why?

I didn’t do this just to ruin Letterpress forever, or join the ranks of Letterpress cheater apps. It was an experiment to teach myself Node.JS. I couldn’t decide if I loved this framework or hated it. It had so many virtues, but it has so many quirks. Curiously, people often advise you not to try… computing… in this computer language.

So I decided to sail straight into the winds, and try to develop a computation-heavy service in Node, just to see how bad it would be. It turned out to be very educational. I’ve split this into two parts.

In Part I, (this document), I’ll discuss LetterPwn’s algorithm for picking the best moves for any given board. It can often rank moves in excess of 100,000 moves per second. Not bad for JavaScript!

In Part II, I discuss the programming strategies to make this service quick and responsive to many users at once. A standard Node.JS server is single-threaded, and might be stuck for many seconds serving a single user.

Ok, so, what is Letterpress?

Letterpress combines two different kinds of games in one.

Given a 25-letter square board, players take turns discovering words. The letters of that word then change to the player’s color (usually red versus blue). When the board is completely colored, the player with the most colored letters wins.

The twist: unless you completely surround a letter, your opponent can steal it back. Vocabulary is your main weapon, but it’s really a battle to take over territory.

Discovering all the possible words on the board

This is such a simple problem it’s often posed in software interviews. I didn’t do anything all that special here.

There is a dictionary file out there which purports to be the word list that Letterpress uses.

The trick relies on building a mapping of each word to the letters in that word, sorted in some canonical order. I used alphabetical:

multurer → elmrrtuu
mum → mmu
mumble → belmmu
...

Then, we sort the board in the same way:

Then, to find mumble, we search for belmmu in abccceeffjjjkklmmmppqtuvw. Using a canonical order it makes it easy because then you can just scan or skip over letters as they match. We could also use a histogram so we wouldn’t need to scan each letter repeatedly, but it’s simpler this way.

Most Letterpress solver apps stop right here. They just give you the longest word that fits on the board.

Do we stop there? Of course not.

First of all, most Letterpress cheating apps recommend words like hagioscopic, which is rather unsubtle. So I gave LetterPwn a sense of how rare words are, using the Google Ngram corpus.

Right now this manifests as a slider which gives you the option to play at different levels: basic, common, highbrow, obscure, and sesquipedalian. This might be useful in creating an adaptive AI, that plays with a vocabulary similar to yours.

But more than just vocabulary, the longest word is rarely the most strategic word to play. To do that we’re going to have to examine the current state of the board, and all the possible ways to play words.

Representing board state

It turns out that everything we need to know about the board can be represented with 25-bit bitmaps. This easily fits in a standard integer, so we can represent the whole board with a couple of numbers. Furthermore, we can then perform calculations on the entire board with simple bitwise operations. Bitwise operations are insanely fast, and this is the main reason why LetterPwn can evaluate so many moves per second.

Let’s see how this works. In the middle of a game, the board might look like this:

We need some way of representing that board state.

It’s easy enough to represent the board, with just a 25-letter string: efpjaccwcejfjvkqmmpbkumlt. Note that here, the order matters, so we don’t sort it.

And as for the colors? Let’s look at just the blue squares for now.

The deeper blue color is just something to remind us that it’s protected due to its neighbors. But it’s not really new information about what squares we control. So we can ignore that, too:

It seems that square can either be colored or not. So we could say each square was on, or off.

That immediately suggests a binary number, to represent the entire board. If we start from the top left corner…

That works out to this binary number:

1

0000000000000101000100011

Remember, just like regular decimal numbers, the rightmost number is the smallest one.

That binary number has a decimal equivalent,

2595

And that’s how LetterPwn currently stores and transmits board state, with these three values:

board: efpjaccwcejfjvkqmmpbkumlt
oursBitMask: 2595
theirsBitMask: 27262992

Note that in this example, theirsBitMask is a larger number, but that just means that they’ve captured squares on the lower part of the board.

Determining all the ways to play words

So we’ve determined that mumble can be played on the board. That doesn’t yet tell us which squares to play. We have to find those squares again, and also see if there are multiple ways to play this word.

Once again, bitmaps to the rescue.

We map each letter to bitmaps of all the possible positions it could have on this board. Then, with k-combinations, we recursively produce the bitmaps of the possible ways to play this word. Note that for words like mumble, we have to make sure that we supply two Ms out of the three that are on the board.

This gives us a list of six moves we could play on the board, represented in bitmap form, so it’s just a list of six integers:

1

[11206657, 11207168, 15269889, 15270400, 15335425, 15335936]

Once we run through the entire dictionary, we’ll probably have thousands of these possible moves. Now we have to decide which one is best.

Ranking moves

Letterpress players quickly learn that capturing corners is best, and protecting one’s own squares is vital. So it’s intuitively clear that the fifth way to play mumble, shown above, is the best.

A lot of Letterpress is about adjacency - enemy squares that sidle up to yours make you vulnerable. And you protect squares by surrounding them with your own. This calculated in complex ways, but it turns out to be easy to do with (you guessed it) bitwise operations.

First we build an “adjacency map” of which squares are next to each other. For example, here’s square 18:

Now that we have a simple mapping of which squares are adjacent to which, we can easily calculate, for instance, which squares are protected:

for each square on the board
  if oursBitMask & adjacent[square] == adjacent[square]
    it is protected

I also made up a ‘vulnerability’ score, which is calculated like this:

vulnerability = 0
for each square on the board
  if it is ours
    vulnerability += countBits(adjacent[square] & ~oursProtectedBitMask)

This computes the attack surface area of a move - the potential ways for our opponent to take over our squares.

So I didn’t have to tell LetterPwn to try to start from a corner and build out from there. That strategy is just a consequence of trying to minimize the vulnerability score.

There are a few other custom calculations that it takes into account when evaluating moves, and most can be done in nano-jiffies because they are just bitwise ops against potential future states.

What’s missing

LetterPwn will mindlessly play the best move for the short-term, even if that leads to a potential win for the opponent on the next move.

Solving this doesn’t require monumentally greater computing resources, though. Once the moves are already ranked, the program could examine them in order from the opponent’s perspective. Moves that result in a win for the opponent would be discarded until we found one that was okay. Or at least estimate the minimum vocabulary the other person needs to have in order to beat us on the next move.

The end result

You can see for yourself by popping open the ‘stats’ link on LetterPwn.

Believe it or not, most of this is I/O. This example is from a live demo running off Heroku.

For almost any board, at the more reasonable vocabulary settings, LetterPwn will return results literally faster than you can blink. It can often rank possible moves in excess of 100,000 moves per second.

However, you can contrive boards with a lot of common letters, which will slow it down for quite a few seconds. The charm, (or stupidity) of Node.JS is that it serves requests one at a time. So if we coded this naively, the server could be completely tied up with one request for entire seconds. Check out part II to see what we can do to make this not only fast, but able to serve many users at once.