Project 4

Assigned Monday April 23, 2012
Due 11:59pm, Wednesday May 9, 2012

Objectives

Overview

Several artificial intelligence (AI) approaches for computer game playing involving creating dictionaries of possible game piece configurations and the moves which worked best for each configuration. Because the number of possible configurations is large (and some configurations are unlikely), it is not practical to create one large table of all the possible configurations. Instead, a common technique is to use a hash table to store game configurations which have been previously seen along with 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 -- a "smart" player that learns and a "dumb" player that chooses moves randomly.

Project Specification

Your project will create the basic infrastructure for a tic-tac-toe game, including two computer players. One computer player is the "dumb" player that always chooses its moves randomly. The dumb player always goes first and is the 'X' player. The other computer player is the "smart" player that learns from experience, always goes second and plays 'O'.

You will use a dictionary of game configurations to store results of previous games so that the smart player can make informed decisions about its next move. If there is incomplete information about possibilities starting from the current configuration, the smart player makes a random choice for its next move and records the results, so that it can make a smarter choice next time.

Each hash table entry should include a game configuration and history of success when continuing from this configuration. To choose a move starting 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, update the hash table with the new win/loss histories.

You will need to design a hash function which takes a game board configuration as input and converts it to an index into the hash table. A game configuration has three possible states (x, o, empty) for each board position. The representation of a game configuration is up to you. Your hash function should scatter game configurations across the hash table as evenly as possible.

Your program accepts four possible command line arguments: a history flag (-h), a save flag (-s), a display flag (-d), and a number of games to play flag (-1, -2, etc).

  1. You must implement the history flag. When the history flag is present in the command line, the program should print out intermediate reports.

    Intermediate reports show the board configuartion after each move. and the accumulated win/loss records of the players. Other information you may find useful may be included in intermediate reports.

  2. You must implement the number of games flag. If the number of games flag is present in the command line your program should play the specified number of games and then exit. Otherwise your program plays just one game.
  3. The configuration save flag is an extra credit option.
  4. The display flag is an extra credit option.

A final summary of the series of games and operations of the the tic-tac-toe program must be printed when your program terminates. The summary must contain the following information:

Example final summary output. This sample is provided to illustrate all required data. The data does not necessarily reflect expected results. Your format may vary provided it is readable and contains all required data. 
run:
     [java] FINAL REPORT: 
     [java] 
     [java] The number of slots is: 267
     [java] The number of entries is: 218
     [java] The % full is: 81.64
     [java] The number of collisions is: 1087
     [java] Smart player has won 342 times which is 34 percent
     [java] Random has won 567 times which is 56 percent
     [java] My favorite first move is: 
     [java] ...
     [java] .OX
     [java] ...
     [java] Won 48.0 out of 71.0 which is 67.60%

Project Notes, Hints, and Requirements

  1. (R) -- 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. (R) -- You must implement your own HashTable class. Your HashTable class must be generic. You are welcome to use the author's code as a starting point. Use of any Java class other than Lists is not permitted. The author's hash table code used quadratic probing. You may copy the file from this link or from Mr. Frey's public directory 
    /afs/umbc.edu/users/f/r/frey/pub/341-Proj4
  3. (R) -- We all know that the center square is the most important and we all know a winning move when we see one near the end of the game, however, DO NOT build this kind of intelligence into the smart player. The smart player should use only the board configuration dictionary to decide which move to make next.
  4. (N) -- an example intermediate report which must be printed if the history flag is present on the command line is available here
  5. (N) -- A tie is not a loss and is not a win. You should reflect this in your intermediate game results.
  6. (R) --Your smart player must exhibit an acceptable rate of learning. The rate at which your smart player wins is incorporated into the grade calculation. To achieve maximum points for the "Learning Curve" portion of your grade, your smart player must achieve an 80% win rate.
  7. (H) -- use the CVS Utilities that have been provided to insure that there are no CVS or ant problems with your submittal.

Project Grading

The expected point breakdown for this project will be something like this:
  1. Project Questions (10 points) -- be sure to edit and submit P4Questions.txt. Your answers must be supported by analysis of your hash table statisitics where applicable.
  2. Functionality
    • Basic Cases (5 points) - This will be a test that attempts to play a few games of Tic-Tac-Toe.
    • More Complex cases (10 points)- This will test implementation of the history flag.
    • Stress Case (10 points) - This test will be based on playing a large number (e.g 18000) of games.
  3. Design/Implementation (15 points) - based on design specifications.
  4. Leaning Curve (50 points)
    We will measure how well your program learns by the percentage of games won by the smart player. As more games are played the smart player should win a higher percentage of the games. Your score for this section will be based on the ratio of your smart player's wininng percent versus the desired 80% winning percent at no more than 18000 games.

Extra Credit

There are several interesting ways to extend your base project. To indicate that you implemented any of these extra credit items, submit a file named README. This will alert 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 not be "smart" until enough games have been played to sufficiently fill the game dictionary with good recommendations. Implement the capability to save and restore game configurations between executions of the program, in order to accumulate more playing experience. Your configuration save file must 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 configuration save file 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 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.

Files to Be Submitted

You must use CVS to check out your module in the Proj4 repository and to check in your code, your build.xml and the answers to the questions in P4Questions.txt. Grading scriptswill execute the commands ant compile and ant run to compile and execute your project.

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. As in previous projects, use the CVS utilities to verify that your code was submitted properly and will build and execute properly using the commands ant compile and ant run. See the projects page for more information.

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 result in the use of grace days.