FS.GG.Algorithms 0.3.0

Prefix Reserved
There is a newer version of this package available.
See the version list below for details.
dotnet add package FS.GG.Algorithms --version 0.3.0
                    
NuGet\Install-Package FS.GG.Algorithms -Version 0.3.0
                    
This command is intended to be used within the Package Manager Console in Visual Studio, as it uses the NuGet module's version of Install-Package.
<PackageReference Include="FS.GG.Algorithms" Version="0.3.0" />
                    
For projects that support PackageReference, copy this XML node into the project file to reference the package.
<PackageVersion Include="FS.GG.Algorithms" Version="0.3.0" />
                    
Directory.Packages.props
<PackageReference Include="FS.GG.Algorithms" />
                    
Project file
For projects that support Central Package Management (CPM), copy this XML node into the solution Directory.Packages.props file to version the package.
paket add FS.GG.Algorithms --version 0.3.0
                    
#r "nuget: FS.GG.Algorithms, 0.3.0"
                    
#r directive can be used in F# Interactive and Polyglot Notebooks. Copy this into the interactive tool or source code of the script to reference the package.
#:package FS.GG.Algorithms@0.3.0
                    
#:package directive can be used in C# file-based apps starting in .NET 10 preview 4. Copy this into a .cs file before any lines of code to reference the package.
#addin nuget:?package=FS.GG.Algorithms&version=0.3.0
                    
Install as a Cake Addin
#tool nuget:?package=FS.GG.Algorithms&version=0.3.0
                    
Install as a Cake Tool

FS.GG.Algorithms

Shared, tested algorithms for FS.GG, decided by ADR-0098. The library depends on FSharp.Core only, and every module compiles under Fable. Surfaces graded LockstepExact give byte-identical results on .NET and JavaScript.

