/*
 * CSI 4106: Assignment 2
 * 
 * Name: Casey Li
 * Student Number: 2570042
 * 
 * Coures: CSI4106
 * Prof: Stan Szpakowicz
 * 
 * MINIMAX KONO GAME
 * 
 * KonoGame Class: The actual running game
 * ComputerPlayer Class: The class used to have a computer play a game
 * Position Class: The representation of a Kono board, with a collection of pieces.
 *       The board has a minimax value evaluated by getMinimaxValue
 * GamePiece Class: Used to hold the position/color of a game piece
 * KonoConstants Class: Contains constants used in the game
 * KeyboardReader Class: (Not coded by Casey Li). Obtained from
 *   http://www4.comp.polyu.edu.hk/~csgngai/courses/COMP201B/asgns/asgn1.html
 *   Used to get input from the user.
 * 
 * For the MARKER:
 * 
 * The computer works by:
 *   ComputerPlayer.computeMove()
 *    which calls Position.getMinimaxValue for each of its generated children
 * 
 * Position.getMinimaxValue is the actual Minimax algorithm implemented WITH ALPHA-BETA
 * pruning.
 * 
 * The Static Evaluation is based on 3 things:
 *   - The number of pieces and their position
 *   - Whether or not the piece can move
 *   - Whether or not the piece can take an opponent's piece
 * 
 * Please refer to Position.getMinimaxValue for details.
 * 
 * For full instructions on playing the game, run the game, and type "Y" when asked
 * "Do you want to see the instructions?[Y/n]"
 * 
 * Generally, you input 4 numbers separated by spaces:
 * (Initial Row) (Initial Col) (Final Row) (Final Col)
 * 
 * where the grid is as follows:
 * 
 *    (0,0)--(0,1)--(0,2)--(0,3)
 *      |      |      |      |
 *      |      |      |      |
 *    (1,0)--(1,1)--(1,2)--(1,3) 
 *      |      |      |      |
 *      |      |      |      |
 *    (2,0)--(2,1)--(2,2)--(2,3)
 *      |      |      |      |
 *      |      |      |      |
 *    (3,0)--(3,1)--(3,2)--(3,3)
 * 
 * For more information, contact Casey Li
 * 
 * cli047@uottawa.ca
 * 
 */

//Imports
import java.util.*;
import java.io.*;


public class KONO 
{
 /*************************************************************************************/
 /*                    */
 /* Main Method                 */
 /*                    */
 /*************************************************************************************/
 public static void main(String[] args)
 {
  KONO x = new KONO();
  x.runKonoGame(args);
 }
 
 public void runKonoGame(String[] args)
 {
  KonoGame game = new KonoGame();
  game.runProg(args);
 }
 
 ///////////////////////////////////////////////////////////////////////////////////////
 
