package players;
import TicTac.*;import java.util.*;

/**
* Sample skeleton for a smart player that knows how to make the next move based
* on the alpha-beta pruning evaluation strategy.
*<Pre>
In computing the min/max value of a game tree node, we can skip ("prune") the
evaluation of some of the children nodes using what is known as alpha-beta pruning.

1.  Let alpha be a lower bound for the value of a max node A, and let B be a child node
of A.  If the value v of a child of B is less or equal to alpha, then we can use v as
a value for B and skip the rest of the children of B.  This is called "alpha pruning".

2.  Let beta be an upper bound for the value of a min node B, and let C be a child node
of B.  If the value v of a child of C is greater or equal to beta, then we can use v as
a value for C and skip the rest of the children of C.  This is called "beta pruning".

*</Pre>
@author Dung X. Nguyen
*/
public class SmartPlayer3 extends TTPlayer
{
	public SmartPlayer3 (char mark)
	{
      _mark = mark;
	}

   /**
   * Randomizes the moves array.
   */
   private final void randomize (Vector moves)
   {
      int movesNum = moves.size();
      for(int i = 0; i < movesNum; i++)
      {
         int x = (int) (movesNum * Math.random());
         Object tmp = moves.elementAt(i);
         moves.setElementAt(moves.elementAt(x), i);
         moves.setElementAt(tmp, x);
      }
   }

   /**
   * Computes the value of a min node.
   * parent node is a max node whose value >= alpha.
   */
	private final int getMin (char[][] board, char playerMark, int alpha)
	{
      // if leaf node then return payoff value:
		if (playerWins (board, _mark))
      {
         return 1;
      }
      else if (playerWins (board, TTEngine.GetOpponentMark(_mark)))
      {
         return -1;
      }
      else if (getNumEmptyCell (board) == 0)
      {
         return 0;
      }

      // else compute the minimum of the children node pruning if appropriate.
      int temp = Integer.MAX_VALUE;
      Vector moves = GetLegalMoves (playerMark, board);
      int nMoves = moves.size();
      for (int i = 0; i < nMoves; i++ )
      {
         TTMove move = (TTMove)moves.elementAt(i);
         MakeMove (playerMark, move, board);
         int childVal = getMax (board, TTEngine.GetOpponentMark(playerMark), temp);
         temp = Math.min (temp, childVal);
         if (childVal <= alpha)
         {
            undoMove (move, board);
            break;
         }
         undoMove (move, board);
      }
      return temp;
	}

   /**
   * Computes the value of max node.
   * parent node is a min node whose value <= beta.
   */
	private final int getMax (char[][] board, char playerMark, int beta)
	{
      // if leaf node then return payoff value:
		if (playerWins (board, _mark))
      {
         return 1;
      }
      else if (playerWins (board, TTEngine.GetOpponentMark(_mark)))
      {
         return -1;
      }
      else if (getNumEmptyCell (board) == 0)
      {
         return 0;
      }

      // else compute the maximum of the children node pruning if appropriate.
      int temp = Integer.MIN_VALUE;
      Vector moves = GetLegalMoves (playerMark, board);
      int nMoves = moves.size();
      for (int i = 0; i < nMoves; i++ )
      {
         TTMove move = (TTMove)moves.elementAt(i);
         MakeMove (playerMark, move, board);
         int childVal = getMin (board, TTEngine.GetOpponentMark(playerMark), temp);
         temp = Math.max (temp, childVal);
         if (beta <= childVal)
         {
            undoMove (move, board);
            break;
         }
         undoMove (move, board);
      }
      return temp;
	}

	/**
	 * Computes the next move based on the current board status.
	 * @param board
	 * @return the next best move.
	 */
	public TTMove NextMove (char[][] board)
	{
      System.out.println ("I'm thinking...");
      int best = getMax (board, _mark, Integer.MAX_VALUE);
      Vector moves = GetLegalMoves (_mark, board);
      randomize (moves);
      for (int i = 0; i < moves.size(); i++)
      {
         TTMove move = (TTMove)moves.elementAt(i);
         MakeMove (_mark, move, board);
         int temp = getMin (board, TTEngine.GetOpponentMark(_mark), Integer.MIN_VALUE);
         if (temp == best)
         {
            undoMove (move, board);
            System.out.println ("OK...");
            return move;
         }
         undoMove (move, board);
      }
		return null; // should never get here!
	}

  private final boolean playerWins (char[][] board, char playerMark)
  {
     return someRowHasAll (board, playerMark)
            || someColHasAll (board, playerMark)
            || someDiagHasAll (board, playerMark);
  }

  private final boolean someRowHasAll (char[][] board, char mark)
  {
     return (board[0][0] == mark && board[0][1] == mark && board[0][2] == mark)
         || (board[1][0] == mark && board[1][1] == mark && board[1][2] == mark)
         || (board[2][0] == mark && board[2][1] == mark && board[2][2] == mark);
  }

  private final boolean someDiagHasAll (char[][] board, char mark)
  {
     return (board[0][0] == mark && board[1][1] == mark && board[2][2] == mark)
         || (board[2][0] == mark && board[1][1] == mark && board[0][2] == mark);
  }

  private final boolean someColHasAll (char[][] board, char mark)
  {
     return (board[0][0] == mark && board[1][0] == mark && board[2][0] == mark)
         || (board[0][1] == mark && board[1][1] == mark && board[2][1] == mark)
         || (board[0][2] == mark && board[1][2] == mark && board[2][2] == mark);
  }

  private final int getNumEmptyCell (char[][] board)
  {    int cell_total = 0;
    int i, j;
    for (i=0; i<TTBoard.SIZE; i++)
    {
      for (j=0; j<TTBoard.SIZE; j++)
      {
	      if (board[i][j] == TTPlayer.B)
         {
	         cell_total++;
	      }
      }
    }
    return cell_total;
  }

 private final Vector GetLegalMoves(char player_color,  char[][] board)
  {    int i, j;
    Vector move_vector = new Vector();
    for (i=0; i<TTBoard.SIZE; i++)
    {
      for (j=0; j<TTBoard.SIZE; j++)
      {
        TTMove move = new TTMove(i, j);
        if (IsMoveLegal(move, board))
          move_vector.addElement(move);
      }
    }
    return move_vector;
  }

  private final boolean IsMoveLegal(TTMove move, char[][] board)
  {    return (move.isInbound () && board[move.x][move.y] == TTPlayer.B);
  }

  private final void MakeMove (char playerMark, TTMove move,  char[][] board)  {    if (!IsMoveLegal(move, board))
    {
      throw new RuntimeException("Illegal move!");
    }
    board[move.x][move.y] = playerMark;
  }

  private final void undoMove(TTMove move,  char[][] board)  {    board[move.x][move.y] = TTPlayer.B;
  }


  public static void main(String[] argv)
  {    TTPlayer playerX = new SmartPlayer3(X);
    TTPlayer playerO = new SmartPlayer3(O);
    if (argv.length==1 && argv[0].equals("-allmachine"))
    {
      TTManager.Singleton().PlayTicTac(playerX, playerO);
    }
    else if (argv.length==1 && argv[0].equals("-humansecond"))
    {
      TTManager.Singleton().PlayTicTacWithHuman(TTPlayer.X, playerX);
    }
    else if (argv.length==1 && argv[0].equals("-help"))
    {
      System.out.println ("Usage:\njava DumbPlayer [-help] [-allmachine] [-humansecond]");
    }
    else
    {
      TTManager.Singleton().PlayTicTacWithHuman(TTPlayer.O, playerO);
    }
  }
}