/***************************************************************************
                          QuiescenceSearch.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/QuiescenceSearch.h>
# include "Moves/Move.h"
# include "Game/Game.h"
# include "Game/Evaluation.h"
# include <Directions/Direction.h>
# include <vector>
# include <algorithm>
# include <functional>
using namespace Alice;
class MoveComp//: public std::greater<SmartPointer<Move> >
{
public:
  MoveComp(const Board& board): mBoard(board){};
  bool operator()(const SmartPointer<Move>& move1,
		const SmartPointer<Move>& move2)
  {
    //move1.checkValidity();
    //move2.checkValidity();
    if(mBoard.at(move1->source())->basicValue() <
       mBoard.at(move2->source())->basicValue())
      return true;
    return (mBoard.at(move1->destination())->basicValue() >
	    mBoard.at(move2->destination())->basicValue());
  }
private:
  const Board& mBoard;
};
/*
template void std::list<Alice::SmartPointer<Alice::Move>, std::allocator<Alice::SmartPointer<Alice::Move> > >::template sort<MoveComp>(MoveComp);
template void std::list<Alice::SmartPointer<Alice::Move>, std::allocator<Alice::SmartPointer<Alice::Move> > >::template merge<MoveComp>(std::list<Alice::SmartPointer<Alice::Move>, std::allocator<Alice::SmartPointer<Alice::Move> > >&, MoveComp);
*/
QuiescenceSearch::QuiescenceSearch(Game& game, Evaluation* evaluation):
  AlphaBeta(game),
  eval(evaluation)
{
};

QuiescenceSearch::~QuiescenceSearch()
{};

void
QuiescenceSearch::search(int depth)
{
  mBestMove = 0;
  mScore = recursiveSearch(100, Score(-32000), Score(32000));
};
inline
bool noCapture(SmartPointer<Move>& r)
{
	return !(r->isCapture());
};

bool
QuiescenceSearch::generateMoves(MoveList& moves)
{
  game().pseudoLegalMoves(moves, true);
  
  // TODO We use a stable sort here, since the std::sort function
  // coming with g++ 3.3.3 and the SmartPointer class appear to be
  // incompatible; it's not clear yet where the bug is.
  std::stable_sort(moves.begin(), moves.end(), MoveComp(game().board()));
  return true;
};

AlphaBeta::Score
QuiescenceSearch::initialScore( Score alpha, Score beta )
{
  Evaluation* e = getEvaluation();
  return e->boundedScore( alpha, beta );
};


AlphaBeta::Score
QuiescenceSearch::recursiveSearch(int depth, Score alpha, Score beta)
{
  Score result(0);
  SearchParameters param(depth, Evaluation::mate(), alpha, beta);
  if (cutOff(param))
    return result;
  Score init = initialScore( alpha, beta );
  Score& max = param.max;
  max = init;
  if (max >= beta)
    return max;
  Score localAlpha(std::max(alpha,max));
  MoveList moves;
  bool stalemate(!generateMoves(moves));
  SmartPointer<Move> bestMove;
  for (MoveIterator it = moves.begin(); it != moves.end(); ++ it) {
    mNodesSearched ++;
    const Square source = (*it)->source();
    const Piece* ownPiece = game().board().at(source);
    const Square destination = (*it)->destination();
    const Score own = getEvaluation()->pieceValue(ownPiece);
    const Piece* otherPiece = game().board().at(destination);
    const Score other = getEvaluation()->pieceValue(otherPiece);
    
    if (init + other < max)
      continue;
    makeMove(it);
    if (movedIntoCheck()){
      takeBack(it); 
      continue;
    }
    if (stalemate){
      stalemate = false;
      bestMove = *it;

    }
    bool doSEE = true;
    if (init + other - own > beta)
      doSEE = false;
    
    if (doSEE && ! staticExchangeEvaluation((*it)->destination(), own, other))
      {
	takeBack(it);
	continue;
      }
    Score result = recursiveSearch(depth-1,
				   propagate(beta),
				   propagate(localAlpha));
    result = backPropagate(result);
    if (result >= beta)
      {
	takeBack(it);
	failHigh(depth, result, *it);
	return result;
      }
    if (result > max) 
      {
	max = result;
	bestMove = *it;
      
      }
    localAlpha = std::max(localAlpha, max);
    takeBack(it);
  } // for it
  if (stalemate) {
    if (game().isInCheck(game().colorToMove()))
      return Evaluation::mate();
    else return Evaluation::stalemate();
  }
  finishNode(param);
  mBestMove = bestMove;
  return max;
};

