|
- 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 */
- /** @} */
- }
|