CMSC 341 Fall 2008
Project 4

Assigned Wed, Nov 5, 2008
Due 11:59pm, Fri Nov 21, 2008
Updates
Nov 17, 2008The project is due Sunday, November 23rd by 11:59pm. This is an extension from the original due date of November 21st.
Nov 13, 2008When both players are automated (i.e., you are not playing against a human as required for one of the extra credit options), one player should choose moves completely at random and the other should use the hash table to choose moves. Only the moves of the player that uses the hash table should be used to update the hash table. In all cases, the X player should go first. If one player is a human, it makes no difference whether that player is X or O.

Objectives

Overview

Several AI approaches for computer game playing involving creating dictionaries of possible game piece configurations and the moves which worked best given each configuration. Because the space of possible configurations is large (and some configurations are unlikely), it is not practical to create one big table of all the possible configurations. Instead, it is common to use a hash table to store game configurations and their likely outcomes. In this project, you will implement a simple tic-tac-toe game, using a hash table to store game configurations to play smarter. Your base program will be automatic play between two computer-controlled players. Graphical display and interactive control of the player are available as extra credit options.

Project Specification

Your project will create the basic infrastructure for a tic-tac-toe game, including an automated opponent. You will use a dictionary of game configurations to store results of previous games and make informed decisions about the next move to make. You should not build other intelligence into the program (for instance, trying to implement your personal strategies for tic-tac-toe). Your program should use only the configuration dictionary to decide which move to make next. If there is incomplete information about possibilities starting from the current configuration, make a random choice and be sure to record the results, so that you can make a smarter choice next time. Your hash table entries should include the game configuration and history of success when starting from from this configuration. From the current configuration, construct each possible next configuration (by considering all legal next moves), retrieve the corresponding configurations, and and check their win/loss histories. When the game ends and you know which player won, be sure to update the hash table with the new win/loss histories.

You will need to design a hash function which takes a game board configuration and converts it to an index into the hash table. A game configuration has three possible states (x, o, empty) for each board position. Your hash function should scatter game configurations across the hash table as evenly as possible. Discuss your hash function design, including how it will scatter entries, in about a paragraph in the function header comment. Also, do the same for your collision resolution strategy in the header comment for the hash class.

The program takes four possible command line arguments: a history flag (-h), a dictionary save flag (-s), a display flag (-d), and a number of games to play flag (-1, -2, etc). The history flag is optional and the default history value should be false. When the history flag is true, the program should print out intermediate reports. Final summaries should be printed regardless of the value of the flag. The dictionary save flag indicates that an initial dictionary should be read in from a file called 'configs.txt' (if it exists) and updated to a file by the same name. Dictionary saving is not required in the base program, but is an extra credit option. This flag is optional and defaults to false. The display flag specifies that a GUI is created to show the board and piece positions. When this option is enabled, a live player plays against a computer controlled opponent. It is optional and defaults to false. When this flag is false the program should be entirely text-in, text-out with no UI created. The display option is not required in the base program, only for extra credit. The number of games flag is optional and should default to 1. For other values, the program should play the specified number of games and then exit.

A final summary of the series of games and operations of the the tic-tac-toe program should contain the following information:

For each game, intermediate reports should give individual moves by each player, including the contents of the configuration record fetched from the hash table. Intermediate reports should also update the accumulated win/loss records of the players. Other useful information may be included in intermediate reports.

Project Notes, Hints, and Requirements

  1. Your project must adhere to basic good design principles, including (but not limited to) appropriate abstraction and encapsulation, logical control flow, reasonably efficient use of memory, and basic computational efficiency. If you feel it advisable to violate one of these principles (or any others), be sure to explain your reasons. We may not necessarily accept your reasons, but will consider them. You may, of course, get feedback on your design decisions before the project is due (ideally, WELL before the project is due). The safest source of such feedback is your instructor, since s/he is the one who ultimately decides how your project will be graded.
  2. You must implement your HashTable class from scratch, with nothing but Object, primitive types, explicitly approved classes, or classes you develop from scratch yourself as a superclass of HashTable or any data elements of HashTable. For the purposes of this assignment, you may use ArrayLists, but other containers and sets are not allowed.
  3. In the interests of reusability, make your HashTable class as general as practical. Specifically, your hash table should be uncoupled from the items stored in it.

Extra Credit

There are MANY interesting ways to extend your base project. 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. Add a GUI display to your program. Your GUI should display the game board and piece positions. In GUI mode, moves of one player should be controllable interactively. Include instructions so that the TA knows how to control the interactive player. Worth five points.
  2. In the base version, the automated player will be pretty dumb until enough games have been played to sufficiently fill the game dictionary with good recommendations. Implement the capability to save and restore game configuration dictionaries between executions of the program, in order to accumulate more playing experience. Your dictionary file should be named 'configs.txt'. The file may not initially exist, in which case it should be created. You should design a file format for your dictionary and explain why this design is appropriate. Worth five points.
  3. Analyze the rate at which the program learns (through building a good configuration dictionary). Play an automatic player that uses a dictionary against one that makes purely random decisions. Plot the performance of these over many games. How many games are required until the dictionary is full enough to make a noticeable difference on the outcome? Write a 1-2 page paper discussing your analysis. Worth five points.
  4. In tic-tac-toe, many game positions are the same for all practical purposes, due to the symmetry properties of the board. Specifically, some moves are reflected or rotated versions of other moves. For instance, an initial move in any of the corners leads to the same options, while a move into the center space is qualitatively different. Most real game dictionaries take advantage of symmetry to reduce the number of entries which must be stored in the table. Write a second hash function that uses symmetry to store and retrieve game configurations. Write a 1-2 page report describing your method and the resulting effect on number of table entries for sequences of games. Be sure to include a theoretical analysis of the number of unique cases in both the base and symmetric versions. Your report should be in pdf format and named 'your_logname.pdf' (insert your logname for your_logname). Worth ten points.

Submission

You must use CVS to check out your module in the Proj4 repository and to check in your code. That must include an ant build.xml file and javadoc. The grading scripts will issue commands like the following, so be sure that your build.xml supports them: 
  ant
  ant doc
  ant -Dargs="arguments go here" run

See the projects page for more information on all of these topics.

If you don't submit a project correctly, you will not get credit for it. Why throw away all that hard work you did to write the project? Check your submittals. Make sure they work. Do this before the due date.

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.