/***************************************************************************
                          HashedAlphaBeta.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 <CpuTimer.h>
# include <Algorithms/HashedAlphaBeta.h>
# include <Game/Game.h>
# include <Color.h>
# include <Moves/SanNotation.h>
# include <RealTimer.h>
# include <FullMoveComp.h>
# include <assert.h>
# include <cmath>
# ifdef __GNU__
#  include <unistd.h>
# endif // __GNU__
using namespace Alice;

/** Constructor
 */
HashedAlphaBeta::HashedAlphaBeta(Game& g):
  AlphaBetaWithQSearch(g),
  ttable(17),
  doNullMove(true)
{
  ttable.startObserving(&g);
};

/** Destructor
 */
HashedAlphaBeta::~HashedAlphaBeta()
{
  ttable.stopObserving();
};

void 
HashedAlphaBeta::searchFixedDepth(int depth)
{
  MoveList moves;
  generateMoves(moves);
  if ((! mBestMove) and ttable.isValid())
    mBestMove = ttable.bestMove();
  if (mBestMove)
    {
      MoveList::iterator it = moves.begin();
      while (it != moves.end() && **it != *mBestMove)
	++ it;
      if (it != moves.end())
	{
	  moves.erase(it);
	  moves.insert(moves.begin(),mBestMove);
	}
    }
  searchFixedDepth(depth, moves);
  //  if (mBestMove)
  //ttable.storeExactScore(mScore, depth, mBestMove);
  searchDepth = depth;
  return;
};

void
HashedAlphaBeta::searchFixedDepth(int depth, MoveList& moves)
{
   if (ttable.isValid() && ttable.depth() >= depth)
    {
      //std::cout<<"found entry: depth "<<ttable.depth();
      //std::cout<<" best move: ";
      //ttable.bestMove()->printOn(std::cout);
      //std::cout<<std::endl;
      //ttable.printScore(std::cout);
      //std::cout<<std::endl;
      mScore = ttable.score();
      mBestMove = ttable.bestMove();
      return;
    }
  
  if (depth <= 0)
    {
      mScore =  getEvaluation()->score();
      return;
    }
  Score max(Evaluation::mate());
  Score alpha(max);
  Score beta(-Evaluation::mate());
  SearchParameters parameters(depth, max, alpha, beta);
  
  bool firstMove = true;
  int i = 0;
  for (MoveIterator it = moves.begin();
       it != moves.end(); ++ it, ++ i) 
    {
      makeMove(it);
      if (! movedIntoCheck()) 
	{
	  if (! firstMove)
	    parameters.beta = parameters.max+1;
	  SearchParameters nextParameters = parameters.next(nextDepth(depth));
	  Score result = recursiveSearch(nextParameters);
	  result = backPropagate(result);
	  if (result >= parameters.beta)
	    {
	      mBestMove = *it;
	      parameters.beta = -Evaluation::mate();
	      SearchParameters nextParameters = 
		parameters.next(nextDepth(depth));
	      Evaluation::Score newResult = recursiveSearch(nextParameters);
	      newResult = backPropagate(newResult);
	      result = newResult;
	    };
	  
	  if (result > parameters.max)
	    {
	      mBestMove = *it;
	      parameters.max = result;
	      if (parameters.max > parameters.alpha)
		parameters.alpha = parameters.max;
	      
	    }
	  firstMove = false;
	}
      takeBack(it);
    }
  //  std::cout<<std::endl;
  mScore = parameters.max;
  //std::cout<<depth<<"  "<<mScore<<"  ";
  //parameters.pv->printTo(std::cout);
  
};

void
HashedAlphaBeta::search(int depth)
{
  mBestMove = 0;
  clock_t before(clock());
  double timeTaken = 0;
  for (int i = 1; i <= depth; i++)
    {
      searchFixedDepth(i);
      clock_t after(clock());
      if (true || i >= 4){
	timeTaken = (1.0*(after-before)/CLOCKS_PER_SEC);
	if (false &&  timeTaken > 2.0)
	  {
	    std::cout<<i<<"   "<<timeTaken<<": "<<score()<<"  ";
	    printPV(std::cout);
	  }
      }
    }
};

void
HashedAlphaBeta::searchTime(double seconds)
{
  this->searchTime(seconds, std::cout);
};


