Module recon_mcts::state_memory

Provides mixins to statically configure how each node's state is stored in memory and compared for equality.

The implementation relies on a hash table to determine whether the state of a newly created leaf node is identical to that of an existing node (effectively a transposition table). For the purpose of determining whether two game states are identical, both GameDynamics::State and GameDynamics::Player are considered.

The provided mixins configure how hash table comparisons are executed. A high-level summary of strengths of each configuration is shown in the table below. However, the decision is best made by testing the configurations to see which works best.

The following mixins are available:

GetState: store the state only for the root node and a hash for all other nodes; recompute the state for equality comparisons by traversing the tree from the root to the target node.
HashOnly: store the state only for the root node and a hash for all other nodes; rely solely on the state's hash for equality comparisons.
StoreState: store the state of all nodes.

Mixin / Strengths	Accuracy	Memory	Performance
GetState	✓	✓
HashOnly		✓	✓
StoreState	✓		✓

The mixins are used in constructing a Tree as follows:

let tree = Tree::new(game, GetState, first_player, root_state);

Structs

GetState	Slower performance but better memory efficiency for large states.
HashOnly	There's a chance of hash collision, which would mean that a parent node connects to an incorrect child node.
StoreState	Memory usage is state dependent (could use lots of storage if states are large).

Traits

StateMemory

A trait used to modify how states are stored in the transposition table. Generally for internal use.