/*
  XBubble - opponent.c

  Copyright (C) 2002  Ivan Djelic <ivan@savannah.gnu.org>
  
  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.
  
  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.
  
  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "utils.h"
#include "cell.h"
#include "bubble.h"
#include "board.h"
#include "setting.h"
#include "opponent.h"
#include <assert.h> /* XXX */

#ifdef DEBUG_OPPONENT
#define DEBUG 1
#else
#define DEBUG 0
#endif

#define MAX_DEPTH 3

struct _Opponent {
  int launch_count;
  int period;
  int angle;
  int max_depth;
  int line[MAX_DEPTH];
  int color[MAX_DEPTH];
  int target[NB_ANGLES];
  int perimeter_cache[NB_CELLS];
  int eval_cache[NB_CELLS][NB_COLORS];
  int best_target;
  int angle_bias_period;
  double *vx;
  double *vy;
  Set explosive_bubbles;
  Set removed_bubbles[MAX_DEPTH];
  Vector floating_cells;
  Vector path[NB_ANGLES];
  Vector targets[MAX_DEPTH];
  Vector perimeters[NB_CELLS];
  struct _Bubble bubble[MAX_DEPTH];
  CellArray array;
  Board board;
};

Opponent new_opponent( Board board, int level ) {
  int i;

  CellArray ca;
  Opponent op;
  op = (Opponent) xmalloc( sizeof( struct _Opponent ));
  op->board = board;
  get_board_info( op->board,
		  &op->vx,
		  &op->vy,
		  &op->color[0],
		  &op->color[1],
		  &op->launch_count,
		  &op->period);

  ca = get_board_array(board);
  op->array = cell_array_new( ca->moving_ceiling );
  op->explosive_bubbles = set_new( NB_CELLS );
  op->floating_cells = vector_new( NB_CELLS );
  for ( i = 0; i < MAX_DEPTH; i++ ) {
    op->removed_bubbles[i] = set_new( NB_CELLS );
    op->targets[i] = vector_new( NB_CELLS );
  }
  for ( i = 0; i < NB_CELLS; i++ )
    op->perimeters[i] = vector_new(16);
  for ( i = 0; i < NB_ANGLES; i++ ) {
    op->path[i] = vector_new( NB_CELLS );
  }
  op->max_depth = 2;

  switch( level ) {
  case VERY_EASY: 
    op->angle_bias_period = 2;
    break;
  case EASY:
    op->angle_bias_period = 4;
    break;
  case NORMAL:
    op->angle_bias_period = 8;
    break;
  case HARD:
    op->angle_bias_period = 0;
    break;
  case VERY_HARD:
    op->max_depth = 3;
    op->angle_bias_period = 0;
    break;
  }
  return op;
}

void delete_opponent( Opponent op ) {
  int i;
  cell_array_free( op->array );
  set_free( op->explosive_bubbles );
  vector_free( op->floating_cells );
  for ( i = 0; i < NB_CELLS; i++ )
    vector_free( op->perimeters[i] );
  for ( i = 0; i < NB_ANGLES; i++ )
    vector_free( op->path[i] );
  for ( i = 0; i < MAX_DEPTH; i++ ) {
    set_free( op->removed_bubbles[i] );
    vector_free( op->targets[i] );
  }
  free( op );
}

/*
  array_overflow() returns 1 if the last played move is losing.
  We don't use cell_array_overflow() because we may simulate board
  lowering by moving the canon up.
*/

static int array_overflow( Opponent op, int depth ) {
  int i, first, last_row;
  last_row = ROWS - 1;
  if ( op->launch_count + depth > op->period )
    last_row--;
  first = COLS*last_row;
  for ( i = first; i < NB_CELLS; i++ )
    if ( op->array->cell[i] != EMPTY_CELL )
      return 1;
  return 0;
}

