/**********************************************************************
 *
 *
 *   FreeDoko a Doppelkopf-Game
 *    
 *   Copyright (C) 2001-2004  by Diether Knof and Borg Enders
 *
 *   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 can find this license in the file 'gpl.txt'.
 *
 *   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
 *
 *  Contact:
 *    Diether Knof dknof@gmx.de
 *    Borg Enders  borg@borgsoft.de
 *
 ********************************************************************/

#include "constants.h"

#include "gametree.h"


#include "trickweighting.h"
#include "VirtualGamesInterface.h"
#include "ai.h"
#include "../../card/trick.h"
#include "../../game/exception.h"
#include "../../game/game_summary.h"
#include "../../ui/ui.h"

static unsigned counter = 0;

// whether to save the runtime
//#define SAVE_RUNTIME

#ifdef RELEASE
#undef SAVE_RUNTIME
#endif

/**
 **
 ** constructor
 **
 ** @param      gametree_interface	the interface
 ** @param      future_limit		the future limit
 ** @param      with_heuristics		whether to use heuristics
 **
 ** @return     -
 **
 ** @version    0.5.4
 **
 ** @author     Diether Knof
 **
 **/
Gametree::Gametree(GametreeInterface const& gametree_interface,
		   unsigned const future_limit,
		   bool const with_heuristics) :
  gametree_interface_(&gametree_interface),
  future_limit_(future_limit),
  end_depth_(0),
  with_heuristics(with_heuristics)
{
  this->end_depth_calculate(future_limit);

  return ;
} // Gametree::Gametree(GametreeInterface const& gametree_interface, unsigned const future_limit)

/**
 **
 ** destructor
 **
 ** @param      -
 **
 ** @return     -
 **
 ** @version    0.5.4
 **
 ** @author     Diether Knof
 **
 **/
Gametree::~Gametree()
{
  return ;
} // Gametree::~Gametree()

/**
 **
 ** -> result
 **
 ** @param      -
 **
 ** @return     the gametree interface
 **
 ** @version    0.5.4
 **
 ** @author     Diether Knof
 **
 **/
GametreeInterface const&
Gametree::gametree_interface() const
{
  return *(this->gametree_interface_);
} // GametreeInterface const& Gametree::gametree_interface() const

/**
 **
 ** -> result
 **
 ** @param      -
 **
 ** @return     the maximal depth to calc into the future (in tricks)
 **
 ** @version    0.5.4
 **
 ** @author     Diether Knof
 **
 **/
unsigned const&
Gametree::end_depth() const
{
  return this->end_depth_;
} // unsign
/**
 **
 ** -> result
 **
 ** @param      -
 **
 ** @return     the future limit
 **
 ** @version    0.6.7
 **
 ** @author     Diether Knof
 **
 **/
unsigned const&
Gametree::future_limit() const
{
  return this->future_limit_;
} // unsigned const& VirtualGames::future_limit() const

/**
 **
 ** Calculates and sets the end depth (how many tricks in the future are
 ** to be calculated).
 **
 ** @param      future_limit	the future limit
 **
 ** @return     the calculated end depth
 **
 ** @version    0.5.4
 **
 ** @author     Diether Knof
 **
 **/
