/**********************************************************************
 *
 *
 *   FreeDoko a Doppelkopf-Game
 *    
 *   Copyright (C) 2001-2006  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 "cards_information.h"
#include "team_information.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

// if a type does always lead to an invalid game exception, take the next one
namespace CARDS_TESTS {
  enum CardsTest {
    VALID_CARDS,
    ALL_CARDS,
    FINISHED
  }; // enum CardsTest
} // namespace CARDS_TESTS 
using CARDS_TESTS::CardsTest;

/**
 ** constructor
 **
 ** @param      gametree_interface	the interface
 ** @param      future_limit		the future limit
 ** @param      with_heuristics		whether to use heuristics
 **
 ** @return     -
 **
 ** @author     Diether Knof
 **
 ** @version    0.5.4
 **/
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     -
 **
 ** @author     Diether Knof
 **
 ** @version    0.5.4
 **/
Gametree::~Gametree()
{
  return ;
} // Gametree::~Gametree()

/**
 ** -> result
 **
 ** @param      -
 **
 ** @return     the gametree interface
 **
 ** @author     Diether Knof
 **
 ** @version    0.5.4
 **/
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)
 **
 ** @author     Diether Knof
 **
 ** @version    0.5.4
 **/
unsigned const&
Gametree::end_depth() const
{
  return this->end_depth_;
} // unsign
/**
 ** -> result
 **
 ** @param      -
 **
 ** @return     the future limit
 **
 ** @author     Diether Knof
 **
 ** @version    0.6.7
 **/
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
 **
 ** @author     Diether Knof
 **
 ** @version    0.5.4
 **/
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().cardsnumber();

      } else {
	future_limit /= this->gametree_interface().handofplayer(current_trick.player_of_card(i)
							       ).validcards(current_trick).cardsnumber();

      }
    } // for (i) 
  } // 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().players_begin();
	 player != this->gametree_interface().game().players_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())
      clog << "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
 **
 ** @author     Diether Knof
 **
 ** @version    0.5.4
 **/
Card
Gametree::best_card() const
{
  HandCard card_best(this->gametree_interface().hand());
  int modi_best = INT_MIN; // best modus
#ifdef OUTDATED
#if defined(WORKAROUND) && defined(RELEASE)
  HandCards const valid_cards
    = this->gametree_interface().hand().validcards(this->gametree_interface().game().trick_current());
#else
  HandCards const valid_cards
    = (!this->gametree_interface().game().isvirtual()
       ? this->gametree_interface().hand()
       : this->gametree_interface().handofplayer(this->gametree_interface().game().player(this->gametree_interface().no()))
      ).validcards(this->gametree_interface().game().trick_current());
#endif
#else
  // 'local_hand' is needed because the cards of 'valid_cards'
  // need a reference hand.
  Hand const local_hand(this->gametree_interface().handofplayer(this->gametree_interface().game().player(this->gametree_interface().no())));
  HandCards const valid_cards
    = local_hand.validcards(this->gametree_interface().game().trick_current());
  this->gametree_interface().game().player(this->gametree_interface().no()).self_check();
#endif
  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 (HandCards::const_iterator c = valid_cards.begin();
       c != valid_cards.end();
       ++c) {
#if defined(WINDOWS) && defined(WORKAROUND)
    HandCard const hc(*c);
    HandCard const* const c = &hc;
#endif
    // Create new players.
    // The hand is set during the recursion.
    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().players_begin();
	 player != this->gametree_interface().game().players_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()->set_no(player_virt.size() - 1);
      player_virt.back()->set_team(real_ai.team_information().guessed_team(player_virt.size() - 1));

    } // 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.players_begin();
	 player != virt_game.players_end();
	 player++) {
      (*player)->set_hand(this->gametree_interface().handofplayer(this->gametree_interface().game().player((*player)->no())));

      (*player)->self_check();
    }

    try {
      { // play the card
	HandCard const card(virt_game.player_current().hand(), *c);
	virt_game.trick_current() += card;
	virt_game.player_current().hand().playcard(card);
	virt_game.teaminfo_update();
	virt_game.player_current_
	  = &virt_game.player_following(virt_game.player_current());
	for (vector<Player*>::iterator p = virt_game.players_begin();
	     p != virt_game.players_end();
	     p++)
	  (*p)->card_played(card);
      } // play the card 'c'

      ::ui->ai_test_card(*c, this->gametree_interface().no());
      int const modi = this->maxmin_modi(virt_game, this->end_depth(),
					 INT_MIN, INT_MAX);
      ::ui->ai_card_weighting(modi);

      // this is needed when 'gametree' is called from 'virtual games'
      if (this->gametree_interface().game().isvirtual()
	  && ((modi == INT_MIN)
	      || (modi == INT_MAX))
	 )
	DEBUG_THROW( InvalidGameException, InvalidGameException() );

#ifdef RELEASE
      DEBUG_ASSERTION(((modi != INT_MIN) && (modi != INT_MAX)),
		      "GameTree::bestcard()\n"
		      "  No valid game found.\n"
		      "  Card: " << *c);
#else
      if ((modi == INT_MIN)
	  || (modi == INT_MAX)) {
	cerr << "GameTree-error\n";

	DEBUG_ASSERTION(((modi != INT_MIN) && (modi != INT_MAX)),
			"GameTree::bestcard()\n"
			"  No valid game found.\n"
			"  Card: " << *c);
      }
#endif
      if (INFO_GAMETREE)
	if (!this->gametree_interface().game().isvirtual())
	  clog << *c << ":\t" << modi << endl;

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

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

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

      throw;
    } // try

    // 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
