CMSC 341 Fall 2007
Project 5

Assigned Mon, Nov 26, 2007
Intermediate deadline 11:59pm, Mon Dec 3, 2007
Due 11:59pm, Wed Dec 12, 2007
Updates

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 in order 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 (but 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.

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. For the intermediate deadline, you should turn in a design specifying what you will store in the hash table items and how they will be used in the play. Turn in a hard copy of this design in the first class you have after the due date.
  2. 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.
  3. This project can be developed using the Eclipse Integrated Development Environment (IDE).
  4. 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.
  5. 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.
  6. As in previous projects, you should submit your project as a package (proj5). Your project should be named Proj5.
  7. To create the file containing your output, use unix redirection on the command line to redirect standard output to a file. You can redirect your output to file by using the command java proj5.Proj5 -h -2 > p5-output.txt.
  8. This project is an OPEN assignment. 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. 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. This item is MANDATORY for the H section.

Files To Be Submitted

Submit the following files:
  1. *.java (including Proj5.java ),
  2. p5-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.