Struct TranspositionTable

pub struct TranspositionTable<Bucket: TwoBucket = AtomicBucket> { /* private fields */ }

A Transposition Table (tt) with a fixed size, memoizing previously evaluated chess positions. The table is safely sharable between threads as immutable. Slots may be updated from an immutable reference as each slot has its own lock.

The table uses a two layer system which ensures that new entries are always inserted into the table while also allowing important entries to remain for as long as they need.

The first layer is the replacement scheme layer, which allows the user to decide when to replace the entry based on a conditional test.

The second layer is the always replace layer, which gets replaced if the first layer does not.

Example:

let tt = Arc::new(TranspositionTable::with_capacity(100));
let age = 1;
let hash = 100;
let entry = Entry::new(hash, Move::new(D2, D4, None), Cp(3), 5, NodeKind::Pv);

tt.replace(entry, age);
assert_eq!(tt.get(hash), Some(entry));

Implementations

impl TranspositionTable

Transposition Table functions that use the default generic parameter bucket.

pub fn new() -> Self

Returns a new Transposition Table using the default bucket type.

pub fn with_capacity(entry_capacity: usize) -> Self

Returns a new Transposition Table that holds entry_capacity entries using the default bucket type.

pub fn with_mb(mb: usize) -> Self

Returns a new Transposition Table with a capacity that fills given Megabytes using the default bucket type.

pub fn with_zobrist(ztable: ZobristTable) -> Self

Returns a new TranspositionTable with provided ZobristTable with pre-allocated default max capacity and default bucket type.

pub fn with_mb_and_zobrist(mb: usize, ztable: ZobristTable) -> Self

Returns a new TranspositionTable with capacity in Megabytes and a given ZobristTable using the default bucket type.

pub fn with_capacity_and_zobrist( entry_capacity: usize, ztable: ZobristTable, ) -> Self

Returns a new TranspositionTable with provided ZobristTable and capacity in entries pre-allocated using the default bucket type.

impl<Bucket: TwoBucket> TranspositionTable<Bucket>

Generic Transposition Table functions.

pub fn zobrist_table(&self) -> &ZobristTable

Returns a reference to the zobrist table.

pub fn new_in() -> Self

Returns a new TranspositionTable with a randomly generated ZobristTable and a pre-allocated default max entry capacity.

pub fn with_capacity_in(entry_capacity: usize) -> Self

Returns a new TranspositionTable with a randomly generated ZobristTable with given capacity pre-allocated, where capacity is the number of entries in table.

pub fn with_mb_in(mb: usize) -> Self

Returns a new TranspositionTable with a randomly generated ZobristTable with capacity calculated to fill given Megabytes.

pub fn with_zobrist_in(ztable: ZobristTable) -> Self

Returns a new TranspositionTable with provided ZobristTable with pre-allocated default max capacity.

pub fn with_mb_and_zobrist_in(mb: usize, ztable: ZobristTable) -> Self

Returns a new TranspositionTable with capacity in Megabytes and a given ZobristTable.

pub fn with_capacity_and_zobrist_in( entry_capacity: usize, ztable: ZobristTable, ) -> Self

Returns a new TranspositionTable with provided ZobristTable and capacity in entries pre-allocated.

pub fn capacity(&self) -> usize

Returns the capacity of entries of the TranspositionTable.

pub fn bucket_capacity(&self) -> usize

Returns the capacity of buckets in this TranspositionTable.

pub fn clear(&mut self)

Removes all items from TranspositionTable. Since the TT uniquely holds its inner vector, this operation is safely guarded by its signature &mut self, as it cannot be held by any other thread.

pub fn set_mb(&mut self, new_mb: usize) -> usize

Drops original table and allocates a new table of size new_mb. Entries in the original table are not preserved. Returns the table’s new entry capacity.

pub fn generate_hash(&self, position: &Position) -> HashKind

Generate a hash for a Position with context to this TranspositionTable. Hashes used for this table must be generated from it’s context, because a hash for any position are likely to be different between different TranspositionTables.

pub fn update_hash( &self, hash: &mut HashKind, position: &Position, move_info: MoveInfo, cache: Cache, )

Update hash for the application of a Move on Position.

pub fn update_from_hash( &self, hash: HashKind, position: &Position, move_info: MoveInfo, cache: Cache, ) -> HashKind

Generate a new hash from a Move applied to an existing Hash and Position.

pub fn hash_to_index(&self, hash: HashKind) -> usize

Convert a full hash to an index for this TranspositionTable.

pub fn contains(&self, hash: HashKind) -> bool

Returns true if a TranspositionTable bucket contains an entry with the given hash. Key collisions are expected to be rare but possible, so care should be taken with the return value.

pub fn get(&self, hash: HashKind) -> Option<Entry>

Returns Entry if hash exists in the indexed bucket, None otherwise.

pub fn replace(&self, priority_entry: Entry, age: AgeKind)

Unconditionally replace an existing item in the TranspositionTable where replace_by true would place it. Capacity of the table remains unchanged.

pub fn swap_replace(&self, priority_entry: Entry, age: AgeKind)

Move entry in priority slot to general slot then place priority_entry into priority slot.

pub fn store(&self, general_entry: Entry)

Store the entry into the index bucket’s general slot, without changing age or scheme slot.

pub fn replace_by<F>(&self, entry: Entry, age: AgeKind, should_replace: F)

where F: FnOnce(&Entry, u8, &Entry, u8) -> bool,

Attempt to insert an item into the tt depending on a replacement scheme. If the replacement scheme evaluates to true, the entry replaces the bucket priority slot. Otherwise, it is inserted into the general slot.

Closure signature: should_replace(&replacing_entry, age, &existing_priority_entry, existing_age) -> bool.

Example:

let mut tt = TranspositionTable::with_capacity(2);
assert_eq!(tt.bucket_capacity(), 1); // All hashes index same bucket.
let age = 1;

let deep_hash = 0;
let deep_ply = 10;
let deep_entry = Entry::new(deep_hash, best_move, score, deep_ply, node_kind);

let shallow_hash = 8;
let shallow_ply = 2;
let shallow_entry = Entry::new(shallow_hash, best_move, score, shallow_ply, node_kind);

fn replacement_scheme(entry: &Entry, age: u8, existing: &Entry, existing_age: u8) -> bool {
    age != existing_age || entry.ply > existing.ply
}

// Hash slot starts empty, so tt_entry replaces priority slot.
tt.replace_by(deep_entry, age, replacement_scheme);
assert_eq!(tt.get(deep_hash).unwrap(), deep_entry);

// Shallow entry does not pass replacement test, so it is placed in always slot.
tt.replace_by(shallow_entry, age, replacement_scheme);
assert_eq!(tt.get(deep_hash).unwrap(), deep_entry);
assert_eq!(tt.get(shallow_hash).unwrap(), shallow_entry);

let other_hash = 101;
let other_ply = 1;
let other_entry = Entry::new(other_hash, best_move, score, other_ply, node_kind);

// Other entry does not pass test for priority, so it replaces the always slot.
tt.replace_by(other_entry, age, replacement_scheme);
assert_eq!(tt.get(shallow_hash), None);
assert_eq!(tt.get(deep_hash).unwrap(), deep_entry);
assert_eq!(tt.get(other_hash).unwrap(), other_entry);

pub fn swap_replace_by<F>(&self, entry: Entry, age: AgeKind, should_replace: F)

where F: FnOnce(&Entry, u8, &Entry, u8) -> bool,

If entry passes the should_replace test, then the existing entry in the priority slot is moved to the general slot and new entry gets placed in the priority slot. Otherwise, the new entry is placed in the general slot.