A faster scrabble move generation algorithm
Steven A. Gordon · Software Practice and Experience · 1994
Abstract Appel and Jacobson1 presented a fast algorithm for generating every possible move in a given position in the game of Scrabble using a DAWG, a finite automaton derived from the trie of a large lexicon. This paper presents a faster algorithm that uses a GADDAG, a finite automaton that avoids the non‐deterministic prefix generation of the DAWG algorithm by encoding a bidirectional path starting from each letter of each word in the lexicon. For a typical lexicon, the GADDAG is nearly five times larger than the DAWG, but generates moves more than twice as fast. This time/space trade‐off is justified not only by the decreasing cost of computer memory, but also by the extensive use of move‐generation in the analysis of board positions used by Gordon2 in the probabilistic search for the most appropriate play in a given position within realistic time constraints.