static void play_move( Opponent op, int depth, int target ) {
  int count, i, cell;
  Bubble bubble, bubble2;

  set_empty( op->removed_bubbles[depth] );

  /* stick bubble in target cell */
  bubble = &op->bubble[depth];
  bubble->state = STUCK;
  bubble->cell = target;
  bubble->color = op->color[depth];
  op->array->cell[target] = bubble;  
  count = count_explosive_bubbles( op->array, target, 
				   op->explosive_bubbles, NULL );
  if ( count >= 3 ) {
    /* remove explosive bubbles */
    for ( i = 0; i < op->explosive_bubbles->size; i++ ) {
      bubble2 = op->explosive_bubbles->element[i];
      op->array->cell[bubble2->cell] = EMPTY_CELL;
      set_add( op->removed_bubbles[depth], bubble2 );
    }
    /* remove dropped bubbles */
    count_floating_bubbles( op->array, op->floating_cells );
    for ( i = 0; i < op->floating_cells->size; i++ ) {
      cell = op->floating_cells->element[i];
      bubble2 = op->array->cell[cell];
      op->array->cell[cell] = EMPTY_CELL;
      set_add( op->removed_bubbles[depth], bubble2 );
    }
  }
  set_empty( op->explosive_bubbles );
  op->line[depth] = target;

  if ( DEBUG ) {
    fprintf( stderr, "\n" );
    for ( i = 0; i < depth; i++ )
      fprintf( stderr, "          " );
    switch( bubble->color ) {
    case 0: fprintf( stderr, "    red" ); break;
    case 1: fprintf( stderr, "   blue" ); break;
    case 2: fprintf( stderr, "  green" ); break;
    case 3: fprintf( stderr, " yellow" ); break;
    case 4: fprintf( stderr, "  black" ); break;
    case 5: fprintf( stderr, "  brown" ); break;
    case 6: fprintf( stderr, "  white" ); break;
    case 7: fprintf( stderr, "magenta" ); break;
    }
    fprintf( stderr, "@%2d%c", target, ( count >= 3 )? 'E' : ' ' );
  }
}

static void unplay_move( Opponent op, int depth ) {
  int i;
  Bubble bubble;
  /* restore removed bubbles */
  for ( i = 0; i < op->removed_bubbles[depth]->size; i++ ) {
    bubble = op->removed_bubbles[depth]->element[i];
    op->array->cell[bubble->cell] = bubble;
  }
  /* empty cell */
  op->array->cell[op->line[depth]] = EMPTY_CELL;
}

/* 
   compute_targets() computes the target cells associated with each 
   firing angle and builds op->targets[depth].
*/

static void compute_targets( Opponent op, int depth ) {
  //  double y, canon_y;
  int i, angle, target, cell, move, target_invalid;
  int cell_cache[NB_CELLS]; 
  
  /* flush cache (used to avoid studying two angles with the same target) */
  memset( cell_cache, 0, NB_CELLS*sizeof(int));
  vector_empty( op->targets[depth] );

  if ( depth == 0 )
    /* full target cell computation for each angle */
    for ( i = 0; i < NB_ANGLES; i++ ) {
      angle = (i/2)*(1-2*(i%2)) + CANON_ANGLE_MAX;
      target = target_cell( op->array, angle, NULL, op->path[angle] );
      /* store target cell */
      op->target[angle] = target;
      /* make targets vector for searching */
      if ( ! cell_cache[target] ) {
	cell_cache[target] = 1;
	vector_push( op->targets[0], target );
      }
    }

  else /* depth >= 1 */
    /*
      Instead of calling target_cell() for every angle (expensive), we try
      to reuse the targets computed at depth 0. In order to do so, we must
      ensure that such a target is still valid at the current searching depth;
      we use the following test:
      
      Let t be the target computed at depth 0;
      
      for each previous played move ( = cell c ), starting from depth 0:
      
      if one of the following conditions is true:
      * board has been lowered
      * cell c is now empty (i.e. some explosion occurred)
      * c == t or c is on the path reaching t
      then we consider t invalid and call target_cell() for recomputation.
      
    */
    for ( i = 0; i < NB_ANGLES; i++ ) {
      angle = (i/2)*(1-2*(i%2)) + CANON_ANGLE_MAX;
      
      /* depth >= 1 : try to use op->target[] */
      //      canon_y = op->canon_y;
      target = op->target[angle];
      target_invalid = 0;
      
      /* move canon up to fake board going down */
      if ( op->launch_count + depth >= op->period + 1 ) {
	//	canon_y -= ROW_HEIGHT;
	target_invalid = 1;
      }
      if ( ! target_invalid )
	/* check if target recomputation is really needed */
	for ( move = 0; move < depth; move++ ) {
	  cell = op->line[move];
	  if (( op->array->cell[cell] == EMPTY_CELL )||
	      ( target == cell )||
	      ( vector_membership( op->path[angle], cell ))) {
	    target_invalid = 1;
	    break;
	  }
	}
      if ( target_invalid )
	target = target_cell( op->array, angle, NULL, NULL );
      /* make targets vector for searching */
      if ( ! cell_cache[target] ) {
	cell_cache[target] = 1;
	vector_push( op->targets[depth], target );
      }
    }
  /*  
  if ( DEBUG ) {
    fprintf(stderr,"\n");
    for( i = 1; i <= depth; i++ )
      fprintf( stderr, "\t");
    fprintf( stderr, "targets[%d]={ ", depth);
    for( i = 0; i < op->targets[depth]->size; i++ )
      fprintf( stderr, "%d,", op->targets[depth]->element[i]);
    fprintf( stderr, "} ");
  }
  */
}