 /*************************************************************************************/
 /*                    */
 /* KonoGame class                */
 /*                    */
 /*************************************************************************************/
 class KonoGame
 {
  public void runProg(String[] args)
  {
   System.out.println("*************************");
   System.out.println("*                       *");
   System.out.println("*     K   O   N   O     *");
   System.out.println("*                       *");
   System.out.println("*************************");
   
   KeyboardReader userInput = new KeyboardReader(System.in);
   
   System.out.println("\nBienvenue à KONO.");
   while(true)
   {
    System.out.println("Voulez-vous voir les instructions [Y / N]");
    String instruct = userInput.readLine();
    if(instruct.equalsIgnoreCase("Y"))
    {
     System.out.println("Le conseil est organisé dans le mode suivant:");
     System.out.println("\n(0,0)--(0,1)--(0,2)--(0,3)");
     System.out.println("  |      |      |      |");
     System.out.println("  |      |      |      |");
     System.out.println("(1,0)--(1,1)--(1,2)--(1,3)"); 
     System.out.println("  |      |      |      |");
     System.out.println("  |      |      |      |");
     System.out.println("(2,0)--(2,1)--(2,2)--(2,3)");
      System.out.println("  |      |      |      |");
      System.out.println("  |      |      |      |");
      System.out.println("(3,0)--(3,1)--(3,2)--(3,3)");
      
      System.out.println("\nUn point sur la carte est indiquée par (Ligne, Colonne) " +
        "\noù le coin supérieur gauche est (0,0)"+
        "\net en bas à droite est (3,3)");
      
      System.out.println("Pour entrer un déménagement, vous inscrire quatre entier valeurs séparées par des espaces:");
      System.out.println("<rangée initiale> <colonne initiale> <rangée dernière> <colonne dernière>");
      System.out.println("ligne et la colonne initiale préciser votre pièce en mouvement" +
        "\n la dernière ligne et colonne spécifiées où vous vous déplacez");
      
     break;
    
    }
    if(instruct.equalsIgnoreCase("N"))
     break;

    System.out.println("Désolé, votre choix d'entrée n'a pas été reconnu.");
   }
   
   //Select Number of PLayers
   int numOfPlayers = 0;
   while(true)
   {
    System.out.println("\nEntre le nombre de joueurs humains");
    String SnumOfPlayers = userInput.readLine();
    try
    {
     numOfPlayers = Integer.parseInt(SnumOfPlayers);
     if((numOfPlayers >= 0) && (numOfPlayers <= 2))
      break;
     else
      System.out.println("Désolé, votre choix n'était pas dans la plage donnée.");
    }
    catch(NumberFormatException ex)
    {
     System.out.println("Désolé, votre choix d'entrée n'a pas été reconnu.");
    }
   }
   
   //Potential Computer Players
   ComputerPlayer CPU1=null;
   ComputerPlayer CPU2=null;
   int CPUdifficulty=1;
   
   if(numOfPlayers < 2)
   {
    //Allow user to select difficulty 
    while(true)
    {
     System.out.println("\nS’il vous plaît choisir ordinateur difficulté / minimax profondeur de coupure [1-10]:");
     System.out.println("Note: 6 ci-dessus exige de grandes quantités de mémoire");
     String Sdifficulty = userInput.readLine();
     try
     {
      CPUdifficulty = Integer.parseInt(Sdifficulty);
      break;
     }
     catch(NumberFormatException ex)
     {
      System.out.println("Désolé, votre mise en difficulté n'a pas été reconnu.");
     }
    }
   
    
    CPU1 = new ComputerPlayer("Noire", CPUdifficulty);
    
    if(numOfPlayers == 0)
     CPU2 = new ComputerPlayer("Blanc", CPUdifficulty);
   }
   
   String userColor="";
   if(numOfPlayers == 1)
   {
    //Allow user to select color
    while(true)
    {
     System.out.println("\nS’il vous plaît choisir votre couleur [N / B]:");
     userColor = userInput.readLine();
     if(userColor.equalsIgnoreCase("B"))
     {
      userColor = "Blanc";
      break;
     }
     if(userColor.equalsIgnoreCase("N"))
     {
      userColor = "Noire";
      CPU1 = new ComputerPlayer("Blanc", CPUdifficulty);
      break;
     }
     System.out.println("Désolé, votre couleur de sélection n'était pas valable");
    }
   
   }
   
   //Start Board
   Position CurrentBoard = new Position(true);

   //Start Turn
   boolean gameOver = false;
   String turn = "Blanc";
   String winner = "";
  
   Random generator = new Random();
   
   //Start Game
   while(!gameOver)
   {
     
    System.out.println("\n"+CurrentBoard);
    CurrentBoard.getChildrenPositions().clear();
    
    if((CurrentBoard.numberOfPieces("Blanc") == 1) &&
     (CurrentBoard.numberOfPieces("Noire") == 1))
    {
     System.out.println("\nC'est un tirage au sort!");
     winner = "aucun";
     break;
    }
    
    System.out.println("\nC'est " + turn + "tour");
    
    //Computer Game
    if(numOfPlayers == 0)
    {
     if(turn.equals(CPU1.getColor()))
     {
      CurrentBoard = CPU1.computeMove(CurrentBoard, generator.nextInt());
      if(CurrentBoard == null)
      {
       System.out.println("...CPU1 se déplace pas.");
       gameOver = true;
       winner = KonoConstants.oppColor(CPU1.getColor());
      }
     }
     else
     {
      CurrentBoard = CPU2.computeMove(CurrentBoard, generator.nextInt());
      if(CurrentBoard == null)
      {
       System.out.println("...CPU2 se déplace pas.");
       gameOver = true;
       winner = KonoConstants.oppColor(CPU2.getColor());
      }
     }
    }
    
    //1 Player Game
    if(numOfPlayers > 0) 
    {
     boolean humanPlayer = false;
     if(numOfPlayers == 2)
     {
      humanPlayer = true;
      userColor = turn;
     }
     if((numOfPlayers == 1) && turn.equals(userColor))
      humanPlayer = true;
     
     if(humanPlayer)
     {
      boolean validMove = false;
     
      //Move array is a special data structure
      //specifying a move:
      //  moveArray[0] = Initial Horizontal Position
      //  moveArray[1] = Initial Vertical Position
      //  moveArray[2] = Final Horizontal Position
      //  moveArray[3] = Final Vertical Position
      int[] moveArray = new int[4];
     
      //Validate Move
      while(!validMove)
      {
       CurrentBoard.generateChildrenPositions(userColor);
      
       //User can't move, game is over.
       if(CurrentBoard.getChildrenPositions().size() == 0)
       {
        gameOver = true;
        winner = KonoConstants.oppColor(userColor);
        System.out.println("...vous n'avez pas de tours");
        break;
       }
      
       System.out.println("S'il vous plaît, entrez votre déplacement:");
       System.out.println("<Init Hori Pos> <Init Vert Pos> <Final Hori Pos> <Final Vert Pos>");
      
       String userMove = userInput.readLine();
       StringTokenizer userMoveTok = new StringTokenizer(userMove, " ");
       //Check if a valid move has been made
       if(userMoveTok.countTokens() != 4)
       {
        System.out.println("\nDésolé, vous n'avez pas donne 4 numéros valables");
       }
       else
       {
        //Parse Move
        String SinitHoriPos = userMoveTok.nextToken();
        String SinitVertPos = userMoveTok.nextToken();
        String SfinalHoriPos = userMoveTok.nextToken();
        String SfinalVertPos = userMoveTok.nextToken();
       
        try
        {
         moveArray[0] = Integer.parseInt(SinitHoriPos);
         moveArray[1] = Integer.parseInt(SinitVertPos);
         moveArray[2] = Integer.parseInt(SfinalHoriPos);
         moveArray[3] = Integer.parseInt(SfinalVertPos);
        
         int moveType = CurrentBoard.validMove(moveArray[0], moveArray[1], moveArray[2], moveArray[3], userColor);
         if(moveType == 1)
         {
          validMove = true;
          //Once move is validated, move there
          CurrentBoard.moveGamePiece(moveArray[0], moveArray[1], moveArray[2], moveArray[3], userColor, false);
         }
         else if(moveType == 2)
         {
          validMove = true;
          //Once move is validated, move there
          CurrentBoard.moveGamePiece(moveArray[0], moveArray[1], moveArray[2], moveArray[3], userColor, true);
         
         }
         else
          System.out.println("\nDéplacement non valide");
        }
        catch(NumberFormatException ex)
        {
         System.out.println("\nDésolé, vous n'avez pas donne 4 numéros");
        }
       }
      }
     }
    
     //Computer's Turn
     else
     {
      System.out.println("\nL'ordinateur est pensé ...");
      CurrentBoard = CPU1.computeMove(CurrentBoard, generator.nextInt());
      if(CurrentBoard == null)
      {
       System.out.println("...l'ordinateur n'a pas de mouvements.");
       gameOver = true;
       winner = "Blanc";
      }
     }
    }
    turn = KonoConstants.oppColor(turn);
   }
   
   System.out.println("\nLe gagnant est " + winner + "!\n");
  }
 }
 
