//-*-c++-*-
/***************************************************************************
                          HashedAlphaBeta.h  -  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.                                   *
 *                                                                         *
 ***************************************************************************/
# ifndef HashedAlphaBeta_h
# define HashedAlphaBeta_h
# include "Algorithms/AlphaBetaWithQSearch.h"
# include "TranspositionTable/TranspositionTable.h"
namespace Alice
{
/** Search algorithm.
	* The performance of alpha-beta search depends greatly on move
	* ordering. If at every node we search the best move first,
	* we have to search only the theoretically minimal number of
	* nodes. On the other hand, if we search the options in a
	* worst-to-best fashion, we will have to consider every single
	* node.
	*
	* Considering the fact that the best move at a given depth has
	* a high probability of being optimal at the next depth, this
	* algorithm starts with a shallow search and performs increasingly
	* deeper searches (iterative deepening). The findings of every
	* search are stored in a TranspositionTable. Thus, when searching
	* the node, we retrieve the previously best move from the table
	* and search it first, thus reducing the tree size.
	*
	* The table has the other useful effect of detecting transpositions,
	* hence we might prune a whole subtree that has already been dealt
	* with.
	*
	*\see TranspositionTable
	*/
class HashedAlphaBeta:
  public AlphaBetaWithQSearch
{
public:
  HashedAlphaBeta(Game& game);
  virtual ~HashedAlphaBeta();
  virtual void search(int depth);
  void searchTime(double seconds);
  void searchTime(double seconds, std::ostream& log);
  void printPV(std::ostream&, int depth = 1);
  double oddBranchingFactor() const {return mOddBranchingFactor;};
  double evenBranchingFactor() const {return mEvenBranchingFactor;};
  void printInfo() 
  {
    std::cout<<nodesSearched()<<"nodes"<<std::endl;
    ttable.printInfo();
  }
  virtual void searchFixedDepth(int depth);
  void searchFixedDepth(int depth, MoveList& moves);
  void setGame(Game& g);
  void printFullPV( Score result);
  void printCompletePV(int maxDepth);
  void printCompletePV(int maxDepth, std::ostream& out);
  std::vector<SmartPointer<Move> > completePV( int depth = 0 );
  void clearTable();
  int getSearchDepth() const;
protected:
  TranspositionTable ttable;
  bool generateMoves(MoveList& moves);
  bool cutOff(SearchParameters& param);
  void finishNode(SearchParameters& param);
  void processCutOff(int depth, Score result, 
		     SmartPointer<Move> bestMove);
  void failHigh(int depth, Score score,
			SmartPointer<Move> bestMove);
  virtual Score initialScore(SearchParameters& parameters);
private: 
  std::stack<int> nullMoveDepths;
  bool doNullMove;
  double mOddBranchingFactor;
  double mEvenBranchingFactor;
  void internalIterativeDeepening(SearchParameters& parameters);
  bool nullMoveCutOff(SearchParameters& parameters);
  bool shouldCheckNullMove(SearchParameters& parameters);
  int searchDepth;
};
}; // namespace Alice
# endif // HashedAlphaBeta
