Labyrinth/src/host/labyrinth/MinMaxPlayer.java

/**
 * @file MinMaxPlayer.java
 *
 * @author
 *    Anastasia Foti AEM:8959
 *    <anastaskf@ece.auth.gr>
 *
 * @author
 *    Christos Choutouridis AEM:8997
 *    <cchoutou@ece.auth.gr>
 */

package host.labyrinth;

/**
 * @brief
 *    This class represents the game's minimax player.
 */
class MinMaxPlayer extends Player {

   /** @name Constructors */
   /** @{ */

   /**
    * Create a new player and put him at the row-column coordinates 
    * @param name       The name of the player
    * @param champion   Flag to indicate if a player is a `champion`
    * @param board      Reference to the board of the game
    * @param row        The row coordinate of initial player position
    * @param column     The column coordinate of initial player's position
    */
   public MinMaxPlayer(String name, boolean champion, Board board, int row, int column) throws Exception {
      super(name, champion, board, row, column);
   }

   /**
    * Create a new player and put him at the row-column coordinates 
    * @param name       The name of the player
    * @param champion   Flag to indicate if a player is a `champion`
    * @param board      Reference to the board of the game
    * @param tileId     The tileId coordinate of player's initial position
    */
   public MinMaxPlayer(String name, boolean champion, Board board, int tileId) throws Exception {
      super(name, champion, board, tileId);
   }
   /** @} */
   /** @name Board's main application interface */
   /** @{ */
   
   /**
    * Utility to get the distance of a possible supply in some direction
    * @param currentPos    The current position of the player
    * @param direction     The direction to check
    * @param board         Reference to the Board object to use
    *
    * @return           The distance or Const.noView
    */
   int supplyInDirection(int currentPos, int direction, Board board) {
      Position pos = new Position(Position.toRow(currentPos), Position.toCol(currentPos));

      for (int i=0 ; i<=Const.viewDistance ; ++i) {
         if (board.hasSupply(pos.getId()))
            return i;
         if (board.isWalkable(pos.getId(), direction))
            pos = new Position(pos.getRow(), pos.getCol(), direction);
         else
            break;
      } 
      return Const.noView;
   }

   /**
    * Utility to get the distance of a possible opponent in some direction
    * @param currentPos    The current position of the player
    * @param direction     The direction to check
    * @param board         Reference to the Board object to use
    *
    * @return           The distance or Const.noView
    */
   int opponetInDirection(int currentPos, int direction, Board board) {
      Position pos = new Position(Position.toRow(currentPos), Position.toCol(currentPos));
      int[] opp = board.getOpponentMove(playerId);

      for (int i=0 ; i<=Const.viewDistance ; ++i) {
         if (opp[MOVE_TILE_ID] == pos.getId())
            return i;
         if (board.isWalkable(pos.getId(), direction))
            pos = new Position(pos.getRow(), pos.getCol(), direction);
         else
            break;
      }
      return Const.noView;
   }

   /**
    * This is the main move evaluation function.
    *
    * @param currentPos    The current position of the player (before the move to evaluate)
    * @param direction     The direction (a.k.a. the move) to evaluate
    * @param board         Reference to the Board object to use
    * @return              A signed real number. The higher the output, the higher the evaluation.
    */
   double evaluate (int currentPos, int direction, Board board) {
      Position next   = new Position (Position.toRow(currentPos), Position.toCol(currentPos), direction);

      int preOpDist   = opponetInDirection (currentPos, direction, board);
      int preSupDist  = supplyInDirection(currentPos, direction, board);
      int postOpDist  = opponetInDirection (next.getId(), direction, board);
      int postSupDist = supplyInDirection(next.getId(), direction, board);

      return ((preSupDist != Const.noView) ? Const.preMoveFactor *(1.0/(preSupDist+1) * Const.supplyFactor) : 0)
           - ((preOpDist != Const.noView)  ? Const.preMoveFactor *(1.0/(preOpDist+1)  * Const.opponentFactor) : 0) 
           + ((postSupDist != Const.noView)? Const.postMoveFactor*(1.0/(preSupDist+1) * Const.supplyFactor) : 0)
           - ((postOpDist != Const.noView) ? Const.postMoveFactor*(1.0/(preOpDist+1)  * Const.opponentFactor) : 0);
   }

   /**
    * Executes the minimax algorithm and return a reference to selected move
    * @param node    The root node to start
    * @return        Reference to the selected move
    */
   Node chooseMinMaxMove(Node node) {
      node.setNodeEvaluation(maxValue(node));
      return node.getPath();
   }

   /**
    * Selects the best possible move to return
    * @param   currentPos  Player's current position to the board
    * @return  The move array
    *
    * @note
    *    This function always return a new move.
    */
   int[] getNextMove(int currentPos) {
      Node root  = new Node (board);
      int [] opp = board.getOpponentMove(playerId);

      createMySubtree(currentPos, opp[MOVE_TILE_ID], root, root.getNodeDepth()+1);

      return chooseMinMaxMove(root).getNodeMove();
   }

