//-*-c++-*-
/***************************************************************************
                          TranspositionTable.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.                                   *
 *                                                                         *
 ***************************************************************************/
//-*-c++-*-

# ifndef TranspositionTable_h
# define TranspositionTable_h
# include <iostream>
# include "Game/GameObserver.h"
# include "TranspositionTable/TableEntry.h"
# include "TranspositionTable/HashTable.h"
# include <Color.h>
namespace Alice 
{
class Piece;
/** stores information about previously visited nodes.
 *
 * This is implemented as a hash table. While observing a game,
 * the ttable constantly updates a hash code for the current
 * position.
 *
 * To deal with collisions, the following policy is currently used:
 * There are two tables of equal size. In the first table items are
 * stored according to search depth; i.e., a nodes that has been
 * searched deeper overwrites other nodes. If an item cannot be
 * stored in this first table, it is written into the second one,
 * no matter what it overwrites. This helps to get some "local"
 * information for short transpositions, which are forgotten
 * soon after.	
 */
class TranspositionTable
  : public HashTable
{
public:
  TranspositionTable(int bits=16);
  virtual ~TranspositionTable();
  void storeExactScore(Evaluation::Score score, int depth, 
		       SmartPointer<Move> bestMove);
  void storeUpperBound(Evaluation::Score score, int depth, 
		       SmartPointer<Move> bestMove);
  void storeLowerBound(Evaluation::Score score, int depth, 
		       SmartPointer<Move> bestMove);
  bool cutsOff(int depth, Evaluation::Score alpha,
	       Evaluation::Score beta, Evaluation::Score& result) const;

  Evaluation::Score score() const;
  bool isValid() const;
  SmartPointer<Move> bestMove() const;
  void printInfo()
    {
      std::cout<<requests<<" requests, "
	       <<successes<<" successes"<<std::endl;
    };
  void print(std::ostream& out);
  void printScore(std::ostream& out) const
    {
      currentEntry->printScore(out);
    };
  void clear();
  
  void startObserving(Game*);
  Evaluation::Score lowerBound() const
  {
    return currentEntry->score();
  }
  int depth() const
  {
    return currentEntry->depth();
  };
protected:
private:
  const TableEntry& firstEntry() const;
  const TableEntry& secondEntry() const;
  TableEntry& firstEntry();
  TableEntry& secondEntry();
  std::vector<std::pair<TableEntry,TableEntry> > entries;
  std::vector<TableEntry> secondEntries;
  mutable bool useSecond;
  mutable const TableEntry* currentEntry;
  mutable int requests;
  mutable int successes;

};

};// namespace Alice
# endif // TranspositionTable_h
