CMSC 341 Fall 2007
Project 3

Assigned Monday, Oct 15, 2007
Due 11:59pm, Friday Nov 2, 2007
Intermediate deadline Mon Oct 22, 2007
Updates Tues. Oct 30, 2007

Objectives

Overview

In this project, you will build an interactive advisor for the Ghost word game. This advisor will read in a dictionary of words, store them in an appropriate ADT, use this ADT to make recommendations on which play should be made next, and build a displayable tree structure. We will give you basic UI code and a display helper class, as well as specify an interface that you must implement for the WordTree clas. Other class design choices are yours.


Rules of Play

Ghost is a word game played with n players. The objective is to add letters to a word fragment in such a way that the fragment does not complete a word but is still the beginning of a legitimate word. The first player starts with any letter. Each player, in turn, must add a letter. The first player to complete a word (of three or more characters) or fail to add a letter loses the round. A player who cannot think of a letter which keeps the word alive without completing it may bluff. Another player can call the bluff and ask for the word in mind. If there is no such word (ie. it was a bluff), the bluffing player loses the round. If there was a word, the calling player loses the round. A losing player gets a penalty letter -- first 'g', then 'h', and so on until 'ghost' is spelled out. The player who lost the round starts the next round. Rounds continue until one player has spelled out the word 'ghost' in penalty letters. For example, a three player game might start like this:

Player 1:	a	(might be thinking of 'apple')
Player 2:	s	(thinking of 'astrology'; two-letter word is OK)
Player 3:	p	(thinking of 'asparagus', forgetting 'asp' is a word)
Player 3 gets 'g'

Player 3:	d	(thinking of 'destiny')
Player 1:	a	(thinking of 'dastardly')
Player 2:	w	(thinking of 'dawn', hoping to force next player out)
Player 3:	d	(thinking of 'dawdle')
Player 1:	l	(thinking of 'dawdle')
Player 2:	i	(thinking of 'dawdling')
Player 3:	n	(thinking of 'dawdling')
Player 1:	g	(forced to finish 'dawdling')
Player 1 gets 'g'. Player 1 and 3 tied at 'g'.



Project Specification

In this project you will be implementing a tree class, named WordTree, from scratch. Its constructor should take the string specifying a file name containing a list of the legitimate words (or dictionary). It should build a WordTree from this list. It should also provide methods to build a displayable list, return the displayable list, and recommend a next letter to give after the partial word passed as parameter. Think carefully about what properties you want your tree to have -- before you start writing code. There are many types of trees and some are not well-suited for this application.

The recommend function takes a partial word and number of players as arguments. If the partial word can not be found as an interior node of the tree (ie, there is no valid word starting with that fragment), the function should return '@'. Otherwise, the method should analyze the subtree beneath the node containing the frament. A good choice is one which does not complete a word (ideally, even on your next turn, which is why the number of players is required). Recommend which letter would be the best choice to play next.

We will be providing you with the code for the UI, which looks like this:

































This is the tree built from the file 'fewwords.txt', after a path has been manually opened up to the word 'help'. Word fragments can be typed in the bottom textbox and recommendations requested by pushing the 'Recommend' button.

The program takes four possible command line arguments (processed in the provided code): a history flag (as in Proj 2), a number of players (betwen 1 and 9), a filename for the list of valid, and (optionally) a list of word fragments to make recommendations on. The provided code parses command line arguments, calls the WordTree constructor, creates a user interface including a displayable tree created by methods of the WordTree class, reads in the list of word fragments to get recommendations about, and then gets recommendations of typed in fragments. When the history flag is set, you should print out the tree created (marking which nodes correspond to valid words), the recommendations for next letters, and some justification for why that recommendation was made (ie the values of some metrics that you computed to compare it to other possibilities).

Dr. Rheingans' public directory for this project is

/afs/umbc.edu/users/r/h/rheingan/pub/341/Proj3 and it contains Proj3.java, the interface specification mentioned above, two dictionaries of valid words ('words.txt' and 'fewwords.txt'), and a list of partial words to make recommendations on ("fragments.txt"). You should write your code to access the dictionary where it is, rather than copying it to your directory and accessing it locally. Call the program with the full pathname of the files on the command line.

Project Notes, Hints, and Requirements

  1. This project can be developed using the Eclipse Integrated Development Environment (IDE).
  2. By the intermediate deadline, hand in a description of the type of tree you intend to implement (about a paragraph) and a picture of the tree created from the file 'fewwords.txt'. A hand-drawn picture is fine. Give both the description and the picture to your instructor at the next class after the deadline (ie, either Tues 23 or Wed 24, depending on when your section meets). You may change design choices later, but you must submit the initial design by the intermediate deadline.
  3. You must implement your WordTree class from scratch, with nothing but Object, primitive types, or classes you develop from scratch yourself as a superclass of WordTree or any data elements of WordTree.
  4. You may not change the WordTreeInterface.
  5. As in previous projects, you should submit your project as a package (proj3).
  6. To create the file containing your output, use unix redirection on the command line to redirect standard output to a file. Thus, once you have the output on the screen as shown in the sample results above, then you can redirect your output to file by using the command java proj3.Proj3 -h > p3-output.txt.
  7. This project is an OPEN assignment (as was Project 2). You are still expected to write your own code, but you may continue to help each other debug. Specifically, you: You MAY NOT: Any help you receive must be documented, including discussion, books, papers, and web resources. With each assignment, you will turn in a README text file indicating the sources you used while working on it and the type of help you received from each. If you received no help, say so. If you helped someone else, say so. Failure to include this README file will result in your program being returned ungraded.

Extra Credit

There are MANY interesting ways to extend your base project. Be sure you finish all requirements of the base project before you begin working on extra credit. Indicate any items of extra credit that you did in your README file. This will allow the TA to look for that additional functionality when grading your project.
  1. Deciding what next letter to recommend, requires traversing the whole subtree rooted at the current word fragment and calculating all possible outcomes. This might be very time consuming. As play moves on to the next player, the subtree to be traversed is a child the last subtree traversed, requiring a repeat of work already done. Modify your WordTree to cache statistics in interior nodes. Compare the performance of the cache-enabled WordTree to the original version. Write a one page analysis of the effects of caching in terms of space and time. Discuss how performance changes as the game proceeds (ie. as you work your way down the tree). Create your own partial word files containing test cases which help you conduct a thorough analysis. Submit your paper in .pdf format. Worth ten points. MANDATORY for H section.
  2. Extend the GUI to expand the path to a fragment for which a recommendation is requested. Worth five points.
  3. Improve your recommend function to try to force your opponent(s) into completing words. Explain your method in your README file. Worth five points.
  4. Explore how your program scales up as the dictionary grows. Run your program on dictionaries of differing sizes. Analyze how your program performs and how big the dictionary can grow before your program begins to have problems. There is a big file of words available in /usr/share/dict/words. You can use this for testing, as well as for creating testfiles of a range of lengths. Discuss the results of your analysis and ideas for adapting your program to handle longer dictionaries in a paper of about two pages. Submit your paper in .pdf format. Worth ten points.

Files To Be Submitted

Submit the following files:
  1. *.java (including Proj3.java ),
  2. p3-output.txt,
  3. README,
  4. any items required for extra credit options

Project grading is described in the Project Policy handout.
Cheating in any form will not be tolerated. Please re-read the Project Policy handout for further details on honesty in doing projects for this course.

Remember, the due date is firm. Submittals made after midnight of the due date will not be accepted. Do not submit any files after that time.