OVERVIEW

The trie representation of the dictionary allowed us to develop an augmented version of a simple, but elegant search strategy proposed by Guy and Jacobson to play Scrabble.  Given a board and rack configuration, our search engine implements a brute force, greedy algorithm that takes every valid move possible, applies Upwords scoring conventions to the proposed moves, and selects the moves that results in the highest immediate point total.
 

COMPARISONS WITH ALTERNATIVE SEARCH ALGORITHMS

Although we could have employed max-min, alpha-beta, or other adversarial based search procedures to solve the Upwords puzzle, we chose not to for various reasons.  At any given time, one has access to the board configuration, one’s current rack state, a short history of moves, and not much else.  Information about opponent rack configuration, etceteras, is by in large unknown.  Consequently, Upwords is, under most circumstances, a game of imperfect information.  Due to the large tile pool, the number of players that can be involved, and the massive nature of the game dictionary, determining what one’s opponents might do in response to a given move is an enormous computational undertaking.  On towards the endgame, and in situations where you are playing with a very small number of opponents, is this feasible with the computing powers of modern computers.  Therefor, we decided that adversarial search strategies were both unsuitable and impractical due to the gigantic branching factor of the search space.  Instead, we have chosen to power our game engine with a brute force, greedy algorithm that only takes into consideration the game board and one’s player rack.
 

ANCHOR SQUARES

Definition of Adjacency: Given a board position X, the board positions, if they exists, directly to the north, south, east, and west of X are considered adjacent squares.

Definition of an Anchor: A square that is either contains a lettered tile, or is directly adjacent to a square containing a lettered tile.  If there are no tiles on the board, that is we are faced with a first move configuration.  In this case, the four special board positions in the middle of the board are considered Anchor Squares.

Upwords’ rules specify that a valid move must involve at least one Anchor square.  Therefor, the first step in searching for a valid move is to identify all Anchor positions on the board.

Once we have identified the Anchor positions, our program starts generates all the horizontal and vertical insertions possible, at each position.  We provide an in-depth description of the process in the sections that follow.
 

HORIZONTAL AND VERTICAL INSERTIONS

Our search strategy is designed to analyze the board in search of an optimal horizontal insertion.  Our program, however, does not ignore vertical insertions; it simply permutes the board so vertical insertions can be analyzed as if they were horizontal moves.  To perform vertical analysis, our program rotates the board counter-clockwise by 90 degrees before applying the horizontal search algorithm to the rotated board.
 

CROSSCHECKS

Our search algorithm builds up words through a series of letter by letter insertions on the board.  When a new letter is inserted onto the board at position X, we must check positions north and south of X, if these positions exist, to see if the new letter will add to or modify an existing vertical word.  We label this portion of validation the crosscheck phase.  During crosscheck, we have three cases to consider:

1. If there are no lettered positions to the north or south of X, then the crosscheck is valid.
2. If there is a lettered board position to the north or south of X and the new vertical word attached to position X is in the dictionary, then crosscheck is valid
3. If there is a lettered board position to the north or south of X and the new vertical word attacked to position X is not in the dictionary, then the crosscheck is invalid.

MOVE GENERATION

We now describe how our algorithm systematically generates all the horizontal moves bound to a given Anchor position.  Because all words are composed to some prefix appended to a suffix, we have divided move generation into two stages:

1. Valid Prefix Generation
2. Valid Suffix Generation

PREFIX GENERATION

Definition of a Valid Prefix: A combination of rack tiles that is a prefix to at least one word in the dictionary.  Each letter in the proposed prefix to be inserted onto the board must span over a contiguous sequence a non-Anchor square.  Given any board or rack configuration, there is at least one prefix that can be generated: The empty prefix.

Requiring that prefixes span over non-Anchor squares ensures that our search algorithm does not duplicate any work.  If we allowed prefixes to include Anchor squares, we see that two Anchor squares in close proximity to each other would duplicate the same work.  For example, given Anchors at position Y and Y+1, we can conceive of the following situation:

• Y:  Proposed word “cat” beginning at position Y-1, with prefix “c”, and suffix “at”
• Y+1: Proposed word “cat” beginning at position Y-1, with prefix “ca”, and suffix “t”

The Prefix Generation Algorithm:

1. Given a root of a trie T, a rack R, initialize the list of prefixes to NULL
2. We select an element X from the rack R
3. If X is a child of T and passes the crosscheck, then add X to the list of prefixes and go to step 4, else go to step 6
4. Recursively generate valid prefixes with T.Children[X] as the new root, and R - X as the new rack
5. Concatenate X to the beginning of each prefix generated in 3, and add the new list to the existing list of prefixes
6. Go to Step 2 as long as we have elements in R that have not been selected

For each given prefix, we must generate all valid suffixes that can be appended to the prefix.  Suffix generation progresses in a manner analogous to prefix generation.  However, there are some subtle differences in the algorithm, which is outlined below.
 

SUFFIX GENERATION

Definition of a Valid Suffix: A combination of rack and board tiles that is a suffix to at least one word in the dictionary.  The suffix must span over a contiguous sequence of board position, and must begin at the Anchor Square under consideration.  The suffix must be of length greater or equal to one.

Definition of a Valid Node: A node is valid if the path from the root to that node spells out a word that is in the dictionary.

The suffix generation process is highly dependent upon the prefix generation process.  We outline these dependencies and provide a general outline of the suffix generation procedure below.

The Suffix Generation Algorithm:

1.  Let T be the trie node where prefix generation left off.
2. Let F be the full player rack.  Let R be F minus the tiles used in the prefix plus the tile at the current position, it the current position is not blank.
3. Given a root of a trie T and a rack R, initialize the list of prefixes to NULL
4. We select an element X from the rack R
5. If X is not child of T or fails crosscheck got to step 8.  Else, if X is a valid node and add X to the list of suffixes.
6. Recursively generate valid suffixes with T.Children[X] as the new root, and R - X as the new rack
7. Concatenate X to the beginning of each suffix generated in 3, and add the new list to the existing list of suffixes
8. Go to Step 2 as long as we have elements in R that have not been selected

BUILDING VALID WORDS

Definition of a Valid Word: Consists of a Valid Suffix appended to a Valid Prefix.  The word must utilize at least one tile from the player rack.

Given the definitions of the prefix and suffix generation algorithms, it is apparent that, in order to generate all valid words at a given anchor, we can simply use the prefix and suffix generation procedures in tandem to generate valid moves.
 

SELECTING THE BEST MOVE

Before move generation commences, we initialize the best move to be worth a scoring value of zero, indicating that, so far, we have not found a valid move.  When a new valid word is generated, its scored value is compared to the value of the current best move.  If the new move is higher in value, the old best move is replaced with the new move, appropriately.  This process keeps bookkeeping at a minimum, and therefor, frees up memory that can be more effectively utilized elsewhere by the program.
 

EXCHANGING LETTERS AND PASSING

If no valid word insertions are found, the program searches for the first occurence of any of the following letters and designates that to be exchanged:

• F J K Q V W X Z