/*
 * Created on Jul 19, 2005
 *
 * To change the template for this generated file go to
 * Window - Preferences - Java - Code Generation - Code and Comments
 */

import java.util.Random;
import java.util.Vector;
import java.awt.Point;

class TicTacBoard
{
	private Piece[][] board;
	private Piece WhoNext;
	private Random generator = new Random();
	
	public TicTacBoard() {
		board = new Piece[3][3];
		for(int i=0; i<3; i++)
			for(int j=0; j<3; j++)
				board[i][j] = new Piece(Piece.Empty, i, j);
		WhoNext = new Piece(Piece.Player1);
	}
	
	public TicTacBoard(char startingPlayer) {
		this();
		WhoNext = new Piece(startingPlayer);
	}
	
	public TicTacBoard(TicTacBoard ttb) {
		board = new Piece[3][3];
		for(int i=0; i<3; i++)
			for(int j=0; j<3; j++)
				board[i][j] = new Piece(ttb.board[i][j]);
		WhoNext = ttb.WhoNext;
	}
	
	/* return true on error */
	public boolean makeMove(Piece p) {
		// Verify that the space is open
		if(board[p.getX()][p.getY()].getPiece()!=Piece.Empty)
			return true;
		// Verify that it is the correct player trying to play
		else if(p.getPiece()!=WhoNext.getPiece())
			return true;

		board[p.getX()][p.getY()].set(p);
		if(WhoNext.getPiece()==Piece.Player1) WhoNext.set(Piece.Player2);
		else WhoNext.set(Piece.Player1);
		return false;
	}
	
	public boolean removeMove(Piece p) {
		// Verify the the piece to remove is really the piece on the board
		if(!board[p.getX()][p.getY()].equals(p))
			return true;
		// Verify that we're taking off a piece that could be the
		// last one played. The last play isn't stored, so who knows....
		// At least the number of pieces on the board for each player is checked.
		else if(p.getPiece()==WhoNext.getPiece())
			return true;
		
		board[p.getX()][p.getY()].set(Piece.Empty);
		if(WhoNext.getPiece()==Piece.Player1) WhoNext.set(Piece.Player2);
		else WhoNext.set(Piece.Player1);
		return false;
	}
	/* Places the piece and returns true if it connects 3. Does NOT
	 * verify the order of play like makeMove and removeMove do.
	 */
	public boolean testMove(Piece p) {
		// Verify that the space is open
		if(board[p.getX()][p.getY()].getPiece()!=Piece.Empty)
			return false;
		board[p.getX()][p.getY()].set(p);
		boolean result = checkWin(p.getPiece());
		board[p.getX()][p.getY()].set(Piece.Empty);
		return result;
	}
		
	
	public String printText() {
		/* returns a text string of the board in plain text */
		String return_str =  "   1   2   3\n" +
			"1  "+board[0][0].getPiece()+" | "+board[0][1].getPiece()+
			" | "+board[0][2].getPiece()+"\n"+
			"  ------------\n"+
			"2  "+board[1][0].getPiece()+" | "+board[1][1].getPiece()+
			" | "+board[1][2].getPiece()+"\n"+
			"  ------------\n"+
			"3  "+board[2][0].getPiece()+" | "+board[2][1].getPiece()+
			" | "+board[2][2].getPiece();
		return return_str;
	}
	
	public void printHTML() {
		/* returns a text string of the the board in formatted HTML */
	}
	
	/* check if player with piece p won. p should be Piece.Player1 or Piece.Player2 */
	public boolean checkWin(char p) {
		// Check rows
		for (int i=0; i<3; i++)
			if (board[i][0].getPiece()==p &&
					board[i][1].getPiece()==p &&
					board[i][2].getPiece()==p)
				return true;
		// Check columns
		for (int j=0; j<3; j++)
			if (board[0][j].getPiece()==p && 
					board[1][j].getPiece()==p && 
					board[2][j].getPiece()==p)
				return true;
		// Check diagonals
		if (board[0][0].getPiece()==p && 
				board[1][1].getPiece()==p && 
				board[2][2].getPiece()==p)
			return true;
		if (board[0][2].getPiece()==p && 
				board[1][1].getPiece()==p && 
				board[2][0].getPiece()==p)
			return true;
		// No win found
		return false;
	}
	
	public boolean checkCat() {
		// First check if the board is full.	
		boolean boardFull=true;
		for (int i=0; i<3; i++)
			for (int j=0; j<3; j++)
				if (board[i][j].getPiece()==Piece.Empty)
					boardFull=false;
		// Then make sure no one won
		if (boardFull)
			return !checkWin(Piece.Player1) && !checkWin(Piece.Player2);
		else
			return false;
	}
	
	private char playGame() {
		/* Plays out a game starting from board with startpiece having
		 *	the next play.  Returns the piece of the winning player (i.e.
		 *	Piece.Player1 or .Player2 or .Empty for a cat game.
		 *	The DecideMove function is used to determine
		 *	move choices so DecideMove should make at least one play choice
		 *	before calling PlayGame (otherwise they will recursively loop
		 *	infinitely.
		 */
		// Save a copy of the board, we don't want to mess with the
		// "real" board.  The name "mash" is for no good reason, but I like.
		TicTacBoard mash = new TicTacBoard(this);
		
		// First see if someone already won
		if (mash.checkWin(Piece.Player1))
			return Piece.Player1;
		else if (mash.checkWin(Piece.Player2))
			return Piece.Player2;

		// Check if board is full (i.e. cat game)
		if(mash.checkCat())
			return Piece.Empty;

		// Choose a move
		Piece NextMove = mash.decideMove();
		// Make the move, watching for an invalid move which could cause an infinite loop
		if(mash.makeMove(NextMove))
			return Piece.Empty;
		
		// Let the opponent move.  (Here it will check if the previous move won.)
		char winner = mash.playGame();
		mash.removeMove(NextMove);
		return winner;

	}
	
