SirRoboGarage/BNNBot_garage/analysis/domain_math.md

Discrete Mathematics Lens on BNNBot

Context: 690-bit binary input (Gray-coded, 10-frame temporal window), online learning, reward = miss distance from circular wave feedback. No gradient descent. Binary weights/activations.

---

Structural Properties of Our Binary Space (Read First)

Before any framework, pin down what structure the 690-bit input already has. These properties constrain which mathematical tools apply and where untapped leverage exists.

Gray Coding = Embedded Metric Structure

Gray code is an isometry between adjacent integers and Hamming-1 neighbors. For our encoding:

• x_t → x_t + δ in physics space maps to Gray(x_t) → Gray(x_t + δ) with Hamming distance ≈ 1 per bit-field (vs up to log2(n) for binary encoding)
• Consequence: physically similar states are Hamming-close states. The input manifold has Lipschitz-like smoothness in Hamming metric. Any distance-based hash, nearest-neighbor lookup, or locality-sensitive scheme exploits this for free.
• Not exploiting this: our Hebbian residual table uses only 24 cells (8 heading sectors × 3 distance bands). The cells discretize the continuous physics space, but ignore the Hamming metric structure entirely. A hash-based retrieval over the full 690-bit vector would be more precise.

Temporal Redundancy (10 frames × 69 bits)

Consecutive frames differ by ~1 enemy move. Gray-coded, that means Hamming distance between frame i and frame i+1 ≈ 3-6 bits out of 69. The 690-bit vector has:

• Strong temporal autocorrelation: I(f_t; f_{t-1}) ≈ high (most bits identical tick-to-tick)
• True information content < 690 bits: an MDL estimate is ~69 bits (one frame) for near-constant velocity movement plus ~6-8 bits for heading+speed change. The 10× redundancy is useful for noise robustness but the irreducible information is small.
• Implication: a model that learns which bits change between frames carries more signal than one treating all 690 bits uniformly. Temporal XOR (frame[t] ⊕ frame[t-1]) compresses the motion into ~6-10 bits per step.

Sparsity (10/24 residual cells active, observed)

The data shows only ~10 out of 24 residual cells activate meaningfully. This suggests the function mapping input → correction is sparse in some basis. The true prediction correction depends on a small number of input features. This is compressed-sensing territory: the signal is k-sparse in some unknown basis with k << 690.

Linearity Obstacle in GF(2)

XOR layers are linear over GF(2). XOR + popcount + threshold is the minimal non-linear binary neuron. Any network restricted to XOR-only layers computes an affine function over GF(2), which cannot represent the non-linear corrections needed. The algebraic normal form of any Boolean function requires at least degree-2 monomials (AND of two variables) to be non-affine. Our residual correction IS non-linear in the input (it depends on distance × heading interaction), so linear-over-GF(2) architectures are fundamentally insufficient.

---

Framework 1: Boolean Function Learning (PAC / Fourier Analysis)

Mathematical Framework

Every Boolean function f: {0,1}^n → {-1,+1} has a unique representation as a multilinear polynomial (the Walsh-Fourier expansion):

f(x) = Σ_{S ⊆ [n]} f̂(S) · χ_S(x)

where χ_S(x) = Π_{i∈S} (1 - 2x_i) is a parity function over subset S, and f̂(S) are real Fourier coefficients. The sum of squared coefficients is 1: Σ f̂(S)² = 1 (Parseval).

PAC learnability classes (Valiant 1984):

• k-CNF and k-DNF (bounded clause width): efficiently PAC-learnable in poly time
• Monotone conjunctions: learnable
• General DNF: open problem; likely hard (hardness results by Klivans & Servedio, 2004)
• Decision trees of depth d: learnable from Fourier spectrum
• Halfspaces (linear threshold functions): poly-time learnable (perceptron)
• Majorities, parities of few bits: learnable; sparse Fourier spectrum

Key result for us: a function is efficiently PAC-learnable iff it has a sparse low-degree Fourier spectrum (KM algorithm, Kushilevitz & Mansour 1993). The SPRIGHT algorithm recovers K-sparse WHT in O(K n log n) samples.

Mapping to 690-bit → Predicted Position

