CS 211 Tic Tac Toe

Overview

• Define a concrete class named TicTacToe for modeling a simple tic-tac-toe board. It will have utility methods for checking if a game board is a win or a loss for either player (or a draw), determining what possible next moves are available for either player, and for displaying the board for visual debugging.
• Define an abstract class named Player for modeling tic-tac-toe players. It should define one abstract method for choosing a single move for a given game board (which will be overridden by its sub-classes), and one concrete method for computing the value of a given board for this player (based on whether it is a winning or losing board).
• Define two concrete sub-classes named UserPlayer and AIPlayer which extend Player and and provide different implementations of the appropriate methods. AIPlayer will use recursion to choose the optimal next move.
• This project has no tester, but provides two complete driver classes which can be used to run your code and check that important components of your solution are implemented correctly. You are responsible for writing your own tests to verify that your code is correct.
• You are allowed to create additional methods or fields as long as they are private. You may import any classes you wish, but you should not need to import anything other than java.util.Scanner.

TicTacToe

The game known as tic-tac-toe is a simple board game played with two players which alternate filling in spaces on an initially blank 3-by-3 board. One player uses the symbol "X" as their mark, and the other player uses the symbol "O". The first player that can make three of their marks in a row horizontally, vertically, or diagonally wins the game. If the entire board is filled without either player winning, the game is a draw. The TicTacToe class we are about to write will model the game board itself, and several useful methods for interacting with the board.

Our TicTacToe class will include the following:

• A private field, board, which is a 2D char array with three rows and three columns.
• Two private fields, x and o, which are references to Player subclasses.
• Getters and setters for all fields.
• A constructor which takes two Player arguments. The first argument should be the player for the "X" symbol, and the second the player for the "O" symbol. This constructor should also initialize the board to '_' (the underscore character) for each space.
• A public method named countBlanks which takes no arguments and returns the number of spaces on the board which are blank (the underscore character) as an int.
• A public method named markerForPlayer which takes a single Player argument and returns the character representing that player's symbol (either 'X' or 'O', the case where the argument is not one of these players will not be tested).
• A public method named checkWin which takes a single Player argument and returns true if the given player is the winner of this board (has three of their marks in a row horizontally, vertically, or diagonally), and false otherwise.
• A public method named checkLose which takes a single Player argument and returns true if the other player is the winner of this board and false otherwise. Note that neither player may be the winner of a given board, either because the game is not over, or because the game is a draw.
• A public method named checkDraw which takes no arguments and returns true if the current board is a draw (no blank spaces and no winner), and false otherwise.
• An overridden toString method which represents the current board as a single String suitable for printing. The String should contain each character of the board in row-column order with newlines between rows. For example the board {{'O','_','X'},{'_','X','_'},{'_','_','_'}} should be represented as the String "O_X\n_X_\n___\n" which, when printed, should display as

O _ X
_ X _
_ _ _

• A public method named possibleMoves which takes a single Player argument and returns a new array of TicTacToe boards representing the possible next moves for the given player. Note that the given player may place their mark on any of the spaces on the board that are currently blank. Important note 1: the order that the possible moves should be returned in is important, and should be in row-column order. Important note 2: this method should not modify the current board, the returned TicTacToe instances should make a deep copy of the current board's configuration, with one of the blank spaces filled in.

PLAYER CLASS

Since we will have two different kinds of players (human and AI), the Player class will be an abstract class which both sub-classes will extend. This class only has two components:

• A public method named chooseMove which takes a single TicTacToe argument and returns one of the possibleMoves. How this move is chosen will depend on the kind of player, so this must be an abstract method which subclasses must override.
• A public method named boardValue which takes a single TicTacToe argument and returns a double value representing how good the given board is for this player. The default implementation for this method should be to return 1.0 if this player has won this board, -1.0 if this player has lost this board, and 0.0 otherwise (see checkWin and checkLose in the TicTacToe class). Since this default implementation is common to all subclasses, this should not be an abstract method.

USERPLAYER CLASS

The first kind of Player subclass we'll create will allow a user to interact with the game board at the terminal. This should help us debug the various features of the other classes, and if the above classes are complete, allow us to play a game of tic-tac-toe using the provided PVPGame class. The UserPlayer class has the following features:

• It should extend the Player class.
• It should have one private String object with the name name.
• It should have one private Scanner object with the name input.
• It should have one public constructor that takes one Scanner and one String as arguments as initial values for these two fields.
• It should override the toString method to return the name field.
• It should override the chooseMove method to do the following:
  • Print out the current board that was passed in as an argument.
  • Use the possibleMoves method of the argument to get the options the user can choose from and print them out.
  • Ask the user to select one of these options and get the user's response using the Scanner object.
  • Return the TicTacToe board selected by the user.

The particular format of the strings printed to the user is not important, and will not be tested, but to aid your own debugging you should use the toString methods of the TicTacToe class, provide clear separation between the current board and the possible options, and indicate which array index corresponds with each board option. Validation of user input will also not be tested, so you can assume the user will always enter a valid option.

AIPLAYER CLASS

With simple games, there are techniques for developing AI players which perform very well. For general games this can be a very challenging task to accomplish efficiently, but for very simple games like tic-tac-toe even a simple recursive solution is efficient enough. This class will model this recursive solution. The AIPlayer class includes the following components:

