in java

Implement a graphical tic-tac-toe program in which a humanplayer can play an AI player, two human players can play eachother or two AI players can play each other.

In this version of tic-tac-toe the board is a five by five gridand four contiguous X's or O's in a line constitute a win. (Thatmeans there are 28 ways to win.) Also, to make the matchesmore interesting, every game should start with 2, 4, 6 or 8randomly chosen squares pre-occupied by 'X's and 'O's. The pre-filled squares should have the same numberof X's and O's.

Implement a Player class to represent each playerand to store the player's name , current score, status (X orO) along with a reference to the shared Board object. Player shouldalso have a move method (possibly abstract) to get theplayer's next move (probably just a square number). Player willhave two subclasses Human and AI which both override the movemethod. The human move method will get a legal square number fromthe user. The AI move method will return a square number based on arecursive algorithm (see below).

Additionally there should be a Board class to store the currentboard, the number of squares occupied (0 to 25) etc along withmethods to determine whether X or O has a win etc.

Finally you'll implement a TicTacToe class to manage thegame and serve as the graphical front end (e.g. via an applet orJFrame) . TicTacToe will include references to each player(via instance variables of type Player) and a reference to thecurrent board object.

The AI version of move should incorporate recursive lookahead tofind the best move. See BB and the exercises posted underTicTacToe on MyProgrammingLab to see how this can work. (Inthose exercises the recursion is "unwound" in the form of severalmethods with similar names that call each other in a chain.)

Your AI player should play at a level equal to or above that ofan average human player. For example, it should usually beator tie someone who is playing 5-by-5 Tic Tac Toe for the firstfew times. It should do that without taking an unreasonabletime to move. A reasonable time should never be more than 3minutes per move and usually much less.

Upload your files and put any instructions for using the programin the comments box. You may collaborate with one otherperson if you want to. Both people should upload the same code andsay who you worked with in the comments box.

Board.java (5.775 KB)

/*

* Return a Move object representing a best move forthe current player.

* Use minimax strategy, meaning out of all possiblemoves, choose the one that is the worst for your opponent.

* Provisionally make a move, then recursivelyevaluate your opponent's possible responses.

* Your best move is the one that "minimizes" thevalue of your opponent's best response.

*/

public Move bestMove() {

Move bestSoFar = new Move(); // an impossibly "bad"move.

int [] squares = new int[10];

randomizeOrder(squares);

for (int i = 1; i

{

int s = squares[i];

if (isFreeSquare(s))

{

Move m = newMove(squares[i],evaluateMove(s));

if(m.betterThan(bestSoFar)) bestSoFar = m;

}

}

return bestSoFar;

}

public int evaluateMove(int square) {

moveToSquare(square);

int val = boardValue(); // if this is != 0then it's a winning move

if (!boardFull() && val ==0) val = bestMove().value;

unDo(square);

return val;

/*

* The numerical value of my move isequal to the value of opponent's best response.

* For example, suppose I'm X and I wantto evaluate a move to a certain square.

* We determine that O's best response(to some other square) has value -1.

* That's a good number for O. (In fact,it means a win for O) but a bad number for me.

* When comparing moves, we prefer smallnumbers for O and big numbers for X.

* The Move.betterThan() method makesthis determination.

*/

}

// Move is an inner class and allows us to wrap a squareand a value together.

// It's an inner class so we have access to the xturn()method of Board.

class Move {

int square, value;

public Move(int square, int value) {

this.square = square;

this.value = value;

}

public Move() {

this(0, Board.this.xturn() ? -2 :2); // give this impossible move an impossibly bad value

}

boolean betterThan(Move m) {

if (Board.this.xturn()) returnthis.value > m.value;

else return this.value

}

public String toString() {return "[ square="+ square + ", value=" + value + " ]";

}

}