Our output is not Boolean but real-valued (predicted x,y correction). We can still ask: what is the structure of the Fourier spectrum of, say, the indicator function "will this input lead to a hit?" Given that 10/24 sectors activate and the function appears to depend on a small number of features, hypothesis: the hit-prediction function has a sparse, low-degree Fourier spectrum.

Key consequence: if the function is concentrated on degree-≤2 Fourier coefficients, it is approximable by a sum of pairwise interactions — which maps directly to a Boltzmann machine or second-order Hebbian network.

Update Rule Sketch

Run a sparse Walsh-Hadamard transform incrementally:

1. Maintain counters c_S for each "candidate" subset S (start with S = singletons + pairs)
2. On each wave feedback: c_S += hit? ? +1 : -1 for each S where χ_S(x) = +1
3. Top-K coefficients define a linear predictor over parity features
4. Prediction: ŷ = Σ_S∈top-K ĉ_S · χ_S(x) (cast to position offset)

This is online Fourier learning. The KM algorithm suggests O(n/ε²) samples for ε-approximation of sparse functions.

Computational Cost

Tracking singletons: O(n) = O(690) counters, trivial. Tracking pairs: O(n²) = O(476K) — borderline. Tracking triples: O(n³) — infeasible. Practical: limit to degree-1 (linear) + degree-2 (pairwise) terms and test if this captures the signal. Expected O(1000) battle samples to recover top-10 coefficients if the function has 10-sparse Fourier spectrum.

Untapped Structure

Gray coding means adjacent input values differ by Hamming-1. In Fourier space, a Gray-smooth function has Fourier weight concentrated at low-frequency (small S) coefficients. This is the Grey-code smoothness guarantee translating to Fourier sparsity at low degree. We should be able to identify the top-K coefficients with far fewer samples than general Boolean functions because smoothness bounds the spectrum.

---

Framework 2: Combinatorial Bandits on the Binary Hypercube

Mathematical Framework

A multi-armed bandit selects actions from an action set A. In the combinatorial bandit setting (Chen et al. 2013, Kveton et al. 2015), each action is a subset of "base arms" (bits), with reward that decomposes over the selected set. Regret bound: O(√(KT log K)) for CombLinUCB where K = number of active bits and T = rounds.

For binary weight vectors, the action is a weight configuration w ∈ {0,1}^N, reward R(w) = hit rate. This is a bandit over an exponential action space — we need structure to make it tractable.

Thompson Sampling (binary/Bernoulli): each weight w_i has Beta(α_i, β_i) posterior on its contribution to reward. Sample θ_i ~ Beta(α_i, β_i), set w_i = 1 if θ_i > 0.5, observe reward. Update: α_i += hit, β_i += miss. This is the simplest online binary learning rule that is principled under uncertainty.

Mapping to Aiming

Reframe: each "arm" is not a single weight but a candidate aiming strategy — a specific correction (Δx, Δy) to add to linear extrapolation. The bandit chooses which correction to apply given input context x. Reward = did the bullet hit?

This is a contextual bandit (the reward depends on x). For contextual bandits with binary context, the LinUCB / LinTS extensions apply.

Practical sketch: Discretize corrections into B bins (e.g., 50 bins per axis = 2500 joint corrections). For each bin b, track Beta(α_b, β_b). Given input x, compute a context-conditioned expected reward E[R | x, b] via Thompson sampling on the posterior. This gives a Bayesian bandit over correction bins — exactly what the Hebbian residual table approximates, but with proper uncertainty quantification and exploration.

Update Rule Sketch

# Per wave-hit event:
b* = current correction bin (from predicted position)
if hit:
    α[b*] += 1
else:
    # reward is shaped by miss distance
    α[b*] += exp(-miss_distance / σ)
    β[b*] += 1 - exp(-miss_distance / σ)

# Prediction:
sample θ_b ~ Beta(α_b, β_b) for each b
b_chosen = argmax_{b} f(x, b, θ_b)  # context-weighted Thompson sampling

Computational Cost and Convergence

