Snake/src/net/hoo2/auth/dsproject/snake/MinMaxPlayer.java

package net.hoo2.auth.dsproject.snake;

import java.util.*;

/**
 * @class MinMaxPlayer
 * @brief Represent a MinMax Player in the Game
 * 
 * The players are playing in a round-robin sequence and we keep track
 * for each one of them their playing order, score and place on the board.
 * This kind of player, is a cheater. He can control the dice. Not fair dude.
 * 
 * @author Christos Choutouridis AEM:8997
 * @email  cchoutou@ece.auth.gr
 */
public class MinMaxPlayer
             extends Player {
   static final int MINIMAX_TREE_DEPTH    = 2;  /**< The maximum depth of the minimax tree */
   /** @name Constructors */
   /** @{ */
   /** Default doing nothing constructor */
   public MinMaxPlayer() {
      super ();
      path = new ArrayList<Integer[]>();
   }
   /**
    * @brief   The main constructor
    * 
    * This creates a player for the game
    * @param playerId   The player's to create
    * @param name       The name of the player
    * @param board      Reference to the board the player will play on.
    */
   MinMaxPlayer (int playerId, String name) {
      super (playerId, name);
      path = new ArrayList<Integer[]>();
   }
   /* @} */

   /** @name Get/Set interface */
   /** @{ */
   ArrayList<Integer[]> getPath() { return path; }
   void setPath (ArrayList<Integer[]> path) {
      this.path = path;
   }
   /** @} */
   
   /**
    * Override dice functionality for the player
    * @return  As this is called from the game only to select playing order 
    *          we cheat and return 1
    */
   @Override
   int dice () {
      return 1;
   }
   
   /**
    * Override get the next move after the user's move
    * @param board   The board in which we play on
    * @param tile    The initial tile
    * @return  The the move as an array
    *          See @ref Node.nodeMove
    */
   @Override
   int[] getNextMove (Board board, int tile) {
      int [] ret = new int[4]; 
      Node root = new Node (board);
      
      createMySubtree(root, 1, tile, selectOpponent(board).getTile());
      // Evaluate each possible dice result and find the better one
      Node r = MaxValue (root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY);
      // Do the move and get the move data
      Integer[] move_data = Arrays.stream (move (board, tile, r.getNodeMove()[3], true))
                                  .boxed()
                                  .toArray(Integer[]::new);
      // Store the move data
      path.add(move_data);
      ret[0] = move_data[MOVE_TILE_IDX];
      ret[1] = move_data[MOVE_INITTILE_IDX];
      ret[2] = move_data[MOVE_POINTS_IDX];
      ret[3] = move_data[MOVE_ROLL_IDX];
      return ret;  // return the new tile position
   }

   /**
    * The MinMax statistics version
    * @param verbose    Flag to select the verbosity
    * @param sum        Flag to select if we need to print a summarize of the user history
    */
   @Override
   void statistics (boolean verbose, boolean sum) {
      if (sum) {
         // If we run the summarize
         int nSnakes      =0;
         int nLadders     =0;
         int nRedApples   =0;
         int nBlackApples =0;

         // Calculate frequencies
         for (int i=0 ; i<path.size() ; ++i) {
            nSnakes += path.get(i)[MOVE_SNAKES_IDX];
            nLadders+= path.get(i)[MOVE_LADDERS_IDX];
            nRedApples   += path.get(i)[MOVE_RED_APPLES_IDX];
            nBlackApples += path.get(i)[MOVE_BLACK_APPLES_IDX];
         }
         // Print the results
         System.out.println("");
         System.out.println("*** Statistics for " + name + " ***");
         System.out.println("   Number of Snake bites       : " + nSnakes);
         System.out.println("   Number of Ladders used      : " + nLadders);
         System.out.println("   Number of Red Apples eaten  : " + nRedApples);
         System.out.println("   Number of Black Apples eaten: " + nBlackApples);
         
      }
      else
         // Call the base version
         super.statistics(verbose, sum);
   }

   /** @name Private helper API */
   /** @{ */
   /** 
    * Select the the best Opponent
    * @param   board    Reference to current board
    * @return  Reference to the player who is most far in the board
    */
   private Player selectOpponent (Board board) {
      Player opp = null;
      int max_tile = Integer.MIN_VALUE;
      for (Player p : board.getPlayers()) {
         if (p == this)                // Please do not return me
            continue;
         if (opp == null)  opp = p;    // init variable
         if (p.getTile() > max_tile) { // max filtering
            opp = p;
            max_tile = p.getTile();
         }
      }
      return opp;
   }

   /**
    * 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 tile    the tile of MinMax player
    * @param oppTile the tile of the best opponent
    */
   private void createMySubtree (Node parent, int depth, int tile, int oppTile) {
      int [] moveData;
      int [] nodeMove;
      for (int roll = 1 ; roll <= 6 ; ++roll) {
         Board nodeBoard = new Board (parent.getNodeBoard());  // clone board
         moveData = move (nodeBoard, tile, roll, false);       // simulate move
         nodeMove = new int[4];                                // create nodeMove
         nodeMove[0] = moveData[MOVE_TILE_IDX];
         nodeMove[1] = moveData[MOVE_INITTILE_IDX];
         nodeMove[2] = moveData[MOVE_POINTS_IDX];
         nodeMove[3] = moveData[MOVE_ROLL_IDX];
         // make child Node
         Node child = new Node (parent, depth, nodeMove, nodeBoard);
         parent.addChild(child);                               // add child to tree
         createOppSubtree (child, depth+1, nodeMove[0], oppTile);
      }
   }

   /**
    * 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 tile    the tile of MinMax player
    * @param oppTile the tile of the best opponent
    */
   private void createOppSubtree (Node parent, int depth, int tile, int oppTile) {
      int [] moveData;
      int [] nodeMove;
      for (int roll =1 ; roll <= 6 ; ++roll) {
         Board nodeBoard = new Board(parent.getNodeBoard());   // clone board
         moveData = move (nodeBoard, oppTile, roll, false);    // simulate move
         nodeMove = new int[4];
         nodeMove[0] = moveData[MOVE_TILE_IDX];
         nodeMove[1] = moveData[MOVE_INITTILE_IDX];
         nodeMove[2] = moveData[MOVE_POINTS_IDX];
         nodeMove[3] = moveData[MOVE_ROLL_IDX];
         Node child = new Node (parent, depth, nodeMove, nodeBoard);   // make child Node
         parent.addChild(child);                               // add child to tree
         if (depth >= MINIMAX_TREE_DEPTH) {
            child.setNodeEvaluation(
                  evaluate(parent.getNodeMove()[0],                           // our tile
                           parent.getNodeMove()[0] - parent.getNodeMove()[1], // our steps
                           parent.getNodeMove()[2],                           // our points
                           nodeMove[0])                                       // opponent tile
            );
         }
         else {
            createMySubtree (child, depth+1, tile, nodeMove[0]);
         }
      }
   }
   /**
    * The main evaluation function
    * @param tile    The current tile of the player
    * @param steps   The total steps of the move
    * @param points  The total points of the move
    * @param oppTile The tile of the best opponent
    * @return        The evaluation of the roll
    */
   private double evaluate (int tile, int steps, int points, int oppTile) {
      if (tile > oppTile)
         return 0.65*steps + 0.35*points;
      else
         return 0.8*steps + 0.2*points - (oppTile - tile)*0.5;
   }

   /**
    * The Minimax recursive function for the maximizing part
    * @param s    The current Node
    * @param a    The alpha for pruning
    * @param b    The beta for pruning
    * @return     The selected Node
    */
   private Node MaxValue (Node s, double a, double b) {
      if (s.getChildren() == null)
         return s;
      else {
         Node r = null;
         double vv, v = Double.NEGATIVE_INFINITY;
         for (Node c : s.getChildren()) {
            if (r == null) r = c;
            vv = MinValue (c, a, b).getNodeEvaluation();
            //v = max (v, vv);
            if (vv > v) {
               v = vv;
               r = c;
            }
            if (vv >= b)
               return c;   // prune
            a = max (a, vv);
         }
         return r;
      }
   }
   
   /**
    * The Minimax recursive function for the minimizing part
    * @param s    The current Node
    * @param a    The alpha for pruning
    * @param b    The beta for pruning
    * @return     The selected Node
    */
   private Node MinValue (Node s, double a, double b) {
      if (s.getChildren() == null)
         return s;
      else {
         Node r = null;
         double vv, v = Double.POSITIVE_INFINITY;
         for (Node c : s.getChildren()) {
            if (r == null) r = c;
            vv = MaxValue (c, a, b).getNodeEvaluation();
            //v = min (v, vv);
            if (vv < v) {
               v = vv;
               r = c;
            }
            if (vv <= a)
               return c;   // prune
            b = min (b, vv);
         }
         return r;
      }
   }

   /** @return the minimum of x and y */
   private static double min (double x, double y) {
      return (x < y) ? x : y;
   }
   /** return the maximum of x and y */
   private static double max (double x, double y) {
      return (x > y) ? x : y;
   }
   /** @} */
   
   /** @name Data members package access only */
   /** @{ */
   private ArrayList<Integer[]> path;  /**< Players history as required */
   /** @} */
}