////////////////////////////////////////////////////////////////////////
//
// Intro to AI Assignment #2
//
// Package:       IntroAI.Assign2.Support
// File:          Instructor.java
//
// Author:        Jeff Stephenson
// Date:          October 18, 1997
// JDK Version:   JDK 1.1.1
// Machine Type:  PC/Win95
// Comments:      Class file was supporting code for Assignment #2
//                Includes TA solution to Assignment
////////////////////////////////////////////////////////////////////////


package IntroAI.Assign2.Support;

import IntroAI.Assign2.Support.BoardValues;
import IntroAI.Assign2.Support.Board;
import IntroAI.Assign2.Support.Verdict;
import IntroAI.Assign2.Support.Hash_element;
import IntroAI.Assign2.Support.Hash_table;

/**
 * Class Instructor contains the TA's methods for playing
 * Connect-N.  These methods include:
 *
 * instructor_find_winner_exhaustive
 * instructor_find_winner_hashing
 * instructor_find_winner_heuristic 
 *
 */


public final class Instructor implements BoardValues
{

   static int ROWS;
   static int COLS;
   static int NEEDED_TO_WIN;
   private static Hash_table game_table;
   
   
   //Constructor  
   public Instructor(int rows, int cols, int needed_to_win)
   {
      this.ROWS = rows;
      this.COLS = cols;
      this.NEEDED_TO_WIN = needed_to_win; 
      game_table = new Hash_table(HASHSIZE);  
   }

   //Calls the appropriate method based upon the whichmethod parameter
   public static Verdict instructor_find_winner(Board b, char whose_turn, int whichmethod)
   {
      b.clearExpansions();
      if (whichmethod == EXHAUSTIVE)
      {
         return instructor_find_winner_exhaustive(b, whose_turn);
      }
      else
      {
         if (whichmethod == HASHING)
         {
            return instructor_find_winner_hashing(b, whose_turn);
         }
         else
         {
            return instructor_find_winner_heuristic(b, whose_turn);   
         }
           
      } 
   
   
   }
   