unsigned const&
Gametree::end_depth_calculate(unsigned future_limit)
{
  this->end_depth_ = 0;

  { // count the number of card-combinations for the current trick
    Trick const& current_trick
      = this->gametree_interface().game().trick_current();
    for (unsigned i = current_trick.actcardno();
	 i < this->gametree_interface().game().playerno();
	 i++)
      if (this->gametree_interface().value(Aiconfig::FAIRPLAYHANDS))
	future_limit /= this->gametree_interface().handofplayer(current_trick.player_of_card(i)
							       ).cards_single().size();
      else
	future_limit /= this->gametree_interface().handofplayer(current_trick.player_of_card(i)
							       ).validcards(current_trick).cards_single().size();
  } // count the number of card-combinations for the current trick

  // calculate for all following tricks the number of cards of each player
  while (future_limit > 0) {
    this->end_depth_ += 1;
    if (this->end_depth_
	== this->gametree_interface().game().tricks_remaining_no())
      break;

    for (vector<Player*>::const_iterator
	 player = this->gametree_interface().game().player_begin();
	 player != this->gametree_interface().game().player_end();
	 player++) {
      if (this->gametree_interface().game().trick_current().cardno_of_player(**player)
	  >= this->gametree_interface().game().trick_current().actcardno())
	// the player still has to play a card in the current trick
	future_limit /= (this->gametree_interface().handofplayer(**player
								).cardsnumber()
			 - this->end_depth_);
      else
	// the player has already played a card, so he has one card less 
	// on the hand
	future_limit /= (this->gametree_interface().handofplayer(**player
								).cardsnumber()
			 - (this->end_depth_ - 1));
    } // for (player \in this->gametree_interface.game().player)
  } // while (future_limit > 0)

  this->end_depth_
    = min(this->end_depth_,
	  ( (this->gametree_interface().last_trick_to_calculate()
	     >= this->gametree_interface().game().trick_current_no())
	    ? (this->gametree_interface().last_trick_to_calculate()
	       - this->gametree_interface().game().trick_current_no())
	    : 0)
	 );

  if (INFO_GAMETREE)
    if (!this->gametree_interface().game().isvirtual())
      COUT << "Player " << this->gametree_interface().no() << ": "
	<< "Gametree: "
	<< "end depth = " << this->end_depth() << endl;

  // always calculate the current trick
  if (this->end_depth_ == 0)
    this->end_depth_ = 1;

  return this->end_depth();
} // unsigned const& VirtualGames::end_depth_calculate(unsigned future_limit)

/**
 **
 ** Calculates the best card (max-min-procedure).
 **
 ** @param      -
 **
 ** @return     the best card to play
 **
 ** @version    0.5.4
 **
 ** @author     Diether Knof
 **
 **/