void
HashedAlphaBeta::searchTime(double seconds, std::ostream& log)
{
  log<<"Time limit: "<<seconds<<" seconds"<<std::endl;
  mBestMove = 0;
  mNodesSearched = 0;
  qsearch->resetNodesSearched();
  CpuTimer cpuTimer;
  RealTimer realTimer;
  bool mateSeen = false;
  for (int depth = 1; realTimer.age() < seconds && depth < 40; depth ++) {
    searchFixedDepth(depth);
    
    double timeTaken = realTimer.age();
    if (true || (timeTaken >= 1.0)) {
      log<<depth<<" "<<roundf(score()/10)<<" "<<
	 roundf(timeTaken*100)<<" ";
      printCompletePV(depth, log);
      log << std::endl;
    }
    if ( isMate(score()))
      {
	if (mateSeen)
	  break;
	mateSeen = true;
      }
    else
      mateSeen = false;
  }
  double realTime(realTimer.age());
  double timeTaken(cpuTimer.age());
  log<<std::endl<<"Time taken: "<<timeTaken<<" seconds"<<std::endl;
  log<<"Real passed:"<<realTime<<" seconds"<<std::endl;
  log<<"CPU: "<<100*timeTaken/realTime<<"%"<<std::endl;
  log<<"Nodes searched: "<<nodesSearched()<<std::endl;
  log<<"normal nodes: "<<mNodesSearched
	   <<"; qnodes: "<<qsearch->nodesSearched()<<std::endl;
  log<<int(nodesSearched()/timeTaken)<<" nodes/sec"<<std::endl;
};

bool
HashedAlphaBeta::generateMoves(MoveList& moves)
{
  game().pseudoLegalMoves(moves);
  //moves.sort(FullMoveComp(game().board()));
  return true;
};
void 
HashedAlphaBeta::printPV(std::ostream& out, int depth)
{
  if (game().isRepeated())
    {
      out<<" = "<<std::endl;
      return;
    };
  if (!ttable.isValid() || depth >= 30)
    {
      out<<std::endl;
      return;
    }
  if (depth % 8 == 0)
    out<<std::endl<<"\t";
  if (game().colorToMove()->isWhite())
    out<<depth/2+1<<". ";
  SmartPointer<Move> move(ttable.bestMove());
  if (! move->isLegal(game()))
    {
      out<<std::endl;
      return;
    }
  SanNotation san(move, game());
  out<<san<<" ";
  //ttable.printScore(out);
  //out<<" ";
  move->makeOn(game());
  printPV(out, depth + 1);
  move->takeBackOn(game());
};

bool
HashedAlphaBeta::nullMoveCutOff(SearchParameters& param)
{
  
  Score& alpha(param.alpha);
  Score& beta(param.beta);
  Score& result(param.max);
  int& depth(param.depth);
  game().doNullMove();
  mNodesSearched ++;
  nullMoveDepths.push(depth);
  //   doNullMove = false;
  Score nullMoveScore = recursiveSearch(depth-2, propagate(beta),
					Score(propagate(alpha)));
  doNullMove = true;
  nullMoveScore = backPropagate(nullMoveScore);
  nullMoveDepths.pop();
  game().takeBackNullMove();
  if (nullMoveScore >= beta){
    result = nullMoveScore;
    return true;
  }
  return false;
}

bool
HashedAlphaBeta::shouldCheckNullMove( SearchParameters& param)
{
  return (doNullMove &&(nullMoveDepths.empty() ||  
			param.depth < nullMoveDepths.top()-1) &&
	  param.depth >= 2 && 
	  ! game().isInCheck(game().colorToMove()));
};

bool 
HashedAlphaBeta::cutOff(SearchParameters& param)
{
  Score& alpha(param.alpha);
  Score& beta(param.beta);
  Score& result(param.max);
  int& depth(param.depth);
  if (ttable.cutsOff(depth, alpha, beta, result)){
    return true;
  }
  if (depth <= 0){
    result =  staticEvaluation(alpha,beta);
    return true;
  }

  if (shouldCheckNullMove(param)) 
    return nullMoveCutOff(param);
  return false;
};

void 
HashedAlphaBeta::finishNode(SearchParameters& param)
{
  if (param.alpha < param.max)
    ttable.storeExactScore(param.max, param.depth, param.bestMove);
  else
    ttable.storeUpperBound(param.max, param.depth, param.bestMove);
};

void
HashedAlphaBeta::processCutOff(int depth, Score result,
			       SmartPointer<Move> bestMove)
{
  ttable.storeLowerBound(result, depth, bestMove);
};
void 
HashedAlphaBeta::failHigh(int depth, Score score,
		    SmartPointer<Move> bestMove)
{
  ttable.storeLowerBound(score, depth, bestMove);
};

