Slashdot Mirror
Word Up
theodp writes "Depending on your perspective, the National Scrabble Championship is a major sporting event, an unrivalled intellectual competition, or the world's biggest dork-fest. So says Slate's Dan Wachtell, who turned to an anagram-drilling Unix program to gain an edge on the 850+ competitors. While hardly mainstream, competitive Scrabble is getting newfound attention thanks to the publication of Word Freak and release of Word Wars."
I like Scrabble so much, I keep running down the battery on my PDA playing the scrabble-like game on it. It gave me the low battery warning this morning so I had to read during lunch.
I'll give these a look though, particularly Word Wars as even AVP wasn't as exciting as most alternative film is. Truth has a habit of being far more interesting than fiction, what with the boring repetitiveness of formula cinema.
To Scrabble beginners, here's some advice: Make the best of the least letters. High scores can be achieved with 2 and 3 letter words and leave fewer openings for opponents. Study the Scrabble dictionary between games. RE, LA, NU are words ;-)
When I heard that the end of wooden tiles was coming, I dashed down to the local game shop and scored one of those sets. I can't imagine playing this with plastic bits, not after my dad taught me the game ages ago. Call me tradition bound.
Dork certainly is a fitting description of someone who turns to a computer to help them with words. It's a game of pitting intellect vs intellect, not intellect vs 'Fred'*.
* Fred is a cycling term for wannabe, but with a strongly negative connotation
A feeling of having made the same mistake before: Deja Foobar
It's not trivial... The tricky part is in the fast generation of valid scrabble words. This is made relatively quick by use of a TRIE or DAWG (Directed Acyclic Word Graph). Basically a DAWG is an efficient data structure where each letter of the alphabet is linked down to each subsequent letter that forms, or is on the way to forming, a valid scrabble word. Nodes where words are formed are marked as such. (Diff between a TRIE and a DAWG is that a DAWG is optimised so that all common endings (ING, ED etc) are stored once and pointed too, rather than a TRIE where it is not optimised.
This means that the lookup for any combination of characters on the board / in the rack is blazingly fast. Want to check the string 'getgstsd' for validity? Well, g passes, ge passes, get passes, getg... Bzzzzt. Wrong, no valid words down this path! Next please.
This is MUCH faster than a traditional binary search, and when you are checking typically thousands of existences per valid board location per move, it's worth it.
All this ignores the nasty recursive algorithms to identify valid placement options, considering that placing a word may create invalid words along the opposite axis - so any extra words created need to be checked for validity too.
I ended up writing a program to play scrabble and it used a feedback mechanism on several criteria (number of tiles used, place in game, ahead or behind status, number of premium squares used, number of premuim squares opened up etc) to weight future decisions. I'm a very good player and this program very quickly destroyed me. It was fascinating though to watch it play itself.
Back in the day it was running on a 486dx2/66 and took about 2 seconds per move so it was possible to watch the games develop.
I still have the code somewhere (in PASCAL!)... I really should break it back out and get it to compile on something new.
Cheers - N