Looking Out To Sea

As mentioned before, I have been thinking about solving Boggle. The best approach is always to start with what you know. We must first decompose the game into its discrete steps so that the problem doesn’t seem too overpowering.

These are my initial thoughts on the game, which may change as the implementation takes shape.

The Board

Boggle takes place on a 4x4 grid (I’m ignoring the 5x5 variant for now). Each place on the grid contains a letter, chosen randomly from six at that position. (In real life, these six are stamped on the faces of a die.) Most of the dice contain only single letters, but there’s also a “qu” variant to allow creation of legitimate English words with the letter Q.

The “qu” variant is a pain, because it means that there is no uniform representation of the grid contents. They’re not all single letters. But representing them all as strings seems wasteful because most of them are single-character strings.

The Game

The idea is to search for words that use adjacent letters on the randomised grid. You can’t reuse letters, but you can move horizontally, vertically and diagonally from any starting point. If you’re lucky you can spell a 16-letter word. In fact, if you get “qu” you can spell inconsequentially. That’s seventeen letters. ;-)

In my mind I can almost see the tightly-bound grid unravelling and hanging out into an n-ary tree. The n in this case is somewhere between 1 and 8, depending on how many neighbours a particular letter has. If only my animation skills were up to the task of showing it!

The words have to be at least three letters long, although this isn’t immediately helpful as far as implementation goes. It doesn’t suggest any useful shortcuts.

The End Game

Once you’ve got a word you have to check if it’s a real word. (This step is somewhat glossed over in real life because people shouldn’t just be writing down arbitrary collections of letters.) The idea is that you get points for long words, but if another player has the same word as you then neither of you get the point. Points are only awarded for unique words.

The person with the most points by the end of the match is the winner. The computer would not be an interesting player in this case. What would I do to simulate imperfect players?

• Put a limit on the character length. Long words are harder than short words for humans.
• Reduce the number of words in the dictionary, since not everybody has a huge vocabulary. Again, a bias for short words would be more realistic here.
• Implement a timer and search in a slow, random fashion so that not all the words are found on each run. Real people don’t work systematically through all the combinations (or maybe I’m just a poor player…).
• Some advantage to the player who can read the grid in the normal orientation, rather than from the side or upside-down.

If I randomly set some of these variables at the start of a round then it might be a more realistic game. Any other ways that the computer could be handicapped to be more like a human player?

Photo from 4rank’s Flickr page.

Trackback URI | Comments RSS