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.
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.
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:
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:
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:
The Prefix Generation Algorithm:
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.
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:
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: