**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:

- If there are no lettered positions to the north or south of X, then the crosscheck is valid.
- 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
- 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:

- Valid Prefix Generation
- 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__:

- Given a root of a trie T, a rack R, initialize the list of prefixes to NULL
- We select an element X from the rack R
- 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
- Recursively generate valid prefixes with T.Children[X] as the new root, and R - X as the new rack
- Concatenate X to the beginning of each prefix generated in 3, and add the new list to the existing list of prefixes
- 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__:

- Let T be the trie node where prefix generation left off.
- 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.
- Given a root of a trie T and a rack R, initialize the list of prefixes to NULL
- We select an element X from the rack R
- 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.
- Recursively generate valid suffixes with T.Children[X] as the new root, and R - X as the new rack
- Concatenate X to the beginning of each suffix generated in 3, and add the new list to the existing list of suffixes
- 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

more than two players.