In a Tic Tac Toe game two players, X and O, take turns to mark the spaces in a 3X3 grid. The winner will be the player who first succeeds in placing three of his/her marks in a horizontal, vertical, or diagonal row. Write a program for a computer (X player) to play with a human (O player) on Tic Tac Toe game given an initial status of the game. The initial status of the game can be represented by a string of 9 characters. For example, the game status in figure 1.1 can be expressed using string OOO_OX_XX". Your program should always play the winning strategies and try to defeat the human player if possible, which mean you have to do the game tree search to find the subgame equilibrium for the computer player. When the game finishes, print out (in Java) who wins the game (Hint*: User recursive function). The sample input and output are shown below:

Example 1: >java A2 Q1 "XXO_1_XO " The computer chooses to fill the cell #4 X O The Computer Won! Example 2: (Note that the green text is the typed input from a human player) >java A2_Q1 "XXOOO_X__" The computer chooses to fill the cell #6 X Human player please select a cell number to fill: 1 Not a valid move, please try again. Please select a cell to fill: 8 Thanks. Now the board looks like: x x O The computer chooses to fill the cell #9 The game is finished. No one won the game. ololo XX Figure 1.1: Tic Tac Toe