//////////////////////////////////////////////////////////////////////////////
//
// File: tplayer.cc
//
// Purpose: Routines for managing the TradPlayer class.
//
// Authors:
//   txe  Travis Emmitt
//
// Modifications:
//   14-APR-1998  txe  Initial Version
//   15-APR-1998  txe  Got logic working - finally!
//   16-APR-1998  txe  Added random selection of equal-quality moves
//   20-APR-1998  txe  Purifying...
//   22-APR-1998  txe  Adjusted ability to randomness ratio
//   23-APR-1998  txe  Using static debug, changed constructor
//   24-APR-1998  txe  Moved ability from Player to here
//   01-MAY-1998  txe  Added hypo, EvaluateMove(x,y,depth) [for look-ahead]
//   02-MAY-1998  txe  Debugging...
//   04-MAY-1998  txe  Added comments
//
//////////////////////////////////////////////////////////////////////////////

#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include "common.h"
#include "board.h"
#include "player.h"
#include "tplayer.h"

//////////////////////////////////////////////////////////////////////////////

TradPlayer::TradPlayer (char *name, int color, int ability)
          : Player     (name, color) {

  ASSERT (ability >= IDIOT && ability <= PERFECT);
  this->ability = ability;
  hypo = NULL;
}

/////////////////////////////////////////////////////////////////////

int TradPlayer::EvaluateMove (int x, int y, int depth) {
  ASSERT (hypo->GetColor (x, y) == EMPTY);
  ASSERT (depth > 0);

  int opp_color = 3 - color;       // assume only 1 opponent for now //
  int quality, win = 0, x0, y0, best = DRAW, worst = WIN;

  DEBUG(3) << "\n" << depth << ": evaluating (" << x << "," << y << ")...\n";
  hypo->SetColor (x, y, color);
  hypo->Print (3);

  ////////////////////////////////////////////////////////////////////
  // DEPTH 1: see if this move would let us win or let opponent win //
  ////////////////////////////////////////////////////////////////////

  if (hypo->GetWinner (win_boards)) {
    best = WIN;
  }
  else {

#if NO_LOOK_AHEAD
    hypo->SetColor (x, y, opp_color);
    if (hypo->GetWinner (win_boards)) {
      best = BLOCK;
    } 
#else
    ITERATE (, x0, y0, size_x, size_y) {
      if (hypo->GetColor (x0, y0) == EMPTY) {
	hypo->SetColor (x0, y0, opp_color);
	win = hypo->GetWinner (win_boards);
	hypo->SetColor (x0, y0, EMPTY);
	if (win) {
	  best = LOSE;
	  break;
	}
      }
    }
#endif

  }

  ///////////////////////////////////////////////////////////
  // DEPTH 2+: use look-ahead to evaluate eventual results //
  ///////////////////////////////////////////////////////////

  if (best == DRAW && depth > 1) {
    ITERATE (, x0, y0, size_x, size_y) {
      best = INVALID;

      if (hypo->GetColor (x0, y0) == EMPTY) {
	DEBUG(3) << depth << ": assume opponent moves to ("
		 << x0 << "," << y0 << ")...\n";
	hypo->SetColor (x0, y0, opp_color);
	hypo->Print (3);

	ITERATE (int, x1, y1, size_x, size_y) {
	  if (hypo->GetColor (x1, y1) == EMPTY) {
	    quality = EvaluateMove (x1, y1, depth - 1);
	    best    = MAX (quality, best);
	    if (best == WIN) {
	      break;
	    }
	  }
	}

	hypo->SetColor (x0, y0, EMPTY);

	if ((worst = MIN (worst, best)) == LOSE) {
	  break;
	}
      }
    }
    best = worst;
  }

  /////////////////////////////
  // return eventual results //
  /////////////////////////////

  hypo->SetColor (x, y, EMPTY);

  DEBUG(3) << depth << ": if we go (" << x << "," << y << "), we'll ";

  if (best == LOSE) {
    DEBUG(3) << "LOSE if opponent goes (" << x0 << "," << y0 << ")\n";
  }
  else if (best == WIN) {
    DEBUG(3) << "WIN!\n";
  }
  else {
    DEBUG(3) << "draw\n";
  }

  return best;
}

//////////////////////////////////////////////////////////////////////////////

