MultiPatternSolver en

中文 | English

The multi-pattern assignment solver (PatternChoiceRepair)

The one part of this port that goes beyond porting upstream — it closes a problem upstream left open.

The problem: greedy single-pick has a ceiling

The VM's resolver picks exactly one pattern per output key (lowest per-craft output first, ties by registration order) and never looks back. When one output has several patterns, greedy selection can over-demand some leaf — reporting missing items that were avoidable, or producing a worse ratio.

In the reference suite, multi-dag/fibonacci/minimum had been upstream's only FALSE_POSITIVE since v1.9.6: the scenario has a stock configuration where every pure single-pick assignment misses by at least 1 (provable — see the footnote), and only a mixed assignment ("this branch on pattern A, that one on pattern B") reaches zero missing. The original author evaluated porting Thunderbolt's budgeted backtracking planner as high-risk and deferred it; an earlier "locally cheapest leaf" heuristic was reverted because it broke greedy-trap scenarios.

The idea: solve the assignment, then encode it as data

The solver (com.ae2vm.vm.PatternChoiceRepair) only starts when the greedy first pass reports missing (successful requests pay nothing), in three steps:

Step 1 — single-choice enumeration (pure algebra, zero engine cost)

Write each candidate pattern's per-craft input consumption (excluding returned items such as catalyst seeds) as a linear demand system, cascade it from the root in topological order, and evaluate all 2^n combinations of the contended keys (≤12) algebraically. Keep all tied optima (up to 8) as starting points for refinement — which optimum can grow into a mixed split depends on the graph, and from a single start every one-step move may be non-improving.

Step 2 — split-weight local search

Each contended key carries a weight vector; its demand is distributed across candidate patterns by the largest remainder method — this is what makes mixed splits (X3 = 4×A + 1×B) expressible. Move rules:

• transfer one weight unit between two candidates, or add one unit to a single candidate (ADD — how a 4:1 ratio is reached from a single-hot state);
• equal-value moves only advance the search position (bounded, no oscillation); strict improvements enter the solution;
• visited keys are GCD-reduced row-wise: weights are ratios, so proportional states ([0,2] and [0,1]) are the same assignment; without reduction, ADD's infinite proportional ladder would exhaust the lateral budget.

Step 3 — virtual pattern synthesis + confirmation gate

The best mixed weights are synthesized into one virtual pattern (VirtualPatternDetails): inputs = Σ share × constituent inputs, output = the merged batch. The split becomes pure data — the execution loop, bundle cache, aggregation and stock-aware semantics all work unchanged; the engine needs zero modifications. The virtual pattern enters the resolver through the ordinary preference mechanism, then one real replay confirms: adopt only on strictly fewer total missing; otherwise keep the original plan. Model distortion can only fail the confirmation — it can never make the plan worse.

Results and a mathematical footnote

• multi-dag/fibonacci/minimum missing 4 → 0; all three stock modes 39/39 stably SUPPORTED (zero flakiness across fresh JVM runs);
• The scenario's optimal stock {X0=1, X1=9, X2=11} was proven by independent enumeration to be unreachable by any pure single-choice assignment (pure optimum misses by 1); it is matched exactly by the mixed share X3 = 4×A + 1×B under the identities X0 = number of B shares, X1 = 4 + A + B, X2 = 7 + A;
• Full pipeline cost: milliseconds of pure algebra + one confirmation replay; with the fast path, the solver scenario runs at ~3.3 ms hot median.

Relation to upstream

Upstream evaluated porting Thunderbolt's full budgeted backtracking planner as high-risk. This approach adds no backtracking planner; it demonstrates that once "choice" is decoupled from execution into a solver, and the solution is encoded as data, the greedy architecture still reaches the exact answer. The per-scenario decision-trace tool TraceSimulationState remains in the test sourceset (wiring notes in Ae2VmReferencePlanner).