TestTreeADT:

public class TestTreeADT {

public static void main(String[] args) {

ArrayTree a1 = new ArrayTree(2, 25);

ArrayTree a2 = new ArrayTree(5, 55);

int val = 1;

System.out.println("*** Test ArrayTree ADT *** ");

testcase("a1.isEmpty()", a1.isEmpty() ? 1 : 0, 1);

int pos = a1.addRoot(val++);

for (int i = 0; i

a1.addChild(pos, 0, val++);

a1.addChild(pos, 1, val++);

pos++;

}

testcase("a1.root()", a1.root(), 0);

testcase("a1.parent()", a1.parent(7), 3);

testcase("a1.child()", a1.child(10, 1), 22);

testcase("a1.size()", a1.size(), 21);

testcase("a1.isEmpty()", a1.isEmpty() ? 1 : 0, 0);

testcase("a1.get()", a1.get(3), 4);

testcase("a1.getChild()", a1.getChild(6, 1), 15);

System.out.println("Small Tree: " + a1 +" ");

testcase("a2.isEmpty()", a2.isEmpty() ? 1 : 0, 1);

pos = a2.addRoot(val++);

for (int i = 0; i

for (int j = 0; j

a2.addChild(pos, j, val++);

}

pos++;

}

testcase("a2.root()", a2.root(), 0);

testcase("a2.parent()", a2.parent(27), 5);

testcase("a2.child()", a2.child(14, 4), 75);

testcase("a2.size()", a2.size(), 51);

testcase("a2.isEmpty()", a2.isEmpty() ? 1 : 0, 0);

testcase("a2.get()", a2.get(18), 40);

testcase("a2.getChild()", a2.getChild(9, 0), 68);

System.out.println("Large Tree: " + a2);

}

private static void testcase(String description, int actual, int expected) {

if (actual == expected) {

System.out.println("Pass: " + description);

} else {

System.out.println("Fail: " + description + ", expected " + expected + ", got " + actual);

}

}

}

