emba-course-solver/openspec/changes/decision-tree-exhaustive-search/proposal.md at main

Files

T

Bill cb49123930 v1.3.1: Exhaustive decision-tree search + UX refinements

The v1.3.0 saturation termination silently capped the search after only
the heuristic-favored part of the tree, leaving most per-set ceiling cells
stuck at "0 specs" and hiding genuinely-feasible 3-spec plans in
maximize-count mode. Replace with full exhaustive enumeration plus a
batch of UX refinements that emerged during testing.

Algorithm:

- Drop the saturation early-termination entirely. Search now runs the
  full open-set cartesian product to completion; the iteration cap is
  also removed so no scenario exits partial.
- Add mode-dependent DFS child ordering: priority-order keeps the
  priority-target-first heuristic; maximize-count orders children by
  descending count of qualifications for reachable specs (generalist
  courses tried first).
- Make the (count, priorityScore) comparator mode-aware: priority-order
  ranks by (priorityScore, count) so the user's top spec surfaces;
  maximize-count ranks by (count, priorityScore) so the highest count
  wins. The same rule drives both top-K position and per-cell ceiling
  selection (and the Recommended badge).
- Add an evaluated boolean to each ChoiceOutcome and set it on first
  leaf evaluation. Distinguishes "still searching" from "evaluated, no
  specs achieved" so the UI never shows misleading 0 specs for a cell
  the search hasn't reached yet.
- Throttled progress events (~100ms) carrying iterations / total leaf
  count, drive both the per-set spinner and the global progress bar.

UI:

- Top Plans header shows a horizontal progress bar with
  "iterations / total · NN%" while the search runs; collapses to
  "Search complete · N explored" on completion.
- Per-set spinner next to each elective set heading while any choice
  in that set is unevaluated.
- Per-cell pulsing dot + "searching" text for unevaluated cells.
- Replace the "(HCR, BNK, ...)" text labels on each course with
  color-coded SpecTag pills using a new fixed per-spec palette
  (app/src/data/specColors.ts). Same palette applied to the Top Plans
  achievement badges so the two views are visually consistent.
- "Top outcome if picked ↓" caption above the right side of each open
  elective set so the spec tags are clearly identified as decision-tree
  outcomes (not the course's own qualifications).
- Recommended badge moved inline next to the course name (instead of
  on a separate row below) to keep button heights stable.

Tests:

- Replace the saturation early-termination test with an exhaustion test
  asserting every cell ends with evaluated: true and partial: false.
- Add mode-dependent ordering test (max-count visits Climate Finance
  before Corporate Governance in fall3).
- Add evaluated-flag transition test.
- Add throttled progress-event test (>= ~100ms between consecutive
  emits).
- Performance smoke updated to a 60s budget for the exhaustive
  user-scenario search; 8-open-set typical case completes in ~7s.

Files: solver/decisionTree.ts, solver/priority.ts (already shipped),
data/specColors.ts (new), components/{TopPlans,CourseSelection}.tsx,
state/appState.ts, workers/decisionTree.worker.ts,
__tests__/searchDecisionTree.test.ts, vite.config.ts, CHANGELOG.md,
openspec/changes/decision-tree-exhaustive-search/* (full change spec).

2026-05-09 15:47:56 -04:00

4.6 KiB

Raw Permalink Blame History

Why

Real-world testing of v1.3.0 surfaced two related defects in the new decision-tree streaming search:

Many per-set choices show "0 specs" — the saturation termination (top-K stable for 500 iterations) fires after exploring only the heuristic-favored part of the tree. Courses in early sets that don't qualify for the priority target are never the chosen course in any evaluated leaf, so their ceilings remain at the initial {count: 0, specs: []} and render as a misleading "0 specs".
Top plans are not exhaustive in maximize-count mode — same root cause: saturation accepts "no improvement" too eagerly, since many leaves yield the same already-found outcome class. Higher-count plans (e.g., [BNK, CRF, FIN] triples) that exist deeper in the search are never reached.

Both behaviors mislead the user: the per-set table claims a course leads to no specs when in fact it was never evaluated, and the Top Plans panel hides plans that genuinely exist. The fix is to drop the early-termination heuristic and run an exhaustive search, with mode-dependent enumeration ordering so the most-likely-good outcomes still appear early in the stream.

What Changes

Remove SATURATION_LIMIT early-termination. Search runs the full cartesian product unless MAX_TREE_ITERATIONS (raised to 100,000 as safety cap) fires.
Add mode-dependent child ordering at every DFS level:
- priority-order mode: keep the existing priorityTarget-qualifying-first heuristic.
- maximize-count mode: new heuristic — order children by descending count of qualifications they hold for reachable specs (specs whose upper bound ≥ 9). "Generalist" courses like Climate Finance (BNK/CRF/FIN/FIM/GLB/SBI) come before specialist courses, surfacing high-count outcomes early.
Distinguish unevaluated cells from evaluated, zero-spec cells in ChoiceOutcome. New field evaluated: boolean (default false, set true on first leaf containing the (set, course) pair). UI renders unevaluated cells with a subtle searching indicator, not "0 specs".
Add per-set progress indicator — a small spinner next to the set name shown when loading is true and any choice in that set is still unevaluated; clears when every choice has been evaluated or when search completes.
Add global progress indicator in the Top Plans panel — "Searching… N / Total explored" with running counts, then "Search complete · N explored" when done. If partial: true, show "Search incomplete · cap hit at N".
Add "Recommended" marker per set — the choice with the best (ceilingCount, priorityScore) per the same comparator the top-K uses; rendered as a small badge on the recommended row. Derived in the UI from analysis.choices (worker protocol unchanged on this front).
Worker emits a new progress event throttled to ~100ms intervals, carrying { iterations, iterationsTotal }. Avoids per-iteration message flood while keeping the UI responsive.

Capabilities

New Capabilities

None — this extends the existing optimization engine.

Modified Capabilities

optimization-engine: drop saturation termination requirement; require exhaustive search up to a safety cap; add mode-dependent ordering, evaluated/unevaluated cell state, per-set + global progress events, and a per-set recommended-choice derivation.

Impact

app/src/solver/decisionTree.ts — drop SATURATION_LIMIT; raise MAX_TREE_ITERATIONS to 100,000; add reorderByReachableQualCount helper for maximize-count mode; gate the chosen reorder strategy by mode; add evaluated: boolean to ChoiceOutcome and set it on first leaf containing the pair; emit throttled progress events; remove saturation logic
app/src/workers/decisionTree.worker.ts — add progress event type to the tagged union; throttle progress emission
app/src/state/appState.ts — track searchProgress: { iterations, iterationsTotal } | null slice; consume progress events
app/src/components/TopPlans.tsx — render global progress text in the header
app/src/components/CourseSelection.tsx — per-set spinner (next to set name); per-cell unevaluated rendering (skeleton/dot, not "0 specs"); "Recommended" badge on the best choice per set
app/src/solver/__tests__/searchDecisionTree.test.ts — remove saturation tests; add exhaustion test (asserts every (set, course) cell has evaluated: true after completion); add mode-dependent ordering test (maximize-count chooses generalist courses first); add unevaluated→evaluated transition test
app/vite.config.ts — bump to 1.3.1 (or 1.4.0 if user wants minor; default patch)
CHANGELOG.md — release entry
No data file changes; no schema migration

4.6 KiB Raw Permalink Blame History

Why