Beta updates: O(1) per arm per round. Sample from Beta: O(1). With B correction bins, total per-tick cost: O(B). Convergence: Thompson sampling achieves O(√(BT log B)) regret (Agrawal & Goyal 2013), meaning after T=1000 battle ticks, expected suboptimality ≈ O(√(B · 1000 · log B)). For B=100, this is ~O(300) — significant but manageable for a battle that repeats.

Key advantage over current table: Thompson sampling maintains per-bin uncertainty and auto-balances exploration/exploitation. The current Hebbian table uses fixed lr=0.2 with no exploration bonus — it may get stuck in local optima in bins with few observations.

---

Framework 3: Binary Optimization Without Gradients

Simulated Annealing on Weight Vectors

SA on {-1,+1}^N: at temperature T, flip weight w_i with acceptance probability min(1, exp(-ΔE/T)). Energy E = cumulative miss distance over recent battles. Schedule: T(t) = T_0 / log(1+t).

Convergence theory: SA converges to global optimum in probability if T→0 sufficiently slowly. In practice, for binary problems with N=690 weights, O(N² log N) iterations needed for reliable convergence — infeasible within a 1000-tick battle.

Practical use: SA is viable for the small residual table (24 cells × 2 floats = 48 params). Current lr=0.2 Hebbian update is essentially SA with constant temperature. Adding a cooling schedule would improve final-state quality at the cost of slower convergence.

Key formula: for binary weights, ΔE per bit flip is the reward delta from that flip. This is exactly weight perturbation (Method 6 in learning_methods_report.md). SA IS weight perturbation with a temperature schedule.

Tabu Search

Maintain a tabu list of recently visited weight configurations. At each step, flip the bit that most improves reward while not being on the tabu list. The tabu list prevents cycling.

For the 24-cell residual table, tabu search is practical. For the full BNN weight matrix (N >> 24), the tabu list overhead grows prohibitively. Recent work (2023, ScienceDirect) shows tabu search exploiting local optimality in binary problems achieves better solutions than SA when the objective has many local optima — which is plausible for a non-stationary opponent.

Convergence: guaranteed if neighborhood is strongly connected (all {-1,+1}^N reachable) and tabu tenure is bounded. In practice, tabu tenure τ ≈ sqrt(N) gives empirically good results.

Convergence Comparison (rough, for context)

Method	Iterations for N-bit problem	Notes
Brute force	2^N	infeasible for N>30
SA	O(N² log N)	with correct schedule
Tabu search	O(N^1.5) to O(N²)	empirically
Bandit (Thompson)	O(N log N) / O(√T) regret	if decomposable
Fourier / KM	O(N/ε²)	if function is sparse
Hebbian (current)	O(1/lr) per cell	greedy, may not converge

For N=24 (current table): all methods viable within 1000 ticks. For N=690 (full weight vector): only bandit and Fourier methods are feasible.

---

Framework 4: Locality-Sensitive Hashing on Gray-Coded Inputs

Mathematical Framework

LSH for Hamming distance: a random hash function h(x) = x[i] (select random bit i) collides two binary vectors x, y with probability 1 - d_H(x,y)/n, where d_H is Hamming distance and n=690. This is Hamming-LSH — trivially computable, requires no training.

For our Gray-coded inputs: two consecutive enemy positions differ by d_H ≈ 3-6 bits. The LSH collision probability for such pairs is (690-5)/690 ≈ 99.3%. This means random bit-sampling is an excellent locality-preserving hash for our input.

Content-Addressable Memory (CAM) System

Architecture: store (input_hash, correction) pairs. On new input, retrieve the k nearest stored inputs by Hamming distance, average their corrections.

This is the k-nearest-neighbor predictor in Hamming space, implemented via LSH buckets for efficiency.

Why this is powerful for us: Gray coding guarantees that physically similar states (same heading, similar distance) have Hamming-close encodings. A CAM retrieval over Hamming distance directly recovers "similar situations had correction Δ_i", which is exactly the non-parametric Hebbian correction we want but without the coarse 24-cell discretization.

Implementation Sketch

# Storage (bounded buffer, ~200 entries max)
memory = []  # list of (x_690bit, correction_xy)

# Learning (on wave hit):
memory.append((current_input, observed_correction))
if len(memory) > MAX: memory.pop(0)  # FIFO or evict worst

