1 TIC TAC TOE

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, whichmean you have to do the game tree search to find the subgame equilibrium for the computer player. When the game finishes, print out who wins the game (Hint*: User recursive function).

The sample input and output are shown below:

Example 1:

java A2_Q1 "XXO_O_XO_"

The computer chooses to fill the cell #4

X X O

X O

X O

The ComputerWon!

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 X O

O O X

X

Human player please select a cell number to fill: 1

Not a validmove, please try again. Please select a cell to fill: 8

Thanks. Now the board looks like:

X X O

O O X

X O

The computer chooses to fill the cell #9

X X O

O O X

X O X

The game is finished. No one won the game.