Chris Pollett > Students > Abraham

    Print View

    [Bio]

    [Blog]

    [CS 297 Proposal]

    [Del 1 - Scrabble Notation]

    [Del 2 - Human Player]

    [Del 3 - Possible Word Retrieval]

    [Del 4 - Simple AI player]

    [CS 297 Report_PDF]

    [CS 298 Proposal]



























Deliverable 3: Find the possible words to play using Trie data structure

In Deliverable 3, we developed a trie data structure useful for the discovery of the most promising words that could be played on each turn. To do that we accumulate the letters from the board and rack to form a combination of possible letters that could be placed on the board. Each letter from the board is fetched to combine with player's rack of tiles. These letters are then passed to a trie data structure as a parameter to explore the permutations of potential words that can be formed from the combination of board and rack letters. The score is also computed for each word in the collection. Once the set of all promising words is created, we play with the highest scoring word from the given set.

The strategy used here is similar to the straightforward strategy used in current best Scrabble computer player called Maven. In the straightforward strategy, human players place the longest word that earns the highest score. A drawback with this method is that it can generate a lot of hot spots for the opponent to place their own tiles. These hot spots on the game board let the opponents to place a high score move in the next turn. This move could be a bingo move that lets the opponents earn 50 bonus points in one turn. Thus, we must remember that the highest scoring move is not always the best one. An intelligent AI player must efficiently apply different strategies at each turn depending upon the board state.

To execute the program, import below folder structure into Eclipse workspace and run JUnitTest.java in the Trie/test folder

Download
TrieWordRetrieval.zip