 /*************************************************************************************/
 /*                    */
 /* ComputerPlayer class               */
 /*                    */
 /*************************************************************************************/
 class ComputerPlayer
 {
  private String color;
  private int difficultySetting;
  
  //Accessors=======================================================================
  
  public String getColor()
  {
   return this.color;
  }
  
  public int getDifficultySetting()
  {
   return this.difficultySetting;
  }
  
  //Constructor=======================================================================
  public ComputerPlayer(String color, int difficultySetting)
  {
   this.color = color;
   this.difficultySetting = difficultySetting;
  }
  
  //Compute Move===================================================================
  //Calls MINIMAX
  public Position computeMove(Position p, int randomNumber)
  {
   Vector randomSelectionOfEqualMax = new Vector();
   int[] moveArray = new int[4];
   
   p.generateChildrenPositions(color);
   
   int maxValue = -999999;
   Position bestMove = null;
   Vector visitedPositions = new Vector();
   //Find best move
   for(int i=0; i<p.getChildrenPositions().size(); i++)
   {
    Position cp = (Position)p.getChildrenPositions().elementAt(i);
    visitedPositions.add(cp);
    int cpValue = cp.getMinimaxValue(this.color, 1, this.difficultySetting, "Min", -999999, 999999);
    
    //New max value
    if(maxValue < cpValue)
    {
     randomSelectionOfEqualMax.clear();
     maxValue = cpValue;
     bestMove = cp;
    }
    if(maxValue == cpValue)
    {
     randomSelectionOfEqualMax.add(cp);
    }
   }
   //Only one best
   if(randomSelectionOfEqualMax.size() == 0)
    return bestMove;
   //Otherwise, select random
   else
   {
    int size = randomSelectionOfEqualMax.size();
    int i = Math.abs(randomNumber%size);
    return (Position)randomSelectionOfEqualMax.elementAt(i);
  
   }
  }
 }
 
 /*************************************************************************************/
 /*                    */
 /* KonoConstants class               */
 /*                    */
 /*************************************************************************************/
 static class KonoConstants 
 {
  //Value Constants
  static final int[][] posValues = { {2, 3, 3, 2},
              {3, 2, 2, 3},
              {3, 2, 2, 3},
              {2, 3, 3, 2}};
  
  public static String oppColor(String color)
  {
   if(color.equals("Blanc"))
    return "Noire";
   if(color.equals("Noire"))
    return "Blanc";
   return "";
  }
  public static String oppMinMax(String minmax)
  {
   if(minmax.equals("Max"))
    return "Min";
   if(minmax.equals("Min"))
    return "Max";
   return "";
  }

 }

