Boggle

Genesis of Assignment

(As is usual, the genesis and related links isn’t necessary to complete the assignment, but it’s full of useful and applied material.)

wikipedia jpg

Prof. Astrachan fondly recalls neighborhood Boggle® games from his now long-ago childhood and was re-introduced to it on Sun Unix workstations as a grad student in the mid 80′s. Boggle is in the Nifty Assignments Archive and the current instantiation of the assignment is a combination of efforts from Compsci educators at Duke, Stanford, and UCSD. This version emphasizes empirical analyses of tradeoffs in different implementations.The Wikipedia Boggle entry explains the game in detail including popular culture references to Boggle. Reviewing the rules on the Wikipedia site will help in understanding the play-of-the-game, but you’ll be looking at implementation trade-offs that are independent of game-playing. You can play games based on words that are similar to Boggle online, e.g., Yahoo! Word Racer is related and Facebook used to have a game called Scramble that is related to Boggle.

Theoretical and practical approaches to word games have formed the basis for The World’s Fastest Scrabble Program (Appel and Jacobson) for recognizing Genomic Signatures in DeBruijn Chains (Heath and Pati) and for An efficient interface between continuous speech recognition and language understanding (Oerder and Ney).

Analyzing alternative implementations and algorithms will help inform a better understanding of both work and play, what a great way to build a foundation in understanding how to turn data into information.

In particular you’ll be examining alternate implementations of a lexicon or word source. You’ll work on a Trie implementation and a compressed Trie that’s similar to a Radix Trie/Patricia Trie, but simpler to implement. Tries are the data structure behind predictive text used in cell-phone texting, e.g., in T9 Text Input and have formed the basis for IP-routing, e.g., see Keith Sklower’sTree-Based Packet Routing Table for Berkeley Unix although changes to IPv6 may change the utility of tries as described here: Scalable high speed IP routing lookups (Waldvogel, Varghese, Turner, Plattner).

You’ll use different word-sources or lexicons. Apparently there’s a controversy as to what the “best” lexicon is for playing word games like Scrabble® and Boggle®

 

 

What You Will Do

You’ll code one class to find a specific word on a Boggle® board and you’ll implement two hierarchies of classes (one for Lexicons, one for Computer/Auto players of the game). Each hierarchy will be a group of classes that implement a common interface and allow you to reason empirically about trade-offs in implementation techniques. You’ll run code/experiments to reason about the classes you write.

 

 

  1. Find Words On Board You’ll design and code one class GoodWordOnBoardFinder that implements theIWordOnBoardFinder interface to find a word on a Boggle board. You’ll use this class in implementing one of the auto-player classes and in determining where a word appears on a board when you or another (human) player plays the game.
  2. Implement and benchmark lexicons You’ll write classes that implement the ILexicon interface. Each lexicon implementation facilitates looking up a word or a possible prefix of a word. The classes differ in how efficiently they support these operations and in how much memory they use.
  3. Implement one AutoPlayer that finds all words quickly You’ll write one class BoardFirstAutoPlayer that implements the IAutoPlayer interface. You’re given a class that implements the interface, LexiconFirstAutoPlayer.< Each class facilitates playing a game of Boggle by finding every possible word on a given Boggle board. These classes use the lexicons from the previous hierarchy.
  4. Empirical Analyses You’ll make conclusions based on empirical, runtime analyses of the classes you write to determine which of several methods is “best”, and to reason in general about the trade-offs in different implementations. Please put this analysis in a file called Analysis.pdf.

 

More information is given in the howto pages.

 

 

Grading

Criteria Points
Functionality of GoodWordOnBoardFinder 6
Functionality of BinarySearchLexicon 4
Functionality of BoardFirstAutoplayer 6
Analysis 4

You can also get extra credit for CompressedTrieLexicon.

Your Analysis.pdf file should list your testing/analysis results.

Your readme should contain all the people with whom you collaborated, and the TAs/UTAs you consulted with. You should include an estimate of how long you spent on the program and what your thoughts are about the assignment.

Submit your README and all of your source code using Eclipse with assignment name boggle.