hash.h

Go to the documentation of this file.

#pragma once

#include "utils.h"
#include <map>
#include <list>

using std::map;
using std::list;

typedef pair<u64, int>  PositionPair;
typedef map<u64, int>   PositionMap; 

//random initialization for hash-like structures
u64 getRandomU64();

//corressponds to maximum depth of UCT tree (in levels ~ moves) 
#define MAX_LEVELS 50

template<typename T> class HashTable
{
  protected:
    map <u64, T> table; 

  public:
    
    HashTable()
    {
      table.clear();
    }

    //--------------------------------------------------------------------- 
    
    void clear()
    {
      table.clear();
    }

    //--------------------------------------------------------------------- 
    
    bool isEmpty()
    {
      return table.empty();
    }

    //--------------------------------------------------------------------- 
    
    bool hasItem(u64 key)
    {
      if (table.find(key) != table.end()) 
        return true;
      return false;
    }

    void insertItem(u64 key, T item)
    {
      table[key] = item;
    }

    bool loadItem(u64 key, T& item)
    {
      if (hasItem(key)){
        item = HashTable<T>::table[key];
        return true;
      }
      return false;
    }
};

template<typename T> class HashTableBoard : public HashTable<T>
{
  public:
    HashTableBoard(): HashTable<T>()
    {
      playerSignature_[0] = getRandomU64();
      playerSignature_[1] = getRandomU64(); 
      for (int i = 0; i < MAX_LEVELS; i++){
        levelSignature_[i] = getRandomU64();
      }
    }

    //--------------------------------------------------------------------- 

    bool hasItem(u64 key, uint playerIndex, uint level=0)
    {
      assert(playerIndex == 0 || playerIndex == 1);
      key ^= playerSignature_[playerIndex];
      key ^= levelSignature_[level % MAX_LEVELS]; 
      return HashTable<T>::hasItem(key);
    }

    //--------------------------------------------------------------------- 

    void insertItem(u64 key, uint playerIndex, T item, uint level=0)
    {
      assert(playerIndex == 0 || playerIndex == 1);
      key ^= playerSignature_[playerIndex];
      key ^= levelSignature_[level % MAX_LEVELS]; 
      HashTable<T>::insertItem(key, item);
    }

    //--------------------------------------------------------------------- 

    bool loadItem(u64 key, uint playerIndex, T& item, uint level=0)
    {
      assert(playerIndex == 0 || playerIndex == 1);
      key ^= playerSignature_[playerIndex];
      key ^= levelSignature_[level % MAX_LEVELS]; 

      return HashTable<T>::loadItem(key, item);
    }

  protected:
    u64 playerSignature_[2];
    u64 levelSignature_[MAX_LEVELS];

};

class ThirdRep: public HashTableBoard<int>
{
        public:
    ThirdRep(): HashTableBoard<int>()
    {
      playerSignature_[0] = getRandomU64();
      playerSignature_[1] = getRandomU64(); 
    }

    void print() { 
      cerr << playerSignature_[0] << " | " << playerSignature_[1] << "|" << isEmpty() << endl; 
    }
    void  update(u64 key, uint playerIndex );

    bool  isThirdRep(u64 key, uint playerIndex ); 
  protected:
    u64 playerSignature_[2];
}; 

extern ThirdRep thirdRep;

//forward declaration
class Node; 

typedef list<Node*> NodeList;

//forward declaration
class ttItem;

//typedef map<u64, Node*> TTpair;
//typedef map<u64, Node*> TTmap;

typedef HashTableBoard<NodeList *> TT;

typedef HashTable<float> EvalTT;

---