Perfect TicTacToe 1. Problem Description You are to develop a program that plays the perfect game of Tictactoe. It should never lose. Your project can be done in three steps of increasing complexity. Basic Level (for a maximum grade of 75%): Develop the Tree ADT as an array-based concrete implementation. Intermediate Level (for a maximum grade of 88%): Your program will then create every possible TicTacToe board configuration arranged as a tree. Advanced Level (for a maximum grade of 100%): Once the configurations have been calculated, you will employ a minimax algorithm to evaluate each position. When playing the game, the user will go first (x) and the computer (0) must respond with the move that maximizes its chances of victory. If done correctly, the computer will never lose. However, most games played with a competent human will end in a draw (a "Cat's Game). For the program, there is no code to start with; you are to develop everything. However, the UML design and test drivers for the Tree ADT have been supplied so you can test your implementation. Your final Java program (Adv. Level) will prompt the user for moves until the game is over. You can review the sample output below to get an idea of the interaction. Depending on the level you choose, you are to turn in the following: Basic Level: Create the Array-based Tree ADT. Run it with TestTreeADT.java to insure it works. Turn in ArrayTree.java. Intermediate Level: Generate a Game Tree of all the possible moves but only print out the first 100. The code for this is shown below in section 2.2. The root of the tree is the empty board. Turn in ArrayTree.java and Gen Tree.java (which will have your main to print the 100 positions). Advanced Level: Write the program that interacts with the user and walks the Game Tree. Turn in ArrayTree.java, GenTree.java and Tictactoe.java. 2. Additional Instructions 2.1. Basic Level: Array Tree ADT Develop an ArrayTree class to meet the design shown here. It should not implement the Tree interface we discussed in class. The behavior of each method should be clear from our discussion in class. While the class is generic (element is type E), the positions are all primitive integers. The default order is 2 and the default capacity is 1000.toString() should print a summary of the data elements as shown in the sample output below: Array - E count in orderint Treener - parempi hidrot, mint 203 -addy getipes: addChisperinchi. Et Chidin.ch -toString Sering Page 1 Running your ArrayTree with TestTreeADT.java should result in the following output. Note: it's ok that you get one Fail in testing a2. You should understand why that is correct as you implement the TreeADT. *** Test ArrayTree ADT *** Pass: al. 1sEmpty() Pass: a1.root() Pass: al.parent() Pass: a1.child() Pass: al.size() Pass: a1.isEmpty() Pass: a1.get() Pass: a1.getChild() Small Tree: [ArrayTree: order 2, count-21, size 25, array-{1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 -... }] Pass: a2.isEmpty() Pass: a2.root) Pass: a2.parent() Fail: a2.child(), expected 75, got - 1 Pass: a2.size() Pass: a2.isEmpty() Pass: a2.get() Pass: a2.getChild() Large Tree: [ArrayTree: order-5, count=51, size-55, array-{22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 .... }] 2.2. Intermediate Level: Generating the Game Tree Develop the element type that will represent each board position. In addition to Tic Tac Toe Position representing the state of the TicTacToe board, you will also need an integer to store +board: String the evaluation of the position in Step 2.3 below. I recommend someth simple +valuation int as the TicTac ToePosition shown here. I chose to represent the board as a +Tic Tac ToePosition(s: String) String of nine characters, each position either a blank, an 'X' or an 'O'. The root of your tree will be the blank board. There are 9 children from here. That is, the human player can select to place their X in any position o through 8. Create these children. From there, each of these positions has at most 8 counter moves for O. This continues down until there are no moves left. We will ignore symmetries. There are at most 9! + ... 11 (986,409) board configurations. Our tree will need to be order 9 and this will result in many empty positions. You should start your tree out with the capacity set at a staggering 500,000,000 places! To perform this step, you may want to study and adapt the breadth-first traversal algorithm. Remember not to generate moves for positions that are already occupied. If this is as far as you get, you will want to prove that your solution works. Print out the first 100 positions in the array. Perhaps you could use code like the following (adapted to any data types/classes you have used). Put this code in the main method of a class called GenTree.java. for (int i 0; i a1 = new ArrayTree(2, 25); ArrayTree a2 = new ArrayTree(5, 55); int val = 1; 8 9 System.out.println("*** Test ArrayTree ADT *** "); testcase("a1.isEmpty()", a1.isEmpty() ? 1 : 0, 1); int pos = a1.addRoot(val++); for (int i = 0; i interface we discussed in class. The behavior of each method should be clear from our discussion in class. While the class is generic (element is type E), the positions are all primitive integers. The default order is 2 and the default capacity is 1000.toString() should print a summary of the data elements as shown in the sample output below: Array - E count in orderint Treener - parempi hidrot, mint 203 -addy getipes: addChisperinchi. Et Chidin.ch -toString Sering Page 1 Running your ArrayTree with TestTreeADT.java should result in the following output. Note: it's ok that you get one Fail in testing a2. You should understand why that is correct as you implement the TreeADT. *** Test ArrayTree ADT *** Pass: al. 1sEmpty() Pass: a1.root() Pass: al.parent() Pass: a1.child() Pass: al.size() Pass: a1.isEmpty() Pass: a1.get() Pass: a1.getChild() Small Tree: [ArrayTree: order 2, count-21, size 25, array-{1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 -... }] Pass: a2.isEmpty() Pass: a2.root) Pass: a2.parent() Fail: a2.child(), expected 75, got - 1 Pass: a2.size() Pass: a2.isEmpty() Pass: a2.get() Pass: a2.getChild() Large Tree: [ArrayTree: order-5, count=51, size-55, array-{22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 .... }] 2.2. Intermediate Level: Generating the Game Tree Develop the element type that will represent each board position. In addition to Tic Tac Toe Position representing the state of the TicTacToe board, you will also need an integer to store +board: String the evaluation of the position in Step 2.3 below. I recommend someth simple +valuation int as the TicTac ToePosition shown here. I chose to represent the board as a +Tic Tac ToePosition(s: String) String of nine characters, each position either a blank, an 'X' or an 'O'. The root of your tree will be the blank board. There are 9 children from here. That is, the human player can select to place their X in any position o through 8. Create these children. From there, each of these positions has at most 8 counter moves for O. This continues down until there are no moves left. We will ignore symmetries. There are at most 9! + ... 11 (986,409) board configurations. Our tree will need to be order 9 and this will result in many empty positions. You should start your tree out with the capacity set at a staggering 500,000,000 places! To perform this step, you may want to study and adapt the breadth-first traversal algorithm. Remember not to generate moves for positions that are already occupied. If this is as far as you get, you will want to prove that your solution works. Print out the first 100 positions in the array. Perhaps you could use code like the following (adapted to any data types/classes you have used). Put this code in the main method of a class called GenTree.java. for (int i 0; i a1 = new ArrayTree(2, 25); ArrayTree a2 = new ArrayTree(5, 55); int val = 1; 8 9 System.out.println("*** Test ArrayTree ADT *** "); testcase("a1.isEmpty()", a1.isEmpty() ? 1 : 0, 1); int pos = a1.addRoot(val++); for (int i = 0; i