predict_fleet_arrival_optimization.md

predict_fleet_arrival optimization (per-turn caching + vectorized kernel)

Status: implemented (2026-06-10). Part 1 = GameState.fleet_arrival_by_id filled by _with_projected_arrivals, consumed via orbit_physics.cached_fleet_arrival (lookup-first and horizon-aware via GameState.arrival_horizon; scalar fallback for non-materialized states and for queries past the materialization horizon). Part 2 = fleet_arrival_vec.py (planet_trajectories + predict_fleet_arrivals_batch), dispatched from _with_projected_arrivals whenever precomputed.pos_table covers turn + horizon + 1. Parity gate: tests/test_fleet_arrival_vec.py — 71,370 replay calls across the three anchor replays, 0 mismatches, exact equality. Measured (local 1-thread, scripts/bench_fleet_arrival_vec.py): 139→23.4 µs/call (5.9×) on episode-77130590, 301→23.3 µs/call (12.9×) on episode-76410200; 730-fleet peak-turn full pass 193ms→16.6ms (11.7×). Acceptance A/B (profile_pipeline on the spam game, budget 1.0s, pre-change HEAD ae53e08 vs this change, both sides measured on an idle machine): pre-optimize LOCAL p95 234.5ms→20.0ms (11.8×, target was ≥5×; max 246.0ms→44.3ms, meeting the ≤45ms peak-turn bar), non-optimize overhead mean 354ms→60ms (p95 861ms→66ms), ScoringState.__init__ mean 85.3ms→14.3ms, full agent() steady mean 4608ms→687ms (optimizer evals no longer scale with fleet count), turns over 1s: 168/217→30/217, Kaggle-projected (×5) pre-optimize p95 1173ms→100ms and POST_RESERVE_S 1.04s→0.09s — the spam regime no longer busts the 1s wall on overhead alone.

Owns: removing orbit_physics.predict_fleet_arrival as the dominant per-turn cost on Kaggle — the scalar horizon×planets Python walk that dominates fleet-heavy turns and comet-spawn cache-invalidation storms. Two multiplicative changes: (1) turn-invariant per-fleet arrival caching on GameState, and (2) a batched, chunked numpy kernel for the predictions that still must be computed.

Related docs: fleet_arrival_cache.md (cross-turn cache this builds on), time_budget.md (why pre-optimize overhead cannot be deadlined away), turn0_eta_optimization.md (the turn-0 lead_shot hotspot — explicitly out of scope here; see "Scope boundary" below).

Feasibility verdict (measured 2026-06-09, local single thread, OMP_NUM_THREADS=1)

A throwaway numpy prototype of the batched kernel was benchmarked against the live scalar path on two full replays, every turn, every in-flight fleet, with Precomputed built from the turn-0 obs (live conditions):

replay	regime	fleet-calls	scalar µs/call	batched µs/call	speedup
data/episode-77130590.json	normal, comet windows (10 fleets/turn mean, 27 peak, ~33 planets)	4,515	171	28	6.2×
data/episode-76410200.json	fleet spam (730 fleets/turn peak)	51,159	306	27	11.3×

Parity: 0 mismatches in 8,230 sampled calls (target planet, arrival turn, and None-vs-hit all identical), including comet turns. The kernel reads the same float64 Precomputed.pos_table the scalar path reads and replicates swept_pair_hit elementwise, so bit-exact parity is achievable, not just approximate agreement.

Why this matters on Kaggle (≈7× slower than local, single core): one full prediction pass over the 730-fleet peak turn costs ≈1.6s scalar — alone above the 1s turn wall — vs ≈0.14s batched. This work runs in build_game_state, before the optimizer deadline can react, so only making it faster (not budgeting) fixes the spam regime. See the fleet-count blowup measurements in the project memory and time_budget.md: pre-optimize p95 goes 53ms @ 9 fleets → 851ms @ 234 fleets local.

Why naive vectorization is NOT enough (measured)

The scalar walk early-exits at the first hit. Measured walk depth on episode-77130590: median 6, p90 24, max 77 of a 120-turn horizon. A straight full-horizon single-fleet vectorization therefore only bought 1.7× (85µs/call) — numpy dispatch overhead plus 20× wasted horizon. The 6–11× numbers require both of:

• Shared planet trajectories per turn: the (P, H+1, 2) planet position array depends only on the state, not the fleet — build it once per state, reuse across all fleets.
• Chunked horizon with batched early-out: evaluate deltas in blocks of 16 across all unresolved fleets at once; drop fleets from the active set as they resolve. Most fleets resolve in the first block.

The two changes

Part 1 — turn-invariant per-fleet arrival cache (no numerics, biggest optimizer-loop win)

Observed in-flight fleet arrivals depend only on board geometry, which no allocation can change (candidate launches add launch_records, never mutate post.fleets or planet positions). Yet today they are re-predicted inside the optimizer loop:

• share_features_runtime._runtime_outflow (share_features_runtime.py:66) and _runtime_outflow_rows (:101) call predict_fleet_arrival(post, fleet) for every fleet on every EXACT (build_mlp_feature_cache) and LOCAL (refresh_mlp_feature_rows) share recompute — i.e. on every apply/apply_many during search. In spam games that is F × ~150µs per optimizer eval, silently eating the search budget (fewer evals/sec → weaker play, even when it doesn't time out).
• prior.infer_fleet_target (prior.py:62) re-predicts per fleet.
• ScoringState._rebuild_turn_constants (scoring_state.py:228) re-predicts when the state is not materialized (test/hand-built states only — live states are materialized).

Change. _with_projected_arrivals (orbit_physics.py:1132) already computes exactly one prediction per fleet (through main's cross-turn ArrivalTable). Store that result on the state instead of discarding it:

• Add fleet_arrival_by_id: Mapping[int, tuple[int, Arrival] | None] | None = None to GameState (frozen dataclass; default None keeps hand-built states working). _with_projected_arrivals fills it for all observed fleets (fleet.id >= 0) alongside arrivals_materialized=True.
• _runtime_outflow / _runtime_outflow_rows: look up post.fleet_arrival_by_id[fleet.id]; fall back to scalar predict_fleet_arrival only when the mapping is None (non-materialized test states).
• prior.infer_fleet_target and the ScoringState._rebuild_turn_constants fallback: same lookup-first pattern.
• Verify propagation: ScoringState._post is derived from self._state via dataclasses.replace-style rebuilds (rebuild_from_allocation, _refresh_post_state). Confirm the new field survives every replace(...) on the post path (it will unless a rebuild constructs GameState from scratch — audit those sites).

This part is pure caching: byte-identical results by construction, no parity risk, and it makes the per-eval optimizer cost independent of fleet count.

Part 2 — batched chunked numpy kernel

For the predictions that still must run — cache-miss fleets in _with_projected_arrivals (new fleets each turn; all fleets after a comet-spawn full invalidation, the measured timeout window) — replace the scalar per-fleet walk with one batched call.

API (new module fleet_arrival_vec.py, or alongside the scalar in orbit_physics.py):

def planet_trajectories(state, horizon) -> tuple[ids, radii, traj]:
    """ids int64[P] in state.planets dict order; radii float64[P];
    traj float64[P, horizon+1, 2] for turns state.turn .. state.turn+horizon,
    NaN where the body is absent (despawned comet path)."""

def predict_fleet_arrivals_batch(state, fleets, horizon=120,
                                 block=16) -> list[tuple[int, Arrival] | None]:
    """Engine-exact batch equivalent of predict_fleet_arrival per fleet."""

Kernel construction (exactness contract — replicate the scalar op-for-op):

1. Planet trajectories. Non-comets: slice precomputed.pos_table[pid, t0:t0+H+1] — the same float64 table scalar position_at returns from, so values are bit-identical by construction. Comets: slice np.asarray(planet.comet_path)[comet_path_index:], NaN-pad past the path end (scalar returns None there → kernel masks NaN cells as no-hit). Pathless comets and static planets: constant rows.
2. Fleet segments. pos + dir·speed·k for k = 0..H, speeds via the same _speed table lookup, directions via cos/sin(angle) (float64 libm — identical to math.cos/sin).
3. Swept hit = vectorized swept_pair_hit (orbit_physics.py:149): same quadratic, same a < 1e-12 → c <= 0 degenerate branch, same disc >= 0 ∧ t2 >= 0 ∧ t1 <= 1 acceptance, float64 throughout (wrap in np.errstate(invalid="ignore"); masked lanes may produce NaN).
4. Exit conditions. Per delta: OOB = not (0 <= x <= BOARD_SIZE and 0 <= y <= BOARD_SIZE) (inclusive, after the move); sun = vectorized point_to_segment_distance(CENTER, seg) < sun_radius. Replicate point_to_segment_distance op-for-op — do not substitute a squared-distance comparison; d² < r² vs sqrt(d²) < r can disagree by an ULP at tangency and the engine rule is strict <. (The prototype used the squared form and still hit 0 mismatches, but the op-for-op form is the one that is provably identical.)
5. Resolution order must match the engine tick: a planet hit at delta d is accepted before the OOB/sun exit test at the same d; within a delta, the winner is the first planet in state.planets dict order (flat argmax over the (delta, slot)-ordered hit mask, hits masked to delta <= first_exit_delta).
6. Chunked early-out. Evaluate deltas in blocks of block (16 measured good; tune 8/16/24 once) over the active-fleet set; resolve and remove fleets per block; stop when the set is empty. Peak temp memory at the spam peak is F×P×B float64 ≈ 3.4MB per temporary — negligible.

Dispatch. _with_projected_arrivals collects cache-miss fleets and makes one predict_fleet_arrivals_batch call (filling main's cross-turn ArrivalTable exactly as today). Per the no-compat-shim rule the batch kernel becomes the only path when state.precomputed is present; the scalar predict_fleet_arrival stays as (a) the path for states without precomputed (hand-built tests, and any horizon that overruns precomputed.horizon — see edge cases), and (b) the parity oracle.

Call sites that stay scalar (few calls, synthetic id=-1 fleets): repair._angle_ok (repair.py:62) — one candidate fleet per repair check; batching buys little and the synthetic fleet can't live in any cache. Revisit only if profiling later shows it.

Scope boundary: turn-0 lead_shot validate

The turn-0 ETA sweep also bottoms out in predict_fleet_arrival (lead_shot.validate, ~71% of the 13.8s 1-core turn-0 build), but in a synthetic 2-planet world whose Precomputed stub has pos_table horizon 1 — the kernel's pos_table fast path never applies there, and with P=2 the scalar early-exit walk is already near numpy dispatch cost per call. That hotspot is owned by turn0_eta_optimization.md Phase 2 (vectorize the candidate search across phases×speeds, which removes most validate calls entirely). If that plan later wants this kernel, the hook is a closed-form orbiting trajectory fill in planet_trajectories (vectorized angle₀ + ω·max(0, t−1) matching position_at's fallback branch) — don't build it speculatively.

Edge cases the implementation must handle

• pos_table range. precomputed.horizon = total_steps + MAX_VALIDATION_HORIZON + 2, and every live per-turn call uses horizon=120 ≤ MAX_VALIDATION_HORIZON, so t0+H+1 is always in range for the per-turn path. Assert this at kernel entry rather than implementing the closed-form rotation fallback; out-of-range callers (late-game lead_shot with turns+10 > 120) are not routed through the kernel.
• Comet despawn mid-horizon: NaN trajectory cells must suppress hits at both segment endpoints (scalar skips when either position_at is None).
• Degenerate relative motion (a < 1e-12): static planet, fleet speed aligned — take the c <= 0 branch exactly.
• Hit exactly at the exit delta: planet sweep wins over OOB/sun at the same delta (engine order).
• Same-delta multi-planet hit: lowest state.planets insertion slot wins.
• Fleets already past the board edge on the first step, sun-grazing tangent paths (strict <), and ships=1 minimum-speed fleets.

Implementation steps

1. Part 1 caching (orbit_model.py field, orbit_physics.py:1132 fill, rewire share_features_runtime.py:66,101, prior.py:62, scoring_state.py:228; audit _post rebuild for field propagation). Land independently — zero numerical risk, immediate optimizer-eval win.
2. Kernel (planet_trajectories + predict_fleet_arrivals_batch), dispatch from _with_projected_arrivals.
3. Tests + bench (below), then promote the kernel to the only precomputed-path implementation.

Tests

New tests/test_fleet_arrival_vec.py:

1. Exhaustive replay parity (the gate). For ≥3 replays — episode-77130590 (comets), episode-76410200 (spam), episode-76844664 — every turn, every fleet: batch result == scalar predict_fleet_arrival exactly (planet id, Arrival tuple, None-vs-hit). This is the 0d849e4 lesson: arrival semantics regressions show up as play collapse, so the bar is bit-exact, not approximate.
2. Synthetic edge cases from the list above, each asserting batch == scalar.
3. Part-1 invariance: _runtime_outflow outputs identical before/after the cache rewiring on a replay state with a nonempty allocation applied (and tests/test_fleet_arrival_cache.py, tests/test_scoring_state.py, tests/test_orbit_physics.py stay green throughout).
4. Block-size independence: results identical for block ∈ {1, 16, 120}.

Bench: extend scripts/bench_predict_fleet_arrival.py (or add scripts/bench_fleet_arrival_vec.py) to report scalar vs batched µs/call and per-turn pass totals on the two anchor replays.

Acceptance

• Parity tests exact-green.
• OMP_NUM_THREADS=1 python scripts/profile_pipeline.py data/episode-76410200.json --player 0: pre-optimize overhead on the spam game's peak turns drops ≥5× (scalar pass ≈223ms local at the 730-fleet peak → ≤45ms), and comet-spawn invalidation turns on episode-77130590 show the same ratio.
• No local tournament regression (cheap guard; with bit-exact parity it should be a formality).
• After landing, revisit time_budget.md's fleet-count-adaptive reserve question — the motivation shrinks ~10× with this in place.

Rejected alternatives

• Full-horizon, per-fleet vectorization (no chunking, no sharing): measured 1.7× only — early-exit loss and numpy dispatch overhead eat the win.
• Numba/C extension: submission bundle is plain numpy; adding a JIT dep to the Kaggle package is a new failure mode for a problem numpy already solves at 6–11×.
• Hard per-turn deadline as the fix: cannot work — the cost is in build_game_state, before any deadline check runs (time_budget.md).