 /*************************************************************************************/
 /*                    */
 /* GamePiece class                */
 /*                    */
 /*************************************************************************************/
 /*
  * Board Layout
  * 
  * Position of a game piece is given by two ints
  * 
  * (horizontal, vertical)
  * 
  * Black pieces start on horizontal = 0;
  * White Pieces start on horizontal = 3;
  * 
  *    (0,0)--(0,1)--(0,2)--(0,3)
  *      |      |      |      |
  *      |      |      |      |
  *    (1,0)--(1,1)--(1,2)--(1,3) 
  *      |      |      |      |
  *      |      |      |      |
  *    (2,0)--(2,1)--(2,2)--(2,3)
  *      |      |      |      |
  *      |      |      |      |
  *    (3,0)--(3,1)--(3,2)--(3,3)
  *   
  * Pieces are either white or black
  * 
  */
 class GamePiece 
 {
  //Variables
  private int horiPos;
  private int vertPos;
  private String color;
  
  //Accessors
  public int getHoriPos()
  {
   return this.horiPos;
  }
  
  public int getVertPos()
  {
   return this.vertPos;
  }
  
  public int getPosValue()
  {
   return KonoConstants.posValues[this.getHoriPos()][this.getVertPos()];
  }
  
  public String getColor()
  {
   return this.color;
  }
  
  //Constructors
  public GamePiece()
  {
    horiPos = 0;
    vertPos = 0;
    color ="";
  }
  
  public GamePiece(int horiPos, int vertPos, String color)
  {
   this.horiPos = horiPos;
   this.vertPos = vertPos;
   this.color = color;
  }
  
  //Change pieces position
  public void movePiece(int newHoriPos, int newVertPos)
  {
   this.horiPos = newHoriPos;
   this.vertPos = newVertPos;
  }
  
  
  
 }

 /*************************************************************************************/
 /*                    */
 /* Position class                */
 /*                    */
 /*************************************************************************************/
 /* A Position represents a state in the game.
  * It it comprised of a set of game pieces (that have positions).
  * It can also generate its minimax-child positions, and its
  * minimax value.
  * 
  */
 class Position 
 {
  //2D array to see if a position is occupied
  private boolean[][] spaceOccupied = new boolean[4][4];
  
  //List of Children Positions in the Minimax Tree
  private Vector childrenPositions;
  
  //List of Game Pieces
  private Vector gamePieces;

  //Accessors=====================================================================
  public Vector getChildrenPositions(){ return this.childrenPositions; }
  public Vector getGamePieces(){ return this.gamePieces; }
  
  //Finds a game piece. Returns null, if the game piece doesn't exist.
  public GamePiece findGamePiece(int horiPos, int vertPos, String color)
  {
   for(int i=0; i<this.gamePieces.size();i++)
   {
    GamePiece tempGP = (GamePiece)this.gamePieces.elementAt(i);
    if((tempGP.getHoriPos() == horiPos) &&
     (tempGP.getVertPos() == vertPos) &&
     (tempGP.getColor().equals(color)))
     return tempGP;
   }
   return null;
  }
  
  public int numberOfPieces(String color)
  {
   int numberOfPieces=0;
   for(int i=0; i<this.gamePieces.size();i++)
   {
    GamePiece tempGP = (GamePiece)this.gamePieces.elementAt(i);
    if(tempGP.getColor().equals(color))
     numberOfPieces++;
   }
   return numberOfPieces;
  }
  
  //Modifiers======================================================================
  //Add a game piece and occupy the space
  public void addGamePiece(GamePiece gamePiece)
  {
   this.gamePieces.add(gamePiece);
   this.occupySpace(gamePiece.getHoriPos(), gamePiece.getVertPos());
  }
  
  //Remove game piece and vacate its space
  public void removeGamePiece(int horiPos, int vertPos, String color)
  {
   GamePiece gp = this.findGamePiece(horiPos, vertPos, color);
   if(gp != null)
   { 
    this.gamePieces.remove(gp);
    this.vacateSpace(horiPos, vertPos);
   }
  }
  
  /*
   * This method moves a game piece.
   * There is no check to see if it is a feasible move.
   */
  public boolean moveGamePiece(int initHoriPos, int initVertPos, int newHoriPos, int newVertPos, String color, boolean take)
  {
   if(this.findGamePiece(initHoriPos, initVertPos, color) != null)
   {
    if(take)
     this.removeGamePiece(newHoriPos,newVertPos, KonoConstants.oppColor(color));
    this.findGamePiece(initHoriPos, initVertPos, color).movePiece(newHoriPos, newVertPos);
    this.occupySpace(newHoriPos, newVertPos);
    this.vacateSpace(initHoriPos, initVertPos);
    
    return true;
   }
   else
    return false;
  }
  
  //Mark a space as occupied
  public void occupySpace(int horizontal, int vertical)
  {
   spaceOccupied[horizontal][vertical] = true;
  }
  
