BrainBrain View Note

I've always wanted to write a word game like Boggle: a game where the player has to form words using the letters on dice. It's a fun game, and would be a good addition to my Flash library. So I built Worgle, or I should say, am building Worgle. The computationally interesting parts are all finished, and they are described here.

For those unfamiliar with the game, there is a grid of 4x4 squares and several dice. The dice are tossed around in a shaker and land in one of the cells of the grid. Each die then shows a single letter on top. The players form words by connecting the letters on neighbouring dice, direct or diagonal. A die may only be used once in a single word. Longer words score more points, and the player with the most points wins.

To see the work in progress look at the the current pre alpha test infant demo version.

I've not done writing all the support articles yet, so a few links may go nowhere.

Algorithms

Ignoring the aspect of multiplayer, the core mechanics of the game require only a few algorithms. Firstly, a way is needed to determine whether the word the player has entered can actually be formed with the given board. Secondly, that word needs to be looked up in a dictionary to check for correctness. And finally, a way to generate random boards is needed.

Checking the board correctness of a word is the simplest of the three and described here.

Generating a board, if you have a set of dice, is quite trivial, so instead you may be interested in how to produce a set of dice with appropriate letters.

Looking up a word in a dictionary doesn't seem very interesting at all; there are hundreds of algorithms which do such things. So instead, let us consider that we have a computer player involved.

Computer Player

At its core, the computer player will be an algorithm to find all the possible words for a given board. Playing against this genius computer is simply no fun however, even on what appears to be an impossible board it will find many words. So the actual abilities of the computer exposed to the player can be formed by passing this complete word list through various filters. That is however not what we are interested in now; the interesting part is how to produce the complete word list.

There are really only two ways to do this: 1) take a known set of words and check each of them in turn if they exist on the board; and 2) permutate the possible sequences on the board and look up each result in a dictionary.

The first option seems entirely reasonable, and indeed if you are using a decently performant language, like C++, it might be viable. But instead we're stuck with Flash, which has absolute dismal computation performance. Thus the option of looking up some 400K words in a language dictionary is just not plausible.

For the second option we need to understand first what permuting means. It means producing all strings of letters which can be produced on the particular board. That is, the set of all sequences which would pass our isOnTheBoard() function. Refer to permuting the word-game letter grid.

Of course, this second option of permuting all possibilities on the board seems even more ludicrous. I'm not even sure how to count all the possibilities, but rest assured is thousands, if not millions, of times more than the size of the dictionary.

An insight is needed to solve this problem. Just a simple observation that not all permutations actually need to be checked. Consider that if during the permutation we are starting the word with "cq" we could know there are no words, in English, that start with this sequence. Therefore we can stop the permutation past this point and move on to the next possibility.

This approach works very well since most of the permutations yield invalid word prefixes very early in their permutation branch. In fact, this essentially limits the computation time to the size of the output set (the number of actual words on the board) rather than the input set (the total number of permutations). We thus also know it will be more efficient than our first idea to look up all dictionary words; the number of a words on a board is certainly a lot less than the number of words in the dictionary. In my version there are usually only hundreds of words on the board (compared to the hundreds of thousands in the dictionary).

Strictly speaking, if a theoretical dictionary is small enough, or the board size is extended to be large enough, the words found in the board could actually be as many as are in the dictionary. For a normal language dictionary this possibility seems obsurd, and I would suspect a proof could be derived to show only a subset of the dictionary is actually possible under normal circumstances. This proof however is beyond what is needed for this article.

Wait a minute! That description leaves a pretty big hole. How exactly "could we know" that a certain word prefix doesn't exist in the language? The simple answer is our dictionary lookup just needs to support prefix lookup. Of course, that is easier said than done, and the full answer is explained in the dictionary trie.