Module pleco::tools::tt

Module for the TranspositionTable, a type of hash-map where Zobrist Keys map to information about a position.

A TranspositionTable is a structure to quickly lookup chess positions and determine information from them. It maps from Board positions to information such as the evaluation of that position, the best move found so far, the depth that move was found at, etc.

Specifically, a TranspositionTable maps from a u64 to an Entry.

This is a lock-free table, able to be concurrently accessed by multiple threads quickly. However, there is still a risk of collisions & over-writes when using this with multiple threads. Furthermore, Keys (generated by a zobrist hash) are not guaranteed to uniquely map to a specific chess position, and unique keys are not guaranteed to map to unique buckets inside the table. The chances of collision are extremely low, but it's still something to take into account when using the transposition table.

Examples

Here, we create a new TranspositionTable with 4,000 entries, and search for a key. Because this table is empty, found should return false. Now, we insert the data for an Entry, and then search again for the key. Now, found will be true, and we'll end up with the data we entered.

let tt = TranspositionTable::new_num_entries(40000);
let prng = PRNG::init(932445561);

let key: u64 = prng.rand();
let (found, entry): (bool, &mut Entry) = tt.probe(key);
assert!(!found);
entry.place(key, BitMove::new(0x555), 3, 4, 3, NodeBound::Exact);
let (found, entry) = tt.probe(key);
assert!(found);

Structs

Cluster	Structure containing multiple Entries all mapped to by the same zobrist key.
Entry	Structure defining a singular Entry in a table, containing the BestMove found, the score of that node, the type of Node, depth found, as well as a key uniquely defining the node.
NodeTypeTimeBound	Abstraction for combining the 'time' a node was found alongside the NodeType.
TranspositionTable	Structure for representing a TranspositionTable. A Transposition Table is a type of HashTable that maps Zobrist Keys to information about that position, including the best move found, score, depth the move was found at, and other information.

Enums

NodeBound

Designates the type of Node in the Chess Search tree. See the ChessWiki for more information about PV Node types and their use.

Constants

CLUSTER_SIZE	Number of Entries per Cluster.
NODE_TYPE_MASK	BitMask for the retrieving a NodeTypeTimeBound's [NodeType].
TIME_MASK	BitMask for the NodeTypeTimeBound's time data.

Type Definitions

Key