/***************************************************************************
                          AlphaBeta.cpp  -  description
                             -------------------
    begin                : Tue May 22 2001
    copyright            : (C) 2001 by Sven Reichard
    email                : reichard@math.udel.edu
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   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.                                   *
 *                                                                         *
 ***************************************************************************/
# include "Algorithms/AlphaBeta.h"
# include "Game/Game.h"
# include "Moves/Move.h"
# include "Color.h"
# include "Game/PositionalEvaluation.h"
using namespace Alice;

/** Constructor
 * \param game a game to be searched
 */
AlphaBeta::AlphaBeta(Game& game):
  mScore(0),
  mNodesSearched(0),
  height(0),
  moveLists(256),
  mGame(&game)
{

};
/** Destructor
 */
AlphaBeta::~AlphaBeta()
{
};

/** perform a fixed depth search
 * \param depth the number of plies to be searched
 * \returns nothing
 */
void
AlphaBeta::search(int depth)
{
  presearch();
  mNodesSearched = 0;
  if (depth <= 0){
    mScore =  getEvaluation()->score();
    return;
  }
  Score max = Evaluation::mate();
  MoveList moves;
  generateMoves(moves);
  for (MoveIterator it = moves.begin();
       it != moves.end(); ++ it) {
    mNodesSearched ++;
    makeMove(it);
    if (! movedIntoCheck()) {
      Score result = recursiveSearch(depth-1, 
				     Evaluation::mate(), 
				     propagate(max));
      result = backPropagate(result);
      if (result > max) {
	mBestMove = *it;
	max = result;
      }
    }
    takeBack(it);
  }
  mScore = max;
  //eval->stopObserving();
  
};
/** returns the score found.
 *   The score has to be determined by calling search() first.
 */
AlphaBeta::Score
AlphaBeta::score() const
{
  return mScore;
};
/** returns the best move.
 * Has to be called after search().
 */
SmartPointer<Move>
AlphaBeta::bestMove() const
{
  return mBestMove;
};
int
AlphaBeta::nextDepth( int depth )
{
  return  (game().isInCheck(game().colorToMove())? depth: depth-1);
};
int
AlphaBeta::nextDepth(const SearchParameters& param)
{
  return nextDepth(param.depth);
};
/** the recursive search function.
 * This function calls itself recursively to determine the
 * score of a given position.
 * \param depth the depth to be searched
 * \param alpha a lower bound for the score
 * \param beta an upper bound for the score
 * \returns the exact score if it lies between \p alpha and
 * \p beta, otherwise a bound for the score.
 */

AlphaBeta::Score
AlphaBeta::recursiveSearch(int depth, Score alpha, Score beta)
{
    SearchParameters parameters(depth, Evaluation::mate(), alpha, beta);

  return recursiveSearch(parameters);
};

AlphaBeta::Score
AlphaBeta::recursiveSearch(SearchParameters& parameters)
{
  Score alpha = parameters.alpha;
  if (game().isRepeated())
    return Evaluation::stalemate();
  if (cutOff(parameters))
    return parameters.max;
  parameters.max = initialScore(parameters);
  if (parameters.max >= parameters.beta)
    return parameters.max;
  parameters.alpha = std::max(parameters.alpha, parameters.max);
  MoveList moves;
  generateMoves(moves);
  for (MoveIterator it = moves.begin(); it != moves.end(); ++ it)
    {
      mNodesSearched ++;
      if (!makeMove(it))
	{
	  takeBack(it); 
	  continue;
	}
      int newDepth = nextDepth( parameters );
      //newDepth = depth-1;
      SearchParameters nextParameters = parameters.next(newDepth);
      parameters.result = recursiveSearch(nextParameters);
      parameters.result = backPropagate(parameters.result);
      
      takeBack(it);
      if (stopSearch(parameters, *it))
	return parameters.result;
    } // for it
  if (!parameters.bestMove)
    return stalemateScore();
  parameters.alpha = alpha;
  finishNode(parameters);
  return parameters.max;
};

AlphaBeta::Score
AlphaBeta::stalemateScore()
{
  if (game().isInCheck(game().colorToMove()))
    return Evaluation::mate();
  else return Evaluation::stalemate();
};

/** a convenience method
 */
bool
AlphaBeta::makeMove(MoveIterator& it)
{
  (*it)->makeOn(game());
  return !movedIntoCheck();
};

/** a convenience method
 */
void
AlphaBeta::takeBack(MoveIterator& it)
{
  (*it)->takeBackOn(game());
};
/** a convenience method
 */
bool
AlphaBeta::movedIntoCheck()
{
  return game().isInCheck(game().colorToMove()->otherColor());
};
/** generate moves.
 * The moves are stored in \p moves, which should be empty
 * when called. It returns true if ???
 */
bool
AlphaBeta::generateMoves(MoveList& moves)
{
  game().pseudoLegalMoves(moves);
  return !moves.empty();
};
/** initial score for the search.
 * Subclasses can overload this as necessary.
 */
AlphaBeta::Score
AlphaBeta::initialScore(SearchParameters&)
{
  return Evaluation::mate();
};
/** the evaluation of the current position.
 * \param alpha a lower bound for the score
 * \param beta an upper bound for the score
 * \returns the current score subject to the bounds above.
 */
AlphaBeta::Score
AlphaBeta::staticEvaluation(Score alpha, Score beta)
{
  return getEvaluation()->score();
};
/** is called before searching.
 * Provides a hook for subclasses.
 */
void
AlphaBeta::presearch()
{
};

/** is called when a cut-off occurs.
 * Provides a hook for subclasses.
 */
bool 
AlphaBeta::cutOff(SearchParameters& param)
{
  if (param.depth <= 0){
    param.max = staticEvaluation(param.alpha, param.beta);
    param.pv->next()->clear();
    param.pv->insert(param.bestMove);
    return true;
  }
  return false;
}
/** is called after searching a node.
 * Provides a hook for subclasses.
 */
void 
AlphaBeta::finishNode(SearchParameters&)
{};
/** is called in case of failing high.
 * Provides a hook for subclasses.
 */
void 
AlphaBeta::failHigh(int depth, Score score,
		    SmartPointer<Move> bestMove)
{};

bool
AlphaBeta::stopSearch(SearchParameters& parameters,
		      SmartPointer<Move> move)
{
  bool result = false;
  if (parameters.result > parameters.max)
    {
      parameters.max = parameters.result;
      parameters.bestMove = move;
      parameters.pv->insert(move);
    }
  if (parameters.result >= parameters.beta) 
    {
      failHigh(parameters.depth, parameters.result, parameters.bestMove);
      result = true;
      return result;
    }
  parameters.alpha = std::max(parameters.alpha, parameters.max);
  return result;
};

void
AlphaBeta::setGame(Game& g)
{
  mGame = &g;
  mNodesSearched = 0;
};

void
AlphaBeta::resetNodesSearched()
{
  mNodesSearched = 0;
};