class
SEESort
{
public:
  SEESort( const Game* g, const Evaluation* e)
    : game( g ),
      eval(e)
  {};
  bool operator()(const Square& sq1, const Square& sq2)
  {
    Evaluation::Score score1 = eval->pieceValue(game->board().at(sq1));
    Evaluation::Score score2 = eval->pieceValue(game->board().at(sq2));
    return score1 < score2;
  };
private:
  const Game* game;
  const Evaluation* eval;
};

bool
QuiescenceSearch::staticExchangeEvaluation(const Square& target,
					   Score own, Score other)
{
  //std::cout<<"SEE"<<std::endl;
  //game().board().displayOn(std::cout);
  std::list<Square> ownAttackers;
  std::list<Square> otherAttackers;
  const std::list<Direction*>& allDirections=Direction::allInstances();
  for (std::list<Direction*>::const_iterator dir = allDirections.begin(); 
       dir != allDirections.end();  ++ dir) 
    {
      Square blocked((*dir)->blockedSquareFrom(target, game().board()));
      if (!blocked.isValid())
	continue;
      const Piece* attacker=game().board().at(blocked);
      if (!attacker->attacks(*dir, blocked, target))
	continue;
      //std::cout<<"found attacker "<<attacker->forsytheLetter()<<std::endl;
      if (attacker->color() == game().colorToMove())
	otherAttackers.push_front(blocked);
      else
	ownAttackers.push_front(blocked);
    }
  SEESort sorter(&game(), getEvaluation());
  ownAttackers.sort(sorter);
  otherAttackers.sort(sorter);
  std::stack<Score> scores;
  //scores.push(other);
  //std::cout<<"pushing "<<other<<std::endl;
  scores.push(own);
  //std::cout<<"pushing "<<own<<std::endl;
  const Color* ownColor = game().colorToMove()->otherColor();
  for(;;) {
    if (otherAttackers.empty())
      break;
    const Square attacker = otherAttackers.front();
    otherAttackers.pop_front();
    Score pieceValue = 
      getEvaluation()->pieceValue(game().board().at(attacker));;
    //std::cout<<"pushing "<<pieceValue<<std::endl;
    scores.push(pieceValue);
    const Direction* backward = &target.directionTo(attacker);
    const Square nextAttacker =
      backward->blockedSquareFrom(attacker, game().board()); 
    if (nextAttacker.isValid())
      {
	
	const Piece* p=game().board().at(nextAttacker);
	//std::cout<<"found attacker "<<p->forsytheLetter()<<std::endl;
	if (p->movesInDirection(&nextAttacker.directionTo(attacker)))
	{
	  if (p->color() == ownColor)
	    {
	      ownAttackers.push_front(nextAttacker);
	      ownAttackers.sort(sorter);
	    }
	  else
	    {
	      otherAttackers.push_front(nextAttacker);
	      otherAttackers.sort(sorter);
	    }
	}
      };
    std::swap(otherAttackers, ownAttackers);
    ownColor = ownColor->otherColor();
  }
  scores.pop();
  //std::cout<<"score size: "<<scores.size()<<std::endl;
  Score max(0);
  while ( scores.size() ) {
    //std::cout<<scores.top()<<"-"<<max<<"="<<scores.top()-max<<std::endl;
    max = Score(std::max(Score(scores.top()-max), Score(0)));
    scores.pop();
    //std::cout<<"max: "<<max<<std::endl;
  };
  //std::cout<<"other: "<<other<<std::endl;
  return max <= other;
};

Evaluation*
QuiescenceSearch::getEvaluation() const
{
  assert(eval != 0);
  return eval;
};

void
QuiescenceSearch::setEvaluation(Evaluation* ev)
{
  eval = ev;
};
