# include <Game/Game.h>
# include <Game/PositionalEvaluation.h>
# include <Moves/Move.h>
# include <CpuTimer.h>
# include <Algorithms/QuiescenceSearch.h>
# include <list>
# include <cmath>
# include <algorithm>
# include <functional>
# include <numeric>
# include <Moves/SanNotation.h>
# include <TranspositionTable/TranspositionTable.h>
using namespace Alice;
typedef std::list<Evaluation::Score> Options;
typedef std::list<Options> OptionsList;



Game g;
const Evaluation::Score delta = 500;
PositionalEvaluation eval;
QuiescenceSearch qsearch(g, &eval);
int gm = 1;
int nodes = 0;
int maximalDepth = 0;
TranspositionTable ttable;

double S(int k)
{
  return 1;
  const double minIncrement = .5;
  const double b = 30;
  if (k > 25)
    return 1;
  return 1.0-std::pow((b-k-1)/b, gm)*(1-minIncrement);
};

double maxDepthPly(const Options& options, Evaluation::Score bound)
{

  int k = std::count_if(options.begin(), options.end(), 
			std::bind2nd(std::greater<Evaluation::Score>(), bound));
  return S(k);
}

double maxDepth(const OptionsList& options, Evaluation::Score v)
{
  double result = 0;
  Evaluation::Score bound = v-delta;
  for (OptionsList::const_iterator it = options.begin();
       it != options.end(); ++ it)
    result += maxDepthPly(*it, bound);
  return result;
};

double minDepthPly(const Options& options, Evaluation::Score bound)
{

  int k = std::count_if(options.begin(), options.end(), 
			std::bind2nd(std::less<Evaluation::Score>(), bound));
  return S(k);
};



double minDepth(const OptionsList& options, Evaluation::Score v)
{
  double result = 0;
  Evaluation::Score bound = v+delta;
  for (OptionsList::const_iterator it = options.begin();
       it != options.end(); ++ it)
    result += minDepthPly(*it, bound);
  return result;
};


struct ConspiracyParameters
{
  Evaluation::Score alpha;
  Evaluation::Score beta;
  double dmax;
  double dmin;
  OptionsList& maxOptions;
  OptionsList& minOptions;
  int realDepth;
  // constructor
  ConspiracyParameters(Evaluation::Score a,
		       Evaluation::Score b,
		       double dx,
		       double dn,
		       OptionsList& maxOpt,
		       OptionsList& minOpt,
		       int depth=0)
    : alpha(a),
      beta(b),
      dmax(dx),
      dmin(dn),
      maxOptions(maxOpt),
      minOptions(minOpt),
      realDepth(depth)
  {};
};


bool 
terminate(Evaluation::Score v,
	  Evaluation::Score alpha,
	  Evaluation::Score beta,
	  double dmax,
	  double dmin,
	  const OptionsList& maxOptions,
	  const OptionsList& minOptions)
{
  bool result;
  if (v >= beta)
    return maxDepth(maxOptions, beta) > dmax;
  //    result =  Max >= dmax;
  else if (v < alpha)
    return minDepth(minOptions, alpha) > dmin;
  //    result =  Min >= dmin;
  else
    result = (maxDepth(maxOptions, v) >= dmax) &&
      (minDepth(minOptions, v) >= dmin);
  return result;
};

bool
terminate(Evaluation::Score v, const ConspiracyParameters& param)
{
  return terminate( v,
		    param.alpha,
		    param.beta,
		    param.dmax,
		    param.dmin,
		    param.maxOptions,
		    param.minOptions );
};

SmartPointer<Move> solution;

Evaluation::Score 
abc(Evaluation::Score alpha,
    Evaluation::Score beta,
    double dmax,
    double dmin,
    OptionsList& maxOptions,
    OptionsList& minOptions,
    int realDepth=0);
Evaluation::Score
abc( ConspiracyParameters& param );