int TradPlayer::GetEasyMove () {
  int quality, best = INVALID, depth, max_depth;
  int best_x[MAX_X*MAX_Y], best_y[MAX_X*MAX_Y], num_best = 0;

  static char quality_name[][20] = {"INVALID", "LOSE", "DRAW", "BLOCK", "WIN"};

  ///////////////////////////////////////////////////////
  // set up hypothetical board (copy of current board) //
  ///////////////////////////////////////////////////////

  if (hypo != NULL) {
    delete hypo;
  }
  if ((hypo = new Board ("Hypothetical", size_x, size_y)) == NULL) {
    ERR << name << " couldn't create hypo board; out of memory!\n";
    exit (-1);
  }
  hypo->Copy (board);

  ////////////////////////////////////////////////////
  // setup best moves array (will be whittled down) //
  ////////////////////////////////////////////////////

  best     = DRAW;
  num_best = 0;

  ITERATE (int, x, y, size_x, size_y) {
    if (board->GetColor (x, y) == EMPTY) {
      best_x[num_best] = x;
      best_y[num_best] = y;
      num_best++;
    }
  }

  //////////////////////////////////////////////////////////////////
  // Calculate max depth = (moves_left / 2) * (ability / PERFECT) // 
  //////////////////////////////////////////////////////////////////

#ifdef NO_LOOK_AHEAD
  max_depth = (ability > IDIOT ? 1 : 0);
#else
  max_depth = (board->MovesLeft() * ability) / (PERFECT * 2);
#endif

  //////////////////////////////////////////
  // keep looking until we break the DRAW //
  //////////////////////////////////////////

  for (depth = 1; depth <= max_depth; depth++) {
    DEBUG(3) << "\n##################### Depth " << depth
	     << " ######################\n";

    int old_num_best = num_best;
    best = INVALID;
    num_best = 0;

    for (int i = 0; i < old_num_best; i++) {
      quality = EvaluateMove (best_x[i], best_y[i], depth);

      DEBUG(3) << "\nfinal quality (" << best_x[i] << "," << best_y[i]
	       << ") = " << quality_name[quality]
	       << "\n-------------------------------------------------\n";
      
      // Non-PERFECT players can make mistakes (random overestimation) //
      
      if (quality != INVALID && ability < PERFECT) {
	if (random ((ability * ability * 4) + 1) == 0) {
	  DEBUG(1) << "  OOPS! (" << name << " made a random mistake)\n";
	  quality += random (2) + 1;
	}
      }
      
      // If best quality, add to list of possibilities //
      
      if (quality > best) {
	best     = quality;
	num_best = 0;
      }
      if (quality >= best) {
	best_x[num_best] = best_x[i];
	best_y[num_best] = best_y[i];
	num_best++;
      }

      // if not still a draw, we're done //

      if (best == WIN) {
	break;
      }
    }

    // if the best we can do is lose, we're done //

    if (best == LOSE || best == WIN || num_best == 1) {
      break;
    }
  }

 // Randomly pick one of the (evenly weighted) possibilities //

  int i = random (num_best);
  i = MAX (0, MIN (num_best-1, i));
  ASSERT (i >= 0 && i < num_best);
  move_x = best_x[i];
  move_y = best_y[i];

  DEBUG(3) << "\n  Here are our (EasyMove) possibilities:\n";
  for (int j = 0; j < num_best; j++) {
    DEBUG(3) << "    best[" << j << "] = ("
	     << best_x[j] << "," << best_y[j] << ")\n";
  }
  DEBUG(3) << "  Randomly picked best[" << i << "]: ("
	   << move_x << "," << move_y << ")\n";

  return best;
}

//////////////////////////////////////////////////////////////////////////////
// This is only used when we use the "magic formula" instead of look-ahead
//////////////////////////////////////////////////////////////////////////////