Card
Gametree::best_card() const
{
  Card card_best;
  int modi_best = INT_MIN;
  Hand const& valid_hand = this->gametree_interface().hand().validcards(this->gametree_interface().game().trick_current()
								       );
  counter = 0;

#ifdef SAVE_RUNTIME
  // for measuring the runtime
  ofstream ostr("GameTree.time", ios::app);
  clock_t const time_begin = clock();
#endif
  // now calculate for all cards the modi
  for (vector<Card>::const_iterator c = valid_hand.cards().begin();
       c != valid_hand.cards().end();
       ++c) {
    // Create new players.
    // The hand is set during the rekursion.
    vector<Player*> player_virt;
    Ai const& real_ai
      = dynamic_cast<Ai const&>(this->gametree_interface().game().player(this->gametree_interface().no()));
    for (vector<Player*>::const_iterator player
	 = this->gametree_interface().game().player_begin();
	 player != this->gametree_interface().game().player_end();
	 player++) {
      if (this->with_heuristics) {
	player_virt.push_back(real_ai.Ai::clone());
	dynamic_cast<Aiconfig*>(player_virt.back())->set_aitype_for_all_tricks(AITYPE::NO_CHOOSEBESTCARD);
      } else { // if !(this->with_heuristics)
	if ((*player)->no() == this->gametree_interface().no())
	  player_virt.push_back(real_ai.Ai::clone());
	else
	  player_virt.push_back(real_ai.Player::clone());
      } // if !(this->with_heuristics)
      player_virt.back()->teaminfo_p = real_ai.teaminfo_p;
      player_virt.back()->no_set(player_virt.size() - 1);
      for (unsigned p = 0;
	   p < this->gametree_interface().game().playerno();
	   ++p)
	player_virt.back()->teaminfo_p[p]
	  = real_ai.teaminfo(real_ai.game().player(p));

    } // for (player)
    // create a virtual game
    Game virt_game(this->gametree_interface().game(), player_virt);

    // set all hands
    for (vector<Player*>::const_iterator player = virt_game.player_begin();
	 player != virt_game.player_end();
	 player++) {
      if ((*player)->type() == Player::AI)
	dynamic_cast<Ai*>(*player)->hand_set(this->gametree_interface().handofplayer(this->gametree_interface().game().player((*player)->no())),
					     !this->gametree_interface().value(Aiconfig::FAIRPLAYHANDS));
      else
	(*player)->hand_set(this->gametree_interface().handofplayer(this->gametree_interface().game().player((*player)->no())));
    }

    // play the card
    virt_game.trick_current() += *c,
      virt_game.player_current().hand().playcard(*c);
    virt_game.teaminfo_update();
    Player const& player_played = virt_game.player_current();
    virt_game.player_current_p
      = &virt_game.player_following(virt_game.player_current());
    for (vector<Player*>::iterator p = virt_game.player_begin();
	 p != virt_game.player_end();
	 p++)
      (*p)->card_played(*c, player_played);

    int const modi = this->maxmin_modi(virt_game, this->end_depth());
    DEBUG_ASSERTION(((modi != INT_MIN) && (modi != INT_MAX)),
		    "GameTree::bestcard()\n"
		    "  No valid game found.\n"
		    "  Card: " << *c);
    if (INFO_GAMETREE)
      if (!this->gametree_interface().game().isvirtual())
	COUT << *c << '\t' << modi << endl;

#ifndef RELEASE
    if (!this->gametree_interface().game().isvirtual())
      COUT << *c << ": " << modi << endl;
#endif

    // test, whether the card is better
    if ( (modi > modi_best)
	 || ( (modi == modi_best)
	      && (c->less(card_best, this->gametree_interface().game()))
	    )
       ) {
      modi_best = modi;
      card_best = *c;
    } // if (modi > modi_best)

    // delete the virtual players
    for (vector<Player*>::iterator player = player_virt.begin();
	 player != player_virt.end();
	 player++)
      delete *player;

    if (::game_status != GAMESTATUS::GAME_PLAY)
      break;
  } // for (c \in valid_hand.cards())

#ifdef SAVE_RUNTIME
  if (counter >= 2000) {
    unsigned const used_time = ((clock() - time_begin)
				/ (CLOCKS_PER_SEC / 1000));
    ostr << setw(8) << counter
      << "\t" << setw(8) << used_time
      << "\t" << setw(8) << (used_time * 1000 / counter) 
      << endl;
  } // if (counter >= 200)
#endif // #ifdef SAVE_RUNTIME

#ifndef RELEASE
  DEBUG_ASSERTION( (this->end_depth() == 1)
		   || (counter
		       <= this->future_limit()
		      ),
		   "VirtualGames::best_card():\n"
		   "  counter > future limit: "
		   << counter << " > "
		   << this->future_limit()
		 );
#endif

#ifdef WORKAROUND
  if (!card_best
      && this->with_heuristics) {
    // ToDo
    // sometimes no card is returned, so use the gametree without the heuristics
    // (perhaps the heuristic makes the hands invalid)
    return Gametree(this->gametree_interface(),
		    this->future_limit() / 2,
		    false).best_card();
  }
#endif

  DEBUG_ASSERTION(card_best,
		  "Gametree::best_card():\n"
		  "  no best card found.\n"
		  << (this->with_heuristics
		      ? "with heuristics"
		      : "without heuristics")
		  << "\n"
		  << "Hand:\n"
		  << this->gametree_interface().hand());

  return card_best;
} // Card VirtualGames::best_card() const

/**
 **
 ** Returns the maximal minimum modi.
 ** From players of the same team, the best modi is returned,
 ** for players of the opposite team, the worst modi is returned.
 **
 ** @param      virt_game	the virtual game
 ** @param      tricks_to_calc	how many tricks to be calced
 **
 ** @return     the maximal minimum modi
 **
 ** @version    0.5.4
 **
 ** @author     Diether Knof
 **
 **/
