The Upwords program has been developed to demonstrate how artificial intelligence techniques can be used to solve complex puzzle situations.  Given a dictionary, game board, and rack configuration, the program is capable of generating all the valid moves possible, and selecting what it considers to be an optimal move.

We selected C as our programming language because it is well suited to handle the dictionary representation and search strategy that we decided upon.  These benefits combined with our experience C background, and the speed savings that compiled programs provide, made C an easy and logical choice for our implementation.

During various stages of our design, we implemented various optimization strategies that enable our program to carry out its tasks extremely quickly.  Supplied with a dictionary, our program preprocesses the dictionary to eliminate words and that can never be legally played during a game.  We chose to represent the dictionary as a trie because it provided significant space savings and complements our move search strategy remarkably well.  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.

In the following sections, we provide an in-depth analysis of our various design decisions.