int TradPlayer::GetHardMove () {
  int x = move_x, y = move_y, moves_taken = 9 - board->MovesLeft ();

  DEBUG(3) << "\nLooking for hard move, moves_taken = " << moves_taken << "\n";

  int nw = board->GetColor (0, 0);
  int n  = board->GetColor (1, 0);
  int ne = board->GetColor (2, 0);
  int w  = board->GetColor (0, 1);
  int c  = board->GetColor (1, 1);
  int e  = board->GetColor (2, 1);
  int sw = board->GetColor (0, 2);
  int s  = board->GetColor (1, 2);
  int se = board->GetColor (2, 2);

  switch (moves_taken) {

  /// IF WE GO FIRST... /////////////////////////// our first turn //////////

  case 0:
    x = 1;                         // Take the center first, because
    y = 1;                         //  future logic depends upon us
    break;                         //  having it.
    
  ///////////////////////////////////////////////// our second turn /////////

  case 2:
    if (n || s) {                  // If opponent moved to an edge,
      x = random (1) * 2;          //  choose an opposite corner at
      y = (n ? 2 : 0);             //  random.
    }                              //
    else if (w || e) {             //
      x = (w ? 2 : 0);             //
      y = random (1) * 2;          //
    }
    else if (nw || sw) {           // If opponent moved to a corner,
      x = 1 + random (1);          // choose an opposite edge at
      y = (nw ? 3 - x : x - 1);    // random.
    }                              //
    else {                         //
      x = random (1);              //
      y = (ne ? 1 + x : 1 - x);    //
    }                              //
    break;
    
  ///////////////////////////////////////////////// our third turn //////////
    
  case 4:
    if (n) {                       // The only "hard case" with four
      x = random(2) * 2;           //  pieces is the "L".  Randomly
      y = random(2) + (nw || ne);  //  choose any place except for
    } 				   //  the space opposite the end of
    else {                         //  the _ in the L.
      x = random(2) + (ne || se);  //
      y = random(2) * 2;           //
    }                              //
    break;
    
	  
  /// IF OPPONENT WENT FIRST... /////////////////// our first turn //////////
	  
  case 1:
    if (c) {                       // If the center is already taken,
      x = random (2) * 2;          //  select a corner at random.
      y = random (2) * 2;          //
    }
    else {                         // If the center is not taken,
      x = 1;                       //  take it (our future logic
      y = 1;                       //  depends upon it being taken).
    }                              //
    break;
    
  ///////////////////////////////////////////////// our second turn ////////

  case 3:
    x = random (2) * 2;            // Select a corner at random.  We
    y = random (2) * 2;            //  might have to tweak this...
    
    if (c == color) {              // If the center is ours...
      if ((nw && se) || (ne && sw)) {  // If diagonal, choose any edge.
	x = random (3);            //
	y = (x == 1 ? random (2) * 2 : 1);
      }                            //
      else if (nw) {               // Otherwise, if there are any
	if (e && x == 0) {         //  corners taken, the shape will
	  x = 1;                   //  look like some rotation of
	  y = 2;                   //  this (X = us, O = opponent):
	}                          //
	else if (s && y == 0) {    //            O| |*
	  x = 2;                   //            -+-+-
	  y = 1;                   //             |X|O
	}                          //            -+-+-
      }                            //             |*|*
      else if (ne) {               //
	if (w && x == 2) {         // Our good moves are shown as
	  x = 1;                   //  asterisks (*); we need to move
	  y = 2;                   //  to one of these squares.
	}                          //
	else if (s && y == 0) {    // There are eight possible
	  x = 0;                   //  orientations of this shape.
	  y = 1;                   //  I could have simply chosen the
	}                          //  opposite corner each time, but
      }                            //  that would have eliminated any
      else if (sw) {               //  opportunity for randonmess...
	if (e && x == 0) {         //
	  x = 1;                   //
	  y = 0;                   //
	}                          //
	else if (n && y == 2) {    //
	  x = 2;                   //
	  y = 1;                   //
	}                          //
      }                            //
      else if (se) {               //
	if (w && x == 2) {         //
	  x = 1;                   //
	  y = 0;                   //
	}                          //
	else if (n && y == 2) {    //
	  x = 0;                   // (below) If only edges are taken,
	  y = 1;                   //  choose a corner that is not
	}                          //  adjacent to at least one of
      }                            //  the edges...

      else if (n && y == 2 && ((w && x == 2) || (e && x == 0))) {
	y = 0;
      }
      else if (s && y == 0 && ((w && x == 2) || (e && x == 0))) {
	y = 2;
      }
    }
    else {                         // If center is opponent's, then
      y = (nw ? 2 - x : x);        //  the only hard case is a diag
    }                              //  line.  Pick an empty corner.
    break;
  }
  
  move_x = x;
  move_y = y;
  
  return WIN;
}

//////////////////////////////////////////////////////////////////////////////

int TradPlayer::GetMove () {
  ASSERT (board != NULL);

  int x, y, quality = INVALID, moves_left;

  // First, see how many moves are left //

  if ((moves_left = board->MovesLeft()) == 0) {
    DEBUG(2) << name << " sees no moves left, passing\n";
    return PASS;
  }

#ifndef NO_LOOK_AHEAD
  // if board is empty, randomly pick a first move //

  if (moves_left == (size_x * size_y)) {
    DEBUG(3) << name << " has first move, randomly picking...\n";
    move_x = random (size_x);
    move_y = random (size_y);
    return 1;
  }
#endif

  // Then, try to find any easy move (either a WIN or a BLOCK) //
  
  //  if (moves_left < 9 && (quality = GetEasyMove ()) == INVALID) {

  if ((quality = GetEasyMove ()) == INVALID) {
    DEBUG(2) << name << " sees no valid easy moves, passing...\n";
    return PASS;
  }
  
#ifdef NO_LOOK_AHEAD
  // If that doesn't work, try finding a harder move (break the DRAW ties) //
  
  if (quality <= DRAW && GetHardMove () == INVALID) {
    DEBUG(2) << name << " sees no valid hard moves, passing...\n";
    return PASS;
  }
#endif

  return 1;
}

//////////////////////////////////////////////////////////////////////////////