Hacking Boggle: Designing A Fast Solver For A Timed Word Game

Zynga released the Android version of their Scramble with Friends game last weekend, which was our first contact with the game. It’s a social version of Boggle – the players take turns finding words in a 4×4 grid of letters, with a couple of additional elements Zygna threw in to spice things up. So naturally we decided to write a solver for it 🙂

Writing word game solvers has become something of a hobby for me. My first project was a Hangman Solver: this started off as a regex filter (Python) applied to a word file which we tweaked to make it more efficient. The next step was modify the program into a Hanging With Friends Solver: there are a few tweaks in Zynga’s rules which make it easier to guess a word (reduced number of possible answers). This website was built by taking these two Python functions and embedding them in a web framework.  The front end is HTML dressed up with some basic JQuery.

Our scrabble word builder served as the starting point for the boggle solver. Scrabble requires an efficient search through the possible combinations of a sequence of letters. Boggle is a twist on scrabble: instead of searching the permuations of a sequence, you’re searching the possible paths through a n x n grid. The required change was a handful of lines in Python to implement.

Drawing the web page was also simple: since a grid is basically just an array with line breaks (thank you, CS 101), we cannibalized the array widget from our other solvers. So far, so good….

Most of our prior solvers relied on the stately “chess-like” pace of play in Hangman and Scrabble. The solver automates the process of finding “options”: we presented a list of possible words, from which the player must select the best option (score + plausibility). From a user perspective, they have the time to flip between screens and page through lists of ideas, since they only need to select and play a single word.

And this is where things came undone….

Instead of passing a sequence of seven letters back and forth, Scramble with Friends (Boggle) requires you to pass a set of sixteen letters into the solver and enter multiple words into the application as your answer. Remember, humans can only hold a small amount of data in memory, forcing the user to make multiple trips. Our solver walked into a “pipe capacity” problem: we needed to move too much information through the player for the available time…

Thank you Mario, but our princess is in another Castle..

For all you aspiring game designers out there, know this: speed is a great antidote to cheating. Speed matters in Boggle / Scramble with Friend. Judging from the boards I saw during testing, a typical Scramble with Friends grid has 300 – 400 possible words. A fast player (like my wife) can knock out 30 – 35 words per hand. Relatively intelligent slowpokes like myself are limited to about 20. That’s a 50% increase in “raw points”, most of which are likely to go unopposed (since those are 10 incremental words). If a game of scrabble will go to the smartest player, a game of boggle goes to the fastest.

This emphasis on speed is facilitated by the fact a good natural player can knock out 500 – 600 points per round using techniques like word stemming (plurals, suffixes, and  prefixes). These are best done outside a solver (eg. looking at the screen) to reduce the amount of screen flipping. Zynga also added an inspiration option to the game, which provides the user with some suggested words to play. These are all alternatives to using a solver (or things you may use in combination with a solver).

So What Actually Helps Here?

First, reframe the problem into something we can actually solve. There just isn’t time for screen flipping: between the time required for a cell phone to switch screens and the limits of human memory, you won’t get enough speed to make the exercise worthwhile. Now if they are using a regular computer or another phone… we’ve got a chance…

You should also consider the fact that the typical user wants an edge but doesn’t want to lose “respectability”. While there are technical options for quickly getting the data into the solver (screen snap -> OCR), most of these actually have a short user lifecycle (for non-psychopaths) since they’re too high powered. After a weekend of absolute carnage, the thrill wanes.

Next – define how the solver is going to help, relative to natural play. Two things matter in boggle: word quality (points value) and word entry speed. Word entry speed breaks into two parts: time spent finding words, time spent “drawing” the word. Identify what you can improve (points value, pattern recognition) and what you can’t (drawing speed).

The most obvious thing we can do to improve points value is to rank our possible words in descending order. That came down to an embarassing trivial Javascript array sort. We already had a JQuery word list widget from our earlier work. Done. While I may only crank out 20 words, I can now find “senator”, “fiendish”, or other high scoring ideas.

Now lets attack the problem of helping the user find words on the letter grid. We solved this by using Javascript to add two features to the front end design. First, we used Jquery to highlight cells containing the letters for the word (green for the first letter, red for the last letter, yellow for everything in between). Next, we used the jsPlumb library to draw lines between the letters in a word. Instead of looking at a wall of letters, the user now sees this:

I was blind but now I see! This was a critical process improvement: our test users spent a lot of time staring at the word grid, trying to find the suggestions. Highlighting the word and drawing the path made it easy to see what you needed to plug into the mobile app. The jsPlumb library was easy to use; however it doesn’t always work for mobile viewers.

To squeeze a little extra performance out of the solver, we worked on reducing the time required to use the solver. We added a “next word” button to help the user quickly page through the suggestions. We added a quick entry box for experienced users: quickly type all the letters in the 4 x 4 grid into the box and it will populate the grid for you. Simple stuff, but no sense in losing performance by neglecting basic UI elements…

Finally, don’t be reluctant to coach your users. The idea usage pattern for this particular solver is actually NOT to use it to play every word. I’ve gotten the best results by using the solver to identify the highest scoring words (juicing my score by 100 – 150 points), then using “word stemming” (plurals, prefixes, suffixes) to crank out a bunch of related words. The “inspiration” option is also pretty useful (Zygna gives you three words).

The final product works pretty well.The solver is more helpful to middle-of-the-road players, where it gives them a few hundred extra points per round. A good natural boggle player often solves the letter grid in their head faster than with the solver.

Before we close, I’d like to point out some of the stuff that we didn’t do in this approach. We didn’t waste any time trying to get the solver to work for a mobile browser… since that isn’t the reasonable use case (can’t flip back and forth fast enough). We also focused our work on only a handful of areas, ignoring several additional improvements, and recycled our existing code. This let me crank out a first working solver in only two evenings of work (one for the solver, one for the UI).

This was a fun little project: while the solver itself is a pretty frivolous application, jsPlumb seems like a pretty useful addition to my toolkit going forward. There are definitely some real world applications for this great little library.

More importantly, I now have a hope of beating my wife at Scramble with Friends!

If you liked this article, share it!