August 31, 2025
Explainable Hyperdimensional Chess Agent in Google Colab With Episodic Memory, Markov Chains…
This article walks through a fully working, end-to-end chess agent I built that you can run in a single Google Colab cell. The agent blends…

By Robert McMenemy
13 min read
- 1 Explainable Hyperdimensional Chess Agent in Google Colab With Episodic Memory, Markov Chains, Quiescent Heuristics, Beam Search, Color-Aware Memories and an Opening Book that Grows Itself
- 2 1) What We're Building — and Why
- 3 2) System Overview
- 4 3) Mathematics (Deep Dive)
- – 3.1 Hypervectors and Operations
Explainable Hyperdimensional Chess Agent in Google Colab With Episodic Memory, Markov Chains, Quiescent Heuristics, Beam Search, Color-Aware Memories and an Opening Book that Grows Itself
This article walks through a fully working, end-to-end chess agent I built that you can run in a single Google Colab cell. The agent blends Hyperdimensional Computing (HDC) with episodic memory, bi- and tri-gram Markov models, a quiescence-augmented heuristic, a shallow beam search and an opening book that both accelerates development and expands automatically from self-play.
It also includes an explainability layer that decomposes every candidate move into interpretable parts (association, reward, Markov bias and heuristic), reported in both UCI and SAN.
You'll find:
- A conceptual overview of the system.
- A rigorous mathematical breakdown of each component (HDC algebra, discounting, Markov smoothing, scoring, quiescence).
- A code walkthrough that ties math to implementation details.
- Benefits and use cases for research, teaching, and lightweight RL-style agents.
- Reproducible results and how to interpret them.
1) What We're Building — and Why
Traditional chess engines rely heavily on deep alpha–beta search with sophisticated evaluation, or on neural networks trained with massive self-play (AlphaZero-style). Here we explore a different axis: symbolic-distributed representations. Hyperdimensional Computing represents structured knowledge as high-dimensional bipolar vectors (e.g., 8,192 dimensions with entries in {−1, +1}), combined by simple algebra:
- Binding (XOR-like): encodes associations by elementwise multiplication.
- Bundling (majority sum): encodes sets or superpositions by sign of summed vectors.
HDC is attractive because it's fast, noise-tolerant, and compositional. We can encode chess boards, moves, and context into hypervectors, store experiences as bound pairs, and retrieve likely actions by cosine similarity.
We add episodic memory with discounted reward, Markov priors to bias plausible continuations, a quiescence-augmented heuristic to stabilize shallow search and a tiny beam search to peek a ply ahead with opponent replies.
The agent supports color-aware memories (separate store for White and Black), an opening book (both start-position and FEN-keyed multi-ply), and explainability that shows how each term sways the decision.
The resulting system is small, transparent, and surprisingly capable for its size.
2) System Overview
The agent comprises the following modules:
HDC Core
Generates random bipolar hypervectors; defines bind, bundle, bipolarize, and cosine.
Chess Encoders
- Board encoder bundles square × color × piece-type bindings, plus tokens for side-to-move, castling rights, and en-passant file.
- Move encoder binds from-square, to-square, mover's piece token, promotion token (if any), and side-to-move.
Episodic Memory with Discounted Reward
During a game, the agent stores (state_hv, move_hv) per ply. After the result, it bundles bind(state, move) with discounted, signed rewards into long-term associative memory (AM) and reward memory (RM).
Markov Models (Bi- & Tri-gram)
Counts transitions of UCI moves m_{t-1}→m_t and (m_{t-2}, m_{t-1})→m_t, blending their smoothed probabilities as a prior for continuation.
Heuristics + Quiescence
A material + PST evaluator is converted into a delta term per candidate move, wrapped via tanh. We add extras for center control, development, captures, checks, and a quiescence probe that evaluates tactical volatility beyond the stand-pat score. A phase scalar (opening→endgame) modulates how strongly some extras apply.
Beam Search (Depth-2) Score all legal moves, keep the top-K "beam," and for each, evaluate the opponent's best reply (minimizing the same score). Select the move with the best (move_score − λ * worst_reply_score).
Opening Book (Two Layers)
- Start-position shortcuts (e4, d4, Nf3, c4 as White; …e5, …c5, …e6, …c6 as Black).
- FEN-keyed multi-ply book, initialized from short lines and grown automatically from winning self-play episodes.
Explainability For any position, list the top-k legal moves with UCI, SAN, and per-term contributions (association, reward, Markov, heuristic) as both raw scores and normalized shares.
Persistence & Curriculum Save/load AM/RM, n-gram counts, and FEN book. Run a brief curriculum (a set of short self-play games) and then reduce exploration.
3) Mathematics (Deep Dive)
This section formalizes the mechanics in compact notation.
3.1 Hypervectors and Operations
3.2 Encoding Chess
We assign fixed random hypervectors to:
At decision time, retrieve prototypes:
3.4 Markov Priors (Bi- and Tri-gram)
3.5 Heuristic: Delta + Extras + Quiescence
Extras. Add interpretable nudges:
3.6 Final Move Score and Beam Search
3.7 Opening Book Growth from Self-Play
3.8 Explainability Metrics
4) Code Walkthrough (What Each Part Does and Why)
Below is a structured tour of the major pieces in the one-cell notebook. The aim is to connect each mathematical idea to the exact levers in code.
4.1 HDC Core
HDC.random_hv()creates a bipolar hypervector of lengthdim.bind(a,b)multiplies elementwise (XOR in bipolar space).bundle(vectors, weights)does a signed summation with an optional list of floats and then takes the sign; ties are broken randomly to preserve bipolarity.bipolarize(v)ensures no zeros remain after arithmetic; this stabilizes cosine values and keeps vectors on the corners of the hypercube.cosine(a,b)is used everywhere we compare prototypes against candidate move encodings.
Design note: HDC lets us produce constant-time encodings and sub-millisecond cosine comparisons even at 8,192 dimensions, which is perfect for Colab.
4.2 Chess Encoders
- Board encoder. For each occupied square, we bind the square token with the color token bound to the piece-type token. Side-to-move, castling flags, and en-passant file (or "none") are appended to the bundle. The result is one stable bipolar B.
- Move encoder. Fromsquare ⊙ Tosquare, bound with MoverPiece token ⊙ Promotion token, bound with side-to-move. This captures direction (from→to), identity, and context.
Why these features? They are cheap, compositional, and distinctly separable in the HDC algebra: you can unbind the state from memory to predict moves.
4.3 Heuristic & PST (With Guardrails)
- We ship 64-entry PST arrays for each piece type and assert their size at import time (
assert arr.size == 64) to avoid shape bugs. evaluate_boardimplements a classic material + PST score with mirror indexing for Black and special handling for mates/draws.q_evalperforms a small quiescence search that only considers captures or checks to reduce the "horizon effect."
Why quiescence? A shallow move that seems good but drops material to a forced capture in the next ply is a classic problem. Quiescence mitigates this by looking at just the "noisy" tactical frontier.
4.4 Opening Book: Start Position & FEN-Keyed
- Start-book: straightforward hard-coded lists for the pristine start. We apply them both as a shortcut (if legal and within depth N, just play the book move) and as a prior (a positive bump to the heuristic if the move matches the book).
- FEN book: built from small lines (
OPENING_LINES) and expanded from the winning side's moves in self-play. We key by full FEN (so side-to-move, EP, castling are captured). Growth is capped by a ply depth to keep entries fresh and focused on early theory.
This two-tier approach stabilizes openings fast while still letting the agent "discover" and retain lines it repeatedly wins with.
4.5 Markov Models
- We maintain dictionaries:
bigram[prev]->Counter(next)andtrigram[(prev2,prev)]->Counter(next). observe_transition()updates both as the game unfolds._markov_boost()computes smoothed probabilities and blends them. This matters because chess is pattern-heavy; e.g., aftere2e4 e7e5 g1f3, many sequences continue with…b8c6or…g8f6. A Markov prior nudges the policy toward plausible continuations without hard-coding theory.
4.6 Episodic Memory & Consolidation
- During a game, every step collects a record with the hypervectors and metadata (
EpisodicEntry). - After the result, we compute discount weights and bundle B⊙M into AM and RM.
- In the color-aware policy, we separate White and Black memories to limit interference and bias.
You can think of AM as associative "what we did" memory and RM as reward-oriented "what worked" memory — both pointed toward likely moves by unbinding with the current state.
4.7 Scoring, Heuristic, and Beam Search
_heuristic_score()implements the delta + extras + phase + quiescence + book prior blend and clips to [−1, 1]._move_total()mixes association, reward, Markov, and heuristic with weights (λ, μ, κ, η).choose_move()optionally uses a beam: score all moves, keep the best K, then for each simulate the opponent's best reply (minimizing the same scoring function) and pick the move with the best (own − λ·opponent) aggregate.
The beam is shallow by design (depth 2). The point is not brute-force strength, but interpretability and speed while making a nod to tactical sanity checks.
4.8 Explainability
explain_position()lists legal moves with UCI, SAN, raw parts (assoc, reward, markov, heuristic), and normalized shares that sum (by absolute contributions) to ≈1.- In interactive games, you can toggle an explainer printout before the agent moves to see why it prefers a particular action.
This is a key advantage over "pure" deep nets — the decision factors are human-readable.
4.9 Stockfish Sparring and Utilities
- You can install and run Stockfish in Colab and play a tiny match (very short time controls).
- Utilities include epsilon scheduling, dumping PGNs, and convenience wrappers.
5) Use Cases
5.1 Teaching and Research in Symbolic-Distributed AI
- Curriculum for HDC: The notebook is a compact, runnable example of HDC's binding/bundling algebra applied to a complex problem.
- Explainable RL-ish agent: Students see how episodic memory with discounted reward interacts with a symbolic heuristic and a tiny search.
- Bridging symbolic and statistical: Markov chains over moves sit naturally next to HDC memories and a quiescent heuristic.
5.2 Rapid Prototyping of Interpretable Agents
- Low hardware footprint: No GPU-heavy training; cosine and elementwise ops dominate.
- Interactive iteration: Tune weights (λ, μ, κ, η), enable/disable beam or quiescence, and watch the explainer change.
- Safe ablations: Turn off Markov to see how reliance on memory shifts; lock book off to stress the policy core.
5.3 Self-Play Discovery with Human-Readable Knowledge
- The FEN book grows with winning lines — not by magic data generation but by explicit, reviewable sequences.
- You can export the book JSON and study which lines stabilize first.
- Add specific theory lines (Sicilian, French, QGD) and let the agent "connect the dots" by similarity and Markov smoothing.
5.4 Hybridization with Engines or Tutors
- Engine-in-the-loop: Use Stockfish to annotate positions the HDC agent misplays and add those as "counterexamples" (negative reward).
- Training wheels: Let the opening book cover the first 6–10 plies reliably, then hand off to the policy + beam + quiescence.
5.5 Explainable Human Interaction
- Coach mode: When humans play the agent, show the top-k table. It's pedagogical: "here's how the agent weighs central control vs. association memories."
- Debug mode: If the agent plays a blunder, the table exposes which term (Markov or heuristic) pushed it there.
5.6 Research Into Memory Structures
- Compare shared vs. color-aware memories.
- Try different discount factors γ\gammaγ to see how far-back rewards should count.
- Experiment with vector dimensionality (4096 vs. 16384) to measure capacity effects on retrieval quality.
6) Benefits (Why This Approach)
- Interpretability from the Start Every score decomposes into physically meaningful parts. You can literally justify "we picked Nf3 because the heuristic (center/dev) dominated, not memory."
- Simplicity and Speed HDC algebra is tiny — elementwise operations and dot products. It's robust to noise and super fast in Python/NumPy.
- Compositional Encodings Binding unbinds cleanly: AM ⊙ State ≈ Move-prototype. This is more structured than opaque embeddings.
- Data-Efficient Learning Episodic bundling with discounting learns immediately from self-play games, no backprop or massive data required.
- Stability via Quiescence & Book The combo of small quiescence, beam, and a short book prevents many shallow-search pitfalls, stabilizing play strength without heavy compute.
- Modularity You can drop in a different heuristic, swap out PSTs, turn beam on/off, or plug in a deeper Markov (4-gram) without rewriting the system.
- Persistence and Transfer Save AM/RM, n-grams, and FEN book; reload to continue learning later or to seed a new run.
7) Results and How to Read Them
All results below come from the same one-cell from the notebook below.
7.1 Warm-Up Self-Play
From the notebook logs:
Bootstrapping (10 self-play games)
[Self-Play] 5/10 — W:5 D:0 B:0[Self-Play] 10/10 — W:6 D:4 B:0
Warm-up stats: {'white': 6, 'black': 0, 'draw': 4}
Brief curriculum (6 additional quick games)
[Self-Play] 6/6 — W:3 D:3 B:0
A pattern you'll notice in early training is White dominance (because we always start from the initial position and symmetry is broken by the side to move). As the memories grow and the opening book expands, play tends to even out, but early on, White commonly scores more wins.
7.2 Explainability at the Start Position
The explainer ranked moves at the initial position (top 12). Your run produced a table like:
uci san assoc reward markov heuristic assoc_% reward_% markov_% heur_% total
g1f3 Nf3 ... ... 0.0 0.6949 ... ... 0.0 0.9687 0.1394
e2e4 e4 ... ... 0.0 0.4956 ... ... 0.0 0.8739 0.1073
d2d4 d4 ... ... 0.0 0.4956 ... ... 0.0 0.9564 0.1036
b1c3 Nc3 ... ... 0.0 0.5449 ... ... 0.0 0.7602 0.0965
...uci san assoc reward markov heuristic assoc_% reward_% markov_% heur_% total
g1f3 Nf3 ... ... 0.0 0.6949 ... ... 0.0 0.9687 0.1394
e2e4 e4 ... ... 0.0 0.4956 ... ... 0.0 0.8739 0.1073
d2d4 d4 ... ... 0.0 0.4956 ... ... 0.0 0.9564 0.1036
b1c3 Nc3 ... ... 0.0 0.5449 ... ... 0.0 0.7602 0.0965
...How to interpret this:
Nf3, e4, d4, Nc3 bubble to the top — sensible opening moves.
The heuristic dominates early (high heur_%), because:
- Phase ϕ\phiϕ ≈ 1 (opening).
- Center and development bonuses are active.
- AM/RM memories are still shallow; Markov has little data at start (hence
markov=0.0here).
The total is a weighted sum; small positive association/reward terms will grow as the agent sees more examples.
This validates that the explainable terms behave as designed: in opening positions, the engine relies on general chess principles; as experience accumulates, association and Markov terms carry more weight in recurring patterns.
7.3 Practical Play
With policy.epsilon=0.05, the agent becomes mostly greedy with occasional exploration. The beam search helps it avoid obvious one-ply blunders, and quiescence prevents many "hang a piece" situations caused by evaluation spikes.
In test games after warm-up, the agent:
- Prioritizes Nf3/e4/d4 as White and reasonable replies as Black (…e5/…c5/…e6/…c6) when the book is active.
- Shows explainable shifts: if the Markov model has seen a line repeatedly, you'll see
markovbecome a nonzero positive booster for known continuations. - Generates a growing FEN book: After decisive games, you'll find new entries in the JSON book, keyed by their exact FEN, that point to the winning side's moves.
7.4 (Optional) Engine Sparring
If you run the quick Stockfish mini-match:
evaluate_vs_stockfish(policy, enc, games=6, movetime_ms=80, max_plies=140)evaluate_vs_stockfish(policy, enc, games=6, movetime_ms=80, max_plies=140)you'll get a small outcome dictionary like {'W': x, 'D': y, 'L': z} for very short time controls. Don't expect engine-class strength—this system is intentionally tiny and explainable—but you can use these matches to sanity-check improvements (e.g., widening the beam, increasing dimension D, refining the heuristic schedule).
8) Practical Guidance and Tuning
8.1 Knobs You Can Turn
- Vector dimension
DIM: 4096 is faster; 16384 or more increases capacity (better separation of concepts) at a compute cost. - Weights (λ, μ, κ, η): Increase
ηif you want more classical chess bias; increaseμto lean on learned reward; increaseκto steer along familiar Markov lines. - Discount
γ: Higher retains longer-term credit assignment; lower emphasizes recent choices. - Quiescence depth: From 1 to 3; 2 is a good compromise.
- Beam width/depth: Wider beams and depth 2–3 raise tactical clarity at runtime cost.
- Opening book depths: Extending FEN book growth to, say, 16 plies will accelerate early strength but risks locking in shallow habits; keep it modest (8–12) early.
8.2 When to Use Color-Aware Memories
- If you observe interference (e.g., patterns that are strong for White but pollute Black's behavior), color-aware is safer.
- If your training regimen includes many scenarios where White and Black face structurally different decisions, color-aware yields cleaner associations.
8.3 Scheduling Exploration
- Start with higher
epsilon(0.2), let the agent explore. - After a short curriculum (10–20 games), reduce it to 0.07–0.05.
- The helper
schedule_epsilon(policy, floor=0.02, steps=20)reduces it gently.
8.4 Growing the Opening Book
- Seed with a few lines (we included a light set) and let self-play add moves from winning games only.
- Periodically review the FEN book JSON to prune noise (e.g., wins that came from opponent blunders outside book relevance).
9) Limitations and Thoughtful Extensions
9.1 Limits
- Shallow lookahead: Beam depth 2 is not full search. The engine will miss deeper tactics.
- Heuristic simplicity: PST + small extras + quiescence is deliberately simple.
- No endgame tablebases: We rely on phase weighting; specialized endgame knowledge is absent.
- Data dependence: Without rich self-play (or guided play vs. stronger opponents), AM/RM may reinforce mediocre lines.
9.2 Extensions
- Principal Variation (PV) logging for beam search, so the explainer shows "we expect …Nf6 as the best reply".
- Learned PSTs: Tune PST entries by small local search or regression to stronger engine evaluations.
- Feature-rich heuristic: Add mobility, king safety, pawn structure (passed/isolated/doubled) with clear coefficients and explainable deltas.
- Depth-adaptive quiescence: Increase capture depth in sharp positions.
- Richer Markov (4-grams) or suffix arrays for more nuanced continuation priors.
- Cross-game curricula: Start from curated mid-game/endgame FENs to diversify memory.
- Variant support: Chess960 (adjust castling tokens and start book), or mini-chess to stress-test memory capacity.
10) Summary of What You Get
- A complete, Colab-ready agent in one cell.
- Hyperdimensional encodings of states and moves that support fast associative retrieval.
- Episodic memory with discounted updates, either shared or color-aware.
- Markov biases (bi/tri-gram) that gently push plausible continuations.
- A compact yet explainable heuristic with quiescence probes and phase awareness.
- A shallow beam search that anticipates immediate refutations.
- An opening book that both bootstraps and grows via winning self-play.
- Explainability tables for every position, broken into weighted parts and percentages.
- Persistence for memories, priors, and book; Stockfish sparring for quick regression checks.
The core value is clarity: you can see and reason about why the agent moves as it does, and you can bend its behavior with small, principled changes — without retraining massive models.
11) Appendix: Reading the Numbers Like a Pro
When you inspect the explainer output:
Total is the decision variable.
Heuristic domination at the start is intentional; as AM/RM and n-grams fill, you'll see assoc and markov pick up.
If a move's heur_% is near 1.0 but the move is still wrong, consider:
- Increasing the beam width so replies are considered.
- Extending quiescence depth in that phase.
- Adjusting PST or extras (e.g., add a small penalty for moving the same piece twice too early).
If markov_% spikes and the move looks theory-ish but dubious, it means self-play reinforced that continuation. Trim the FEN book or run guided games vs. a stronger engine to counter-train.
For self-play stats:
- Early runs showing White wins and draws are common.
- As more entries populate the book for Black, you should see Black wins appear (particularly after adopting sound replies like …e5/…c5).
12) Notebook
Google Colab Edit description
13) Concluding Remarks
This project demonstrates that interpretable, memory-based decision systems can play a complex game like chess at a reasonable level with minimal compute and transparent logic. Hyperdimensional Computing provides the algebra to bind chess structure into reusable, queryable patterns.
Episodic bundling turns raw experience into action prototypes; a tiny Markov layer biases continuations; a classical heuristic, enhanced with quiescence, gives tactical sanity; and a narrow beam adds "one-step" prudence. Most importantly, every move is explainable in a way that is useful to humans.
If your goal is to build agents that you can teach, debug, and trust, this style of architecture is a powerful baseline. From here, you can enrich the heuristic, widen the beam, add PV explanations, or knit in learned components — while preserving the compositional backbone that makes the system understandable.
Happy experimenting, and may your book grow with wins you can explain.