ITERSSS*
Algorithms AIMech:ITERSSSStar DRAFT
A memory-bounded solution-tree search algorithm for minimax evaluation of a finite uniform alternating game tree that controls an SSS*-style OPEN list through active and inactive entries, capacity-gated MAX-node expansion, and bound-dependent pruning and reactivation.
Identity Notes & Concept Scope
The current cohort361 prewrite comparison at base add2c806f6729c8599f4d5cfd6d75c7decde006c covered 1,243 maintained records (801 native and 442 pinned AIO), 4,927 identity-field occurrences and 3,766 normalized values. Candidate-normalized identity matches were empty. Four ignored- and hidden-inclusive fixed-string/word-boundary scans produced 6,732 occurrences across 1,557 distinct matching contents, assessed through three attributed reader scopes and exact inherited-wrapper reconstruction. ITERSSS* denotes the 1986 finite uniform alternating game-tree procedure with active/inactive OPEN entries, solution-tree pruning and memory-controlled passes. It differs from single-agent A*/IDA*/IE, MA*/MAO*/SMA*/MREC/ITS, original Stockman SSS* and the uninspected PARSSS*/MemSSS*/RecSSS*/RecDual* followups. Main911 carries the exact 1986 bibliography responsibility while retaining earlier memory-search scopes, four original references, three followup routes and three source-interface questions. Fixed-order, finite-tree, theorem-proof, tie and nonuniform-extension limits remain explicit.
Claims & Grounded Evidence
9 Claims
Mechanism
#open-entry-budget
In the source’s finite uniform alternating game-tree presentation, ITERSSS* receives an OPEN-entry budget M with M >= M0, where M0 = ceil(d/2) * (b - 1) + 1 for a MAX root, depth d and branching factor b. It initializes the root as LIVE and INACTIVE with an infinite upper-bound value and SPACE = M - 1.
Mechanism
#flag-restricted-selection
OPEN entries carry a value h, a LIVE or SOLVED status, and an ACTIVE or INACTIVE type. Selection takes the greatest h among entries whose type equals FLAG and resolves ties by lexicographically smaller Dewey codes. FLAG begins INACTIVE, switches to ACTIVE on a capacity-blocked MAX expansion or absence of an eligible entry, and does not switch back.
Mechanism
#terminal-and-min-advance
A selected LIVE terminal is assigned min(h, v), becomes SOLVED and ACTIVE. A selected LIVE nonterminal MIN node is replaced by its first child, which inherits h, receives LIVE status and takes the current FLAG as its type.
Mechanism
#capacity-gated-max-expansion
A selected LIVE nonterminal MAX node is replaced by all b children only when SPACE >= b - 1; the children inherit h and FLAG, and SPACE decreases by b - 1. Otherwise that node stays in OPEN as INACTIVE and FLAG becomes ACTIVE.
Mechanism
#solved-max-sibling-progression
For a selected SOLVED nonroot MAX node, ITERSSS* removes that node and passes its h to the next sibling as LIVE and ACTIVE. After the last sibling it instead inserts the MIN parent as SOLVED and ACTIVE. The displayed branch explicitly excludes the root.
Mechanism
#solved-min-purge-and-reactivation
For a selected SOLVED MIN node x, the procedure removes other OPEN entries below its parent whose h is no greater than h(x), releasing one entry of SPACE per removal. If an inactive entry remains below that parent, it activates one at greatest depth and retains x; otherwise it replaces x by the parent as SOLVED and ACTIVE with the same h.
Mechanism
#abstract-space-bookkeeping
Under the displayed conceptual replacements, SPACE equals M minus the number of OPEN entries: initialization uses one entry, one-for-one replacements leave SPACE unchanged, MAX expansion consumes b - 1 entries, and each purge removal releases one. This describes the stable OPEN-entry bookkeeping, not a bound on total implementation memory.
Scope
#source-stated-pruning-scope
Using the paper’s solution-tree and fixed-order quantities A_L(x) and B(x), Theorem 4.4 states that A_L(x) >= B(x) is sufficient for ITERSSS* not to examine x. The paper combines this one-way condition with its specified alpha-beta pruning characterization to state inclusion of the terminal nodes examined by ITERSSS* within those examined by that comparator.
Scope
#source-stated-sss-endpoint
For the presented uniform tree, the paper states that setting M = b^ceil(d/2) yields the same operation as SSS*. This is a source-stated sufficient full-memory setting for the parameterized procedure, not a claim that it is the smallest budget producing a matching terminal count on every instance.
⚠️ Curated Limitations & Negative Results
- The detailed procedure assumes a finite, uniform, alternating MAX/MIN tree with a MAX root, fixed Dewey-code ordering, supplied terminal scores and a finite minimax value. A remark that node coding generalizes to nonuniform trees does not supply a complete variable-branch memory threshold or certify cycles, transpositions, infinite games or learned move ordering.
- The memory parameter counts OPEN entries in the stable abstract replacement model. It does not bound total bytes, priority-queue overhead, node-code storage or transient allocations. M >= M0 is a premise; no operation below that threshold or extrapolation to depth-zero and other exceptional tree shapes is certified. Informal above-threshold prose is not used to erase the inclusive formal endpoint.
- The purge and inactivesucc helper use the word successor. Reading it as descendant scope is supported by greatest-depth selection and the parent-subtree explanation, but remains a disclosed interpretation. The source does not specify a tie rule among equally deep inactive candidates; lexicographic first-selection ties do not silently fill that separate gap.
- The first helper may return null, while the case predicates and loop-termination expression refer to the selected node and its status. Safe null evaluation and short-circuit conventions require implementation choices. The null case changes FLAG; it is not an explicit general failure return or an independently proved remedy for every possible lack of active work.
- The source omits its formal proofs. It states that SSS* termination and correct root value also hold for ITERSSS*, but the SSS* one-representative-per-solution-tree lemma does not carry over to the ACTIVE subset. Neither the local SPACE arithmetic nor the purge-selection argument replaces a complete proof of ITERSSS* correctness or liveness.
- Theorem 4.4 gives only a sufficient ITERSSS* non-examination condition. The two-sided SSS* iff characterization, its strict right-hand comparison and an exact memory-dependent pruning law are not transferred. The alpha-beta terminal-set inclusion uses the stated comparator and common order; it does not apply automatically after different move ordering, tie/cutoff rules or implementation changes.
- The full-memory SSS* endpoint does not make ITERSSS* a global alias of SSS* or alpha-beta, and the source distinguishes it from an alpha-beta/SSS* hybrid. Matching terminal counts at a smaller budget does not establish identical control flow. A general per-instance monotone terminal-count theorem as M increases is not supplied by the displayed experimental trend.
- The reported evaluation measures average terminal evaluations as a percentage of b^d leaves, using four uniform tree configurations, ten random terminal-value sets per configuration and five M settings. It does not report runtime results. Queue bookkeeping and leaf-evaluation cost can affect time, and no algorithm or benchmark was executed for this draft.
- The finite synthetic study does not report exact random seeds, a fully specified terminal-value generator distribution, variance or confidence intervals. Its source-reported averages and memory trends do not establish real-game generalization or strict improvement on every input; the paper calls for broader practical evaluation.
- The inspected defining source is the official five-page 1986 proceedings PDF. Its later digitization metadata does not create a new algorithm version. The earlier MA*/MAO* bibliography uses a different spelling of the first author and a slightly different title; that exact citation remains unchanged alongside the defining PDF metadata. Four cited originals, three retrieved follow-up groups and three additional source questions remain retained without alias, ownership, access or closure decisions.
Artificial Intelligence Ontology (AIO) Grounding
Explicit AIO Snapshot Assessment: No Match
Rationale: No selected AIO target captures this particular non-learning minimax search procedure at the appropriate abstraction level. Tree/graph representation, active scheduling, memory use, mathematical value and game application alone do not justify a broad, narrow or related mapping. The finding is bounded to the pinned snapshot and inspected targets.
Search Scope: Mechanical identity probes cover all 442 pinned AIO class labels and scoped synonyms. Fresh semantic reading covers all 25 selected full nodes and 97 direct incident edge occurrences (89 unique triples), including definition/comments/synonyms/subsets and their relation directions. No fresh reading of every one of the 442 full definitions is claimed. This is the historical prospective proposal snapshot, not fresh future curation clearance.
| Examined AIO Candidate | Rejection Reason |
|---|---|
AIO:MachineLearningTask
|
The pinned definition is a process intended to build methods that learn from data. The inspected 1986 procedure evaluates a supplied game tree using fixed terminal scores; it does not train or learn a method. Search is not sufficient for this mapping. |
AIO:Model
|
The target is an abstract representation of a complex system. The game tree is the input representation, while ITERSSS* denotes a particular computation and memory-control procedure over it; input-model versus algorithm is not collapsed. |
AIO:Network
|
The target denotes an interconnected system. A tree can be represented by nodes and arcs, but the candidate is the active/inactive search algorithm, not that structure or a network family. |
AIO:ArtificialNeuralNetwork
|
No artificial neurons, trainable connections or neural forward computation define ITERSSS*. Possible use of a neural leaf evaluator would be an optional application choice, not evidence for this mapping. |
AIO:DecisionTree
|
Despite a broad decision-support comment, the pinned definition and is_a edge identify a classification. ITERSSS* searches an adversarial minimax game tree rather than learning or applying that decision-tree classification; tree terminology alone is insufficient. |
AIO:RandomForest
|
The target builds an ensemble of decision trees during training. ITERSSS* neither trains such trees nor aggregates a forest; its solution-tree interpretation belongs to a supplied game tree. |
AIO:MathematicalFunction
|
Minimax is a mathematical objective, but the proposed record denotes a stateful search and memory schedule that computes it. It is not the bare input/output rule or a scalar activation function. |
AIO:MaximumLayer
|
This target merges equal-shaped input tensors elementwise. MAX game-tree nodes and maximum-h OPEN selection do not make the algorithm a neural merging layer. |
AIO:MinimumLayer
|
This target performs elementwise tensor minimum. MIN adversary nodes and solution-tree values are search semantics, not a layer implementation. |
AIO:MemoryCellLayer
|
The target is a layer of cells with internal state or weights and has-part connections to neural/language models. The source M parameter counts abstract OPEN entries and does not define such a cell layer. |
AIO:MemoryAugmentedLLM
|
This target is an externally memory-augmented language model. ITERSSS* is not a language model; its finite OPEN budget is not learned textual memory. |
AIO:NeuralTuringMachineNetwork
|
The target combines neural-network pattern matching with programmable-computer capabilities and is_a DeepFeedForwardNetwork. No such neural architecture is part of the game-tree algorithm. |
AIO:ReinforcementLearning
|
The source supplies a game tree and terminal evaluations; it does not specify agent training from rewards, an exploration/exploitation learning policy or learned value updates across interactions. Game-playing relevance alone does not support even a useful source-backed related mapping here. |
AIO:ReinforcementLearningLLM
|
Reward-fine-tuned text generation is not the mechanism or application evaluated in this 1986 game-tree procedure. |
AIO:TrainingStrategy
|
The pinned class concerns methods used to train machine-learning models. OPEN scheduling and minimax pruning are not a model-training strategy. |
AIO:ActiveLearning
|
ACTIVE/INACTIVE are execution-state tags, not query selection for labeling a data set. The shared word active is not a conceptual relation. |
AIO:ReasoningLLM
|
The target explicitly denotes a language model performing reasoning during language tasks. Search is automated reasoning in a broad sense, but this does not make ITERSSS* a language model or provide a source-backed relation to this class. |
AIO:RecursiveLLM
|
The target learns syntactic composition through recursive neural architectures. ITERSSS* is an explicitly maintained OPEN algorithm; neither its repeated processing nor solution-tree structure establishes this language-model identity. |
AIO:RecursiveLanguageModel
|
The target is a deep neural network learning syntactic composition, with input/memory/output parts. The candidate has no such learning or architectural parts. |
AIO:RecursiveNeuralNetwork
|
The target recursively applies shared weights to structured inputs. Recursive problem structure and minimax backup alone are not that trained neural architecture. |
AIO:GraphConvolutionalPolicyNetwork
|
The target generates graphs through graph-convolutional reinforcement learning and adversarial loss. Adversarial game-tree evaluation is not learned graph generation, and no graph convolution is present. |
AIO:ProbabilisticGraphicalModel
|
Its graph expresses conditional dependence among random variables. The presented game tree expresses alternating choices with static terminal scores, not a probability-factorization model. |
AIO:CausalGraphicalModel
|
Acyclic input structure does not establish causal data-generating assumptions. The source method is neither a causal model nor causal inference. |
AIO:Classification
|
The candidate computes a minimax root value, not supervised distribution of observations into categories. LIVE/SOLVED and ACTIVE/INACTIVE are algorithmic tags, not learned labels. |
AIO:HierarchicalClassification
|
The tree ordering does not define hierarchical class prediction. A minimax solution tree and an ontology of class labels are different objects. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
bhattacharya1986
|
Subir Bhattacharya, Amitava Bagchi
|
primary paper
full_text
|
sha256:90bfd737475f…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-16T05:14:56Z
Updated: 2026-10-16T05:14:56Z
Source File:
data/curated/ITERSSSStar.yaml