This repository also owns the fs-gg-algorithms knowledge pack, delivered under ALGO-01.3 (.github#5225).

What is here (tranche 1: foundations and harvest)

Namespace Surface Grade Oracle
FS.GG.Algorithms.Collections BinaryHeap, IndexedHeap (decrease-key, update, remove) LockstepExact, frozen ordering contract sorted-list and map models; lazy-deletion equivalence
FS.GG.Algorithms.Numerics Fixed (Q16.16: saturating, no int64) LockstepExact (float conversions Portable) exact BigInteger arithmetic
FS.GG.Algorithms.Graph BestFirst (Dijkstra, A*, distances) on the indexed heap LockstepExact for integer costs BFS, Bellman-Ford, exhaustive enumeration
FS.GG.Algorithms.Random Xoshiro128 (xoshiro128**, seed, split, jump) LockstepExact (nextFloat Portable) published reference vector; independent Python implementation
FS.GG.Algorithms.Numerics Percentile (nearest rank, exact integer rank) LockstepExact exhaustive small domain; BigInteger
FS.GG.Algorithms.Graph Scc (iterative Tarjan: components, cycles, componentOf) LockstepExact a recursive Tarjan; reachability closure
FS.GG.Algorithms.Graph UnionFind (smallest-member representative, partition by a conflict predicate) LockstepExact BFS components
FS.GG.Algorithms.Graph TopoSort (Kahn, least-first under a caller order; critical-path method) LockstepExact Tarjan cycles; a list model; brute-force longest path
FS.GG.Algorithms.Search.Grid DoorGrid (layered-grid A*: thin walls, doors, planes and stairs, no corner cutting) LockstepExact an independently written adjacency plus Dijkstra
FS.GG.Algorithms.Spatial KdTree (nearest, k-nearest, radius and rectangle queries over integer points) LockstepExact a brute-force scan
FS.GG.Algorithms.Decision Arbitration (priority bands, pre-emption, suspend and resume) LockstepExact invariants after every input; no-starvation drain; a Python model
FS.GG.Algorithms.Decision Hfsm (a pure reducer for hierarchical state machines: innermost-first dispatch, nested exit, effect and entry actions, initial-child descent, internal transitions) LockstepExact an independent nesting stack machine; a list-based reference model; exhaustive small hierarchies; a Python model
FS.GG.Algorithms.Adversarial Negamax and Zobrist (alpha-beta negamax with a transposition table and iterative deepening; Zobrist keys as two int32 halves) LockstepExact an independent plain minimax with explicit MAX and MIN players; a textbook recursive alpha-beta; a solved tic-tac-toe; a Python minimax model
FS.GG.Algorithms.Decision BehaviourTree (a pure tick reducer: memory composites, and reactive Sequence and Fallback for priority interrupts that halt the abandoned running branch; parallel, decorators, blackboard) LockstepExact a recursive reference interpreter; an invariant fuzz of the halt invariant; fail-fast and idempotence properties

Release 0.3.0 adds Decision.UtilityAi, graded LockstepExact, with independent integer oracles for bounded scoring, monotone curves, ordered multiplication and stable selection, and Decision.Hfsm, graded LockstepExact, a hierarchical finite state machine whose exit and entry actions are proven properly nested against two independent oracles. It also adds Adversarial.Negamax and Adversarial.Zobrist, graded LockstepExact, an alpha-beta search whose value is proven equal to plain minimax.

The grades are recorded in src/FS.GG.Algorithms/Fable/compatibility-profile.v1.json. The public surface is declared in the .fsi signature files.

Utility AI (0.3.0)

Decision.UtilityAi uses F2 Q16.16 throughout. score clamps every raw Fixed value to 0..1; evaluate applies UtilityCurve.Linear, Quadratic or SquareRoot after clamping. The responses are monotone increasing with exact endpoints. invert complements a score for decreasing responses. Quadratic rounds by F2 nearest/ties-up multiplication; square root rounds down.

product multiplies considerations in list order, rounding after each multiplication. Empty means 1, and zero vetoes. It applies no compensation or weights; order can affect the last bit through rounding. choose returns the first highest-scoring action, including the first when all scores are zero, or None for an empty list. Both traversals are iterative. Callers supply normalized inputs and stable action ordering; no floating-point transcendental participates in action selection.

The admission evidence is the independent integer FsCheck oracles, exhaustive 65,537-point response checks, operation 16 in the append-only lockstep corpus, and the maintained packed .NET/Fable consumer. The new decision/utility-ai/score-select benchmark covers 1,000, 10,000 and 100,000 actions on each runtime; its timing baseline is in the 0.3.0 hosted baseline below. The historical 0.2.0 baseline does not measure utility AI.

Hierarchical state machine (0.3.0)

Decision.Hfsm (ADR-0098 N4) is a pure reducer over a state hierarchy. A state is its index in the list given to Hfsm.compile; its parent must be an earlier state, so the hierarchy is a tree by construction, and a composite state's first listed child is its initial child. The memory is one integer, the active leaf; the active configuration is that leaf and its ancestors. Events are caller-chosen integers, and actions are caller values that step returns and never runs.

An event goes to the active leaf and then outward to the root. The innermost state with a transition for it handles it, and within a state the first declared transition wins. An external transition from S to T emits the exit actions of the active states below the lowest proper common ancestor of S and T, innermost first, then the transition's effect, then the entry actions down to T outermost first, then the entries along initial children down to a leaf. A self transition or a transition to a descendant exits and re-enters the source; one to an ancestor exits the source and re-enters the ancestor, then follows initial children. An internal transition (Target = None) emits only its effect. History, orthogonal regions, deferred events and guards are not in this surface; a guard decides which integer event the caller dispatches.

The admission evidence is two independent oracles under FsCheck: a stack machine that replays every emitted action trace as nested scopes (an entry must be a child of the innermost entered state; an exit must be that state; the stack after each step must equal the reported root-to-leaf path), and a list-based reference model written on explicit paths. An exhaustive check enumerates every hierarchy up to six states with every source, target and active leaf. Operation 17 of the append-only lockstep corpus adds 17 cases, checked by a third, Python, model and run identically on .NET and under Fable/Node; every operation is a loop, and a hierarchy 10^5 levels deep and one 10^5 states wide run under Node's default stack. The decision/hfsm/dispatch benchmark dispatches 1,000, 10,000 and 100,000 events through a 127-state hierarchy on each runtime; its work counts are equal on both runtimes in the harness smoke. Its timing baseline is in the 0.3.0 hosted baseline below.

Negamax alpha-beta search (0.3.0)

Adversarial.Negamax (ADR-0098 N5) searches a two-player zero-sum game of perfect information. The caller supplies a NegamaxGame: Moves, Apply, Evaluate (the score for the side to move, within +/-10^9) and Key. Key is a ZobristKey, a 64-bit position key held as two int32 halves, so no int64 (a BigInt under Fable) is used; Zobrist builds the keys from the library's 32-bit generator and combines them by xor, so a game can update a key move by move. Negamax.searchFixed searches to an exact depth. Negamax.iterate runs the depths 1, 2, ... in turn on one TranspositionTable, so each depth tries the previous depth's best move first.

The table answers a position only when it was searched to exactly the plies still to go, and only when its bound decides the current window; a deeper entry would answer a different question. The result is therefore the plain fixed-depth minimax value whatever the table size, its contents or the move order, provided a position's value depends only on the position. The root is never answered from the table, so it always reports a move. The search is a loop over an explicit stack: a line 10^5 plies deep and a position with 10^5 moves run under Node's default stack.

The admission evidence is an independent plain minimax with explicit MAX and MIN players and no pruning, checked under FsCheck over random game graphs with transpositions and cycles, for every table size from one slot, for tables already filled by earlier searches, and for reversed move order; node counts that equal a textbook recursive alpha-beta on game trees; and a solved tic-tac-toe. Operation 18 of the append-only lockstep corpus adds 20 cases, checked by a Python minimax model and the xoshiro128** reference model for the keys, and run identically on .NET and under Fable/Node. The adversarial/negamax-alpha-beta-tt/iterate benchmark searches an implicit 4096-position game to depths 6, 8 and 10 on each runtime; its work counts are equal on both runtimes in the harness smoke. Its timing baseline is in the 0.3.0 hosted baseline below. The pack entry cites the merged revision 472c170.

0.3.0 API additions

Additive only; no existing public signature or LockstepExact result changes, and the heap ordering contract below is unchanged. FS.GG.Algorithms.Skills 0.2.0 ships the matching pack entries.

  • Decision.UtilityAi: bounded Q16.16 scoring, three monotone responses, ordered product and first-on-tie choose (fixture operation 16).
  • Decision.Hfsm: a pure hierarchical state machine reducer with properly nested exit and entry actions (fixture operation 17).
  • Adversarial.Negamax and Adversarial.Zobrist: alpha-beta negamax with a transposition table and iterative deepening, and two-int32-half Zobrist keys (fixture operation 18).

0.2.0 API additions

BehaviourTree.tickTracedWithHalts adds a fifth return value to the traced result: the preorder indices of leaves halted by preemption or a finishing Parallel. Cancel those actions after the tick returns. The indices identify tree occurrences, so equal leaf values can appear at different indices. Halts follow abandonment-event order, then preorder within each abandoned branch; repeated activations can repeat an index. Completed and idle leaves are excluded. Existing tick and tickTraced calls retain their results.

let status, nextState, nextBlackboard, visited, halted =
    BehaviourTree.tickTracedWithHalts program leaf state blackboard

The heap ordering contract is frozen. Among equal priorities, BinaryHeap pops in push order and IndexedHeap pops in the order the priorities were set. FS.GG.Game.Core pins this contract (ADR-0098 §1). Changing the pop order for any input is a breaking change with a new compatibility identity.

Layout

src/FS.GG.Algorithms/            the library (packs its sources under fable/ for Fable consumers)
  Fable/                         compatibility profile, fixture schema, toolchain manifest
tests/FS.GG.Algorithms.Tests/    FsCheck properties against oracles in the test project only
tests/FS.GG.Algorithms.Lockstep/ the cross-runtime fixture program and fixtures/v1/{cases,expected}.bin
scripts/lockstep-fixtures.py     corpus generator and independent Python oracle
eng/fable-proof.sh               the Fable proof (ADR-0069)
bench/                           BenchmarkDotNet, the Node harness, the results schema and baselines
docs/licence-allowlist.md        what may be ported, and from where

Build and verify

The SDK is pinned in global.json (10.0.403), and Fable 5.26.0 is pinned in .config/dotnet-tools.json.

dotnet restore FS.GG.Algorithms.slnx --locked-mode
dotnet build FS.GG.Algorithms.slnx --no-restore
dotnet run --project tests/FS.GG.Algorithms.Tests --no-build     # FSGG_ALGO_MAXTEST=5000 for a longer soak
eng/fable-proof.sh                                                # needs node

The Fable proof checks five things:

  • The same canonical input bytes run on .NET and under Node, and both outputs are byte-identical to expected.bin.
  • An independent Python oracle re-derives every record.
  • The 10^5-element stack-safety checks pass under Node's default stack.
  • A clean consumer compiled by Fable from the packed package prints the same line as on .NET.
  • The package depends on FSharp.Core only.

After changing the corpus generator, run scripts/lockstep-fixtures.py generate. Then regenerate expected.bin from the .NET fixture program, check it with scripts/lockstep-fixtures.py oracle, and update both digests in fixture-schema.v1.json. A changed expected.bin for an existing case is a change to a LockstepExact surface.

Benchmarks

bench/run.sh times every kernel on .NET (BenchmarkDotNet) and on Node (the Fable output, bench/fable/run.mjs). It uses fixed seeded inputs at three declared sizes and records deterministic work counts. Results go to bench/baselines/<host>-<date>-<version>.json against bench/results.schema.v1.json.

A recording run is admitted only by FS-GG/.github's fdev-lane-capacity.py --max-load-per-core 0.25. A held probe waits and is never overridden, and a recording run refuses a dirty tree. bench/run.sh --smoke proves the harness without recording anything. Work counts may gate regressions; timings never do.

Because fdev is rarely quiet while review lanes run, the baseline for FS-GG/.github#5224 is recorded on a GitHub-hosted runner. The bench workflow (workflow_dispatch, ubuntu-latest) runs the full bench with bench/run.sh --hosted. Three such runs on clean main are combined by bench/combine.py into one baseline, with the per-kernel median across runs and the run-to-run spread (min, max and CV). The baseline also records the runner image, the .NET SDK, Node and Fable. Hosted-runner numbers are for regression comparison under the same runner class, not absolute performance. A quiet-fdev baseline remains an optional refinement (FS.GG.Algorithms#1).

The 0.3.0 hosted baseline records all 45 cases per runtime, adding decision/utility-ai/score-select, decision/hfsm/dispatch and adversarial/negamax-alpha-beta-tt/iterate (9 cases) to the 36 of the 0.2.0 baseline. It combines three sequential runs on clean commit c4582f7d720ade92e22e524d03ab52bd2d58719c (package version 0.3.0): 42537183401, 42538300843 and 42539475961. All three used Ubuntu 24 image 20261101.360.1, SDK 10.0.403, Fable 5.26.0 and Node 26.13.0, and their case and work-count sets match; work counts are equal on both runtimes. The CPU models varied within that hosted class, and the run-to-run CVs reach 0.39 (the largest, .NET graph/union-find/random-unions at 10,000). decision/utility-ai/score-select at 100,000 actions on .NET has run medians from 4.3 ms to 8.6 ms (CV 0.29), so read the stored min/max and CV alongside each median when comparing runs. The three new kernels' work counts are 2,000, 20,000 and 200,000 (utility-ai), 8,844, 88,359 and 881,189 (hfsm), and 1,880, 14,346 and 83,496 (negamax, summed over depths 6, 8 and 10).

The 0.2.0 hosted baseline records all 36 cases per runtime, including decision/behaviour-tree/reactive-ticks at 1,000, 10,000 and 100,000 ticks. It combines three sequential runs on clean commit 12b7e6426c27c637edcdacd5a1a0a9beb98864a0: 41776406267, 41777472739 and 41778657220. All three used Ubuntu 24 image 20261026.354.1, SDK 10.0.403, Fable 5.26.0 and Node 26.13.0, and their full case and work-count sets match. The CPU models varied within that hosted class; the reactive cases have run-to-run CVs of about 0.24–0.33. Read the stored min/max and CV alongside each median when comparing runs. The reactive kernel measures the BehaviourTree.tick entry point.

Release

.github/workflows/release.yml publishes the library to nuget.org only, through Trusted Publishing (OIDC). It pushes the retained .nupkg and never re-packs it. It has three jobs:

  • verify (read-only) runs the gates on the exact commit: locked restore, build, property tests and the Fable proof. For a fresh publish it also does the one pack, retained as an artifact with its sha256.
  • publish holds the credentials, behind the org publication writer lock (ADR-0097). It verifies the archive's sha256, then pushes. nuget.org counts as holding a version only on HTTP 200 and as lacking it only on HTTP 404; any other answer fails closed (eng/release-checks.py, tested by eng/release-checks.test.py). It refuses to re-push a version that nuget.org already holds, because a re-pack is not byte-identical; it always records publish-state.json.
  • readback (read-only) checks that nuget.org's copy carries the retained archive's payload, apart from its signature and core properties. The retained archive is this run's, or the validated source run's; a feed copy is never taken as the original. It then restores a clean consumer from nuget.org alone and runs it on .NET and under Fable.
Trigger Ref Effect
push tag v<version> the tag publish; the tag must equal <Version>
dispatch dry-run any verify and pack only
dispatch login-preflight any verify, pack and the nuget.org token exchange, with no push
dispatch publish refs/tags/v<version> publish
dispatch resume + source_run_id refs/tags/v<version> re-push the original archive of a partial publish. The source must be the fresh publish run of this commit and version, with its publish-state.json naming the archive's sha256, and any copy nuget.org serves must carry its exact payload; nothing is re-packed
dispatch readback + source_run_id refs/tags/v<version> readback only, after a readback timeout, against the retained archive of the original publish run

A resume or standalone readback needs the original run's retained archive and publish-state.json. Both are kept for 90 days, so neither mode is possible after that.

Licence

MIT (LICENSE). Code is implemented from papers. It is ported only under the allowlist in docs/licence-allowlist.md, with the notice carried in THIRD-PARTY-NOTICES.md. No GPL or LGPL code, and no game data.

Product Compatible and additional computed target framework versions.
.NET net10.0 is compatible.  net10.0-android was computed.  net10.0-browser was computed.  net10.0-ios was computed.  net10.0-maccatalyst was computed.  net10.0-macos was computed.  net10.0-tvos was computed.  net10.0-windows was computed. 
Compatible target framework(s)
Included target framework(s) (in package)
Learn more about Target Frameworks and .NET Standard.

NuGet packages

This package is not used by any NuGet packages.

GitHub repositories

This package is not used by any popular GitHub repositories.

Version Downloads Last Updated
0.4.0 103 11/9/2026
0.3.0 94 11/9/2026
0.2.0 195 11/4/2026
0.1.0 1,100 11/2/2026