• It should extend the Player class.
• It should have one private String object with the name name.
• It should have one private Player object with the name opponent.
• It should have a getter and setter for the opponent field.
• It should override the toString method to return the name field concatenated with the string " (AI)" (so if the name field was "Player 1" the return value should be "Player 1 (AI)")
• It should have one public constructor that takes one String and one Player as arguments as initial values for these two fields.
• It should have two mutually recursive methods, minValue and maxValue. If regular recursion is when a method calls itself, then mutual recursion is when method A calls method B, and method B calls method A. In this case, the recursive calls in minValue will be to maxValue, and the recursive calls in maxValue will be to minValue. The details of how these methods work are as follows:
  • Both methods are public, take a TicTacToe instance as their single argument, and return a double value.
  • The base cases for both methods are the same: if the argument represents a tic-tac-toe game where this AIPlayer has won the game the return value is 1.0. If the argument is a game where this player has lost the game the return value is -1.0. If the argument is a draw game, the return value is 0.0. If no one has won and the game is not a draw, the return value of the board must be computed recursively.
  • The recursive cases are similar to each other, but slightly different. The maxValue method is used to determine what value this player could get by choosing optimally among the options provided by possibleMoves for the current game board. In order to compute this, the AIPlayer assumes that its opponent is going to try and choose the move option on the next board which minimizes its return. Therefore, maxValue should compute the minValue of each of the possible moves for this player, and then return the value of the option with the highest value.
  • Similarly, the recursive case for the minValue method looks at the possibleMoves for the opponent, computes the maxValue of each option, and returns the value of the option which is lowest.
• With the above two recursive methods completed, the AIPlayer can now override the chooseMove method. This method should get all of the possibleMoves for the given board, calculate each of the possible moves' minValue, and then return the move with the highest value.
• Since the AIPlayer has a mechanism for computing the value of a game board that is more sophisticated than the default provided in Player, we should override the boardValue method as well, so that it returns the maxValue of the given board. This might be helpful when debugging your recursive implementations. For example, consider the following board:

O _ X
_ X _
_ O X

• The current player in this situation is "O", but regardless of which option they choose, the "X" player can win on the next turn. Therefore, even though though this board isn't complete yet, the boardValue for the "X" player should be 1.0 (and -1.0 for the "O" player). It can be helpful when debugging your recursive solution to construct several different boards that are one, two, or three moves away from a winning/losing or draw board, and then trace the recursion step by step.

PVPGAME AND VSCOMPUTER CLASSES

Both of these classes are complete as provided. If all your other classes are implemented correctly, you should be able to compile and run either class to play a game of tic-tac-toe. You may modify these classes as you wish, but you should make sure that in your final submission your code compiles and runs correctly with the original contents. You do not need to include PVPGame.java or VSComputer.java in your submission (and your submission should compile cleanly if these files are missing).

TESTING:

There are two completly implemented classes which are provided to you for testing your code:

• PVPGame.java
• VSComputer.java

Both classes create instances of the TicTacToe and UserPlayer classes, and use them to play a game of tic-tac-toe with a user on the command line. The PVPGame class creates two UserPlayer's, and can be used to quickly verify that the basic game functionality works correctly. The VSComputer class creates one UserPlayer and one AIPlayer so that you can test your tic-tac-toe skills against a difficult opponent. If you have implemented everything correctly, the AIPlayer should never lose, and should win if the UserPlayer makes mistakes! In order to compile these two classes, you must have created all of the appropriate .java files, and much of the API must be correct. Most logic errors should be clear when running these classes, however you should still write your own tests to verify the correctness of your code. You do not need to use the junit framework (or jar file) to compile these two classes, but you should use unit testing for your own tests.

PVPGame.java

// PVPGame.java
import java.util.Scanner;
public class PVPGame{
public static void main(String[] args){
Scanner s = new Scanner(System.in);
Player p1 = new UserPlayer(s,"X");
Player p2 = new UserPlayer(s,"O");
TicTacToe board = new TicTacToe(p1,p2);

while(!board.checkWin(p1) && !board.checkWin(p2) && !board.checkDraw()){
board = p1.chooseMove(board);
Player tmp = p1;
p1 = p2;
p2 = tmp;
}
if(board.checkWin(p1)){
System.out.println("Player ["+p1+"] wins!");
} else if(board.checkWin(p2)){
System.out.println("Player ["+p2+"] wins!");
} else if(board.checkDraw()){
System.out.println("Draw");
}
System.out.println("Final game board:");
System.out.println(board);
}
}

VSComputer.java

// VSComputer.java
import java.util.Scanner;
public class VSComputer {
public static void main(String[] args){
Scanner s = new Scanner(System.in);
Player p1 = new UserPlayer(s,"X");
Player p2 = new AIPlayer("O",p1);
TicTacToe board = new TicTacToe(p1,p2);

while(!board.checkWin(p1) && !board.checkWin(p2) && !board.checkDraw()){
board = p1.chooseMove(board);
Player tmp = p1;
p1 = p2;
p2 = tmp;
}
if(board.checkWin(p1)){
System.out.println("Player ["+p1+"] wins!");
} else if(board.checkWin(p2)){
System.out.println("Player ["+p2+"] wins!");
} else if(board.checkDraw()){
System.out.println("Draw");
}
System.out.println("Final game board:");
System.out.println(board);
}
}