  //Mark a space as vacant
  public void vacateSpace(int horizontal, int vertical)
  {
   spaceOccupied[horizontal][vertical] = false;
  }
  
  //Constructors===================================================================
  //Default Constructor
  public Position()
  {
   gamePieces = new Vector();
   childrenPositions = new Vector();
  }
  
  //Constructor that initializes start position
  public Position(boolean startPosition)
  {
   gamePieces = new Vector();
   childrenPositions = new Vector();
   
   this.addGamePiece(new GamePiece(3,0,"Blanc"));
   this.addGamePiece(new GamePiece(3,1,"Blanc"));
   this.addGamePiece(new GamePiece(3,2,"Blanc"));
   this.addGamePiece(new GamePiece(3,3,"Blanc"));
   
   this.addGamePiece(new GamePiece(0,0,"Noire"));
   this.addGamePiece(new GamePiece(0,1,"Noire"));
   this.addGamePiece(new GamePiece(0,2,"Noire"));
   this.addGamePiece(new GamePiece(0,3,"Noire"));
  }
  
  //Constructor to clone a position
  public Position(Position p)
  {
   gamePieces = new Vector();
   childrenPositions = new Vector();
   
   //copy positions
   for(int i=0; i<p.getGamePieces().size(); i++)
   {
    //Grab game piece from p
    GamePiece tempGPfromP = (GamePiece)p.getGamePieces().elementAt(i);
   
    //copy its position into a new game piece, and add it to this one
    GamePiece gp = new GamePiece(tempGPfromP.getHoriPos(), tempGPfromP.getVertPos(), tempGPfromP.getColor());
    
    //add copied game piece to this board
    this.addGamePiece(gp);
   }
  }
  
  //Move Validators=================================================================
  
  //0 - not a valid move
  //1 - valid single move
  //2 - valid take move
  public int validMove(int currentHoriPos, int currentVertPos, int finalHoriPos, int finalVertPos, String color)
  {
   //Valid input values
   int[] moveArray = new int[4];
   moveArray[0] = currentHoriPos;
   moveArray[1] = currentVertPos;
   moveArray[2] = finalHoriPos;
   moveArray[3] = finalVertPos;
   
   //Check within valid range
   for(int i=0; i<4; i++)
    if((moveArray[i] < 0) || (moveArray[i] > 3))
     return 0;
   
   //Initial coordinates match an actual game piece
   if(this.findGamePiece(currentHoriPos, currentVertPos, color) == null)
    return 0;
   
   //Single move
   int horiMovement = Math.abs(finalHoriPos - currentHoriPos);
   int vertMovement = Math.abs(finalVertPos - currentVertPos);
   int totalMovement = horiMovement + vertMovement;
   
   //If it is a single movement, and that space is not occupied
   if(totalMovement == 1)
   {
    if(!this.spaceOccupied[finalHoriPos][finalVertPos])
     return 1;
    return 0;
   }
   
   //If it is a take move
   else if(totalMovement == 3)
   {
    //Left or right take
    if(vertMovement == 3)
    {
     if(this.canTakeLeft(currentHoriPos, currentVertPos, color))
      return 2;
     if(this.canTakeRight(currentHoriPos, currentVertPos, color))
      return 2;
     return 0;
    }
    //Up or down take
    else
    {
     if(this.canTakeUp(currentHoriPos, currentVertPos, color))
      return 2;
     if(this.canTakeDown(currentHoriPos, currentVertPos, color))
      return 2;
     return 0;
    }
   }
   else
    return 0;
  }
  
  //If a piece can move left
  public boolean canMoveLeft(int currentHoriPos, int currentVertPos)
  {
   if((currentVertPos>0) && (!this.spaceOccupied[currentHoriPos][currentVertPos-1]))
    return true;
   return false;
  }
  
  //If a piece can move right
  public boolean canMoveRight(int currentHoriPos, int currentVertPos)
  {
   if((currentVertPos<3) && (!this.spaceOccupied[currentHoriPos][currentVertPos+1]))
    return true;
   return false;
  }
  
  //If a piece can move up
  public boolean canMoveUp(int currentHoriPos, int currentVertPos)
  {
   if((currentHoriPos>0) && (!this.spaceOccupied[currentHoriPos-1][currentVertPos]))
    return true;
   return false;
  }
  
  //If a piece can move down
  public boolean canMoveDown(int currentHoriPos, int currentVertPos)
  {
   if((currentHoriPos<3) && (!this.spaceOccupied[currentHoriPos+1][currentVertPos]))
    return true;
   return false;
  }
  
  //If a piece can take a piece to the left
  public boolean canTakeLeft(int currentHoriPos, int currentVertPos, String color)
  {
   if( (currentVertPos == 3) &&
    //Piece beside if same color
    (this.findGamePiece(currentHoriPos, 2, color) != null) &&
    //Two spaces over is empty
    (!this.spaceOccupied[currentHoriPos][1]) &&
    //Three spaces over is opposite color
    (this.findGamePiece(currentHoriPos, 0, KonoConstants.oppColor(color)) != null))
    return true;
   return false;
  }
  
