You are not allowed to use any built-in Java API Data Structure classes to implement this assignment except where noted.

You may use Scanner, InputStreamReader, or any other class that you wish for keyboard input.

After watching Googles AI, AlphaGos Go match with the best Go player in the world, you feel motivated to start moving into the Artificial Intelligence field of Computer Science. However, even though you want to Go, you have no clue where to start. It seems the world is playing chess, and you're just trying to play checkers. Perhaps the simplest game to brute-force is Tic-Tac-Toe. Your job is to build a Tic Tac Toe AI that can't lose. In order to do this, you will have to build a game tree for tic tac toe.

Required Classes

The following sections describe classes which are required for this assignment. Each section provides a description and the specification necessary to complete each class. If you feel that additional methods would be useful, you may feel free to add them during your implementation as you see fit.

Note: The instructions detailed in this specification should be considered more as a guideline than as a set of fixed rules. Please feel free to add additional classes, methods, member variables as you see fit. As long as the requirements are satisfied, i.e. all operations in the grading key are supported, you may be as flexible as you like when implementing the assignment. Please keep in mind that standard OOP practices should still be followed, and points will be deducted for poor software design (e.g. using public instance variables).

Box enum

Write a simple enum named Box, which lists all the possible configurations of a box on the Tic-Tac-Toe board. Java enums are very similar to Java classes, though they are typically used to encapsulate a set of related constants. In this case, we use it to represent the possible configurations of a box on the game board, which can be either X, O, EMPTY.

GameBoard

Write a fully documented class named GameBoard. This class represents the board the game Tic-Tac-Toe is being played on. Each game board will only contain one private member variable which is an array of Boxes. This will be the representation of the Tic-Tac-Toe game board.

private Box[] board

private final int boardSize = 9

public GameBoard()

The default constructor for the GameBoard class. This constructor should initialize the array of Boxes to size boardSize.

The representation of the GameBoard will be as follows:

Example GameBoard:

|X|O|X|

|_|X|O|

|O|X|_|

Indexing will go from top to bottom, left to right. The indexing of the array of Boxes will work like this:

|0|1|2|

|3|4|5|

|6|7|8|

However, the user should see numbers 1 through 9.

If board[i] == Box.EMPTY, the console representation should be an underscore. The initial representation of an empty GameBoard should look like this:

|_|_|_|

|_|_|_|

|_|_|_|

GameBoardNode

Write a fully documented class named GameBoardNode which represents a possible configuration of the board. The GameBoardNode class should contain an array of 9 GameBoardNode references, config[]. In addition the class should contain three more variables, board (GameBoard), isEnd (boolean), currentTurn (Box), and winner (Box). The board is the representation of the current state of the game of Tic-Tac-Toe, the isEnd boolean will be true if the end of the game has been reached, the currentTurn will be of type Box and will represent if its Xs turn or Os turn at the current configuration of the board, and the winner will be of type Box and represent who the winner was, or if the game ended in a draw.

private GameBoard board

private boolean isEnd

private Box currentTurn

private Box winner

Note: If the game ended in a draw, the value of this variable should be Box.EMPTY.

private GameBoardNode config[] //size=9

private double winProb=the number of winning leavesumber of total leaves in the subtree from this node

private double loseProb=the number of losing leavesumber of total leaves in the subtree from this node

private double drawProb=the number of draw leavesumber of total leaves in the subtree from this node

Note: Each GameBoardNode reference in the config array will be to a possible move from the current state of the GameBoard. If the move is impossible from the current state of the game (i.e. if that Box is already filled by some other value), then that child will be null.

public GameBoardNode(GameBoard board, Box currentTurn)

The default constructor for the GameBoardNode class. The configurations of the GameBoard (aka the config references) should be created based on the configuration of the board as well as whose turn it currently is. The value of currentTurn will determine which extra Box will be filled in.

Preconditions:

currentTurn != Box.EMPTY

board is not null.

Note: you may include custom constructors which take any parameters you like.

public void setProbabilities()

Sets all probabilities of winning, losing and drawing from the current configuration of the GameBoard. This method should not return anything, but should set the variables winProb, loseProb, and drawProb to their respective probabilities.