void
HashedAlphaBeta:: internalIterativeDeepening(SearchParameters& parameters)
{
  if (! ttable.isValid() && parameters.depth > 2)
    recursiveSearch(parameters.depth-2, parameters.alpha, parameters.beta);
};

HashedAlphaBeta::Score
HashedAlphaBeta::initialScore(SearchParameters& parameters)
{
  internalIterativeDeepening(parameters);
  if (! ttable.isValid())
    return Evaluation::mate();	
  SmartPointer<Move> hashedMove(ttable.bestMove());
  if (!hashedMove->isLegal(game()))
    {
      return Evaluation::mate();
    }
  if (ttable.depth() >= parameters.depth)
    parameters.alpha = std::max(parameters.alpha, ttable.lowerBound());
  hashedMove->makeOn(game());
  if (movedIntoCheck())
    {
      hashedMove->takeBackOn(game());
      return Evaluation::mate();
    }
  int newDepth = nextDepth(parameters);
  parameters.max = recursiveSearch(newDepth, 
				   propagate(parameters.beta),
				   propagate(parameters.alpha));
  parameters.max = backPropagate(parameters.max);
  hashedMove->takeBackOn(game());
  if (parameters.max >= parameters.beta)
    processCutOff(parameters.depth, parameters.max, hashedMove);
  parameters.bestMove = hashedMove;
  return parameters.max;
};

void
HashedAlphaBeta::printFullPV( Score result)
{
  std::cout<<"\t"<<result<<"  ";
  mBestMove->takeBackOn(game());
  SanNotation san(mBestMove, game());
  std::cout<<"1.";
  int pvDepth = 1;
  if (game().colorToMove()->isBlack()){
    std::cout<<"..";
    pvDepth = 2;
  }
  std::cout<<" ";
  san.printOn(std::cout);
  mBestMove->makeOn(game());
  
  std::cout<<" ";
  printPV(std::cout, pvDepth);
  
  
	
};

void
HashedAlphaBeta::setGame(Game& g)
{
  ttable.stopObserving();
  ttable.clear();
  AlphaBetaWithQSearch::setGame(g);
  mBestMove = 0;
  ttable.startObserving(&g);
};

std::vector<SmartPointer<Move> >
HashedAlphaBeta::completePV( int depth )
{

  //  std::cout<<"complete pv, depth "<<depth<<std::endl;
  SmartPointer<Move> saveBestMove = bestMove();
  Score saveScore = score();
  int saveLastDepth = getSearchDepth();
  std::vector<SmartPointer<Move> > pv;
  int maxDepth = depth;
  //  if (ttable.isValid())
  //{
  //  maxDepth = ttable.depth();
  //  std::cout<<"ttable depth: "<<maxDepth<<std::endl;
  //}
  for (int depth = maxDepth; depth > 0;)
    {
      search(depth);
      if (! bestMove())
	{
	  break;
	}
      pv.push_back(bestMove());
      SanNotation san(pv.back(), game());
      pv.back()->makeOn(game());
      depth = nextDepth(depth);
    }
  for(;;)
    {

      qsearch->search(100);
      if (!qsearch->bestMove())
	break;
      pv.push_back(qsearch->bestMove());
      qsearch->bestMove()->makeOn(game());
    };
  
  for (int i = pv.size()-1; i >=0; i--)
    pv[i]->takeBackOn(game());
  
  mBestMove = saveBestMove;
  mScore = saveScore;
  searchDepth = saveLastDepth;
  return pv;
}

void
HashedAlphaBeta::printCompletePV(int maxDepth)
{
  printCompletePV(maxDepth, std::cout);
};

void
HashedAlphaBeta::printCompletePV(int maxDepth, std::ostream& out)
{

  SmartPointer<Move> saveBestMove = bestMove();
  Score saveScore = score();
  std::vector<SmartPointer<Move> > pv = completePV(maxDepth);
  int moveCounter = 2;
  if (game().colorToMove()->isBlack())
    {
      out<<"1... ";
      moveCounter = 3;
    };
  for (int i = 0; i < pv.size(); i++)
    {
      if (moveCounter % 2 == 0)
	out<<moveCounter/2<<". ";
      moveCounter++;
      SanNotation san(pv[i], game());
      out<<san<<" ";
      pv[i]->makeOn(game());

    };
  //  out<<eval->score();
  for (int i = pv.size()-1; i >= 0; i--)
    pv[i]->takeBackOn(game());

  mBestMove = saveBestMove;
  mScore = saveScore;
};

void
HashedAlphaBeta::clearTable()
{
  ttable.clear();
};

int
HashedAlphaBeta::getSearchDepth() const
{
  return searchDepth;
};