  //If a piece can take a piece to the right
  public boolean canTakeRight(int currentHoriPos, int currentVertPos, String color)
  {
   if( (currentVertPos == 0) &&
    //Piece beside if same color
    (this.findGamePiece(currentHoriPos, 1, color) != null) &&
    //Two spaces over is empty
    (!this.spaceOccupied[currentHoriPos][2]) &&
    //Three spaces over is opposite color
    (this.findGamePiece(currentHoriPos, 3, KonoConstants.oppColor(color)) != null))
    return true;
   return false;
  }
  
  //If a piece can take a piece above
  public boolean canTakeUp(int currentHoriPos, int currentVertPos, String color)
  {
   if( (currentHoriPos == 3) &&
    //Piece above if same color
    (this.findGamePiece(2, currentVertPos, color) != null) &&
    //Two spaces above is empty
    (!this.spaceOccupied[1][currentVertPos]) &&
    //Three spaces above is opposite color
    (this.findGamePiece(0, currentVertPos, KonoConstants.oppColor(color)) != null))
    return true;
   return false;
  }
  
  //If a piece can take a piece below
  public boolean canTakeDown(int currentHoriPos, int currentVertPos, String color)
  {
   if( (currentHoriPos == 0) &&
    //Piece below if same color
    (this.findGamePiece(1, currentVertPos, color) != null) &&
    //Two spaces below is empty
    (!this.spaceOccupied[2][currentVertPos]) &&
    //Three spaces below is opposite color
    (this.findGamePiece(3, currentVertPos, KonoConstants.oppColor(color)) != null))
    return true;
   return false;
  }
  
  //If a piece can move at all
  public boolean canMove(int currentHoriPos, int currentVertPos, String color)
  {
   return ( canMoveSingle(currentHoriPos, currentVertPos) ||
     canTake(currentHoriPos, currentVertPos, color));
  }
  
  //If a piece can move a single space
  public boolean canMoveSingle(int currentHoriPos, int currentVertPos)
  {
   return ( canMoveLeft(currentHoriPos, currentVertPos) ||
     canMoveRight(currentHoriPos, currentVertPos) ||
     canMoveUp(currentHoriPos, currentVertPos) ||
     canMoveDown(currentHoriPos, currentVertPos));
  }
 
  //If a piece can take another piece
  public boolean canTake(int currentHoriPos, int currentVertPos, String color)
  {
   return ( canTakeLeft(currentHoriPos, currentVertPos, color) ||
     canTakeRight(currentHoriPos, currentVertPos, color) ||
     canTakeUp(currentHoriPos, currentVertPos, color) ||
     canTakeDown(currentHoriPos, currentVertPos, color));
  }
  
  
  //Other Operators==============================================================
  