#if 0
  DEBUG_ASSERTION( (this->end_depth() == 1)
		   || (counter <= this->future_limit()
		      ),
		   "GameTree::best_card():\n"
		   "  counter > future limit: "
		   << counter << " > "
		   << this->future_limit() << '\n'
		   << "  end depth = " << this->end_depth()
		 );
#endif
#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
 ** @param      lb		lower bound for the modi
 ** @param      ub		upper bound for the modi
 **
 ** @return     the maximal minimum modi
 **
 ** @author     Diether Knof
 **
 ** @version    0.5.4
 **
 ** @todo	use lower and upper bound for faster calculating
 **/
int
Gametree::maxmin_modi(Game& virt_game, unsigned const tricks_to_calc,
		      int lb, int ub) const
{
  ::ui->update();
  if (::game_status != GAMESTATUS::GAME_PLAY)
    return 0;

  // the correspoding virtual player to the ai
  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;

    try {
      virt_game.evaluatetrick();
    } catch (...) {
      throw;
    }

    if (tricks_to_calc > 1) {
      virt_game.tricks().push_back(new Trick(virt_game.player_current()));
      for (vector<Player*>::iterator p = virt_game.players().begin();
	   p != virt_game.players().end();
	   p++)
	(*p)->trick_open(virt_game.trick_current());
      int const modi = maxmin_modi(virt_game, tricks_to_calc - 1, lb, ub);
      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) {

	virt_game.finish();

	GameSummary const game_summary(virt_game);

	modi = 1000 * game_summary.points(this->gametree_interface().no());
	if (game_summary.winnerteam() == TEAM::NOTEAM) {
	  modi = 10000 * (game_summary.points(virt_ai.team())
			  - game_summary.points(opposite(virt_ai.team())));
	} else { // if !(game_summary.winnerteam() == TEAM::NOTEAM)
	  if (::maybe_to_team(game_summary.winnerteam()) == virt_ai.team())
	    modi = 10000 * game_summary.points();
	  else
	    modi = -10000 * game_summary.points();
	} // if !(game_summary.winnerteam() == TEAM::NOTEAM)
      } 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)

  if (same_team)
    lb = INT_MIN;
  else
    ub = INT_MAX;


  // 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);
  HandCard card; // card that is played

  // first set the hand of the player
  Hand hand;
  try {
    hand = virt_ai.handofplayer(virt_game.player_current());
  } catch (InvalidGameException e) {
    cerr << "\n\n\n\n\n\n\n\n\n\n\n\n\n";
    cerr << "invalid handofplayer:\n";
    cerr << this->gametree_interface().game();
    cerr << dynamic_cast<Ai const&>(this->gametree_interface().game().player(this->gametree_interface().no())).cards_information();
    // nothing to do, because 'maxmin_modi' cannot get changed
    throw;
  } // catch()

  if (this->with_heuristics) {

    // update/set the hand of the current player
    virt_game.player_current().set_hand(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.players_begin();
	   player != virt_game.players_end();
	   player++) {
	player_virt.push_back((*player)->clone());
	player_virt.back()->set_no(player_virt.size() - 1);

	player_virt.back()->set_hand(virt_ai.handofplayer(virt_ai.game().player(player_virt.size() - 1)));
      } // for (player)
      Game* const virt_game_2 = new Game(virt_game, player_virt);

      unsigned const counter_bak = counter;
      try { // play the card
	try {
	  HandCard const card2(virt_game_2->player_current().hand(), card);
	  virt_game_2->trick_current() += card2;
	  virt_game_2->player_current().hand().playcard(card2);
	  virt_game_2->teaminfo_update();
	  virt_game_2->player_current_
	    = &virt_game_2->player_following(virt_game_2->player_current());
	  for (vector<Player*>::iterator p = virt_game_2->players_begin();
	       p != virt_game_2->players_end();
	       p++)
	    (*p)->card_played(card2);

	  int modi;
	  try {
	    ::ui->ai_test_card(card, virt_game.player_current().no());
	    modi = this->maxmin_modi(*virt_game_2, tricks_to_calc, lb, ub);

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

	    ::ui->ai_card_weighting(modi);
	  } catch(...) {
	    ::ui->ai_card_weighting(INT_MIN);
	    throw;
	  } // try

	  // 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;
	} 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;
	} // try
      } catch (InvalidGameException const& e) {
	counter = counter_bak;
	DEBUG_CAUGHT();
      } catch (...) {
	throw;
      } // try

    } // if (card)

  } // if (this->with_heuristics)

  if (card)
    hand.remove(card);


  // this mark is taken if no valid game has been found and not all cards
  // have been tested (only the valid cards)
  CardsTest cards_test
    = ((!this->gametree_interface().value(Aiconfig::FAIRPLAYHANDS)
	|| same_team)
       ? CARDS_TESTS::VALID_CARDS
       : CARDS_TESTS::ALL_CARDS);

  // When the ai does not 'know' the hand of the player
  // all cards have to be viewed, else there can result only invalid games.
  HandCards valid_cards
    = ((cards_test == CARDS_TESTS::VALID_CARDS)
       ? hand.validcards(virt_game.trick_current())
       : hand.cards_single());


  int modi_sum = 0;
  do {
    // now test all cards
    for (HandCards::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.players_begin();
	   player != virt_game.players_end();
	   player++) {
	player_virt.push_back((*player)->clone());
	player_virt.back()->set_no(player_virt.size() - 1);

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

      try {
	{ // now play the card
	  HandCard const card2(virt_game_2->player_current().hand(), *c);
	  virt_game_2->trick_current() += card2;
	  virt_game_2->player_current().hand().playcard(card2);
	  virt_game_2->teaminfo_update();

	  virt_game_2->player_current_
	    = &virt_game_2->player_following(virt_game_2->player_current());
	  try {
	    for (vector<Player*>::iterator p = virt_game_2->players_begin();
		 p != virt_game_2->players_end();
		 p++)
	      (*p)->card_played(card2);
	  } catch (...) {
	    throw;
	  }
	} // play the card 'c'

#ifndef RELEASE
	if (virt_game_2->tricks_remaining_no() > 1)
	  for (vector<Player*>::const_iterator player
	       = virt_game_2->players_begin();
	       player != virt_game_2->players_end();
	       player++)
	    DEBUG_ASSERTION(((*player)->hand().cardsnumber() >= 1),
			    "Gametree::maxminmodi():\n"
			    "  empty hand.\n"
			    "Game: \n");
#endif
	// get the modi through the recursion
	::ui->ai_test_card(*c, virt_game.player_current().no());
	try {
	  int const modi = this->maxmin_modi(*virt_game_2, tricks_to_calc, lb, ub);
	  ::ui->ai_card_weighting(modi);
	  modi_sum += modi;
	  if ((modi != INT_MIN) && (modi != INT_MAX))
	    // think about this contition ;-)
	    if ((modi > maxmin_modi) == same_team) {
	      maxmin_modi = modi;
	      card = *c;
	      if (same_team) {
		if (modi > lb)
		  lb = modi;
	      } else { // if !(same_team)
		if (modi < ub)
		  ub = modi;
	      } // if !(same_team)
	    } // if (better modus)
	} catch (...) {
	  ::ui->ai_card_weighting(INT_MIN);
	  throw;
	}
      } catch (InvalidGameException const& 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;

	cerr << __LINE__ << " " << *c << endl;
	throw;
      } // try

      // 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 (same_team) {
	if (maxmin_modi >= ub)
	  break;
      } else { // if !(same_team)
	if (maxmin_modi <= lb)
	  break;
      } // if !(same_team)
    } // for (c \in valid_cards)

    if ((cards_test == CARDS_TESTS::VALID_CARDS)
	&& ((maxmin_modi == INT_MIN)
	    || (maxmin_modi == INT_MAX) )) {
      // test only the cards that have not been tested, yet
      HandCards remaining_cards = hand.cards_single();
      remaining_cards.remove(valid_cards);
      valid_cards = remaining_cards;
      cards_test = CARDS_TESTS::ALL_CARDS;
      continue;
    } // if (no valid game found)
    cards_test = CARDS_TESTS::FINISHED;
  } while (cards_test < CARDS_TESTS::FINISHED);

  if ((maxmin_modi == INT_MIN)
      || (maxmin_modi == INT_MAX))
    return maxmin_modi;
  else
    // the sum is added because else in the end when not all teams are known
    // special points (i.e. charlie) could be lost
    // note: when the game is not finished, 'modi_sum' < 1000
    return maxmin_modi + modi_sum / 1000;
} // int VirtualGames::maxmin_modi(Game& virt_game, unsigned tricks_to_calc, int lb, int ub) const