# Prediction:
# Find k nearest inputs by Hamming distance (XOR+popcount, hardware-accelerated)
dists = [popcount(x XOR stored_x) for stored_x in memory]
k_nearest = nsmallest(k, zip(dists, memory))
correction = weighted_average([c for (_, c) in k_nearest],
                              weights=[1/(d+1) for (d, _) in k_nearest])

Cost: O(|memory| × 690/64) per prediction (popcount on 64-bit words, ~11 ops per entry). For 200 stored entries: ~2200 bitops per prediction — within 1ms budget.

Convergence: after M examples, k-NN with Hamming metric converges to the Bayes-optimal predictor for any Lipschitz-continuous function in Hamming metric. Our Gray-coded input IS Hamming-Lipschitz. This is non-parametric with O(M^{-d/(d+2)}) convergence rate for effective dimension d. If d is small (our data suggests ~3-5 physical degrees of freedom map to the correction), convergence is fast.

What We're Not Exploiting

The current 24-cell table partitions input space by two hand-chosen features (heading sector, distance band). LSH with Hamming distance exploits all 690 bits equally weighted. The Gray structure means we could use ANY two bits that differ between nearby states as an LSH hash for those states. The system naturally finds the relevant bits by collision frequency.

---

Framework 5: Information-Theoretic Approaches

Minimum Description Length (MDL) for Model Selection

MDL principle: choose the model M that minimizes L(M) + L(Data|M), where L is description length in bits.

For our prediction problem, MDL gives a principled way to choose between:

• Linear extrapolation (24 params × 32 bits = 768 bits to describe)
• Hebbian 24-cell table (24 × 64 bits = 1536 bits + cell selection logic)
• k-NN memory (200 × (690+64) bits = ~150KB)
• Full BNN (690 × 128 + 128 × 64 = 97K params × 1 bit = 12KB binary)

MDL predicts: use the simplest model that compresses battle data. If linear extrapolation already compresses (MAE 8.1 units baseline), the incremental description-length reduction from more complex models must exceed their description cost.

Practical MDL estimate:

• Linear: already needs 0 extra bits (hardcoded physics)
• Hebbian table: 24 cells, each storing 2 floats. If only 10 cells activate, effective description is 10 × 2 × 32 ≈ 640 bits. Very cheap.
• Full BNN: 12KB. This is only justified if it reduces prediction error enough to compress the residuals by > 12KB.

Key insight: Given that 10/24 Hebbian cells activate, the true model has ~10 degrees of freedom. Any model with > 10 effectively independent parameters is overfitting to a sparse signal. This argues strongly against large BNN architectures for this task.

Mutual Information and the Information Bottleneck

The information bottleneck principle (Tishby & Zaslavsky 2015): an optimal representation Z of input X for predicting output Y maximizes I(Z; Y) while minimizing I(Z; X) (compression).

For our 690-bit input:

• I(X; Y) = mutual information between input and correct correction ≈ a few bits (given that ~97.8% of motion is constant-velocity, the correction signal is low-entropy)
• Optimal bottleneck Z should be ~5-10 bits if the correction depends on ~3-5 physical variables

Implication: a 690-bit → 5-bit bottleneck should capture nearly all prediction-relevant information. More hidden-layer capacity is wasted on input noise. The current Hebbian table with 24 cells (effectively log2(24) ≈ 4.5 bits of index) is close to the information-optimal representation size.

Rate-Distortion Lower Bound

For any binary encoding of corrections with rate R bits: D*(R) ≥ D_max · 2^{-R/H}

where D_max is the baseline distortion and H is the entropy of the correction signal.

If H ≈ 5 bits (3-5 degrees of freedom): to halve prediction error (D = 0.5 D_max) we need R = 5 bits of model capacity. The current 4.5-bit residual table is near the Shannon limit for this task. Going deeper adds computation without information-theoretic benefit unless we're wrong about H.

---

Framework 6: Finite Field Arithmetic — GF(2)

What GF(2) Can and Cannot Compute

A Boolean function f: {0,1}^n → {0,1} has a unique algebraic normal form (ANF):

f(x) = Σ_{S ⊆ [n]} a_S · Π_{i∈S} x_i   (sum/product mod 2)