  /*
   * MINIMAX METHOD
   * This recursive method implements the minimax algorithm
   * to a depth cut-off.
   * It also uses Alpha-Beta pruning.
   */
  public int getMinimaxValue(String color, int currentDepth, int cutOffDepth, String minmax, int alpha, int beta)
  {
   int ownColorScore=0;
   int oppositeColorScore=0;
   
   GamePiece tempGP;
   
   //Base Case
   //
   // STATIC EVALUATION Based on
   //     -Number of Pieces
   //     -Number of Pieces that can move
   //     -Number of Pieces that can take other pieces
   //
   // It calculates these factors for your own color, and then
   // for your opponents color, and takes the difference.
   //
   //For safety reasons, add ">" condition
   if(currentDepth >= cutOffDepth)
   {
    for(int i=0; i<gamePieces.size(); i++)
    {
     tempGP = (GamePiece)gamePieces.elementAt(i);
     
     //Calculate Own Score
     if(tempGP.getColor().equals(color))
     {
      //Count pieces
      //ownColorScore+=tempGP.getPosValue();
      
      //Can Move
      if(this.canMove(tempGP.getHoriPos(), tempGP.getVertPos(), tempGP.getColor()))
      {
       if(this.canMoveSingle(tempGP.getHoriPos(), tempGP.getVertPos()))
        ownColorScore += tempGP.getPosValue();
       if(this.canTake(tempGP.getHoriPos(), tempGP.getVertPos(), tempGP.getColor()))
        ownColorScore += tempGP.getPosValue();
      }
      //Can't move piece
      else
       ownColorScore -= tempGP.getPosValue();
     }
     
     //Calculate opposite color score
     else
     {
      //Count pieces
      //oppositeColorScore+=tempGP.getPosValue();
      
      //Can Move
      if(this.canMove(tempGP.getHoriPos(), tempGP.getVertPos(), tempGP.getColor()))
      {
       if(this.canMoveSingle(tempGP.getHoriPos(), tempGP.getVertPos()))
        oppositeColorScore += tempGP.getPosValue();
       if(this.canTake(tempGP.getHoriPos(), tempGP.getVertPos(), tempGP.getColor()))
        oppositeColorScore += tempGP.getPosValue();
      }
      //Can't move piece
      else
       oppositeColorScore -= tempGP.getPosValue();
     }
    }
    
    //RETURN DIFFERENCE
    return (ownColorScore - oppositeColorScore);
   }
   
   //Recursive Case
   //
   // MINIMAX TREE GENERATOR
   //
   //
   else
   {
    //GENERATE MAX (OWN COLOR) MOVES AND FIND THE BIGGEST MINMAX VALUE
    //Max turn
    if(minmax.equals("Max"))
    {
     //Generate Children Positions of Minimax Tree
     this.generateChildrenPositions(color);
     
     //Can't Move
     if(this.getChildrenPositions().size() == 0)
      return -8888;
     
     //Evaulate Children Positions
     //int maxValue = -8888; /original without Alpha-beta
     for(int i=0; i<this.getChildrenPositions().size(); i++)
     {
      Position cp = (Position)this.getChildrenPositions().elementAt(i);
      int cpValue = 
       cp.getMinimaxValue(color, currentDepth+1, cutOffDepth, KonoConstants.oppMinMax(minmax), alpha, beta);
      
      //if(cpValue > maxValue) /original without Alpha-beta
      // maxValue = cpValue;  /original without Alpha-beta
      if(cpValue > alpha)
       alpha = cpValue;
      if(alpha > beta)
       break;
     }
     //return maxValue; /original without Alpha-beta
     return alpha;
    }
    
    //GENERATE OPPONENTS (OPP COLOR) MOVES AND FIND THE SMALLEST MINMAX VALUE
    //Min Turn
    if(minmax.equals("Min"))
    {
     //Generate children of Minimax Tree
     this.generateChildrenPositions(KonoConstants.oppColor(color));
     
     //Min can't move
     if(this.getChildrenPositions().size() == 0)
      return 8888;
     
     //Evaluate Children Positions
     //int minValue = 8888; /original without Alpha-beta
     for(int i=0; i<this.getChildrenPositions().size(); i++)
     {
      Position cp = (Position)this.getChildrenPositions().elementAt(i);
      int cpValue = 
       cp.getMinimaxValue(color, currentDepth+1, cutOffDepth, KonoConstants.oppMinMax(minmax), alpha, beta);
      
      //if(cpValue < minValue) /original without Alpha-beta
      // minValue = cpValue; /original without Alpha-beta
      if(cpValue < beta)
       beta = cpValue;
      if(alpha > beta)
       break;
       
     }
     //return minValue; /original without Alpha-beta
     return beta;
    } 
    return 0;
   }
  }

  
  
  /*
   * This method check to see if 2 positions are equal
   * based on the Game pieces.
   */
  public boolean equals(Position p)
  {
   //Different number of game pieces
   if(this.getGamePieces().size() != p.getGamePieces().size())
    return false;
   
   for(int i=0; i<this.gamePieces.size(); i++)
   {
    GamePiece gp = (GamePiece)this.gamePieces.elementAt(i);
    if( (p.findGamePiece(gp.getHoriPos(), gp.getVertPos(), gp.getColor())) == null)
     return false;
   }
   return true;
  }
  