   /**
    * MinMaxPlayer's move.
    *
    * A player of this kind cheats. He does not throw a dice to get a direction. In contrary he
    * calculates his next move very carefully.
    * If the player is a champion then he also picks up a possible supply from the tile.
    *
    * @param id   The id of the starting tile.
    * @return     An array containing player's final position and possible supply of that position.
    *             The array format is:
    * <ul>
    * <li> int[0]: The tileId of the final player's position.
    * <li> int[1]: The row of the final player's position.
    * <li> int[2]: The column of the final player's position.
    * <li> int[3]: The dice/direction of the move.
    * </ul>
    */
   @Override
   int[] move(int id) {
      // Initialize return array with the current data
      int[] ret = getNextMove(id);
      y = Position.toRow(ret[MOVE_TILE_ID]);
      x = Position.toCol(ret[MOVE_TILE_ID]);

      int supplyFlag =0, moveFlag =1;
      // In case of a champion player, try also to pick a supply
      if (champion && (board.tryPickSupply(ret[MOVE_TILE_ID]) != Const.noSupply)) {
         ++score;                               // keep score
         ++supplyFlag;
      }
      ++dirCounter[ret[MOVE_DICE]];             // update direction counters
      board.updateMove(ret, playerId);

      // Update supply and opponent distance
      int smin =Const.noView, omin =Const.noView;
      for (int d = DirRange.Begin ; d<DirRange.End ; d += DirRange.Step) {
         int s = supplyInDirection (ret[MOVE_TILE_ID], d, board);
         int o = opponetInDirection(ret[MOVE_TILE_ID], d, board);
         if (s < smin)  smin = s;
         if (o < omin)  omin = o;
      }
      // update path
      Integer[] p = {
            ret[MOVE_TILE_ID], ret[MOVE_DICE], moveFlag, supplyFlag,
            dirCounter[Direction.UP], dirCounter[Direction.RIGHT], dirCounter[Direction.DOWN], dirCounter[Direction.LEFT],
            smin, omin
      };
      path.add(p);
      return ret;
   }

   /**
    * Prints round information for the player
    */
   void statistics() {
      if (!path.isEmpty()) {
         Integer[] last = path.get(path.size()-1);
         String who = String.format("%12s", name);
         System.out.print(who + ": score[" + score + "]" + ", dice =" + last[1] + ", tileId =" + last[0] + " (" + Position.toRow(last[0]) + ", " + Position.toCol(last[0]) + ")");
         if (last[2] == 0)
            System.out.println(" *Can not move.");
         else if (last[3] != 0)
            System.out.println(" *Found a supply.");
         else
            System.out.println("");
         // extra prints for minimax player
         if (last[8] != Const.noView) System.out.println("              supply   =" + last[8]);
         else                         System.out.println("              supply   = blind");
         if (last[9] != Const.noView) System.out.println("              opponent =" + last[9]);
         else                         System.out.println("              opponent = blind");
      }
   }
   
   /**
    * Prints final statistics for the player
    */
   void final_statistics () {
      String who = String.format("%12s", name);
      System.out.println();
      System.out.println(who + ": score[" + score + "]");
      System.out.println("    Moves up: " + dirCounter[Direction.UP]);
      System.out.println(" Moves right: " + dirCounter[Direction.RIGHT]);
      System.out.println("  Moves down: " + dirCounter[Direction.DOWN]);
      System.out.println("  Moves left: " + dirCounter[Direction.LEFT]);
   }

   /** @} */

   /** @name Minimax algorithm related part */
   /** @{ */

   /**
    * Get the previous direction of the player
    * @param   parent   Reference to previous nNode
    * @return  The previous direction if exist, else return Direction.NONE
    */
   private int prevDirection(Node parent) {
      if (parent != null && parent.getParent() != null)
         return parent.getParent().getNodeMove()[MOVE_DICE];
      return Direction.NONE;
   }

   /**
    * A simulated move in a copy of the bard.
    *
    * @param board         The board on witch we simulate the move
    * @param currentPos    The current position of the player to the @c board
    * @param dir           The direction of the move
    * @param champion      Flag to indicate if the player is champion or not
    * @return              The move array
    */
   private int[] dryMove (Board board, int currentPos, int dir, boolean champion) {
      int[] ret = new int[MOVE_DATA_SIZE];
      Position p = new Position(Position.toRow(currentPos), Position.toCol(currentPos), dir);
      ret[MOVE_TILE_ID] = p.getId();
      ret[MOVE_ROW]     = p.getRow();
      ret[MOVE_COLUMN]  = p.getCol();
      ret[MOVE_DICE]    = dir; 

      board.updateMove(ret, (champion) ? playerId : board.getOpponentId(playerId));
      return ret;
   }

