You are to implement a program that will play an optimal game of tic-tac-toe against a human user. Prior to playing the game itself, the program must first construct a game tree to represent all possible configurations of the board. You must use the representation of a general tree discussed in class and also described in section 4.1 of your textbook, in which each node has a pointer to its leftmost child and its (own) next sibling. Your program will always allow the human user to have the first turn. The human user has 9 possible moves for their first turn (represented by 9 children of the root node in the game tree). The computer then has 8 possible moves (represented by 8 children for each of the nodes at the previous level), the human user then has 7 possible moves for each of those, etc. You should initially construct the tree in this way, without considering which moves are better or whether a winner has already been determined. Some of the configurations in the game tree will represent a win or a loss for the computer, while others will still be undetermined. Consider the following examples, in which X is the human user and O is the computer opponent: X X X O X X X O X O X X O X O O O O Undetermined Win for X Win for O According to the rules of tic-tac-toe, the game stops once one of the players has won the game. For example, in the second configuration shown above, O is not allowed to make another move since X has already won the game. Therefore if it can be determined who has won the game by looking at a given configuration, then the node representing this configuration should be modified as necessary so that it does not have any children. The next step in your program is therefore to traverse the tree using a preorder traversal, and determine which nodes represent configurations for which a win or loss may be determined. During the traversal, if such a node n is identified, then the program should remove all subtrees of n. For example, the second configuration shown above would have the following 2 children, in which O fills one of the 2 remaining empty squares: X O X X O X X O X O O X O O X O Each of those children would in turn have 1 child, in which X fills the only remaining empty square. In general, a node representing a configuration with i remaining empty squares is the root of a tree that contains exactly i! leaves. We wish our program to try to make the best move, so we must also store information in the tree that enables us to find such a move. Each node n represents a given configuration, and the children of n are the configurations resulting from all legal moves from n. We shall define an optimal move as the one that results in a configuration c satisfying all of the following: c is a child of n, and amongst all children of n, c maximizes the value w-l, where w = # of leaves in all winning configurations (for the computer) in the subtree rooted at c, and l = # of leaves in all losing configurations (for the computer) in the subtree rooted at c. In each node, you must store the values w and l; these must be determined recursively, using a postorder traversal. In order for the program to be as efficient as possible during the course of a game, you must now sort the children of each node so that they are arranged (left-right) in increasing order of the value w-l. You can use any sorting algorithm of your choice. After this step, all precomputation is finished and your program is ready to play against a human user. Your program will now display an empty board and prompt the user for their first move. Note that you will not be marked on how fancy the graphics are that you use to display the board, so you simply need to choose something that is clear. After each move (human or computer), the program must display the new status of the board and determine if there is a winner. If the human user wins, then display the message you win. If the computer wins, then display the message I win. If there is no winner after the board is entirely full, then display the message no winner. The program must then ask the user if they wish to play another game.