1 Overview For this assignment you are required to write a Java program that plays (n, k)-tic-tac-toe; (n, k)-tic- tac-toe is played on a board of size n x n and to win the game a player needs to put k symbols on adjacent positions of the same row, column, or diagonal. The program will play against a human opponent. You will be given code for displaying the gameboard on the screen. 2 The Algorithm for Playing (n, k)-Tic-Tac-Toe The human player always starts the game. The human uses 'X's and the computer uses 'O's. In each turn the computer examines all possible plays or moves and selects the best one; to do this, each possible move is assigned a score. Your program will use the following 4 scores for moves: HUMAN_WINS = 0: this score is given to a move that will ensure that the human player wins UNDECIDED = 1: this score is give to a move for which it is not clear which player will win DRAW = 2: this score is given to a move that will lead to a draw (i.e. no player wins the game) COMPUTER_WINS = 3: this score is given to a move that will ensure that the computer wins For example, suppose that the gameboard looks like the one in Figure 1(a). If the computer plays in position 8, the game will end in a draw (see Figure 1(b)), so the score for the computer playing in position 8 is 2 (DRAW). Similarly, the score for the computer playing in position 9 is 0 (HUMAN_WINS). A configuration is the positioning of the symbols on the gameboard. For example, the configu- ration shown in Figure 1(b) corresponds to a game that ends up in a draw. The configuration in Figure 1(c) corresponds to a game won by the human player. Each configuration is also assigned one of the 4 above scores. So, the configuration in Figure 1(b) gets a score of 2 and the configuration in Figure 1(c) gets a score of 0. 'olx'x 'x'x O 07 o'xlx 'X 'x'o olx olxlx 'X'X 'O olxlo (a). (1) (c) 3 Classes to Implement You are to implement at least 3 Java classes: Dictionary.java, nk_TicTacToe.java, and Record.java. You can implement more classes if you need to. You must write all the code yourself. You cannot use code from the textbook, the Internet, or any other sources. You cannot use the stan- dard Java classes Hashtable, HashMap, HashSet or any other Java provided class that implements a hash table. You cannot use the hashCode () method. 3.1 Record This class represents an entry in the dictionary, associating a configuration with its integer score. Each board configuration will be represented as a string as follows: concatenate all characters placed in the board starting at the top left position and moving from left to right and from top to bot- tom. For example, for the configurations in Figure 1, their string representations are "OXXXXOO._.", "OXXXXOOOX", and "OXXXXOOXO". For this class, you must implement all and only the following public methods: public Record (String config, int score): A constructor which returns a new Record with the specified configuration and score. The string config will be used as the key attribute for every Record object. public String getConfig(): Returns the configuration stored in this Record. public int getScore(): Returns the score in this Record. You can implement any other methods that you want to in this class, but they must be declared as private methods (i.e. not accessible to other classes). 3.2 Dictionary This class implements a dictionary. You must implement the dictionary using a hash table with separate chaining. You will decide on the size of the table, keeping in mind that the size of the table must be a prime number. A table of size between 6000-8000, should work well. You must design your hash function so that it produces few collisions. (A bad hash function that induces many collisions will result in a lower mark.) Collisions must be resolved using separate chaining. For this class, you must implement all the public methods in the following interface: public interface DictionaryADT { public int insert (Record pair) throws DictionaryException; public void remove (String config) throws DictionaryException; public int get (String config); public int numElements(); The description of these methods follows: public int insert (Record pair) throws DictionaryException: Inserts the given Record pair in the dictionary. This method must throw a DictionaryException (see below) if pair.getConfig() is already in the dictionary. You are required to implement the dictionary using a hash table with separate chaining. To determine how good your design is, we will count the number of collisions produced by your hash function. Method insert must return the value 1 if the insertion of pair produces a collision, and it will return the value 0 otherwise. In other words, if for example your hash function is h(key) and the name of your table is T, this method will return the value 1 if Th(pair.getConfig())] already stores at least one element; it will return 0 if T[h(pair.getConfig()] was empty before the insertion. public void remove(String config) throws DictionaryException: Removes the entry with the given config from the dictionary. Must throw a DictionaryException (see below) if the configuration is not in the dictionary. public int get(String config): A method which returns the score stored in the dictionary for the given configuration, or -1 if the configuration is not in the dictionary. public int numElements(): A method that returns the number of Record objects stored in the dictionary. Since your Dictionary class must implement all the methods of the Dictionary ADT interface, the declaration of your method should be as follows: public class Dictionary implements Dictionary ADT The interface DictionaryADT can be found in file DictionaryADT.java. The only other public method that you can implement in the Dictionary class is the constructor method, which must be declared as follows public Dictionary (int size) this returns an empty dictionary of the specified size. You can implement any other methods that you want to in this class, but they must be declared as private methods (i.e. not accessible to other classes). 3.3 nk Tic Tac Toe This class implements all the methods needed by algorithm computerPlay, which are described below. The constructor for this class must be declared as follows public nk_TicTacToe (int board size, int inline, int max_levels) The first parameter specifies the size of the board, the second is the number of symbols in-line needed to win the game, and the third is the maximum level of the game tree that will be explored by the program. So, for example, to play the usual (3,3)-tic-tac-toe, the first two parameters will have value This class must have an instance variable gameBoard of type char [] [] to store the gameboard. This variable is initialized inside the above constructor method so that every entry of gameBoard stores a space'!. Every entry of gameBoard stores one of the characters 'X', 'O', or'! This class must also implement the following public methods. public Dictionary createDictionary (): returns an empty Dictionary of the size that you have selected. public int repeatedConfig (Dictionary configurations): This method first represents the content of gameBoard as a string as described above; then it checks whether the string representing the gameBoard is in the configurations dictionary: If it is in the dictionary this method returns its associated score, otherwise it returns the value -1. public void insertConfig (Dictionary configurations, int score): This method first represents the content of gameBoard as a string as described above; then it inserts this string and score in the configurations dictionary. Retu public void storePlay (int row, int col, char symbol): Stores symbol in gameBoard [row][col]. public boolean squareIsEmpty (int row, int col): Returns true if gameBoard [row][col] is ''; otherwise it returns false. public boolean wins (char symbol): Returns true if there are k adjacent occurrences of symbol in the same row, column, or diagonal of gameBoard, where k is the number of required symbols in-line needed to win the game. public boolean isDraw(): Returns true if gameBoard has no empty positions left and no player has won the game. public int evalBoard(): Returns one of the following values: 3, if the computer has won, i.e. there are k adjacent 'O's in the same row, column, or diagonal of gameBoard; 0, if the human player has won. 2, if the game is a draw, i.e. there are no empty positions in gameBoard and no player has won. - 1, if the game is still undecided, i.e. there are still empty positions in gameBoard and no player has won