I am trying to write a boggle solver right now.

What I have done so far is not to generate each possible path, but to move in each direction and see if that direction is a legal move. If it is, then I check whether the resulting “word” is (a) a prefix to a dictionary word, and (b) a dictionary word. The prefix is part is important because if it’s false, we don’t need to generate any more paths from that “word,” and that prunes some of the search space.

The adjacency list is not something I’d heard of (still new to this) so thank you for bringing it up. I have a feeling that it’s a very useful thing in general.

Using a real spell-checker… that is pretty clever
Here is a text-file Scrabble dictionary, if you want it, 6 months after posting, even: http://www.calvin.edu/~rpruim/scrabble/ospd3.txt

Oh and I can tell the games that are played by bots, it’s fairly obvious, the cheater often leaves their POGO profile blank ( a true lover of words doesn’t do that) or the profile is incredibly dull and unimaginative, and as New Age weirdo as this may sound you can feel the energy of the cheater is not the same energy of a true word lover. Sometimes you feel no human energy period, so I suspect the cheater either has the program running and is not even on their computer, or maybe they are but not on POGO ( how they would do that I have no idea).

I think you should create an anti cheat program/bot, to me that would be an honorable and, I bet, fun thing to do. Imagine the hilarity when a cheater goes into a room on POGO, particularly Boggle Bash and they sit there all smug just knowing they are going to win when aha the anti cheat program kicks in and hahahaha nothing! It no longer works! Imagine the frustration and then the anger that would arise as they keep trying to get their cheat software, or is it hardware, sorry, I am computer illiterate, but no matter what the term is, it would be quite humorous that they could no longer cheat. I say use your genius and ability for good! And having an anti-cheat bot is good! You computer geniuses should do good things, like go after cyber bullies, ( finding their personal info and sending them e-mails letting them know you know who they are, where they live etc and if they do not cease being bullies online you will out them on various message boards and chat rooms they are…. as you know vermin hide in the darkness, when the light comes on they scurry away), and you could use your talents in going after cheaters at games, and you could screw up sites that send spam, viruses, worms, etc. If I were brilliant at computers I would do those kind of things.

Yeah, I think the runtime is exponential in the size of the interval list, so that’s obviously not great. But at first glance this problem seems almost identical to the knapsack problem, so I’m guessing there’s no real easy optimizations (but as always, I could be wrong).

Thanks for your comment; I can see that you have some fairly strong feelings regarding this subject, so let me clear up a few details.

First, my motivation for doing this project was not so I could cheat at BoggleBash. It was simply a problem that I found interesting, and decided to work on one weekend. You asked “What does one accomplish by cheating?”, but that question misses the point of this exercise. I’m not out to get more POGO points, I’m simply trying to gain a better understanding of AI algorithms, and further my programming skills. I don’t think there’s anything immoral about that.

I understand your frustration regarding bots. But honestly, even if I didn’t do this project, a BoggleBash bot was going to get built. Heck, during testing, my BoggleTrainer was beaten (sometimes soundly) by other, more sophisticated bots. That’s just how it goes in the world of online gaming: it’s all an arms race. The servers build better bot detectors, so people build better bots. IMHO, being able to tell the difference between a computer operated by a human and a computer operating itself seems like a nearly impossible task.

In the end though, I don’t think bots completely ruin games. We have computers that can play (nearly) perfect games of Scrabble and poker, yet Scrabulous and online poker are as popular as ever. When Deep Blue beat Kasparov, people didn’t up and quit playing chess en masse. In fact, computers have been helping chess players become stronger than ever by allowing them to analyze thousands of possible lines quickly, and scan through libraries containing hundreds of thousands of games.

Anyway, I’m sorry this project got you so worked up. I hope I’ve given you a better understanding of my motivation to work on it.

I truly hope all the dumb cheaters, who are far too ignorant to play fairly, well I hope bad things occur to them. And really what does one accomplish by cheating? The cheating creates anger in those who have good morals and don’t cheat and their games get screwed up as well, since the cheat programs steal the words in the non cheaters games. So I hope all bad things come to the cheaters, I truly do and I want to write a great big thank you …sarcasm there…. thank you for taking what is a fun and relaxing game and turning it into a negative energy game and ruining the fun, thank you soooo much,,, again sarcasm. May karma get all the cheaters!!! And yeah even little non important ( to cheaters) things likle cheating at games is bad energy and yes is immoral, with morals they go across the spectrum of human behavior and traits and even things like cheating at games is bad.

O_o

Thanks for showing me your solution to the problem, it’s definitely much more elegant than the one I hacked together It’s also a good reminder to strengthen my functional-programming-fu, as I definitely don’t (ab)use generators as much as I probably should in my python code.