Search Iteration Architecture

This document follows one search runtime from construction through one TreeExploration.step() iteration. It is intentionally practical: the goal is to show which layers own which responsibilities in the current implementation, not to propose a new design.

Canonical vocabulary

  • ITreeNode: the structural/navigation protocol shared by tree helpers.

  • TreeNode: the concrete structural node that stores state, parent/child links, depth, and branch-opening bookkeeping.

  • AlgorithmNode: the runtime/search wrapper around a TreeNode. It adds tree evaluation, exploration-index payloads, and optional evaluator representations.

  • direct_value: the immediate evaluator output for one node.

  • backed_up_value: the subtree-derived value propagated from children.

  • candidate value: the best currently available value, preferring backed_up_value over direct_value when both exist.

  • canonical value: the required concrete Value returned to consumers that need one; it is obtained from the current candidate value and therefore raises if no value is available yet.

  • tree evaluation: the runtime state attached to an AlgorithmNode that owns candidate/canonical value access, branch ordering, branch frontier tracking, and principal variation (PV).

  • exploration-index payload: the per-node data object stored on an AlgorithmNode for search-priority strategies.

  • selector: the object that decides which node or branch to open next.

  • opening instructor: the object that turns “open this node” into concrete branch-opening instructions.

  • runtime assembly: the internal wiring that builds a runnable search runtime from factories and strategy configuration.

Main architectural layers

Public runtime creation

anemone.factory is the canonical public entry point. create_search(...) builds a runnable TreeExploration runtime. TreeAndValueBranchSelector is the secondary convenience wrapper for callers who only want recommend(...).

Internal runtime assembly

anemone._runtime_assembly wires together the direct evaluator, tree evaluation factory, selector factory, tree factory, and tree manager. anemone.search_factory is an assembly helper, not the preferred public entry point.

Structural and runtime node layers

TreeNode owns only structural concerns. AlgorithmNode wraps it and adds runtime state. Generic tree helpers stay on ITreeNode; search logic works with AlgorithmNode.

Direct evaluation

anemone.node_evaluation.direct owns the immediate evaluator pass that fills direct_value on newly created nodes.

Tree evaluation

anemone.node_evaluation.tree owns the search-time evaluation state attached to each node: candidate/canonical value access, branch ordering, branch frontier, and PV tracking. Family-specific backup semantics are injected through backup policies.

Exploration indices

anemone.indices.node_indices defines per-node exploration payload classes. anemone.indices.index_manager chooses the update strategy and recomputes payloads across the tree.

Selector and opening flow

anemone.node_selector chooses where the search goes next. Selectors return OpeningInstructions, and the OpeningInstructor expands a selected node into the concrete branches to open. Depending on configuration, selectors may use only evaluations, or they may also consult frontier and exploration-index state.

One search iteration: step by step

The current implementation is easiest to read as this flow:

create_search(...)
  -> assemble_search_runtime_dependencies(...)
  -> create_tree_exploration(...)
  -> TreeExploration.step()
     1. choose openings
     2. expand structurally
     3. direct-evaluate new nodes
     4. propagate backup / PV / branch-order updates upward
     5. refresh exploration indices

1. Runtime creation starts at the public factory

anemone.factory.create_search(...) creates a default NodeTreeMinmaxEvaluationFactory and then delegates to create_search_with_tree_eval_factory(...). That function calls anemone._runtime_assembly.assemble_search_runtime_dependencies(...), which builds:

  • a NodeDirectEvaluator

  • a SearchFactory that can create the configured selector and per-node exploration payloads

  • an AlgorithmNodeFactory

  • a ValueTreeFactory

  • an AlgorithmNodeTreeManager

Finally, create_tree_exploration(...) builds the runtime object itself.

2. Tree creation evaluates the root before the first step

ValueTreeFactory.create(...) creates the root AlgorithmNode and immediately runs the direct evaluator on it. So the tree handed to TreeExploration already contains:

  • a structural root TreeNode

  • a runtime root AlgorithmNode

  • a tree-evaluation object

  • an exploration-index payload shell (if configured)

  • a root direct_value

This happens before the first call to TreeExploration.step().

3. The selector proposes what to open next

TreeExploration.step() starts by calling node_selector.choose_node_and_branch_to_open(...). The selector sees:

  • the current tree

  • the latest TreeExpansions log from the previous iteration

In the current implementation, selectors are often composed from:

  • an optional priority override

  • a base selector such as Uniform, RecurZipf, or Sequool

The selector decides which node to open next. The OpeningInstructor then turns that choice into concrete branches to open. With the current OpeningType.ALL_CHILDREN mode, this means “open every legal action from the selected node”.

TreeExploration then lets the stopping criterion shrink that batch if the current search budget requires it.

4. Structural expansion opens or reuses child nodes

AlgorithmNodeTreeManager.expand_instructions(...) does two things:

  • it marks the selected branches as opened in the node’s branch-frontier state

  • it delegates to TreeManager.expand_instructions(...) for structural work

