ZobristDistribution

Declared in astar/Distribution.h; the same class on the site of Doxygen.

template<FeatureDomain D>
class ZobristDistribution

HDA*[Z]: Zobrist hashing of the features of the state.

\( Z( s ) = R[ x_0 ] \oplus \cdots \oplus R[ x_n ] \), where \( x_0 , \ldots , x_n \) are the features of \( s \), \( R \) a table of random 64-bit strings and \( \oplus \) the exclusive or of the bits [see Zobrist, 1970, and Kishimoto, Fukunaga and Botea, AIJ 2013]. Zobrist hashing is simple tabulation hashing, which is 3-independent: it spreads the states uniformly over the workers, but nearly every successor lands on another worker than its parent.

Public Functions

inline explicit ZobristDistribution(const D &domain, std::uint64_t seed = 1)

constructor, drawing the table of D from the seed

inline std::uint64_t hash(const state_t<D> &s) const

the Zobrist hash of s

inline std::uint32_t key(const state_t<D> &s) const

the key of s, the high 32 bits of its hash

inline unsigned owner(const state_t<D> &s, unsigned p) const

the owner of s among p workers, that of its key

inline std::uint32_t key(std::uint32_t k, const state_t<D> &s, const state_t<D> &t) const

the key of t, a successor of s whose key is k

Equal to key( t ), but it reads the entries of the features that the move changes only [see IncrementalFeatureDomain].

Public Static Functions

static inline std::string name(void)

the name in the notation of Jinnai and Fukunaga