public String toString()

Creates and returns the String representation of the GameBoard configuration in the current GameBoardNode.

GameTree

Write a fully documented class named GameTree which represents the tree of possible moves in the game of Tic-Tac-Toe. This class should be a 9-ary tree of GameBoardNodes, which are structured as a continuous chain of possible moves the user may make to reach the end of the game (any leaf node). The member variables are as follows:

private GameBoardNode root

A reference to the root of the GameBoardNode of this tree. All GameTree instances should have the same root node with the initial empty configuration. Even if the GameTree is empty and contains no GameBoardNodes, the root variable should always reference an object with these attributes. This is the starting configuration of the GameBoard.

private GameBoardNode cursor

A reference to the currently selected GameBoardNode in the tree. The cursor should never be null and should select the root node by default.

public GameTree()

The default constructor for the GameTree class. An empty GameTree should still have a root with the default initial configuration.

Note: you may include custom constructors which take any parameters you like.

public void makeMove(int position)

Attempts to make the move on the position passed in as a parameter.

Preconditions:

0

Throws:

IllegalArgumentException if position is out of range or if the move the user would like to make is illegal.

public static GameBoardNode buildTree(GameBoardNode root, Box turn)

Builds the GameTree from the current state the game is in. The root represents the current state of the game and the turn represents the turn to be made when building the GameTree.

Returns the root of the GameTree built from the current game state.

public static Box checkWin(GameBoardNode node)

Checks whether or not the passed in GameBoardNodes configuration is a winning state or not.

Returns the winners symbol if it is a winning state. If the current configuration of the GameBoard in the GameBoardNode is not a leaf in the GameTree (all child references are null), then this method should return null. If the configuration is a draw, this method should return Box.EMPTY.

public double cursorProbability()

Returns the current probability of winning for the GameBoardNode configuration at the cursor.

TicTacToeAI

Write a fully documented class named TicTacToeAI. This class should contain a main method along with a static utility function, playGame(GameTree tree). This is the function that will allow the user to play the Tic-Tac-Toe game given by the respective GameTree. When the program begins, you should create a GameTree and use the static function GameTree.playGame(tree).

public static void main(String[] args)

Creates the empty GameTree and initializes which player is going to have which symbol from the Box enum.

public static void playGame(GameTree tree)

Provides a user interface allowing a player to play against the Tic-Tac-Toe AI represented by tree. This method will allow a user to keep playing the TicTacToe game until either the user wins or loses, or the game ends in a draw. At each turn, you should print out the probability of winning, losing, and drawing from the current configuration. You should round these probabilities to two decimal places. Note that your probabilities could possibly not add to 1.0 because Java truncates decimals, that is OK.

Note: It may be a good starting strategy for the Tic-Tac-Toe AI to choose which position in the board to place the decision based on probabilities determined in the passed in GameTree. For more details see strategy.

It is required for the AI to try to block any opposing two out of three when possible, and to make a winning move if has two out of three and the remaining spot is empty. If it is caught in a "double trap" blocking either of the possible wins is ok (although a great AI will never get there in the first place).

Warning: You should make sure that you catch ALL exceptions that you throw anywhere in your code. Exceptions are used to indicate illegal or unsupported operations so that your program can handle unexpected events gracefully and prevent a crash. Your program should NOT crash from any of the above exceptions (it should not crash from any exception,but especially not one that you throw yourself).

Extra Credit

For extra credit, if the user enters 0, it should undo his/her previous move. This cannot be used once the game is finished. In terms of the game tree, you should find the current node's grand parent. This will be worth 4 points if implemented correctly. GUI is worth 7 points, Android is worth 10 points.

General Recommendations

You might want to implement a toString() method for classes to make debugging and printing easier. You do not have to do this, but it will help you.

You can feel free to add extra methods and variables if you need.

Strategy: Here is a comprehensive strategy guide: https://www.cs.jhu.edu/~jorgev/cs106/ttt.pdf

A decent starting point is to always take the branch that minimizes the probability of losing.

Output Format