   //Exhaustively expands the game tree and picks the best move for the 
   //current player.  A win for the current player, is better than a tie.
   //A tie is better than a loss.
   private static Verdict instructor_find_winner_exhaustive(Board b, char whose_turn)
   {
      Verdict temp[] = new Verdict[COLS];
      
      char status;
      char nextp;
      
      if (whose_turn==XPLAYER)
      {
         nextp = OPLAYER;
      }
      else
      {
         nextp = XPLAYER;
      }
      status = b.query_status();
      if (status != NON_TERMINAL)
      {
         //if terminal return
         return new Verdict(DEFAULT, status);
      }
  
      int col;
      for (col=0; col < COLS; col++)
      {
         if (!b.is_full(col))
         {
            try
            { 
               b.make_move (col, whose_turn);   
               temp[col]= instructor_find_winner_exhaustive(b, nextp);
               b.unmake_move (col);
            }
            catch (InvalidBoardException e)
            {
               System.out.println("Error: " + e);
               System.exit(1); 
            }
         }
         else
         {
            temp[col] = new Verdict(EMPTY);
         }
      }
      
      /* The following code picks the best move for player out of the array of outcomes 
         for possible moves. */
      int x;
      int availcol = -1;
      Verdict tieflag = new Verdict(EMPTY);
      for (x=0; x<COLS; x++)
      {
         if (temp[x].get_result() == whose_turn)
         {
            return new Verdict (x, whose_turn);
         }
         if (temp[x].get_result() == TIE)
         {
            tieflag.set_result(TIE);
            tieflag.set_move(x);
         }
         if (temp[x].get_result() != EMPTY)
         {
            availcol=x;
         }
      }
      
      if (tieflag.get_result() != EMPTY)
      {
         return tieflag;
      }
      else 
      {
         return new Verdict(availcol, nextp);
      }
   
   }
   
   
   //This method is very similar to find winner_exhaustive, except that 
   //it uses a hash_table to save its work.  The method always checks the 
   //hash_table for the result of a board before recursively expanding.  
   //If it is forced to recursively expand, it saves the result of the
   //expansion in the hash_table for future use.  
   private static Verdict instructor_find_winner_hashing(Board b, char whose_turn)
   {
      Verdict temp[] = new Verdict[COLS];
      Verdict holder;
      Verdict new_verdict;
      
      char status;
      char nextp;
      
      if (whose_turn==XPLAYER)
      {
         nextp = OPLAYER;
      }
      else
      {
         nextp = XPLAYER;
      }
      status = b.query_status();
      if (status != NON_TERMINAL)
      {
         return new Verdict(DEFAULT, status);
      }
  
      int col;
      for (col=0; col < COLS; col++)
      {
         if (!b.is_full(col))
         {
            try
            { 
               b.make_move (col, whose_turn);
               holder = game_table.lookup(b);   //hash_table lookup
               if (holder != null)
               {
                  temp[col] = holder;
               }   
               else 
               {
                  temp[col]= instructor_find_winner_hashing(b, nextp);
               }
               b.unmake_move (col);
            }
            catch (InvalidBoardException e)
            {
               System.out.println("Error: " + e);
               System.exit(1); 
            }
         }
         else
         {
            temp[col] = new Verdict(EMPTY);
         }
      }
      
      /* The following code picks the best move for player out of the array of outcomes for possible moves. */
      int x;
      int availcol = -1;
      Verdict tieflag = new Verdict(EMPTY);
      for (x=0; x<COLS; x++)
      {
         if (temp[x].get_result() == whose_turn)
         {
            new_verdict = new Verdict (x, whose_turn);
            game_table.insert(b, new_verdict);
            return new_verdict;
         }
         if (temp[x].get_result() == TIE)
         {
            tieflag.set_result(TIE);
            tieflag.set_move(x);
         }
         if (temp[x].get_result() != EMPTY)
         {
            availcol=x;
         }
      }
      
      if (tieflag.get_result() != EMPTY)
      {
         game_table.insert(b, tieflag);
         return tieflag;
      }
      else 
      {
         new_verdict = new Verdict(availcol, nextp);
         game_table.insert(b, new_verdict);     //hash_table insert
         return new_verdict;
      }
   }
 
 
   //This function calls heuristic helper and makes a decision based
   //on the values returned.  
   private static Verdict instructor_find_winner_heuristic(Board b, char whose_turn)
   {
      char nextp;
      long temp[] = new long[COLS];
      
      if (whose_turn==XPLAYER)
      {
         nextp = OPLAYER;
      }
      else
      {  
         nextp = XPLAYER;
      }
  
      int col;
      char status;
      
      for (col=0; col < COLS; col++)
      {
         if (!b.is_full(col))
         {
            try
            { 
               b.make_move (col, whose_turn);
          
               status = b.query_status();
               
               temp[col]= Heuristic_helper(b, nextp, 1);
                  
               b.unmake_move (col);
               
               if (status == XPLAYER)
               {
                  temp[col] = 9999;
               }
               if (status == OPLAYER)
               {
                  temp[col] = -9999;
               } 
            }
            catch (InvalidBoardException e)
            {
               System.out.println("Error: " + e);
               System.exit(1); 
            }
         }
         else
         {
            temp[col] = DEFAULT;
         }
      }
         
      int bestmove = DEFAULT;
      long bestforplayer = DEFAULT;
         
      for (col=0; col<COLS; col++)
      {
         if (bestforplayer == DEFAULT)
         {
            bestforplayer = temp[col];
            bestmove = col;
         }
         if (temp[col]>bestforplayer && whose_turn==XPLAYER && temp[col]!=DEFAULT)
         {
            bestforplayer = temp[col];
            bestmove = col;
         }
            
         if (temp[col]<bestforplayer && whose_turn==OPLAYER && temp[col]!=DEFAULT)
         {
            bestforplayer = temp[col];
            bestmove = col;
         }         
      }
         
         
      if (bestforplayer >= 0)
      {
         return new Verdict(bestmove, XPLAYER);
      }
      else
      {
         return new Verdict(bestmove, OPLAYER);
      }         

   }
   
   //This function implements a mini-max algorithm that propogates the 
   //result of the evaluation function on the leaf nodes up to the top
   //of the 3-ply tree.  The depth parameter stops the method from expanding
   //past MAX_HEURISTIC_DEPTH.
    