TreeManager applies dynamics.step(...) for each opening instruction, then either:

  • creates a new child node via AlgorithmNodeFactory and TreeNodeFactory, or

  • reuses an existing node if the reached state already exists at that depth

Each structural change is recorded as a TreeExpansion inside a TreeExpansions log. Newly created AlgorithmNode objects already contain their tree-evaluation object and exploration-index payload object, but they have not been directly evaluated yet.

5. Direct evaluation fills direct_value on newly created nodes

AlgorithmNodeTreeManager.evaluate_expansions(...) queues each newly created node in NodeDirectEvaluator.

NodeDirectEvaluator first checks for obvious terminal outcomes on the node’s own state. Non-terminal nodes are then batch-evaluated by the configured master state evaluator. The result is written into node.tree_evaluation.direct_value.

At this point, a newly created node has immediate local evaluation data, but its ancestors have not been recomputed yet.

6. Upward propagation recomputes backed-up values

AlgorithmNodeTreeManager.update_backward(...) triggers ValuePropagator.propagate_from_changed_nodes(...) from the changed child nodes. The propagator only owns scheduling: it processes dirty ancestors in descending depth order and recomputes each dirty node from a full snapshot of its currently open children.

For each dirty ancestor, the propagator calls node.tree_evaluation.backup_from_children(...). In the default minimax path, that delegates to ExplicitTreeBackupPolicy through the configured backup policy.

7. Branch ordering and PV updates happen inside backup

The runtime loop does not update branch ordering or PV directly. That happens as part of backup:

  • the backup policy refreshes cached branch-ordering keys for the changed child branches

  • it computes the new backed_up_value

  • it updates frontier membership

  • it rebuilds or refreshes the principal variation when the best branch or a best-child PV changed

The generic mechanics live in:

  • anemone.node_evaluation.tree.node_tree_evaluation

  • anemone.node_evaluation.tree.branch_ordering_runtime

  • anemone.node_evaluation.tree.principal_variation_runtime

  • anemone.backup_policies.*

8. Optional depth metadata and exploration-index payloads are refreshed

After value propagation, TreeExploration runs two more refresh phases:

  • propagate_depth_index(...) updates descendant-depth payloads when that feature is enabled

  • refresh_exploration_indices(...) calls anemone.indices.index_manager.update_all_indices(...)

update_all_indices(...) initializes the root exploration payload, then walks the tree depth by depth. For each parent, it uses the parent’s current decision ordering to recompute child exploration data with the configured strategy. Depending on configuration, that strategy may be:

  • global-min-change

  • interval/local-min-change

  • recursive Zipf/factored-probability

  • or the null/no-op strategy

9. The next iteration sees the updated runtime state

After TreeExploration.step() finishes, the tree is richer in three ways:

  • the structure may contain newly opened children

  • direct and backed-up values may have changed

  • branch frontier, branch ordering, PV, and exploration-index payloads may have changed

The selector on the next iteration reads this updated tree. Which parts it actually uses depends on the configured selector strategy.

Where to look in the code

  • public runtime creation: anemone.factory and anemone.tree_and_value_branch_selector

  • internal wiring: anemone._runtime_assembly and anemone.search_factory

  • runtime loop: anemone.tree_exploration

  • structural vs runtime nodes: anemone.nodes.itree_node, anemone.nodes.tree_node, anemone.nodes.algorithm_node.algorithm_node

  • node creation: anemone.node_factory.algorithm_node_factory and anemone.trees.factory

  • direct evaluation: anemone.node_evaluation.direct.factory and anemone.node_evaluation.direct.node_direct_evaluator

  • tree evaluation, branch ordering, and PV: anemone.node_evaluation.tree.node_tree_evaluation, anemone.node_evaluation.tree.branch_ordering_runtime, and anemone.node_evaluation.tree.principal_variation_runtime

  • backup sequencing: anemone.backup_policies.explicit_tree and the family-specific backup policies in anemone.backup_policies

  • exploration indices: anemone.indices.node_indices and anemone.indices.index_manager.node_exploration_manager

  • selector/opening flow: anemone.node_selector.factory, anemone.node_selector.composed.composed_node_selector, and anemone.node_selector.opening_instructions

  • tree-wide structural and algorithm-aware phases: anemone.tree_manager.tree_manager and anemone.tree_manager.algorithm_node_tree_manager

Common confusions and notes

  • anemone.factory is the public entry point; anemone.search_factory is assembly infrastructure behind it.

  • TreeNode stores structure; AlgorithmNode is the object search code works with at runtime.

  • direct_value is local evaluator output, backed_up_value is subtree backup output, the candidate value is the best available one, and the canonical value is the required concrete Value returned to callers.

  • Exploration-index payloads are stored per node, but recomputation is a tree-wide strategy pass.

  • Branch ordering and PV updates are not a separate top-level runtime phase; they are triggered inside backup.

  • The search loop typically stops when the root value becomes exact, even if the root state is not terminal and some siblings remain unopened.