Evaluation::Score 
abc(Evaluation::Score alpha,
    Evaluation::Score beta,
    double dmax,
    double dmin,
    OptionsList& maxOptions,
    OptionsList& minOptions,
    int realDepth)
{
  ConspiracyParameters param( alpha, beta, 
			      dmax, dmin,
			      maxOptions, minOptions,
			      realDepth );
  return abc(param);
};
void
generateOptions(ConspiracyParameters& param,
		MoveList& moves)
{
  
  param.maxOptions.push_front(Options());
  Options& siblingOptions = param.maxOptions.front();
  for (MoveList::iterator it = moves.begin();
       it != moves.end(); ++ it)
    {
      (*it)->makeOn(g);
      if (! g.isInCheck(g.colorToMove()->otherColor()))
	siblingOptions.push_back(qsearch.recursiveSearch(100, 
							 param.alpha, 
							 param.beta));
      (*it)->takeBackOn(g);
    };
};

Evaluation::Score 
abc( ConspiracyParameters& param )
{
  OptionsList& maxOptions(param.maxOptions);
  int realDepth(param.realDepth);

  SmartPointer<Move> bestMove;
  maximalDepth = std::max(maximalDepth, param.realDepth);
  nodes ++;
  Evaluation::Score v = 
    qsearch.recursiveSearch(100, param.alpha, param.beta);
  if (terminate(v, param))
    {
      return v;
    }
  MoveList moves;
  g.pseudoLegalMoves(moves);
  if (ttable.isValid())
    {
      SmartPointer<Move> hashedMove = ttable.bestMove();
      for (MoveList::iterator it = moves.begin();
	   it != moves.end();
	   ++ it)
	if (**it == *hashedMove)
	  {
	    moves.erase(it);
	    break;
	  }
      moves.push_front(hashedMove);
    }
  
  generateOptions( param, moves );
  // perform negamax search
  v = param.alpha;
  bool stalemate = true;
  ConspiracyParameters nextParam(-param.beta, -param.alpha,
				 param.dmin, param.dmax,
				 param.minOptions, maxOptions,
				 param.realDepth + 1);
  for (MoveList::iterator it = moves.begin();
       it != moves.end(); ++ it)
    {
      if (realDepth == 0)
	{
	  // std::cout<<"."<<std::flush;
	  SanNotation san(*it, g);
	  std::cout<<"making "<<san<<std::endl;
	}
      (*it)->makeOn(g);
      
      if ( g.isInCheck(g.colorToMove()->otherColor()))
	{
	  (*it)->takeBackOn(g);
	  continue;
	}
      
      Evaluation::Score result = -abc(nextParam);
      if (result > v)
	{
	  v = result;
	  bestMove = *it;
	  nextParam.beta = -v;
	}
      stalemate = false;
      (*it)->takeBackOn(g);
      if (realDepth == 0)
	{
	  // std::cout<<"."<<std::flush;
	  SanNotation san(*it, g);
	  std::cout<<"result: "<<v<<std::endl;
	  std::cout<<"max depth: "<<maximalDepth<<std::endl;
	  std::cout<<"taking back "<<san<<std::endl;
	}
      if (v >= param.beta)
	break;
    }
  maxOptions.pop_front();
  if (stalemate)
    {
      if (g.isInCheck(g.colorToMove()))
	return Evaluation::mate();
      else
	return 0;
    }
  if (v > param.alpha)
    {
      ttable.storeExactScore(v, 100-param.realDepth, bestMove);
    }
  if (realDepth == 0)
    {
      solution = bestMove;
    }
  
  return v;
};

int main( int argc, char* argv[])
{
  OptionsList maxOptions;
  OptionsList minOptions;
  if (argc > 1)
    {
      std::string forsythe(argv[1]);
      g.forsytheString(forsythe);
    };
  eval.startObserving(&g);
  ttable.startObserving(&g);
  gm = 10;
  double increment = S(2)/2;
  for (double d = .1; d <= 2; d+= increment)
    {

      nodes = 0;
      CpuTimer timer;
      ConspiracyParameters param(-20000, 20000, d,d, maxOptions, minOptions,0);
      Evaluation::Score result = abc(param);
      std::cout<<std::endl;
      std::cout<<"depth:  "<<d<<std::endl;
      std::cout<<"result: "<<result<<std::endl;
      SanNotation san(solution, g);
      std::cout<<"best:   "<<san<<std::endl;
      std::cout<<"nodes:  "<<nodes<<std::endl;
      std::cout<<"time:   "<<timer.age()<<std::endl;
      std::cout<<"nodes/sec: "<<nodes/timer.age()<<std::endl;
      std::cout<<"qnodes:    "<<qsearch.nodesSearched()<<std::endl;
      std::cout<<"max depth: "<<maximalDepth<<std::endl;
    }
      
};