   private static long Heuristic_helper(Board b, char whose_turn, int depth)
   {
   
      if (depth == MAX_HEURISTIC_DEPTH)
      {
         return Evaluation_function(b, whose_turn);
      }
      else
      {
         char nextp;
         char status;
         long temp[] = new long[COLS];
      
         if (whose_turn==XPLAYER)
         {
            nextp = OPLAYER;
         }
         else
         {  
            nextp = XPLAYER;
         }
  
         int col;
         for (col=0; col < COLS; col++)
         {
            if (!b.is_full(col))
            {
               try
               { 
                  b.make_move (col, whose_turn);
          
                  status = b.query_status();
                  temp[col]= Heuristic_helper(b, nextp, depth+1);
                  
                  b.unmake_move (col);
                  
                  if (status == XPLAYER)
                  {
                     temp[col] = 9999;
                  }
                  if (status == OPLAYER)
                  {  
                     temp[col] = -9999;
                  }     

               }
               catch (InvalidBoardException e)
               {
                  System.out.println("Error: " + e);
                  System.exit(1); 
               }
            }
            else
            {
               temp[col] = DEFAULT;
            }
         }
         
         long bestforplayer=DEFAULT;
         
         for (col=0; col<COLS; col++)
         {
            if (bestforplayer == DEFAULT)
            {
               bestforplayer = temp[col];
            }
            if (temp[col]>bestforplayer && whose_turn==XPLAYER && temp[col]!=DEFAULT)
            {
               bestforplayer = temp[col];
            }
            
            if (temp[col]<bestforplayer && whose_turn==OPLAYER && temp[col]!=DEFAULT)
            {
               bestforplayer = temp[col];
            }         
         }
         
         
         return bestforplayer;
      
      }
   
   }
   
   //An evaluation function that produces a long data type for a 
   //given board.  The return value is based upon the number of
   //marks in consecutive positions.
   //
   private static long Evaluation_function (Board b, char whose_turn)
   {
      long heuristic_value = 0;
      int temp;
      int i;
      int x;
      int y;
      
      for (i=0; i<2; i++)
      {
         if (i==1)
         {
            if (whose_turn == XPLAYER)
            {
               whose_turn = OPLAYER;
            }
            else
            {
               whose_turn = XPLAYER;
            }   
         }
         
         for (x=0; x<COLS; x++) /*vertical*/
         {
            temp = b.vector_streak(whose_turn, x, 0, 0, 1);
            if (whose_turn == OPLAYER)
            {
               heuristic_value = heuristic_value - (temp*temp*temp);
            }
            else
            {
               heuristic_value = heuristic_value + (temp*temp*temp);
            }
         }
      
         for (y=0; y<ROWS; y++) /*horizontal*/
         {
            temp = b.vector_streak(whose_turn, 0, y, 1, 0);
            if (whose_turn == OPLAYER)
            {
               heuristic_value = heuristic_value - (temp*temp*temp);
            }
            else
            {
               heuristic_value = heuristic_value + (temp*temp*temp);
            }
         }
      
         for (x=1; x<COLS-1; x++) /*diagonals that intersect row 0 */
         {
            temp = b.vector_streak(whose_turn, x, 0, 1, 1);
            if (whose_turn == OPLAYER)
            {
               heuristic_value = heuristic_value - (temp*temp*temp);
            }
            else
            {
               heuristic_value = heuristic_value + (temp*temp*temp);
            }
            
            temp = b.vector_streak(whose_turn, x, 0, -1, 1);
            if (whose_turn == OPLAYER)
            {
               heuristic_value = heuristic_value - (temp*temp*temp);
            }
            else
            {
               heuristic_value = heuristic_value + (temp*temp*temp);
            }  
         }
      
         for (y=0; y<ROWS; y++) /* '/' diagonals that intersect column 0, or */
         {                      /* '\' diagonals that intersect column COLS-1*/ 
            temp = b.vector_streak(whose_turn, 0, y, 1, 1);
            if (whose_turn == OPLAYER)
            {
               heuristic_value = heuristic_value - (temp*temp*temp);
            }
            else
            {
               heuristic_value = heuristic_value + (temp*temp*temp);
            }
            
            temp = b.vector_streak(whose_turn, COLS-1, y, -1, 1);
            if (whose_turn == OPLAYER)
            {
               heuristic_value = heuristic_value - (temp*temp*temp);
            }
            else
            {
               heuristic_value = heuristic_value + (temp*temp*temp);
            }
         }
        
      }
      return heuristic_value;
   }

}