An interactive S-SQEP policy simulator

The main post on the Stochastic Sequential Queens Elimination Problem (S-SQEP) makes a fairly specific empirical claim: that Adaptive Coverage Greedy (ACG) tracks the true optimal value \(V^{*}(s_0)\) closely across the whole range of kill probabilities \(p\), while a plain greedy-by-degree rule and a random admissible policy fall further behind. Table 2 and Figure 3 of the manuscript back this up with numbers, but a static table is a strange way to present a sequential decision process. This post is a small widget that lets you drive the process yourself.

Pick a policy (Random-admissible, Greedy-degree, or ACG) and a kill probability \(p\), then step or play through the trajectory one activation at a time. At every step you can see which queen was chosen, which of its unblocked neighbors were actually eliminated (a coin flip per neighbor, independently, at probability \(p\)), and how the conflict count \(\kappa(S^{(t)})\) and the cumulative cost \(\Psi\) evolve. The right-hand panel shows the same Monte Carlo comparison as Figure 3, with the currently selected \(p\) marked, so you can see exactly where the run you're watching sits relative to the aggregate statistics.

Why the browser never simulates anything itself

Everything in this widget; the exact value \(V^{*}(s_0)\), the Monte Carlo means and standard errors, and every frame of every replay; is computed once in Python, directly from the same reference implementation behind the paper's own experiments (sqep_model.py, sqep_algorithms.py): \(V^{*}\) via the backward induction of Theorem 12 over the 256 reachable states, and ACG's activation choice via the closed-form gain of Lemma 17. The browser only replays those precomputed results; it does not reimplement any part of the model in JavaScript. That was a deliberate choice: a hand-rolled JS port of the attack/blocking logic could quietly drift from the paper's own code, and there would be no easy way to notice. Baking the computation into a static JSON payload means the widget can never show a trajectory the reference implementation itself wouldn't produce.

The instance is the same \(n=8\), seed-7 board already used for fig_kappa_decay.png, fig_policy_vs_p.png, and fig_acg_bound.png in the main post \(\kappa(s_0) = 9\) so the numbers below are directly comparable to those static figures rather than a different random instance.

What to look for

• Set \(p\) low (around 0.20) and compare ACG against Greedy-degree: the gap Table 2 reports (ACG tracking \(V^{*}\) within roughly 2%, Greedy-degree noticeably further behind) is easier to feel by stepping through a run than by reading a column of numbers.
• Watch which queen gets activated first at each \(p\). ACG and Greedy-degree agree far more often than you might expect on this board; the disagreement, when it happens, is usually a queen with slightly lower degree but conflicts that overlap less with everyone else's.
• As \(p \to 1\), all three curves in the right-hand chart converge toward \(\kappa(s_0) = 9\); consistent with Remark 10, since a single sufficiently well-chosen activation can resolve every conflict on this particular board when kills are deterministic.