/*
  add_to_perimeter() is used to add cell neighbors to a perimeter 
  ( a list of cells used in evaluate_target_potential() ).
*/

static void add_to_perimeter( Opponent op, Vector perimeter, int cell ) {
  int neighbor;
  Quadrant q;
  for ( q = 0; q < 6; q++ ) {
    neighbor = neighbor_cell( op->array, cell, q );
    if (( neighbor != OUT_OF_BOUNDS )&&
	( op->array->cell[neighbor] == EMPTY_CELL )&&
	( ! op->perimeter_cache[neighbor] )) {
      vector_push( perimeter, neighbor );
      op->perimeter_cache[neighbor] = 1;
    }
  }
}

/*
  evaluate_target_potential() is used to evaluate the potential benefit
  of putting a bubble of any color in a given target.
  The following algorithm is used:

  FOR each color c:
    eval[c] = eval_min;
    put a bubble of color c in target;
    IF this bubble triggers an explosion:
      FOR each exploding bubble in cell C:
        eval[c] += row(C);
      FOR each dropped bubble in cell C:
        eval[c] += row(C) + 1;
    ELSE
      IF this bubble has a neighbor of the same color:
        eval[c] += 2;

    IF board overflow
      eval[c] = 1;

  Additionally, the function can build of list of cells called "perimeter":
  this is actually a list of the empty neighbors of all cells that would be 
  "touched" (i.e. exploded/dropped/neighbor) if a bubble was put in target.
  This is later used in eval_tree() to avoid redundant calls to 
  evaluate_target_potential().
*/

