Working on this project improved our understanding of how artificial intelligence techniques can be applied to solve a wide variety of computational problems.
Supplied with sample English dictionaries, we demonstrated that the preprocessor is able to effectively screens out large portions of the dictionary that can never be played during a game. Our preprocessing algorithm is very simple and straightforward and can be readily adapted to work with different versions of Upwords.
Our decision to use a trie to represent the dictionary resulted in large, measurable space savings, and complemented our move selection strategy. In future implementations, we recommend that a graph-based representation be adopted in place of the tree-based dictionary data structure. A graph-based representation promises great space savings due to the fact that various graph minimization algorithms can be applied.
The brute force, greedy algorithm we selected is well suited for analysis of Upwords game states. Although we decided not to employ any adversarial search strategies, due to the large search spaces that result from most game situations, we do recognize the fact that, during the end-game stage, it may indeed be possible to introduce such search techniques.
Our implementation of the Upwords program effectively demonstrates how
artificial intelligence methodologies can be used to solve complex game
playing situations. Now it is time to kick some butt!