COMP 110-003 Spring 2013

180 points

Description

In this final programming project, you will write a java applet tic-tac-toe game. This game will have an artificial intelligence (AI) so that a human player can play against the computer. I have given you the starting program file TicTacToe.java where you will have to fill in the missing pieces. The program I have given you has some functionality, make sure you read the comments and understand which pieces you can change and which pieces you should not change. You MUST read paint() method to understand the game logic.

This is a very hard program and I recommend starting simple and then adding more complicated features. Particularly, you are strongly recommended to start IMMEDIATELY!

Tic-tac-toe (or Noughts and crosses, Xs and Os) is a game for two players. Each player take turns marking the spaces in a 3x3 grid. The player who succeeds in placing three respective marks in a horizontal, vertical, or diagonal row wins the game. You can read the wikipedia page to learn more about the game.

Also, you must play the games by yourself to understand the details. I have made three versions for your to play with (and eventually you have to implement them by yourself). The three versions are: random CPU player, smart CPU player, and smart CPU player with first-move.

Required Funcionalities:

• When the user clicks on a legal square (not taken by players), mark the square as taken by user and save the board status to the 2-dimensional array gameboard; when the user clicks on an illegal square or somewhere else, do nothing.
• After the user makes a move, make a legal move automatically (or saying, by the computer player).
• Whenever the game ends and a player wins, highlight the winning row and display a message. Whenever the game ends as a draw, display a message. In either way, the game will be restarted after the next mouse click.

Special Topic 1: Mouse Clicking

You have been given method mouseDown() that detects mouse clicks and gets xx and y as the location of the mouse click. x and y will range from 0 to the size of the window. You will be using the Graphics class to display your game board. The window is 600 x 600 with (0,0) in the upper left corner. You should think of the board as a visual array with gameBoard[0][0] as the top left corner and each square is 200 x 200. To determine which square the user has selected you will need to convert the location of x and y to your array indices in setMouseSquare() method. There is a very easy way to do this without using if statements or switch statements. You will need to write a method that determines the current index location the user has selected.

Coordinates range:

• index 0: 0 - 199
• index 1: 200 - 399
• index 2: 400 - 599

Special Topic 2: Game Display

Once you know which index the user has selected you will need to display a circle (or whatever shape you want) in the correct square on the board. You have had the experience of drawing circles in Lab 3 and Lab 5 (displaying Smiley). You can determine the location of your shape by multiplying and adding your current index by numbers. You will need to write a method that determins the exact position to draw circles.

Special Topic 3: Generating Random Numbers

The basic version of your AI will generate a random move (as long as it is legal). You can check the example here: random CPU player.

A random integer can be generated by a random number generator. You can use it like this to get a random integer in the range from 0 to N-1:
int N; // You can set its value
Random generator = new Random();
int randomNum = generator.nextInt(N);

You need to use the random number to make a legal random move. There are many ways to do it.

Special Topic 4: Smart Moves

The advanced version of your AI will generate a smart move. You can check the example here: smart CPU player. Your grade in this part will be determined according to the "smartness" of your program. At least, your program should be able to:

• Make the winning move if the computer player can win in this move.
• Block the winning move if the human player can win in the next move.

There are more rules that you can think of. It is possible to write a perfect AI that never lose. If you want to find a good opponent to test your program, use this example to play against your AI: smart CPU player with first-move

Special Topic 5: Extra Points

You receive extra 10 points if your CPUMove() method can work in CPU-first-move manner. You can change the paint() method to other names and change the CPUFirstpaint() method to paint() to let the computer player move first. Ideally, you don't have to write new strategies -- try to make the decision based on the current board instead of the current move.

Moreover, I am planning a tournament for you to play against each other. The current planned extra points are: 3/2/1 points on the final grade to the champion/runner-up/third-place. I will decide the organization of the tournament (league/knock-off, online/offline, etc.) depending on the number of competitors. Write me an email to register before Tuesday, April 23.

Milestones and Submission Requirements

• Turn in something to show your progress no later than Thursday, April 11.
• Turn in the basic version (with all required functions and the random CPU move) no later than Saturday, April 20. After that day, you lose 1 point each day until April 30 if you do not turn it in.
• Turn in everything no later than Tuesday, April 30. The required code and documents include:
  • The basic version (if not submitted yet) .java file
  • The advanced version (with the smart CPU move) .java file
  • The extra-points version (with the smart CPU move and letting CPU move first) .java file
  • A report that includes the following contents (I am expecting about 3 pages):
    • Difficulties you met during the project and ideas/thoughts/suggestions that you want to share
    • Your strategy for the advanced version AI, possibly including code/pseudocode or figures to explain your idea, and proper references if any ideas are not your own
    • The strategies that you successfuly implemented but found not a good strategy. You can include your code, which may earn you partial credits
    • The strategies that you imagined but failed to implement. You can describe why you think that they may work, and why you don't implement them

Grading

• 25 points Progress check. Turn in something to show your progress by Thursday, April 11 (no extension will be allowed). You receive 20 points if you make the submission. The other 5 points will depend on your progress.
  
• 10 points Submission time score: 10 points if the submission of the basic version is no later than April 20; (10-x) points if no later than April 2x. You lose a half or the whole project (not only this 10 points) if you submit later than April 30!
  
• 40 points Correct in-game play. You get all 40 points if the program can track user clicks and display moves.
  
• 30 points Correct end-game play. You get all 30 points if the program can correctly detect when the game ends.
  
• 20 points Correct highlight display. You get all 20 points if the program can highlight the winning row(s).
  
• 15 points Basic version AI (the random AI). You get all 15 points if the program can make legal random moves (it's not required whether the move follows certain random distributions).
  
• 40 points Advanced version AI (the smart AI). The grade will be given based on the code, the smartness of the program and the report.
  
• 10 extra points Extra-point version.

How to hand in the assignment

• Submit correct versions of TicTacToe.java files on Sakai. It is strongly recommended that you backup your source files when you are moving to the next version.
• Make sure you document your code. Especially, you must include your name in all your header comment! Otherwise you will not get credit for this program.
• Your java files should have the appropriate header.
• The due date of the program is Tuesday, April 30 by 11:59pm. Everything received after that time will be considered late submission.
• You can lose points for incorrectly handing in the assignment, not using appropriate white space, not using conventional Java names for your variables, and not commenting your code properly.
• Please let me know if you are having any problems with the assignment submission process.