The world's fastest Scrabble program

Reviewer: Philip L. Phipps

This very interesting paper describes the data structures used (directed acyclic word-graphs, or DAWGs), search strategies (backtracking constrained by precomputed “anchor points and cross-checks”), and special heuristics that produce a very fast Scrabble-playing program. The claim is discussed with respect to both other computer programs and human players. A number of speed-ups are used. The program scans the board for playable connections before scanning the lexicon and letter rack. It stores the lexicon as a DAWG (one-way), allowing a memory reduction of about 5 to 1 over a tree organization and thus allowing the entire lexicon to reside in RAM memory. It splits the search into two parts, left of the anchor point and right of the anchor point. Rows and columns are handled identically—just transpose the board. Special heuristics are needed to handle blanks and contiguous letters. Some statistics about the program (which contains 1500 lines of C code) are discussed, including lexicon sizes versus speed and the machines for which it has been programmed (the VAX 11/780 and Apple Macintosh). Future refinements are suggested, such as a two-way DAWG lexicon, adversary search, and look-ahead strategy. Four other Scrabble programs are discussed and papers about them are listed among the 11 references. All appear to be much less capable than this one. The work with the DAWG data structure is applicable to other large lexicon searches, as the authors note. The title is sort of a challenge to the rest of the computer science world and, of course, gets attention. The paper is easy to read, although liberal use of data structure concepts is made. The paper is an excellent example of the trade-off between “trie” and DAWG data structures; some of the key C code routines are given. An actual game summary is given at the end—of course, the computer won.