[creativity]
[identity][home][verbosity]
[transitivity]
creativity

Where the spirit does not
work with the hand,
there is no art.

- Leonardo da Vinci

1 0 1 1 1 1

[wordfinder]

There are probably hundreds of anagrammers and shareware tools out there that are of some use to Scrabble and Literati players. Fortunately, there do not seem to be any that are any good that are available for free. There is, however, some good documentation on how to write an extremely efficient algorithm for finding moves based on a given board and set of tiles. All it would take is some magnanimous or malicious (depending on your perspective) programmer to put together such a tool and unleash it on the Web.

I am not that programmer. I play Literati too often to see it ruined by lazy script kiddies who aren't interested in playing fair and somehow derive satisfaction from cheating. I can't understand how it would be enjoyable to win a game if you weren't even the one playing, but unfortunately sociopaths like that do exist. I used to play in a league, and I finally got fed up with the fact that people who were obviously cheating were still allowed to continue to play against those of us who weren't. I say obvious because they would play fantastically obscure words on the board, spelling them correctly on the first try, yet would still be unable to exhibit a fourth-grade mastery of the English language (or spelling, for that matter) when they chatted in game room lobbies.

No, I am not the programmer that will unleash such a tool on the Web. I am a programmer who would write one, however. I will not post the code until I modify it from a simple move finder to an interactive program that will play Literati or Scrabble against you (and very likely beat the pants off of you every single time). In that form, it is not useful to the little cheaters unless they find the initiative to learn Java and write an implementation that can actually be used to cheat based on the code I post. If they're smart enough to do that, they'd be smart enough to write it on their own, anyway. That's not the cheater's mindset, though. The cheater isn't looking to do any work of his own.

The algorithm on which I based my tool was developed by Andrew Appel and Guy Jacobson (incidentally, Appel wrote the textbook I used for my compilers class in college). The most important insight in their approach was that the game can essentially be reduced to one dimension. Once that reduction is made, the problem then becomes a simple search problem which can be very efficiently solved by representing the game dictionary as a directed acyclic word graph (DAWG).

It is trivial to create a search tree that represents an entire dictionary by defining each node with twenty-six branches, each corresponding to a different letter of the alphabet. Each node also contains a flag which dictates whether the the node is a termination point, which is set if the letters seen up until that node represent a complete word. The challenge in creating a DAWG from this search tree is eliminating subtrees that have identical flag and node patterns. Fortunately, this only has to be done once, and the resulting dawg can be stored for future use with any applicable algorithm.

I have included my Java implementation of this process here, because it is useless without the code which makes use of the DAWG to perform move searches. In fact, even if a cheater manages to compile the code and produce a DAWG, it is impossible to use it unless he understands the format in which it is being stored in the first place.

. dawggenerator.java

I'll post the actual game once it's completed.

[ Next]



[creativity]
[identity] [home] [verbosity]
[transitivity]

[comments/blog]

[ ]

[401valid]