Hello. Sorry about the length of this post. I am trying to implement a hash
table for my chess program, and decided to try using the VC++ . NET
(Dinkumware) version of hash_map.
The role of the hashtable is to store HashEntry objects, which contain
information about chess positions.
A BitBoard is just an __int64, and this is used to determine the hash key.
I have not shown the definition of class ChessPosition, but all you need to
know is that it contains a number of BitBoards as members. The Member 'A' is
used to create the key.
All of this seems to work quite well (and fast!), but I have a few
questions:
1. I am still confused about the correct way to use hash_compare. The
documentation suggests that you either make your own, or derive your own
class from hash_compare and selectively override functions as required (eg
the hash function). I have gone for the first option, and called it
MyHashCompare . Can you please tell me if I have done anything wrong ?
2. As I insert items, the hash_multimap just gets bigger and BIGGER, and
BIGGER !! (it is eating about 3 megs/second on my system). Is there any way
to put a limit on the size of the hash_multimap, say limiting it 256 MB ? If
not, is it more appropriate to simply use a container with a fixed size. (A
static size would be totally acceptable)
3. When retrieving HashEntry's, another part of my program (the search()
function) expects to get a pointer to a HashEntry, which is why I have
really ugly code like:
pH=&((*it).seco nd);
Is there a better way of interfacing with the rest of the program, and if
so, what function prototype would you recommend for LookupHash() ?
// hash.h:
#ifndef _HASH_H
#define _HASH_H 1
#include <hash_map>
#include "movegen.h"
using namespace std;
size_t Hash(BitBoard B);
enum HashEntryFlags
{
hashfVALUNKNOWN ,
hashfEXACT,
hashfALPHA,
hashfBETA
};
class HashEntry
{
public:
HashEntry()
{
Flags=hashfVALU NKNOWN;
}
ChessPosition P;
int Depth;
HashEntryFlags Flags;
int Value;
Move bestMove;
};
class MyHashCompare
{
public:
enum
{
// parameters for hash table
bucket_size = 4, // 0 < bucket_size
min_buckets = 8 // min_buckets = 2 ^^ N, 0 < N
};
size_t operator()(cons t BitBoard& A) const
{
// hash function. Thanks to Thomas Wang for this
// (http://www.concentric.net/~Ttwang/tech/inthash.htm)
BitBoard B(A);
B += ~(B << 32);
B ^= (B >> 22);
B += ~(B << 13);
B ^= (B >> 8);
B += (B << 3);
B ^= (B >> 15);
B += ~(B << 27);
B ^= (B >> 31);
return static_cast<siz e_t>(B);
}
bool operator()(cons t BitBoard A, const BitBoard B) const
{
// Used for determining order when keys are the same
return (A<B);
}
};
typedef hash_multimap<B itBoard,HashEnt ry,MyHashCompar e> HashTable;
bool InsertHash(Hash Table& rT, const HashEntry& rH);
const HashEntry* LookupHash(cons t ChessPosition& rP, const HashTable& rT);
#endif
// hash.cpp:
#include "hash.h"
bool InsertHash(Hash Table& rT, const HashEntry& rH)
{
rT.insert(HashT able::value_typ e((rH.P.A) /* BitBoard 'A' of Position used
as key */,rH));
return true;
}
const HashEntry* LookupHash(cons t ChessPosition& rP, const HashTable& rT)
{
// Define a pair of iterators, and get an equal range
pair<HashTable: :const_iterator ,HashTable::con st_iterator> p=
rT.equal_range( rP.A);
// Return first entry with a matching Position
const HashEntry* pH=NULL;
for(HashTable:: const_iterator it = p.first; it != p.second; ++it)
{
if( ((*it).second.P ) == rP )
{
pH=&((*it).seco nd);
break;
}
}
return pH;
}
table for my chess program, and decided to try using the VC++ . NET
(Dinkumware) version of hash_map.
The role of the hashtable is to store HashEntry objects, which contain
information about chess positions.
A BitBoard is just an __int64, and this is used to determine the hash key.
I have not shown the definition of class ChessPosition, but all you need to
know is that it contains a number of BitBoards as members. The Member 'A' is
used to create the key.
All of this seems to work quite well (and fast!), but I have a few
questions:
1. I am still confused about the correct way to use hash_compare. The
documentation suggests that you either make your own, or derive your own
class from hash_compare and selectively override functions as required (eg
the hash function). I have gone for the first option, and called it
MyHashCompare . Can you please tell me if I have done anything wrong ?
2. As I insert items, the hash_multimap just gets bigger and BIGGER, and
BIGGER !! (it is eating about 3 megs/second on my system). Is there any way
to put a limit on the size of the hash_multimap, say limiting it 256 MB ? If
not, is it more appropriate to simply use a container with a fixed size. (A
static size would be totally acceptable)
3. When retrieving HashEntry's, another part of my program (the search()
function) expects to get a pointer to a HashEntry, which is why I have
really ugly code like:
pH=&((*it).seco nd);
Is there a better way of interfacing with the rest of the program, and if
so, what function prototype would you recommend for LookupHash() ?
// hash.h:
#ifndef _HASH_H
#define _HASH_H 1
#include <hash_map>
#include "movegen.h"
using namespace std;
size_t Hash(BitBoard B);
enum HashEntryFlags
{
hashfVALUNKNOWN ,
hashfEXACT,
hashfALPHA,
hashfBETA
};
class HashEntry
{
public:
HashEntry()
{
Flags=hashfVALU NKNOWN;
}
ChessPosition P;
int Depth;
HashEntryFlags Flags;
int Value;
Move bestMove;
};
class MyHashCompare
{
public:
enum
{
// parameters for hash table
bucket_size = 4, // 0 < bucket_size
min_buckets = 8 // min_buckets = 2 ^^ N, 0 < N
};
size_t operator()(cons t BitBoard& A) const
{
// hash function. Thanks to Thomas Wang for this
// (http://www.concentric.net/~Ttwang/tech/inthash.htm)
BitBoard B(A);
B += ~(B << 32);
B ^= (B >> 22);
B += ~(B << 13);
B ^= (B >> 8);
B += (B << 3);
B ^= (B >> 15);
B += ~(B << 27);
B ^= (B >> 31);
return static_cast<siz e_t>(B);
}
bool operator()(cons t BitBoard A, const BitBoard B) const
{
// Used for determining order when keys are the same
return (A<B);
}
};
typedef hash_multimap<B itBoard,HashEnt ry,MyHashCompar e> HashTable;
bool InsertHash(Hash Table& rT, const HashEntry& rH);
const HashEntry* LookupHash(cons t ChessPosition& rP, const HashTable& rT);
#endif
// hash.cpp:
#include "hash.h"
bool InsertHash(Hash Table& rT, const HashEntry& rH)
{
rT.insert(HashT able::value_typ e((rH.P.A) /* BitBoard 'A' of Position used
as key */,rH));
return true;
}
const HashEntry* LookupHash(cons t ChessPosition& rP, const HashTable& rT)
{
// Define a pair of iterators, and get an equal range
pair<HashTable: :const_iterator ,HashTable::con st_iterator> p=
rT.equal_range( rP.A);
// Return first entry with a matching Position
const HashEntry* pH=NULL;
for(HashTable:: const_iterator it = p.first; it != p.second; ++it)
{
if( ((*it).second.P ) == rP )
{
pH=&((*it).seco nd);
break;
}
}
return pH;
}
Comment