static void evaluate_target_potential( Opponent op,
				       int target,
				       int *eval,
				       int search_depth,
				       Vector perimeter ) {
  int cell, count, color, i;
  struct _Bubble temp_bubble;
  Bubble bubble;
  if ( perimeter != NULL )
    vector_empty(perimeter);

  /* stick temporary bubble in target cell */
  temp_bubble.state = STUCK;
  temp_bubble.cell = target;
  op->array->cell[target] = &temp_bubble;
  for ( color = 0; color < NB_COLORS; color++ ) {
    eval[color] = 1000;
    temp_bubble.color = color;
    count = count_explosive_bubbles( op->array, target, 
				     op->explosive_bubbles, NULL );
    if ( count >= 3 ) { /* explosion */
      count_floating_bubbles( op->array, op->floating_cells );
      /* sum explosive bubbles */
      for ( i = 0; i < op->explosive_bubbles->size; i++ ) {
	bubble = op->explosive_bubbles->element[i];
	eval[color] += bubble->cell/COLS;
	if ( perimeter != NULL )
	  add_to_perimeter( op, perimeter, bubble->cell );
      }
      /* sum dropped bubbles */
      for ( i = 0; i < op->floating_cells->size; i++ ) {
	cell = op->floating_cells->element[i];
	eval[color] += cell/COLS + 1; /* dropping bonus */
	if ( perimeter != NULL )
	  add_to_perimeter( op, perimeter, cell);
      }
    }
    else { /* no explosion */
      if ( perimeter != NULL )
	for ( i = 0; i < op->explosive_bubbles->size; i++ ) {
	  bubble = op->explosive_bubbles->element[i];
	  add_to_perimeter( op, perimeter, bubble->cell );
	}
      if ( count == 2 )
	eval[color] += 2;
    }
    set_empty( op->explosive_bubbles );    
    /* check if move is losing */
    if ( array_overflow( op, search_depth ))
      eval[color] = 1;
  }
  /* flush cache only if we used it */
  if (( perimeter != NULL )&&( perimeter->size ))
    memset( op->perimeter_cache, 0, NB_CELLS*sizeof(int));
  /* remove temporary bubble */
  op->array->cell[target] = EMPTY_CELL;
}

static int eval_tree( Opponent op, int depth ) {
  int i, j;
  int target;
  int cell;
  int eval;
  int first;
  int sum;
  int compute_sum;
  int best_eval = 0;
  int need_target_evaluation;
  int target_eval[NB_COLORS];
  int leaf_best_eval[NB_COLORS];
  Bubble bubble;

  if ( array_overflow( op, depth ) ) {
    /* losing later is better than losing now */
    if ( DEBUG )
      fprintf( stderr, "* [%d]", depth+1 );
    return depth + 1;
  }
  if ( depth < op->max_depth-1 ) {
    /* compute list of available targets */
    compute_targets( op, depth );
    
    if ( depth == 0 ) {
      if ( DEBUG )
	fprintf( stderr, "\nfilling eval_cache[] and perimeters[]");
      /* fill eval_cache[] and perimeters[] */
      for ( i = 0; i < op->targets[0]->size; i++ ) {
	target = op->targets[0]->element[i];
	evaluate_target_potential( op,
				   target,
				   op->eval_cache[target],
				   0,
				   op->perimeters[target] );
      }
    }
    
    /* scan targets */
    for ( i = 0; i < op->targets[depth]->size; i++ ) {
      target = op->targets[depth]->element[i];
      play_move( op, depth, target );
      eval = eval_tree( op, depth+1 );
      /* XXX */
      assert( eval >= 1 );
      unplay_move( op, depth );
      if ( best_eval < eval ) {
	best_eval = eval;
	if ( depth == 0 )
	  op->best_target = target;
      }
    }
    return best_eval;
  }
  else { 
    /* 
       leaf node evaluation: the idea is to compute all available targets 
       and evaluate each of them for all possible colors. 
    */
    if ( DEBUG )
      fprintf( stderr, " (" );
    memset( leaf_best_eval, 0, sizeof(int)*NB_COLORS );
    /* compute list of available targets */
    compute_targets( op, depth );
    for ( i = 0; i < op->targets[depth]->size; i++ ) {
      target = op->targets[depth]->element[i];
      /* 
	 we don't really want to call evaluate_target_potential() because
	 it's expensive, so let's try to use cached info:
      */
      need_target_evaluation = 0;
      /* of course if this is a new target we need to evaluate it */
      if ( ! vector_membership( op->targets[0], target ))
	need_target_evaluation = 1;
      else
	/* 
	   We use perimeters to ensure evaluation is still valid:
	   for a given target t, we use its cached evaluation if none of
	   the followings conditions holds:
	   - an explosion occured since depth 0.
	   - a bubble has been played in target's perimeter since depth 0.
	   
	*/
	for ( j = 0; j < depth; j++ ) {
	  cell = op->line[j];
	  if (( op->array->cell[cell] != &op->bubble[j] )||
	      ( vector_membership( op->perimeters[target], cell ))) {
	    need_target_evaluation = 1;
	    break;
	  }
	}
      
      if ( need_target_evaluation ) {
	/* miss :-( */
	if ( DEBUG )
	  fprintf( stderr, "." );
	evaluate_target_potential( op, target, target_eval, depth, NULL);
      }
      else { 
	/* hit !! */
	if ( DEBUG )
	  fprintf( stderr, "!" );
	for ( j = 0; j < NB_COLORS; j++ )
	  target_eval[j] = op->eval_cache[target][j];
      }
      /* compute max evaluations */
      for ( j = 0; j < NB_COLORS; j++ )
	if ( leaf_best_eval[j] < target_eval[j] )
	  leaf_best_eval[j] = target_eval[j];
    }
    if ( DEBUG ) {
      fprintf( stderr, ")" );
      for ( j = 0; j < 16 - op->targets[depth]->size; j++ )
	fprintf( stderr, " " );
    }

    /* last step of our evaluation: take into account bubble positions. */
    compute_sum = 0;
    for ( j = 0; j < NB_COLORS; j++ )
      if ( leaf_best_eval[j] > 1 ) {
	compute_sum = 1;
	break;
      }
      else
	leaf_best_eval[j] = 1 + depth;
    if ( compute_sum ) {
      sum = NB_CELLS*ROWS;
      /* compute global sum on bubbles */
      first = first_cell(op->array);
      for ( i = first; i < NB_CELLS - COLS; i++ ) {
	bubble = op->array->cell[i];
	if ( bubble != EMPTY_CELL )
	  /* higher cell is better */
	  sum -= bubble->cell/COLS;
      }
      for ( j = 0; j < NB_COLORS; j++ )
	if ( leaf_best_eval[j] > 1 + depth )
	  leaf_best_eval[j] += sum;
    }
    /* 
       OK, now we have an evaluation of our position for every color;
       We compute an average:
    */
    for ( i = 0; i < NB_COLORS; i++ )
      best_eval += leaf_best_eval[i];
    best_eval = best_eval/NB_COLORS;

    if ( DEBUG )
      fprintf( stderr, "[%04d]", best_eval );
    return best_eval;
  }
}

