Simmoril’s Domain

Introduction

So, I recently became addicted to an online game called Boggle Bash, which is pretty much the original Boggle with a couple of twists thrown in. Although I’d been playing it for a couple weeks, at the very outset I had an overwhelming urge to build a program to ‘assist’ me in playing Boggle Bash. This is the story of me finally giving into that urge.

The Rules

For those of you who haven’t played Boggle, it’s a word game where 16 die are randomly ‘thrown’ into the slots of a 4×4 grid. The goal of the game is to form as many words as you can before the timer runs out. How do you form a word? Well, you start at any slot and move to any adjacent slot (up,down, left, right, and diagonally) that you haven’t already visited. Here’s a screenshot from the Boggle Bash website to illustrate:

In this example, you can form the word TEN by starting with the T in row 2, column 4, and moving down to the E, then diagonally down to the N. But, you can’t form the word TENSE, since you can’t use the one E twice. There’s some other weird nuances, like no words less than 3 letters long, no proper nouns, no acronyms, etc., but you get the basic idea.

Bending the Rules

Some of you out there might already begin to see how a computer program could play Boggle. One method (and, coincidentally, the one I chose) is brute force, which is a two step process:

1. Find every single possible legal combination of letters.
2. Check each combination of letters. If it’s a word, keep it. If not, discard it.

Simple, yet highly effective. Let’s take a look at each step.

Walking a Boggle Board

One way to look at the Boggle board is not as a 4×4 grid, but as a graph with 16 nodes (sorry, my graphviz skills suck, tilt your head to see it oriented properly):

The problem of finding Boggle-legal words now becomes the problem of finding paths on the graph that have 3 or more vertices (without visiting any vertex more than once). Fair warning: the following explanation might not make total sense, and I take full responsibility.

Building the Graph

The first thing we need to do is build a representation of the above graph by creating an adjacency list, which is just a list that tells us which vertices are connected to which.

We start with a 4×4 matrix representing the Boggle board. This matrix is then used to build the adjacency list via the following algorithm: for every vertex in the matrix:

1. Try to move in all 8 directions (up-left, up, up-right, left, right, down-left, down, down-right).
2. For each direction, if you haven’t walked off the matrix, add the new vertex to this vertex’s adjacency list.

So, as a quick example, starting with node 0, we see we can walk right, down-right, and down, so the adjacency list for 0 is (1, 4, 5).

Finding all valid paths

Given the adjacency list, we now need to find a list of all valid paths through the graph. We start by trying to find all valid paths of an arbitrary length, call it n. To do this, for every vertex in the graph:

1. Use the adjacency list to find all vertices adjacent to the current one that you haven’t already visited.
2. For each adjacent vertex, find all paths of length n – 1 from that vertex. Tack on the current vertex to each path you find and voila! You have now found all paths of length n from the given vertex.

Sound confusing? Yeah, it was to me at first too. Here’s a quick example to illustrate: say you wanted to find all paths of length three. The method above takes us through the following steps:

1. We start at vertex 0, and the adjacency list tells us we can go to vertices 1, 4, and 5. We now look for all paths of length 2 from these vertices.
2. We start with vertex 1. The adjacency list tells us we can go to vertices 0, 2, 4, 5, and 6. We discard vertex 0, since we’ve already visited it, leaving 2, 4, 5, and 6. We now look for paths of length 1 from each of these vertices.
3. We start with vertex 2. Since our path length is now 1, we stop here, and record our first found path of length 3, namely (0 -> 1 -> 2).
4. We now start with vertex 4 from step 2. Again, the path length is now 1, so we stop here, and record the second found path of length 3, namely (0 -> 1 -> 4).

Building lists of paths for every length from 3 to 16 gives us a list of every valid path through the Boggle board (yes, there are a lot of them!).

Finding Real Words

So now we’ve got this big list of paths like (0 -> 1 -> 2), (0 -> 1 -> 4), (0 -> 1 -> 5), etc. The next task is to turn these paths into strings, and check if the strings are valid words. This step is actually quite a bit easier than building the list of paths. Just substitute letters for each of numbers, put all the letters together, and then use a spell-checker to see if the string you have it a valid word. For example, using the above graph and Boggle screenshot, we can translate the path (0 -> 1 -> 2) into the string JED. Our spell-checker (hopefully) tells us that’s not a word, and so we discard it.

From Theory to Practice

And now for the punchline you’ve all been waiting for: my implementation of the above method is written in python, and consists of two classes: BoggleBoard.py and BoggleTrainer.py. BoggleBoard uses the above method to generate a list of all possible paths. BoggleBoard is actually quite a bit more flexible than is needed, as it can generate valid path lists for Boggle boards of arbitrary dimensions.

BoggleTrainer then uses this path list and a given board layout to generate a list of all possible strings. It then checks those string using the Enchant spell-checking library. Valid words are kept, invalid words are discarded.

Reality is a Harsh Mistress

I field-tested the code for about a week or so, and the results were pretty positive. Running the code with python 2.6.2 on a 3.00 GHz Pentium 4 with 2 GB of RAM, the script was able to find all valid words up to 8 letters long in a reasonable amount of time. However, although the script works as advertised, it turns out there’s a few shortcomings:

• The script doesn’t run fast enough to be able to check every single possible string in time (a single round of Boggle Bash is 3 minutes). The bottleneck is mostly with the Enchant library, although since the script attempts to cache all possible paths in RAM, that could be a bottleneck as well. However, at longer string lengths, the odds of finding a valid word decrease rapidly. I therefore decided to make a trade-off of only scanning strings up to 8 letters long.
• The dictionary included with Enchant doesn’t exactly match Boggle Bash’s dictionary. Most notably, names and acronyms show up as false positives, and there are words that Enchant does not recognize as valid (how is ‘online’ not a word?).
• The script itself doesn’t interface with the actual Boggle client at all. The board layout has to be entered manually as a string of 16 characters, and words from the word list have to be entered back into the Boggle client by hand. However, interfacing with the Boggle Bash client wasn’t really the main point of this exercise, so this is more of a side-note than an actual problem.

What Now?

I’m sure there’s like a kerjillion different optimizations/tweaks/enhancements that I completely missed so please feel free to leave them in the comments. One I thought of right off the top of my head was to spread out the spell checking over multiple cores by using python’s XML-RPC for message passing. Another might be trying to speed up the spell-checker, or doing something with tries. Actually interfacing with the Boggle Bash client might be cool too.

That’s it for my end, thanks to Pogo.com for creating such an enjoyable game, and I hope you’ve had as much fun reading this article as I’ve had writing it!

This entry was posted on Tuesday, July 21st, 2009 at 12:46 am and is filed under General. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.