   /**
    * One of the 2 recursive functions for creating the minimax tree. This one 
    * creates children for the MinMax player.
    *
    * @param parent        The parent Node
    * @param depth         The current depth for the children
    * @param currentPos    The tile of MinMax player
    * @param oppCurrentPos The tile of the opponent
    *
    * @note
    *    Even though unnecessary we calculate the evaluation for every node and not only for the leafs.
    *    This follows the exercise instructions. We could also rely on lazy evaluation of "evaluation()"
    *    and use AB pruning but the depth of the tree is not worth the try.
    */
   private void createMySubtree (int currentPos, int oppCurrentPos, Node parent, int depth) {
      ShuffledRange dirs = new ShuffledRange(DirRange.Begin, DirRange.End, DirRange.Step);
      int [] nodeMove;
      
      for (int dir = dirs.get() ; dir != Const.EOR ; dir = dirs.get()) {
         if ((dir != Direction.opposite(prevDirection(parent)))
          && parent.getNodeBoard().isWalkable(currentPos, dir)) {
            Board nodeBoard = new Board (parent.getNodeBoard());     // clone board
            double eval = evaluate (currentPos, dir, nodeBoard);     // evaluate the move
            nodeMove = dryMove (nodeBoard, currentPos, dir, true);   // simulate the move
            // make child Node
            Node child = new Node (parent, depth, nodeMove, nodeBoard, eval);
            parent.addChild(child);                                  // add child to tree
            createOppSubtree (nodeMove[MOVE_TILE_ID], oppCurrentPos, child, depth+1);
         }
      }
   }

   /**
    * One of the 2 recursive functions for creating the minimax tree. This one 
    * creates children for the opponent player.
    *
    * @param parent        The parent Node
    * @param depth         The current depth for the children
    * @param currentPos    The tile of MinMax player
    * @param oppCurrentPos The tile of the opponent
    *
    * @note
    *    Even though unnecessary we calculate the evaluation for every node and not only for the leafs.
    *    This follows the exercise instructions. We could also rely on lazy evaluation of "evaluation()"
    *    and use AB pruning but the depth of the tree is not worth the try.
    */
   private void createOppSubtree (int currentPos, int oppCurrentPos, Node parent, int depth) {
      ShuffledRange dirs = new ShuffledRange(DirRange.Begin, DirRange.End, DirRange.Step);
      int [] nodeMove;
      
      for (int dir = dirs.get() ; dir != Const.EOR ; dir = dirs.get()) {
         if ((dir != Direction.opposite(prevDirection(parent)))
               && parent.getNodeBoard().isWalkable(oppCurrentPos, dir)) {
            Board nodeBoard = new Board(parent.getNodeBoard());         // clone board
            nodeMove = dryMove (nodeBoard, oppCurrentPos, dir, false);  // simulate move
            Position init = new Position(                               // evaluate from "My" perspective the move
                  parent.getNodeMove()[MOVE_ROW],
                  parent.getNodeMove()[MOVE_COLUMN],
                  Direction.opposite(parent.getNodeMove()[MOVE_DICE])
            );
            double eval = evaluate(init.getId(), parent.getNodeMove()[MOVE_DICE], nodeBoard);
            // make child Node
            Node child = new Node (parent, depth, nodeMove, nodeBoard, eval);
            parent.addChild(child);                                     // add child to tree
            if (depth < Const.minimaxTreeDepth) {
               createMySubtree (currentPos, nodeMove[MOVE_TILE_ID], child, depth+1);
            }
         }
      }
   }
   
   /**
    * The Minimax recursive function for the maximizing part.
    *
    * @param node The current Node
    * @return     The selected Node
    */
   private double maxValue (Node node) {
      if (node.getChildren() == null) {
         //node.setPath(node);
         return node.getNodeEvaluation();
      }
      else {
         double M = Double.NEGATIVE_INFINITY;
         for (Node n : node.getChildren()) {
            n.setNodeEvaluation(minValue(n));   // evaluation propagation
            if (M < n.getNodeEvaluation()) {
               M = n.getNodeEvaluation();
               node.setPath(n);                 // path propagation
            }
         }
         return M;
      }
   }
   
   /**
    * The Minimax recursive function for the minimizing part.
    *
    * @param node The current Node
    * @return     The selected Node
    */
   private double minValue (Node node) {
      if (node.getChildren() == null) {
         //node.setPath(node);
         return node.getNodeEvaluation();
      }
      else {
         double m = Double.POSITIVE_INFINITY;
         for (Node n : node.getChildren()) {
            n.setNodeEvaluation(maxValue(n));   // evaluation propagation
            if (m > n.getNodeEvaluation()) {
               m = n.getNodeEvaluation();
               node.setPath(n);                 // path propagation
            }
         }
         return m;
      }
   }

   /** @} */
   
}