	public Piece decideMove() {
	/* Decide what move to make based on the current pieces on the board. */
		// local variables:
		int i, j, i2, j2;
		char mypiece, oppiece;
		
		// Figure out who is who
		mypiece = WhoNext.getPiece();
		if (mypiece==Piece.Player1)
			oppiece=Piece.Player2;
		else
			oppiece=Piece.Player1;

		// This also allows a recursive call to be made to this function
		// without worrying about an infinite loop.
		boolean BoardFull=true;
		for (i=0; i<3; i++)
			for (j=0; j<3; j++)
				if (board[i][j].getPiece()==Piece.Empty)
					BoardFull=false;
		if (BoardFull)
			return null;

		// See if this is the first move
		boolean IMoved = false;
		boolean OpMoved = false;
		Point op = new Point(0, 0);
		for (i=0; i<3; i++)
			for (j=0; j<3; j++)
				if (board[i][j].getPiece()==mypiece)
					IMoved=true;
				else if (board[i][j].getPiece()==oppiece) {
					OpMoved=true;
					 // store move for first counter-move
					op.move(i, j);
				}
					
		if (!IMoved && !OpMoved)
			// Strategy 1: Best chance to win
			// very first move: pick a corner
			//return new Piece(mypiece, 0, 0);

			// Strategy 2: More fun to play
			// Make a random first move and at least go for a cat game
			return new Piece(mypiece, generator.nextInt(3), generator.nextInt(3));
		if (!IMoved && OpMoved) {
			// first counter move: most complicated choice!
			// decision will be hard-coded based on opponents choice
			// If opponent took a corner, go on adjacent edge
			if (op.equals(new Point(0,0)) || op.equals(new Point(0,2)))
				return new Piece(mypiece, 1, 1);
			if (op.equals(new Point(2,0)) || op.equals(new Point(2,2)))
				return new Piece(mypiece, 1, 1);
			// If opponent took an edge, take an adjacent corner
			if (op.equals(new Point(0,1)) || op.equals(new Point(1,0)))
				return new Piece(mypiece, 0, 0);
			if (op.equals(new Point(2,1)) || op.equals(new Point(1,2)))
				return new Piece(mypiece, 2, 2);
			// If opponent took center, take a corner
			if (op.equals(new Point(1,1)))
				return new Piece(mypiece, 0, 0);
		}

		// See if one move will win the game
			for (i=0; i<3; i++)
				for (j=0; j<3; j++)
					if (testMove(new Piece(mypiece, i, j)))
						return new Piece(mypiece, i, j);  // return the move if it wins


		// See if opponent can win the game in one move
		for (i=0; i<3; i++)
			for (j=0; j<3; j++)
				if (testMove(new Piece(oppiece, i, j)))
					return new Piece(mypiece, i, j); // return move to block opp.

		// See if two moves will win the game
		// For each possible move see if two winning moves
		// exist for next turn.
		for (i=0; i<3; i++)
			for (j=0; j<3; j++) {
				if (board[i][j].getPiece()==Piece.Empty) {
					makeMove(new Piece(mypiece, i, j)); // Make the potential move
					Vector NextWin = new Vector(); // list of possible winning next moves
					for (i2=0; i2<3; i2++)
						for (j2=0; j2<3; j2++)
							if (testMove(new Piece(mypiece, i2, j2)))
									NextWin.add(new Piece(i2, j2));
					if (NextWin.size()>=2) {
						removeMove(new Piece(mypiece, i, j)); // Take back the move
						return new Piece(mypiece, i, j);
					}
					removeMove(new Piece(mypiece, i, j)); // Take back the move
				}
			}
		// Play out game for each possible move and pick one where I win,
		// or if I can't win, at least a cat game.
		Vector IWin = new Vector();
		Vector ScratchGame = new Vector();
		char winner;
		for (i=0; i<3; i++)
			for (j=0; j<3; j++) {
				if (!makeMove(new Piece(mypiece, i, j)))  { // Make the potential move
					winner = playGame(); // Play out game
					if (winner==mypiece) {
						IWin.add(new Piece(mypiece, i, j));
						removeMove(new Piece(mypiece, i, j)); // Take back the move
						return new Piece(mypiece, i, j);
					}
					else if (winner==Piece.Empty)
						ScratchGame.add(new Piece(mypiece, i, j));
					removeMove(new Piece(mypiece, i, j)); // Take back move
				}
			}
		if (IWin.size()>0)
			return (Piece) IWin.get(generator.nextInt(IWin.size())); // If I can win, pick a random winning
		else if (ScratchGame.size()>0) 
			return (Piece) ScratchGame.get(generator.nextInt(ScratchGame.size())); // If I can't win, pick a random scratch game

		// No good move found: take the center square if it is open
		if (board[1][1].getPiece()==Piece.Empty)
			return new Piece(mypiece, 1, 1);

		// No strategy at all, just pick the first open space.
		for (i=0; i<3; i++)
			for (j=0; j<3; j++)
				if (board[i][j].getPiece()==Piece.Empty)
					return new Piece(mypiece, i, j);
	
		return new Piece(mypiece, 0, 0); // should never get to this line
	}
}