int find_best_angle( Opponent op , int *best_eval ) {
  int i, angle;
  static int counter = 0;
  CellArray ca; 
  /* make a clean copy of board array */
  ca = get_board_array(op->board);
  memcpy( op->array->cell, ca->cell, sizeof(void *)*NB_CELLS);
  memset( op->array->tagged, 0, sizeof(int)*NB_CELLS );
  memset( op->perimeter_cache, 0, NB_CELLS*sizeof(int));
  op->array->first_row = ca->first_row;
  op->array->parity = ca->parity;
  get_board_info( op->board,
		  &op->vx,
		  &op->vy,
		  &op->color[0],
		  &op->color[1],
		  &op->launch_count,
		  &op->period);
  /* depth first search */
  *best_eval = eval_tree( op, 0 );
  /* retrieve best angle */
  for ( i = 0; i < NB_ANGLES; i++ ) {
    angle = (i/2)*(1-2*(i%2)) + CANON_ANGLE_MAX;
    if ( op->target[angle] == op->best_target ) {
      angle -= CANON_ANGLE_MAX;
      if ( op->angle_bias_period ) {
	counter++;
	/* add a random factor sometimes to simulate bad aiming */
	if ( counter % op->angle_bias_period == 0 )
	  angle += rnd(8) - 4;
      }
      if ( DEBUG )
	fprintf( stderr, "\n*** best = %d (%d) ***", op->best_target, 
		 *best_eval);
      return angle;
    }
  }
  /* should not be reached */
  fprintf( stderr, "\nOUCH : best_eval=%d best_target=%d\n", *best_eval,
	   op->best_target );
  return 0;
}