• Degree 1 (a_S = 0 for |S| > 1): affine functions = XOR of input bits + constant
• Degree 2: affine + pairwise products (AND of two bits XOR'd together)
• Maximum degree n: any Boolean function is representable

Key result: any function with full degree n in its ANF is not learnable from a linear (XOR-only) network. Our required correction function, mapping Gray-coded position to position offset, has non-trivial degree because distance × heading interactions are necessary for good corrections.

Algebraic immunity: A function with algebraic immunity d requires an adversary to know d+1 bits of correlation to predict the output. For cryptographic functions (bent functions), algebraic immunity is maximized (≈ n/2). For our case, we want the OPPOSITE: low algebraic immunity means few bits predict the output, which is what we observe.

Bent Functions and Non-Linearity

A bent function is maximally non-linear: equally distant from all affine functions. The correction from linear extrapolation is a non-affine function of the input, but we want to characterize how non-linear it is to choose the right architecture.

If the correction function has low algebraic degree (2-3), a second-order Hebbian network (tracking pairwise bit correlations) would suffice. If it has high degree, deeper architectures are needed.

Hypothesis from data: since 10/24 coarse cells captures 14-21% MAE reduction, the correction is primarily a degree-1 function of the coarse features (heading, distance) plus small degree-2 perturbations. Algebraic degree ≤ 2 is a reasonable prior.

Practical Consequence

XOR + popcount + threshold computes a linear threshold function over GF(2) — a halfspace in {0,1}^n with the XOR inner product. This is equivalent to a single parity-check + threshold. It is more expressive than pure XOR (which is degree-1 over GF(2)) but less expressive than arbitrary degree-2 functions. The key non-linearity needed — "distance AND heading interaction" — requires at minimum one AND gate, which is degree-2 over GF(2).

Architecture implication: XOR + popcount is necessary AND nearly sufficient for degree-2 correction functions, because popcount over a selected subset of bits computes a weighted degree-2 interaction. A single hidden layer with XOR + popcount neurons is algebraically adequate for the signal we observe.

---

Framework 7: Cellular Automata Rules

Wolfram's Elementary CA Rule Space

Elementary 1D CA: 256 rules mapping (left, center, right) bits → new center bit. Wolfram's Class IV (e.g., Rule 110, proven Turing-complete by Cook 2004) produces complex, structured patterns from simple rules.

Application to Temporal Pattern Prediction

Our 10-frame temporal window looks like a 1D CA: at each step, the state evolves according to some rule that depends on neighbors (surrounding bits in the encoding). If enemy motion follows a simple physical rule, the temporal evolution of the 690-bit vector might be approximated by a CA rule applied to a small neighborhood of bits.

Sketch: identify which 3-7 bits in frame t most predict the change in bit b in frame t+1 (via correlation). Define a local rule: b_{t+1} = f(neighborhood_t). This rule, applied uniformly across the 69-bit frame encoding, defines a CA-like predictor.

Convergence and utility: for the specific physical evolution (constant velocity), the CA rule would be a simple linear shift in position bits — computable in O(n) time. For non-linear motions (turns, acceleration), the CA rule would need higher complexity. The key value here is structural insight: if the transition looks like a CA rule, we can predict the next frame without a full network evaluation.

Reality check: CA rules are defined for spatial neighbors; our input is a flat binary vector with non-spatial structure. The CA framing is more metaphorical than literal here — it suggests looking for local update rules in the binary representation rather than global functions.

---

Framework 8: Compressed Sensing / Sparse Recovery

Mathematical Framework

Classical compressed sensing: y = Ax where y ∈ R^m, A ∈ R^{m×n}, x ∈ R^n is k-sparse (at most k non-zero entries). Recovery guarantee (Candes & Tao 2005): if A satisfies the restricted isometry property (RIP) with δ_{2k} < √2 - 1, then x is recoverable from m = O(k log(n/k)) measurements.

For n=690, k=10 (observed sparsity): m ≈ 10 × log(69) ≈ 43 measurements. We have ~1000 battle ticks with wave feedback — well above threshold if measurements are well-structured.

Binary Measurement Matrices

Our network weights ARE the measurement matrix A. A binary weight matrix W ∈ {-1,+1}^{m×690} satisfies a form of RIP with high probability when entries are iid Rademacher (Baraniuk et al. 2008). This means a single-hidden-layer BNN with ~43 neurons is mathematically sufficient to recover a 10-sparse correction signal from 690 binary inputs.

Mapping to Our Problem

Reframe: the "true" correction vector c ∈ R^2 (Δx, Δy) is not sparse, but the function that maps inputs to corrections is sparse in the feature basis — only ~10 features of the 690-bit input predict the correction. This is compressed sensing in function space.

Sparse recovery update rule:

1. Treat each wave-feedback event as a measurement: y_t = c_true + noise
2. Build measurement matrix A from historical inputs x_t (690 bits each)
3. Solve: min ||w||_0 subject to Aw ≈ y (sparse regression)
4. Use LASSO (L1 relaxation) online: w ← w - η · (Aw - y) · sign(w)

The online L1 update is a soft-thresholding step — computable without gradients of the loss if we treat (Aw - y) as a signal (not a derivative).

What We're Not Exploiting

Our observation that "only 10/24 residual cells activate" is an empirical signal of sparsity. But we're not measuring which 690 bits drive the prediction — we're only asking which of 24 coarse cells. Compressed sensing applied at the bit level would:

1. Identify the ~10 input bits most predictive of the correction
2. Build a sparse predictor that ignores the other 680 bits
3. Potentially achieve better prediction with less memory than the current architecture

The LSH approach (Framework 4) implicitly does this via Hamming nearest-neighbors, but an explicit sparse recovery would be more interpretable and theoretically grounded.

---

Framework 9: SAT as Learning

Framing the Learning Problem as Weighted MAX-SAT

Define a clause for each battle observation: "given input x_t, the aiming correction that would have hit enemy was c_t." Binary weight vector w must satisfy (approximately):

sign(w · x_t) = sign(c_t_x)   [x-component of correction]
sign(w · x_t) = sign(c_t_y)   [y-component]

This is a linear feasibility problem over {-1,+1} — equivalent to finding w that satisfies a set of soft halfspace constraints. Each battle tick adds a new clause.

Weighted MAX-SAT reformulation: each tick t has a "clause" (x_t, c_t) with weight w_t = 1. Find w ∈ {-1,+1}^N that satisfies maximum total clause weight.

Survey Propagation

SP (Mezard et al. 2002) is a message-passing algorithm for random SAT that operates near the SAT threshold. It maintains probability distributions ("surveys") over variables and iteratively updates them. SP solves instances with 10^6 variables in seconds at clause-to-variable ratios near the phase transition.

Relevance: at each battle step, we have a growing SAT instance. SP could run incrementally as new clauses arrive. Convergence: SP converges in O(n) iterations per update for satisfiable instances. For our 690-variable problem with ~1000 clauses after a battle, this is in the well-satisfiable regime (many more solutions than constraints) — SP would converge very fast.

Practical obstacle: SP outputs probability distributions, not binary assignments. It requires a "decimation" step to extract a concrete assignment. The combined SP + decimation + local search (WalkSAT) is a standard pipeline but adds complexity beyond what our 1ms budget allows for each tick.

WalkSAT for Online Binary Weight Updates

WalkSAT local search: pick an unsatisfied clause at random, flip a bit that satisfies it (or random flip with probability p). Convergence to satisfying assignment (if one exists) in O(n·2^{αn}) steps for random 3-SAT, better for structured problems.

For our problem: each unsatisfied clause is a "this prediction was wrong" event. WalkSAT would flip the weight bit that "fixes" the most errors. This is a greedy local search on {-1,+1}^N.

Online WalkSAT sketch:

# On wave hit (new clause (x_t, c_t) arrives):
if current_prediction wrong:
    best_flip = argmax_i [improvement in satisfied clauses if w[i] flipped]
    w[best_flip] = -w[best_flip]

Cost per update: O(N × |active_clauses|) — expensive for N=690 and |clauses|=100+. Maintain an active clause buffer of bounded size to keep cost bounded.

Convergence: empirically O(N log N) flips to satisfy random binary clause sets. For N=24 (our table), this is ~100 flips — achievable within a battle. For N=690, substantially more.

---

Synthesis: Unexploited Structure Summary

The Core Mathematical Insight We Are Missing

The 690-bit input has Gray-coding × temporal autocorrelation × low-dimensional physics structure that we currently exploit only via a 24-cell coarse grid. The mathematically precise statement is:

The function f: {0,1}^{690} → R² (correction) lies in a space of functions with sparse Fourier spectrum (few non-zero Walsh coefficients), low algebraic degree (≤2 over GF(2)), and Lipschitz continuity in Hamming metric (from Gray coding). This combination makes it efficiently learnable by any of: sparse Fourier recovery, degree-2 Hebbian network, or Hamming k-NN.

Prioritized Opportunities

Highest impact (small change, large gain):

1. Hamming k-NN over raw bits (Framework 4): Replace 24-cell table with a bounded memory buffer of (input_690bit, correction_xy) pairs. Retrieve k nearest by XOR+popcount. Exploits Gray structure, no architecture change needed, O(200 × 11) bitops per prediction. This gives the residual table infinite resolution at O(200) memory cost.

2. Temporal XOR features (implicit in Framework 1 and 8): Add frame[t] ⊕ frame[t-1] as explicit input features (~69 bits of velocity-change signal). These are the "sparse changing bits" that carry motion information. Near-zero cost to compute, likely captures the degree-2 correction interactions.

Medium impact (architecture changes):

3. Sparse Fourier learning (Framework 1): Track pairwise bit correlations with corrections. The KM algorithm guarantees recovery of the top-K Fourier coefficients with O(n/ε²) samples. For n=690, K=10, ε=0.1: needs ~69K samples — more than one battle provides. Feasible across multiple battles (inter-battle learning).

4. Thompson sampling on correction bins (Framework 2): Replace fixed lr=0.2 Hebbian with Beta(α,β) posterior per bin. Principled exploration, uncertainty-aware predictions. O(bins) extra memory, same architecture.

Lower priority (diminishing returns):

5. MDL analysis confirms: 10 active degrees of freedom suggest the current architecture is near- optimal in capacity. Going deeper adds parameters without proportionate information gain unless opponent behavior is demonstrably multi-modal or adversarial.

6. GF(2) algebra analysis confirms: XOR + popcount + threshold (the planned BNN neuron) is the minimal architecture for degree-2 functions, and degree-2 is sufficient given the data. No need for deeper networks from this angle.

What Structure We ARE Exploiting

• Gray coding (Hamming smoothness) → implicitly in the 8-sector heading table
• Temporal window (10 frames) → used as input, not architecturally modeled
• Physics sparsity (constant velocity) → linear extrapolation baseline

What Structure We Are NOT Exploiting

• Hamming distance between full input vectors (nearest-neighbor retrieval)
• Temporal XOR (which bits change per tick = motion signal in compressed form)
• Fourier coefficient sparsity at low degree (sparse linear model over parity features)
• Information-theoretic limit (current table is near Shannon bound for this task)
• Uncertainty quantification (Bayesian correction bins vs fixed learning rate)

---

Sources

• A Theory of the Learnable — Valiant 1984 (acolyer.org summary)
• On PAC Learning Algorithms for Rich Boolean Function Classes
• Analysis of Boolean Functions — O'Donnell (full text, CMU)
• SPRIGHT: Sparse Walsh-Hadamard Transform
• An Efficient Algorithm for Combinatorial Semi-Bandits (JMLR 2016)
• A Tutorial on Thompson Sampling (Stanford)
• Convergence Rate of Simulated Annealing with Noisy Observations
• Tabu Search Exploiting Local Optimality in Binary Optimization (2023)
• Locality Sensitive Hashing Lecture Notes (LUMS)
• Hamming Distance Metric Learning
• Minimum Description Length — Scholarpedia
• Bent function — Wikipedia
• Algebraic Normal Form of a Bent Function
• Compressed Sensing Using Binary Matrices of Nearly Optimal Dimensions
• Survey Propagation: An Algorithm for Satisfiability (Wiley 2002)
• Rule 110 Turing Completeness — Matthew Cook proof
• Learning DNF Expressions from Fourier Spectrum
• Rate-Distortion Theory of Neural Coding and Working Memory (eLife)