ALGO-01.2 — Library seed tranche: tested F# implementations harvested from reviewed code #5224

Activity

1. EHotwagner

   added a parent issue on Nov 1, 2026

   • ALGO-01 — Shared algorithms & optimization capability: F# library + product skill knowledge pack, available in product workspaces #5222
2. EHotwagner

   marked this as blocked on Nov 1, 2026

   • ALGO-01.1 — ADR: ownership, taxonomy, knowledge-pack format and product-workspace distribution #5223
3. EHotwagner commented on Nov 1, 2026

   

   EHotwagner

   on Nov 1, 2026

   ContributorAuthor

   More actions

   Root/fdev: ADR-0098 is accepted (#5227), so the blocker is cleared. Root created the public FS-GG/FS.GG.Algorithms repo. Owner dispatched: PR 1 is the bootstrap plus F1–F4, and PR 2 is the harvest re-implementations.
4. EHotwagner commented on Nov 1, 2026

   

   EHotwagner

   on Nov 1, 2026

   ContributorAuthor

   More actions

   Owner progress on ALGO-01.2. These are pointers for recovery, not acceptance.

   Repository: FS-GG/FS.GG.Algorithms, created by Root. It holds two staged PRs; nothing is merged or published.

   PR	Scope	Head	State
   FS.GG.Algorithms#2	Bootstrap and foundations F1-F4 (heap with a frozen pop order, Q16.16, best-first search, xoshiro128**)	907a8390	Ready for review; CI 4/4 green
   FS.GG.Algorithms#3	Harvest 18-21 (iterative Tarjan, union-find, nearest-rank percentile, priority arbitration), stacked on #2	966a5f4f	Ready for review; CI 4/4 green

   Owed or held, with owners:

   • Bench baselines: FS.GG.Algorithms#1. The quiet-host probe held at 0.25 per core; load5 was 5.6 to 9.3 on 12 cores.
   • F2 trigonometry: owed.
   • The N-items: the follow-on, in ranked order, listed in 208: rename fs-skia-ui-version/-bom → fs-gg-ui-version/-bom; ADR-0003 Accepted #3.
   • Call-site migrations: .github Blockers.cycles and Lanes.partition, Governance nearestRank, and RuneScape's arbiter (owner work).
   • The Game.Core heap migration: a separate FS.GG.Game PR after the release.
   • The release: Root admits it.
   • Atlas capture gap: two Fable findings, the int32 multiply precision loss and the lsr identifier miscompile. I will capture them after merge, citing the merged Internal/Bits.fs.

   Refs #5222
5. EHotwagner commented on Nov 2, 2026

   

   EHotwagner

   on Nov 2, 2026

   ContributorAuthor

   More actions

   These are the next PRs under ALGO-01.2: the ADR-0098 §11 part 3 N-items, in ranked order. Each follows the §4 admission bar: FsCheck against an in-library oracle, a Fable proof, a bench (or owed under FS.GG.Algorithms#1), and a pack entry once ALGO-01.3 lands.

   Order	Entry id	Oracle	Builds on
   N1	graph/topological-sort-cpm (Kahn, critical path)	Edges are respected; a cycle is reported exactly when iterative Tarjan finds an SCC larger than one node	Graph.Scc
   N2	decision/behaviour-tree (with a blackboard)	Tick determinism
   N3	decision/utility-ai (IAUS)	Scores bounded to 0-1; monotone curves	F2 Fixed
   N4	decision/hfsm	Entry and exit properly nested
   N5	adversarial/negamax-alpha-beta-tt	Equals plain minimax on random trees	F4 (Zobrist keys as two int32 halves)
   N6	adversarial/mcts-uct (with an ISMCTS mode)	Converges on small solved games	F4
   N7	steering/reynolds	Arrives within ε with no overshoot	F2
   N8	net/prediction-reconciliation-interpolation	Converges to the server under a lossy simulator
   N9	net/rollback	Byte-identical to a zero-latency run
   N10	systems/backoff-jitter-token-bucket	Delays within bounds; long-run rate at most r	F4
   N11	search.mesh/navmesh-astar-funnel	No longer than the portal-midpoint path; LOS-clear	F3
   N12	search.grid/lazy-theta-star	No longer than A* + smooth; LOS-valid	F3
   N13	search.grid/hpa-star	Suboptimality against A* within a bound	F3
   N14	spatial/kd-tree	Equals a brute-force scan	F1
   N15	optimization/csp-ac3 (MRV, LCV)	Agrees with brute force on small instances
   N16	optimization/local-search	Never worse than the start; seed-deterministic	F4
   N17	optimization/hungarian	Equals the brute-force minimum for n ≤ 7
   N18	procgen/wfc-simple-tiled	All adjacencies legal; seed byte-identity	F4
   N19	procgen/opensimplex2-worley	Range bounds; seed byte-identity	F4
   N20	learning/bandits-ucb1-thompson	Sublinear regret on synthetic arms	F4
   N21	decision/goap	Plan cost equals BFS over the state space	F3

   #5224's "at least two classic additions" are N1 and N2.

   Also held under #5224:

   • F2 trigonometry (a LUT or CORDIC).
   • Call-site migrations: .github Blockers.cycles and Lanes.partition, Governance nearestRank, and RuneScape's arbiter (owner work).
   • The Game.Core heap migration: a separate FS.GG.Game PR after the release.
   • The recorded bench baselines: FS.GG.Algorithms#1.
   • The release, which is a separate step Root admits.

   State now:

   • FS.GG.Algorithms#2 is merged as e6e451b4.
   • FS.GG.Algorithms#3 is at b1456799: 5/5 checks green, including routine-eligibility, and waiting for Root.
   • The Atlas capture is in atlas: record two Fable lessons from FS.GG.Algorithms (int32 multiply semantics, compile-gate exit status) (Refs #5224) #5230.

   Refs #5222
6. EHotwagner commented on Nov 2, 2026

   

   EHotwagner

   on Nov 2, 2026

   ContributorAuthor

   More actions

   Owner progress on ALGO-01.2. These are pointers, not acceptance. The two classic additions are both in review:

   PR	Entry	Head	Base	CI
   FS.GG.Algorithms#4	N1 graph/topological-sort-cpm	a7d9a655	main	5/5, including routine-eligibility
   FS.GG.Algorithms#5	N2 decision/behaviour-tree	68a554d4	#4 (stacked)	4/4; routine-eligibility runs after the retarget

   When both merge, #5224's "at least two classic additions" is met. Root decides whether to accept #5224 with these as follow-ups:

   • N3-N21;
   • F2 trigonometry;
   • the call-site migrations;
   • the Game.Core heap migration, after a release;
   • the bench baselines, FS.GG.Algorithms#1.

   Refs #5222
7. EHotwagner commented on Nov 2, 2026

   

   EHotwagner

   on Nov 2, 2026

   ContributorAuthor

   More actions

   Root/fdev: N1 is merged (FS.GG.Algorithms#4). N2 (#5) is approved and rebasing.

   New ranked item N2b, decision/behaviour-tree-reactive, from the #5 review:

   • What: reactive Sequence/Fallback, the Colledanchise–Ögren defaults, which enable priority interrupts.
   • Done when: abandoned running branches are halted, so there is no stale running child.
   • Proof: the reference interpreter and the invariant fuzz are extended.

   It is ranked immediately after N2, because game AI needs priority interrupts.
8. EHotwagner commented on Nov 2, 2026

   

   EHotwagner

   on Nov 2, 2026

   ContributorAuthor

   More actions

   ALGO-01.2 Done-when mapping, as of 2026-11-02. "Fable" means a LockstepExact grade proven by the cross-runtime fixture corpus, gated by eng/fable-proof.sh (which has a negative control) and checked by an independent Python oracle.

   Harvested

   Done-when item	Entry (FS.GG.Algorithms)	PR	Tests and oracle	Fable	Bench row
   A* with doors and plane handling	search.grid/doors-and-planes (Search.Grid.DoorGrid)	#6 (in review)	Neighbours equal an independent adjacency; A*/Dijkstra equal an oracle Dijkstra; paths valid; heuristic is a lower bound	yes, op 13	search.grid/doors-and-planes/corner-to-corner
   Behaviour composition	decision/behaviour-tree (N2)	#5, merged c599ea49	Equal to a recursive reference interpreter over 8 ticks; fail-fast and succeed-fast; idempotence	yes, op 12	decision/behaviour-tree/ticks
   Arbitration primitives	decision/priority-arbitration	#3, merged f2804c4c	RuneScape's invariant suite ported to FsCheck (400 runs) plus a drain (300)	yes, op 9	not a hot loop
   Nearest-neighbour or spatial queries	spatial/kd-tree (also N14)	#6 (in review)	Every query equals brute force under heavy ties	yes, op 14	spatial/kd-tree/nearest-1000-queries

   Notes on the harvested rows:

   • Doors and planes: written generically from the item; no RuneScape source, flags or data were used.
   • Behaviour composition: memory composites only. Reactive composites are N2b, FS.GG.Algorithms#8.
   • Arbitration: a clean re-implementation, not a copy.
   • Spatial queries: Game.Core's SpatialGrid (uniform grid) is indexed in place, below.

   Absorbed

   The algorithms behind the grids, collision, line-drawing and visibility skills are indexed in place, not extracted. This follows ADR-0098 §1 and §8 and the default for open question 1.

   • Game.Core stays the implementation of record.
   • The pointer pack entries are ALGO-01.3 (ALGO-01.3 — fs-gg-algorithms product skill + knowledge pack, materialized into fs-gg-fable-game workspaces #5225).
   • Game's owed evidence is FS.GG.Game#804: the A* vs BFS property, the Fable grades for integer-only surfaces, and the timing benches.

   New (at least two classic additions)

   Entry	PR	Tests and oracle	Fable	Bench row
   N1 graph/topological-sort-cpm	#4, merged 043146d	Tarjan cycles; a list model; brute-force longest path; the CPM rules	yes, op 11	graph/topological-sort-cpm/random-dag
   N2 decision/behaviour-tree	#5, merged c599ea49	As above	yes, op 12	As above
   N14 spatial/kd-tree (bonus)	#6	As above	yes, op 14	As above

   Foundations and harvests the tranche builds on

   • F1-F4 (heap, Q16.16, best-first search, xoshiro128**): ADR-0002: record versioning hardening as accepted Decision 5 #2, merged e6e451b4. Fable ops 1-5 and 10.
   • Harvests 18-20 (iterative Tarjan, union-find, nearest-rank percentile): 208: rename fs-skia-ui-version/-bom → fs-gg-ui-version/-bom; ADR-0003 Accepted #3. Fable ops 6-8.

   The other Done-when clauses

   Clause	Status
   Property tests	All entries. 117 tests on #6's head; FsCheck against in-library oracles only (ADR-0098 §4)
   Fable proof where portable	Every public surface is graded; there are no Unclassified surfaces. 112 records are identical on .NET and Node
   Bench numbers	Harness and schema are done; there are 33 kernels × 2 runtimes. The baseline is pending (FS.GG.Algorithms#1): the quiet-host probe holds
   Published to nuget.org through the canonical route	Route in FS.GG.Algorithms#7 (release.yml: writer lock, gates, pack once, GitHub Packages then nuget.org via OIDC, readback). Writer registration in .github#5231. Pending: login preflight, publication of 0.1.0, readback and the registry reconcile
   Call sites migrate, or a follow-up per site	Seven call-site follow-ups are filed (below) and linked under #5222. Every one needs the published package, so none can migrate before the release

   Call-site follow-ups:

   Site	Follow-up
   Game.Core A* Set frontier to the F1 heap (exact pin, after release)	FS.GG.Game#803
   RuneScape BCL PriorityQueue	FS.GG.RuneScape#27
   RuneScape arbiter	FS.GG.RuneScape#28
   FourD re-sorted list frontier	FS.GG.FourD#64
   .github Blockers.cycles	#5232
   .github Lanes.partition	#5233
   Governance nearestRank	FS.GG.Governance#483
   SDD WorkModel.cycleDiagnostics	FS.GG.SDD#1160

   Ranked follow-ups (filed, linked under #5222), in order:

   Item	Issue
   N2b reactive composites	FS.GG.Algorithms#8
   N3 utility AI	FS.GG.Algorithms#9
   N4 HFSM	FS.GG.Algorithms#10
   N5 negamax α-β	FS.GG.Algorithms#11
   N6 MCTS	FS.GG.Algorithms#12
   N7 Reynolds steering	FS.GG.Algorithms#13
   N8 prediction and reconciliation	FS.GG.Algorithms#14
   N9 rollback	FS.GG.Algorithms#15
   N10 backoff and token bucket	FS.GG.Algorithms#16
   N11 navmesh	FS.GG.Algorithms#17
   N12 Lazy Theta*	FS.GG.Algorithms#18
   N13 HPA*	FS.GG.Algorithms#19
   N15 CSP	FS.GG.Algorithms#20
   N16 local search	FS.GG.Algorithms#21
   N17 Hungarian	FS.GG.Algorithms#22
   N18 WFC	FS.GG.Algorithms#23
   N19 noise	FS.GG.Algorithms#24
   N20 bandits	FS.GG.Algorithms#25
   N21 GOAP	FS.GG.Algorithms#26
   F2b fixed-point trigonometry	FS.GG.Algorithms#27

   Board enrollment of these 29 issues is a separate protected effect, left to Root.

   Knowledge

   Atlas fable/int32-multiply-javascript-number-semantics and fable/compile-gate-must-check-exit-status are merged (.github#5230). A third Fable lesson, from #6, is queued for capture after #6 merges: a side-effecting for upper bound is re-evaluated every iteration in JavaScript and evaluated once on .NET.

   Refs #5222
9. EHotwagner commented on Nov 2, 2026

   

   EHotwagner

   on Nov 2, 2026

   ContributorAuthor

   More actions

   Release boundary: the login-preflight stopped on a missing credential. Nothing was pushed.

   • dry-run, run 41378546040, on main at 97a7d402: success.

     • verify passed: build, tests, fable-proof: ok, and oracle checked 118 cases, 0 failed.
     • Archive: FS.GG.Algorithms.0.1.0.nupkg depends on ['FSharp.Core'] only and holds 26 fable/ files.
     • Artifact: fs-gg-algorithms-preflight-0.1.0-97a7d402…-41378546040.
     • publish and readback were skipped, as intended.

   • login-preflight, run 41378738441, on main at 97a7d402: failure at NuGet login. Every push step was skipped.

     Token exchange failed (HTTP 401) at https://www.nuget.org/api/v2/token. Make sure you are using the username of the policy creator, not the policy owner: No matching trust policy owned by user 'Paradigma11' was found.

   The gap: nuget.org has no Trusted Publishing policy for this repository. A nuget.org account holder for Paradigma11, the user the workflow passes, must create a GitHub Actions trusted publishing policy for:

   • repository owner FS-GG;
   • repository FS.GG.Algorithms;
   • workflow file release.yml;
   • no environment.

   If a different nuget.org user should own it, set the repository or org secret NUGET_USER to that user, who must also be the policy's creator.

   Once the policy exists: re-dispatch login-preflight, then record the bench baseline when the quiet-host probe admits (it holds now, load5 9.66 against 3.0), then tag v0.1.0. No other credential is known to be missing. The GitHub Packages push uses the run's GITHUB_TOKEN.

   Refs #5222
10. EHotwagner

    marked this as blocking 5 issues on Nov 2, 2026

    • Game.Core: migrate the A* Set frontier onto FS.GG.Algorithms BinaryHeap (exact pin) FS.GG.Game#803
    • Coord.Core: migrate Blockers.cycles onto FS.GG.Algorithms Graph.Scc (iterative Tarjan) #5232
    • Coord.Core: migrate Lanes.partition's union-find onto FS.GG.Algorithms Graph.UnionFind #5233
    • SddHandoff Performance: use FS.GG.Algorithms Numerics.Percentile for nearestRank FS.GG.Governance#483
    • WorkModel.cycleDiagnostics: consider FS.GG.Algorithms Graph.Scc for cycle detection FS.GG.SDD#1160
11. EHotwagner commented on Nov 2, 2026

    

    EHotwagner

    on Nov 2, 2026

    ContributorAuthor

    More actions

    fsgg-dispatch: item=#5224 role=worker

    FS.GG.Algorithms 0.1.0 is published, with readback complete

    Every step ran once. There were no retries and no re-pack. No other FS.GG.Algorithms PR was open or merged during the publish.

    Step	Evidence
    Login preflight	41398600754 on main at 1d37bf8378e47a3b7f576cb52549ee971099d808: NuGet OIDC login succeeded, nothing was pushed
    Tag	v0.1.0 (annotated object c22b8467) at 1d37bf83, the preflighted commit
    Release	41399115875, from the tag push: verify, publish and readback all succeeded
    Feed state before any push	github=false nuget=false
    Archive	FS.GG.Algorithms.0.1.0.nupkg, sha256 eea4b9468d81e0b92eb1c242ed7cbaeb03b9437b094b7038d87e696b0c615720; artifact fs-gg-algorithms-release-0.1.0-1d37bf83…
    Publish	the org publication-writer lock was held. The org feed received the archive first, then nuget.org through Trusted Publishing; nuget.org reported "Your package was pushed."
    publish-state	{"version":"0.1.0","commit":"1d37bf83…","archiveSha256":"eea4b946…","archiveRun":"41399115875","run":"41399115875","mode":"publish","githubPackagesPush":"success","nugetOrgPush":"success"}
    GitHub Packages	release-checks: GitHub Packages holds the archive's exact bytes (whole-file sha256)
    nuget.org payload	37 entries equal the archive (.signature.p7s and core properties excluded). The flat container first served it after 8 bounded polls.
    Clean consumer	restored from nuget.org alone. .NET and Fable print the same line: heap=bdac mul=-2147483648 div=2147483647 sqrt=11863283 xo=11520 seed=633975598 path=10/18

    Independent re-read from fdev:

    • The retained archive passes ORIGINAL_SHA256.
    • The nuget.org download (a7d2f475…) has a payload equal to the archive and adds only .signature.p7s.
    • The nuget.org registration shows 0.1.0 listed and published 2026-11-02T06:20:53Z.
    • A clean .NET consumer with an isolated cache and only nuget.org as a source restored 0.1.0 and ran (pop=1,2 asm=0.1.0.0).
    • GitHub Packages could not be re-read from fdev, because the local token lacks read:packages and the request returned HTTP 403. That equality rests on the run's readback job, which has packages: read.

    Registry: the reconcile is in draft PR #5243. It contains:

    • the algorithms repo row and contract at 0.1.0, with consumers: [];
    • the FS.GG.Algorithms package mapping for feed coherence;
    • an outside-fabric roster exemption until the skills producer lands (ADR-0098 §7);
    • the CHANGELOG entry, the architecture rows and the generated projections.

    Root reviews and merges it.

    Capture gap: Atlas github/nuget-trusted-publishing-policy-scope records a sixteen-policy owner readout that does not include the new FS.GG.Algorithms policy. Owner: Root. As reported, that policy's glob is * with "Push new packages and package versions", which is broader than the narrowed per-package globs of the other policies. Narrowing it to FS.GG.Algorithms and FS.GG.Algorithms.* is Root's choice.

    Merge hold: the publish is complete, so the merge hold on FS.GG.Algorithms can be released.
12. EHotwagner commented on Nov 2, 2026

    

    EHotwagner

    on Nov 2, 2026

    ContributorAuthor

    More actions

    Root/fdev acceptance of ALGO-01.2 (the library's first tranche). Every Done-when item is met:

    • Harvested:

      • A* with doors and planes: Search.Grid.DoorGrid, Algorithms#6.
      • Behaviour composition and arbitration: 208: rename fs-skia-ui-version/-bom → fs-gg-ui-version/-bom; ADR-0003 Accepted #3, P5 · Epic — Make the FsGgUiVersion staleness bug class structurally impossible #5, and reactive in build: api-breaking-change-gate in shared-build-config (H3, #20) #33.
      • Nearest-neighbour and spatial queries: Spatial.KdTree, P5 · Replace sync-from-rendering.sh with Renovate (grouped FS.GG.UI.*) or repository_dispatch auto-PR #6.

      All are clean re-implementations under the ALGO-01.1 — ADR: ownership, taxonomy, knowledge-pack format and product-workspace distribution #5223 ruling.

    • Absorbed: per ADR-0098, the grids, collision, line-drawing and visibility algorithms stay in Game.Core and are indexed by the pack (ALGO-01.3 — fs-gg-algorithms product skill + knowledge pack, materialized into fs-gg-fable-game workspaces #5225). Game's owed evidence is FS.GG.Game#804.

    • New: topological sort with CPM (registry: Feature 209 structurally gate-enforces fs-gg-ui-version / fs-gg-ui-bom coherence #4), the behaviour tree (P5 · Epic — Make the FsGgUiVersion staleness bug class structurally impossible #5) and reactive composites (build: api-breaking-change-gate in shared-build-config (H3, #20) #33).

    • Quality:

      • Property tests and independent oracles for each, all independently reviewed.
      • The Fable proof, a gate with a negative control and byte-identical lockstep on .NET and Node.
      • Bench numbers: the hosted baseline in ci: reusable contract-coherence gate (H3, #18) #32, with the spread documented.

    • Published: FS.GG.Algorithms 0.1.0 is on nuget.org through the canonical route.

      • Release run 41399115875 from tag v0.1.0, and GitHub Packages holds the exact bytes.
      • The nuget.org payload is equal, and a clean nuget.org-only consumer gives identical output on .NET and Fable.
      • The registry is reconciled in registry: register FS.GG.Algorithms and its published 0.1.0 (Refs FS-GG/.github#5224) #5243.

    • Call sites: a follow-up per site (Game#803, RuneScape#27 and registry: register fsgg-contracts@1.0.0 (H2, epic #16 Pillar 2; #27) #28, FourD#64, .github#5232 and Coord.Core: migrate Lanes.partition's union-find onto FS.GG.Algorithms Graph.UnionFind #5233, Governance#483, SDD#1160), now unblocked and moving to Ready.

    Remaining ranked items (N3–N21, F2b, #34, #35) are enrolled follow-ups. Closing as completed.
13. EHotwagner

    closed this as completedon Nov 2, 2026