int
Gametree::maxmin_modi(Game& virt_game, unsigned const tricks_to_calc) const
{
  ::ui->update();
  if (::game_status != GAMESTATUS::GAME_PLAY)
    return 0;

  // the correspoding virtual player to the ai
  // ToDo: AiConfig::REMEMBERTRICKS hochsetzen
  Ai const& virt_ai
    = dynamic_cast<Ai const&>(virt_game.player(this->gametree_interface().no()));
  // the team of the ai
  Team const ai_team = virt_ai.team();

  if (virt_game.trick_current().isfull()) {
    counter += 1;

    virt_game.evaluatetrick();
#if 0
    if ( (this->gametree_interface().game().trick_current_no() == 8)
	 && (this->gametree_interface().no() == 3) )
      COUT << virt_game.trick_current();
#endif

    // increase the remember tricks number of the ai
    dynamic_cast<Ai&>(virt_game.player(this->gametree_interface().no())
		     ).set(Aiconfig::REMEMBERTRICKS,
			   virt_ai.value(Aiconfig::REMEMBERTRICKS) + 1);
    if (tricks_to_calc > 1) {

      virt_game.trick_p.push_back(new Trick(virt_game.player_current()));
      int const modi = maxmin_modi(virt_game, tricks_to_calc - 1);
      return modi;
    } else { // if !(tricks_to_calc > 1)
      int modi = 0;

      // game finished, the main interest is the final result...
      if (virt_game.tricks_remaining_no() == 0) {

	// it can be that not all teams are set during the game
	// (p.e. in the case that only one club queen has been played)
	for (vector<Player*>::iterator p = virt_game.player_begin();
	     p != virt_game.player_end();
	     ++p) {
	  if (((*p)->team() != TEAM::RE)
	      && ((*p)->team() != TEAM::CONTRA)) {
	    if ((*p)->team() == TEAM::UNKNOWN)
	      (*p)->teaminfo_p[(*p)->no()] = this->gametree_interface().team();
	    else
	      (*p)->teaminfo_p[(*p)->no()] = maybe_to_team((*p)->team());
	  } // if ((*p)->team() not known)
	} // for (p \in virt_game.player)

	virt_game.finish();

	GameSummary game_summary(virt_game);

	modi = ( ((game_summary.winnerteam() == ai_team)
		  ? +1
		  : -1)
		 * 10000 * game_summary.points() );
	modi += virt_game.points_of_team(ai_team);
      } else { // if !(virt_game.tricks_remaining_no() == 0)
	// add the modi for all tricks
	for (unsigned t = this->gametree_interface().game().trick_current_no();
	     t < virt_game.trick_current_no();
	     t++) {

	  modi += TrickWeighting::modi(this->gametree_interface(),
				       virt_game.trick(t),
				       virt_ai.team(),
				       virt_game.trick(t).card_of_player(virt_ai));
	}
	// copied from 'WVirtualGames'
	// add some points, if the own team is in the back,
	if (virt_game.trick_current_no() < virt_game.trickno() - 1) {
	  modi += TrickWeighting::backhand(this->gametree_interface(),
					   virt_game.trick_current().card_of_player(virt_ai),
					   virt_game);
	} // if (virt_game.trick_current_no() < virt_game.trickno() - 1)
      } // if !(virt_game.tricks_remaining_no() == 0)

      return modi;
    } // if (tricks_to_calc > 1)
  } // if (!virt_game.trick_current().isfull())

  // Here we are in the middle of a trick.
  // Try all cards and take the worst/best modi if the player is in the
  // opposite/same team.

  //  The player is in the same team, if the team of the ai is known to all
  //  and the team of the player is the team of the ai.
  bool same_team = false;

  // first look, whether the team of the ai is known to all
  if (virt_game.teaminfo(virt_ai) == ai_team) {
    // next test, whether the team of the player is the same of the ai
    if (virt_game.teaminfo(virt_game.player_current()) == ai_team)
      same_team = true;
    else if ((virt_game.teaminfo(virt_game.player_current()) == TEAM::UNKNOWN)
	     && (this->gametree_interface().teamofplayer(virt_game.player(virt_game.player_current().no()))
		 == ai_team))
      // The team of the player is not known,
      // but the interface says, that the teams are the same.
      same_team = true;
  } // if (team of virt_ai known)


  // Now test all the cards and calc the maxmin modus

  // this ensures, that the modi can be improved
  int maxmin_modi = (same_team ? INT_MIN : INT_MAX);
  Card card = Card();

  // first set the hand of the player
  Hand hand;
  try {
    //Hand const& hand = virt_ai.handofplayer(virt_game.player_current());
    hand = virt_ai.handofplayer(virt_game.player_current());
  }

  catch (InvalidGameException e) {
    // nothing to do, because 'maxmin_modi' cannot get changed
    throw;
  } // catch()

  if (this->with_heuristics) {

    // update/set the hand of the current player
    if (virt_game.player_current().type() == Player::AI)
      dynamic_cast<Ai&>(virt_game.player_current()).hand_set(hand,
							     !this->gametree_interface().value(Aiconfig::FAIRPLAYHANDS));
    else
      virt_game.player_current().hand_set(hand);

    card = dynamic_cast<Ai&>(virt_game.player_current()).card_get();
    if (card) {
      // create a new virtual game
      vector<Player*> player_virt;
      for (vector<Player*>::const_iterator player
	   = virt_game.player_begin();
	   player != virt_game.player_end();
	   player++) {
	player_virt.push_back((*player)->clone());
	player_virt.back()->no_set(player_virt.size() - 1);

	if (player_virt.back()->type() == Player::AI)
	  dynamic_cast<Ai*>(player_virt.back())->hand_set(virt_ai.handofplayer(virt_ai.game().player(player_virt.size() - 1)),
							  !this->gametree_interface().value(Aiconfig::FAIRPLAYHANDS));
	else
	  player_virt.back()->hand_set(virt_ai.handofplayer(virt_ai.game().player(player_virt.size() - 1)));
      } // for (player)
      Game* const virt_game_2 = new Game(virt_game, player_virt);

      // play the card
      virt_game_2->trick_current() += card;
      virt_game_2->player_current().hand().playcard(card);
      virt_game_2->teaminfo_update();
      Player const& player_played = virt_game_2->player_current();
      virt_game_2->player_current_p
	= &virt_game_2->player_following(virt_game_2->player_current());
      for (vector<Player*>::iterator p = virt_game_2->player_begin();
	   p != virt_game_2->player_end();
	   p++)
	(*p)->card_played(card, player_played);

      unsigned const counter_bak = counter;
      try {
	int const modi = this->maxmin_modi(*virt_game_2, tricks_to_calc);

	if ((modi == INT_MIN)
	    || (modi == INT_MAX))
	  DEBUG_THROW( InvalidGameException, InvalidGameException() );

	// delete the created virtual players and virtual game
	for (vector<Player*>::iterator player = player_virt.begin();
	     player != player_virt.end();
	     player++)
	  delete *player;
	delete virt_game_2;

	return modi;
      } // try
      catch (InvalidGameException e) {
	// the heuristic leads to an invalid game, so reject the card and test
	// the whole hand
	//
	// delete the created virtual players and virtual game
	for (vector<Player*>::iterator player = player_virt.begin();
	     player != player_virt.end();
	     player++)
	  delete *player;
	delete virt_game_2;

	counter = counter_bak;
	DEBUG_CAUGHT();
      } // catch()
    } // if (card)

  } // if (this->with_heuristics)

  // When the ai does not 'know' the hand of the player
  // all cards have to be viewed, else there can result only invalid games.
  vector<Card> valid_cards
    = ((this->gametree_interface().value(Aiconfig::FAIRPLAYHANDS)
	&& !same_team)
       ? hand
       : hand.validcards(virt_game.trick_current())
      ).cards_single();

  // this mark is taken if no valid game has been found and not all cards
  // have been tested (only the valid cards)
  bool test_cards_loop = false;

test_cards:

  // now test all cards
  for (vector<Card>::const_iterator c = valid_cards.begin();
       c != valid_cards.end();
       ++c) {
    // create a new virtual game
    vector<Player*> player_virt;
    for (vector<Player*>::const_iterator player
	 = virt_game.player_begin();
	 player != virt_game.player_end();
	 player++) {
      player_virt.push_back((*player)->clone());
      player_virt.back()->no_set(player_virt.size() - 1);

      if (player_virt.back()->type() == Player::AI)
	dynamic_cast<Ai*>(player_virt.back())->hand_set(virt_ai.handofplayer(virt_ai.game().player(player_virt.size() - 1)),
							!this->gametree_interface().value(Aiconfig::FAIRPLAYHANDS));
      else
	player_virt.back()->hand_set(virt_ai.handofplayer(virt_ai.game().player(player_virt.size() - 1)));
    } // for (player)
    Game* const virt_game_2 = new Game(virt_game, player_virt);

    // now play the card
    virt_game_2->trick_current() += *c;
    virt_game_2->player_current().hand().playcard(*c);
    virt_game_2->teaminfo_update();

    Player const& player_played = virt_game_2->player_current();
    virt_game_2->player_current_p
      = &virt_game_2->player_following(virt_game_2->player_current());
    for (vector<Player*>::iterator p = virt_game_2->player_begin();
	 p != virt_game_2->player_end();
	 p++)
      (*p)->card_played(*c, player_played);

#ifndef RELEASE
    if (virt_game_2->tricks_remaining_no() > 1)
      for (vector<Player*>::const_iterator player
	   = virt_game_2->player_begin();
	   player != virt_game_2->player_end();
	   player++)
	DEBUG_ASSERTION(((*player)->hand().cardsnumber() >= 1),
			"Gametree::maxminmodi():\n"
			"  empty hand.\n"
			"Game: \n");
#endif
    try {
      // get the modi through the recursion
      int const modi = this->maxmin_modi(*virt_game_2, tricks_to_calc);
      // think about this contition ;-)
      if ((modi != INT_MIN) && (modi != INT_MAX))
	if ((modi > maxmin_modi) == same_team) {
	  maxmin_modi = modi;
	  card = *c;
	} // if (better modus)
    } // try
    catch (InvalidGameException e) {
      // nothing to do, because 'maxmin_modi' cannot get changed
      DEBUG_CAUGHT();
    } // catch()

    // delete the created virtual players and virtual game
    for (vector<Player*>::iterator player = player_virt.begin();
	 player != player_virt.end();
	 player++)
      delete *player;
    delete virt_game_2;

    if (::game_status != GAMESTATUS::GAME_PLAY)
      break;
  } // for (c \in valid_cards)

  if (!test_cards_loop
      && ((maxmin_modi == INT_MIN)
	  || (maxmin_modi == INT_MAX) )) {
    if (this->gametree_interface().value(Aiconfig::FAIRPLAYHANDS)
	&& same_team) {
      // ToDo
      // test only the cards that have not been tested, yet
      {
	Hand remaining_cards = hand.cards_single();
	remaining_cards.remove(valid_cards);
	valid_cards = remaining_cards.cards();
      }
      test_cards_loop = true;
      goto test_cards;
    } // if (not all cards tested)
  } // if (no valid game found)
  test_cards_loop = false;

  return maxmin_modi;
} // int VirtualGames::maxmin_modi(Game& virt_game, unsigned const tricks_to_calc) const