  /*
   * This method generates all the child Positions for possible moves.
   * It considers the 4 possible single-space moves
   * and the 4 possible captures.
   */
  public void generateChildrenPositions(String color)
  {
   this.childrenPositions.clear();
   GamePiece tempGP;
   
   //for each piece, generate all possible moves
   for(int i=0; i<gamePieces.size(); i++)
   {
    //Which player are we generating moves for?
    tempGP = (GamePiece)gamePieces.elementAt(i);
    if(tempGP.getColor().equals(color))
    {
     //examine position
     int horiPos = tempGP.getHoriPos();
     int vertPos = tempGP.getVertPos();
     //possible new positions
     
     /////////////////////SINGLE SPACE MOVES////////////////////////////////////////////////
     //move left
     if(this.canMoveLeft(horiPos, vertPos))
     {
      //create new position
      Position childPositionLeft = new Position(this);
      //Move appropriate piece
      childPositionLeft.moveGamePiece(horiPos, vertPos, horiPos, vertPos-1, color, false);
      //Add childPosition to the list
      this.childrenPositions.add(childPositionLeft);
     }
     //move right
     if(this.canMoveRight(horiPos, vertPos))
     {
      //create new position
      Position childPositionRight = new Position(this);
      //Move appropriate piece
      childPositionRight.moveGamePiece(horiPos, vertPos, horiPos, vertPos+1, color, false);
      //Add childPosition to the list
      this.childrenPositions.add(childPositionRight);
     }
     //move up
     if(this.canMoveUp(horiPos, vertPos))
     {
      //create new position
      Position childPositionUp = new Position(this);    
      //Move appropriate piece
      childPositionUp.moveGamePiece(horiPos, vertPos, horiPos-1, vertPos, color, false);   
      //Add childPosition to the list
      this.childrenPositions.add(childPositionUp); 
     }
     
     //move down
     if(this.canMoveDown(horiPos, vertPos))
     {
      //create new position
      Position childPositionDown = new Position(this);    
      //Move appropriate piece
      childPositionDown.moveGamePiece(horiPos, vertPos, horiPos+1, vertPos, color, false);      
      //Add childPosition to the list
      this.childrenPositions.add(childPositionDown);
     }
     /////////////////////END SINGLE SPACE MOVES////////////////////////////////////////////////
     
     //////////////////////TAKE COLOR MOVE/////////////////////////////////////////////////////
     //take opponent by moving left
     if(this.canTakeLeft(horiPos, vertPos, color))
     {
      //create new position
      Position childPositionTakeLeft = new Position(this);
      //Move appropriate piece
      childPositionTakeLeft.moveGamePiece(horiPos, vertPos, horiPos, 0, color, true);
      //Add childPosition to the list
      this.childrenPositions.add(childPositionTakeLeft);
     }
     //take opponent by moving right
     if(this.canTakeRight(horiPos, vertPos, color))
     {
      //create new position
      Position childPositionTakeRight = new Position(this);
      //Move appropriate piece
      childPositionTakeRight.moveGamePiece(horiPos, vertPos, horiPos, 3, color, true);
      //Add childPosition to the list
      this.childrenPositions.add(childPositionTakeRight);   
     }
     //take opponent by moving up
     if(this.canTakeUp(horiPos, vertPos, color))
     {
      //create new position
      Position childPositionTakeUp = new Position(this);
      //Move appropriate piece
      childPositionTakeUp.moveGamePiece(horiPos, vertPos, 0, vertPos, color, true);
      //Add childPosition to the list
      this.childrenPositions.add(childPositionTakeUp);   
     }
     //take opponent by moving down
     if(this.canTakeDown(horiPos, vertPos, color))
     {     
      //create new position
      Position childPositionTakeDown = new Position(this);
      //Move appropriate piece
      childPositionTakeDown.moveGamePiece(horiPos, vertPos, 3, vertPos, color, true);
      //Add childPosition to the list
      this.childrenPositions.add(childPositionTakeDown);   
     }
    }
   }
  }
  
 
  /*
   * Method checks if this position is in a list
   * of other positions. It is based on Position of pieces.
   * Used for "Visited before nodes"
   */
  public boolean inList(Vector positions)
  {
   boolean inList = false;
   for(int i=0; i<positions.size(); i++)
   {
    Position p = (Position)positions.elementAt(i);
    if(this.equals(p))
     inList = true;
   }
   return inList;
  }
  
  /*
   * This method outputs the board
   */
  public String toString()
  {
   String[][] markers = { {"-", "-", "-", "-"},
     {"-", "-", "-", "-"},
     {"-", "-", "-", "-"},
     {"-", "-", "-", "-"}};
   
   for(int i=0; i<this.gamePieces.size();i++)
   {
    GamePiece gp = (GamePiece)this.gamePieces.elementAt(i);
    if(gp.getColor().equals("Blanc"))
     markers[gp.getHoriPos()][gp.getVertPos()] = "B";
    if(gp.getColor().equals("Noire"))
     markers[gp.getHoriPos()][gp.getVertPos()] = "N";
   }
   
   String output = "";
   for(int i=0; i<4; i++)
   {
    for(int j=0; j<4; j++)
    {
     output += markers[i][j];
     if(j!=3)
      output += "--";
    }
    if(i!=3)
     output += "\n|  |  |  |\n|  |  |  |\n";
   }
   
   return output;
   
  }
 }

 /*************************************************************************************/
 /*                    */
 /* Utility: KeyboardReader class             */
 /* http://www4.comp.polyu.edu.hk/~csgngai/courses/COMP201B/asgns/asgn1.html   */
 /*************************************************************************************/
 class KeyboardReader 
 { 
  private BufferedReader reader;
     KeyboardReader(InputStream inStream) 
  {  
       this.reader = new BufferedReader(new InputStreamReader(inStream));     
     }
     String readLine() 
     { // instance method 
       String inputLine = "";
       try 
   {
        inputLine = reader.readLine(); 
   } 
       catch (IOException e) 
   {
    System.out.println(e); 
    System.exit(1); 
   } 
       return inputLine; 
     }
     int readInt()
     {
       String inputString = readLine(); 
       int n = Integer.parseInt(inputString); 
       return n; 
     }
     double readDouble() 
     { 
       String inputString = readLine(); 
       double x = Double.parseDouble(inputString); 
       return x; 
     } 
    
 }

}