PacMan/src/gr/auth/ee/dsproject/node/Tree.java

/**
 * @file MinMaxTree.java
 * @brief
 *    File containing the Pacman Min-Max Tree class. A collection
 *    of static routines to build a search tree and execute
 *    a alpha-beta pruning algorithm to it
 * 
 * @author  Christos Choutouridis   8997 cchoutou@ece.auth.gr
 * @author  Konstantina Tsechelidou 8445 konstsec@ece.auth.gr
 */
package gr.auth.ee.dsproject.node;


/**
 * @brief
 *    A tree-like data structure containing move nodes to apply the min-max
 *    algorithm.
 * @note
 *    This is NOT a real tree. We do not insert node based on a key etc...
 */
public class Tree
{
   /*
    * ============ Constructor ==============
    */
   /**
    * @brief
    *    The simple constructor. Do nothing (this is a static class)
    */
   public Tree () { }

   /*
    * ========== private helpers  ==============
    */
   /** @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;
   }

   /*
    * ========== Tree-like public methods =============
    */
   /**
    * @brief
    *    Insert a node to a parent directly.
    *    This is NOT a real tree. We do not insert node based on a key
    * @param node    Node to insert
    * @param parent  The parent in witch to insert
    * @return        Reference to inserted node
    *                If insert fail, returns null
    */
   public static Node89978445 grow (Node89978445 node, Node89978445 parent) {
      if (parent.children.add (node)) {
         node.parent = parent;
         node.depth = parent.depth + 1;
         return node;
      }
      else
         return null;
   }

   /**
    * @brief
    *    A recursive implementation of an alpha-beta pruning algorithm.
    *    Alpha–beta pruning is a search algorithm that seeks to decrease
    *    the number of nodes that are evaluated by the minimax algorithm in its search tree.
    *    It stops completely evaluating a move when at least one possibility has
    *    been found that proves the move to be worse than a previously examined move.
    *    Such moves need not be evaluated further.
    * @param node    current node of the tree. In the initial call is the root node
    * @param depth   the maximum depth to investigate
    * @param a       alpha (start -infinity)
    * @param b       beta (start +infinity)
    * @param maxingPlayer  helper variable to switch between min-max behavior 
    * @return
    *    reference to node with the maximum evaluation resulting path.
    */
   public static Node89978445 minmaxAB (Node89978445 node, int depth, double a, double b, boolean maxingPlayer)
   {
      double v, ev;
      Node89978445 vNode = null;

      if ((depth == 0) || (node.children.isEmpty()))  // Escape
         return node;
      
      if (maxingPlayer) {
         // maximizing player part
         v = Integer.MIN_VALUE;  // start small for max algorithm to work
         // recursively call alpha-beta for every child, reducing depth and toggling between min and max 
         for (int i=0 ; i<node.children.size() ; ++i) {
            ev = minmaxAB (node.children.get (i), depth-1, a, b, false).getEvaluation();
            // select the maximum output node
            if (ev > v) {
               v = ev;
               vNode = node.children.get (i);
            }
            a = max (v, a);   // mark alpha
            if (b <= a)       // cut-off alpha
               break;
         }
         return vNode;
      }
      else {
         // minimizing player part
         v = Integer.MAX_VALUE;  // start big for min algorithm to work
         // recursively call alpha-beta for every child, reducing depth and toggling between min and max 
         for (int i=0 ; i<node.children.size() ; ++i) {
            ev = minmaxAB(node.children.get (i), depth-1, a, b, true).getEvaluation();
            if (ev < v) {
               v = ev;
               vNode = node.children.get (i);
            }
            b = min (v, b);   // mark beta
            if (b <= a)       // cut-off beta
               break;
         }
         return vNode;
      }
   }
   
}