[−][src]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 |
NodeTypeTimeBound | Abstraction for combining the 'time' a node was found alongside the |
TranspositionTable | Structure for representing a |
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 |