All lists must be printed in a nice and tabular form as shown in the sample output. You may use C style formatting as shown in the following example. The example below shows two different ways of displaying the name and address at pre-specified positions 21, 26, 19, and 6 spaces wide. If the - flag is given, then it will be left-justified (padding will be on the right), else the region is right-justified. The s identifier is for strings, the d identifier is for integers. Giving the additional 0 flag pads an integer with additional zeroes in front.

String name = "Doe Jane"; String address = "32 Bayview Dr."; String city = "Fishers Island, NY"; int zip = 6390; System.out.println(String.format("%-21s%-26s%19s%06d", name, address, city, zip)); System.out.printf("%-21s%-26s%19s%06d", name, address, city, zip); // Output Doe Jane 32 Bayview Dr. Fishers Island, NY 06390 Doe Jane 32 Bayview Dr. Fishers Island, NY 06390

Sample Input/Output

*****run 1****

Welcome to Tic Tac Toe!

This is the board:

|1|2|3|

|4|5|6|

|7|8|9|

Please make a move

1

|X|_|_|

|_|O|_|

|_|_|_|

the probability of a win is:0.41

the probability of a draw is:0.20

the probability of a loss is:0.37

Please make a move

2

|X|X|O|

|_|O|_|

|_|_|_|

the probability of a win is:0.23

the probability of a draw is:0.25

the probability of a loss is:0.51

Please make a move

4

|X|X|O|

|X|O|_|

|O|_|_|

the probability of a win is:0.0

the probability of a draw is:0.0

the probability of a loss is:1.0

The winner is:O

*****run 2****

Welcome to Tic Tac Toe!

This is the board:

|1|2|3|

|4|5|6|

|7|8|9|

Please make a move

1

|X|_|_|

|_|O|_|

|_|_|_|

the probability of a win is:0.41

the probability of a draw is:0.20

the probability of a loss is:0.37

Please make a move

3

|X|O|X|

|_|O|_|

|_|_|_|

the probability of a win is:0.26

the probability of a draw is:0.39

the probability of a loss is:0.34

Please make a move

8

|X|O|X|

|_|O|_|

|_|X|O|

the probability of a win is:0.33

the probability of a draw is:0.66

the probability of a loss is:0.0

Please make a move

7

|X|O|X|

|O|O|_|

|X|X|O|

the probability of a win is:0.0

the probability of a draw is:1.0

the probability of a loss is:0.0

Please make a move

6

|X|O|X|

|O|O|X|

|X|X|O|

the probability of a win is:0.0

the probability of a draw is:1.0

the probability of a loss is:0.0

It's a draw

*****extra credit****

Welcome to Tic Tac Toe!

This is the board:

|1|2|3|

|4|5|6|

|7|8|9|

Please make a move

1

|X|_|_|

|_|O|_|

|_|_|_|

the probability of a win is:0.41

the probability of a draw is:0.20

the probability of a loss is:0.37

Please make a move

3

|X|O|X|

|_|O|_|

|_|_|_|

the probability of a win is:0.26

the probability of a draw is:0.39

the probability of a loss is:0.34

Please make a move

8

|X|O|X|

|_|O|_|

|_|X|O|

the probability of a win is:0.33

the probability of a draw is:0.66

the probability of a loss is:0.0

Please make a move

7

|X|O|X|

|O|O|_|

|X|X|O|

the probability of a win is:0.0

the probability of a draw is:1.0

the probability of a loss is:0.0

Please make a move

0//undo move 7 by user

|X|O|X|

|_|O|_|

|_|X|O|

the probability of a win is:0.33

the probability of a draw is:0.66

the probability of a loss is:0.0

Please make a move

6

|X|O|X|

|_|O|X|

|O|X|O|

the probability of a win is:0.0

the probability of a draw is:1.0

the probability of a loss is:0.0

Please make a move

4

|X|O|X|

|X|O|X|

|O|X|O|

the probability of a win is:0.0

the probability of a draw is:1.0

the probability of a loss is:0.0

It's a draw

O IX XIO Original Board Move 1 (partial) Possibilities after move 1 (partial Move 2 (partial) Possibilities after move 2 (partial O IX XIO Original Board Move 1 (partial) Possibilities after move 1 (partial Move 2 (partial) Possibilities after move 2 (partial