Build a playable Computer Science Capstone: compare five indexes, inspect every legal move, then compose an AI policy from probability, future setup, retaliation risk and board control.
Do you take the biggest score now, reach for a triple-word square, keep a promising leave, or lock an anchor until the opponent has nothing comfortable to play? Build the position, ask five indexes, then challenge their answer. The fastest move is not always the smartest move.
Each edge is a letter. Starting at an anchor, the solver follows only prefixes that still exist and prunes the rest immediately.
Letters become a frequency signature, so LISTEN and SILENT open the same bucket. Rack subsets retrieve candidate groups before the board validates anchors and cross-words.
Students integrate discrete mathematics, data structures, databases, probability, explainable AI, APIs and performance engineering into a complete game engine that can be demonstrated, measured and defended. The playable product becomes both the Capstone artifact and the evidence behind every design decision.
Represent the lexicon, rack and board so impossible candidates disappear early; then derive the real cost of prefix traversal, recursion, subset generation and output-sensitive move enumeration.
Insert CAT by starting at the root and following or creating C, A and T edges. Mark T terminal. Inserting CAR reuses C and A, creates R, then marks R terminal. A lookup succeeds only when every character edge exists and the final node is terminal; prefix search omits the terminal requirement.
INSERT(word):
node = root
for ch in word:
node = node.child.get_or_create(ch)
node.terminal = true
CONTAINS(word):
follow every edge; return final.terminalAt an empty square, traversal branches only to child letters available in the rack and allowed by the cross-check mask. At an occupied square it follows exactly the fixed board letter without consuming the rack. The state therefore contains Trie node, board position, remaining multiset, placed tiles and whether an anchor was covered.
EXTEND(node, square, rack):
if square is fixed: follow its one edge
else for child in node.children:
if rack has child AND crossMask allows child:
consume tile; recurse
emit only terminal states covering an anchorComplexity: exact lookup is O(L). Move generation is output-sensitive and depends on anchors A, branching b, rack states and legal outputs Z—not simply O(L).
Sets, multisets, equivalence relations, combinatorics and the fundamental theorem of arithmetic explain why anagrams can share one identity and why a seven-tile rack has a bounded but exponential family of choices.
Assign a different prime to each letter: A=2, B=3, C=5, …, Z=101. Multiply the primes of a word. Fundamental uniqueness of prime factorization makes anagrams share one product: ABBA and BABA both equal 2²×3²=36, while another multiset has another exact integer product.
primeKey("LISTEN")
= p[L] × p[I] × p[S] × p[T] × p[E] × p[N]
= primeKey("SILENT")This is excellent for teaching, but a fixed 64-bit product eventually overflows. Reducing modulo a table size also introduces collisions, so equality must still compare the original signature.
The engine stores 26 letter counts. Because a Scrabble word needs only a small count per letter, two 4-bit counts are packed into each byte: 26 counts become a collision-free 13-byte key. FNV-1a 64-bit maps that key to an open-addressed table; linear probing resolves occupied slots, and all 13 bytes are compared before accepting a hit.
offset = 1469598103934665603
for byte in packedSignature:
hash = (hash XOR byte) × 1099511628211
slot = hash AND (capacity − 1)
while occupied AND key != storedKey:
slot = (slot + 1) AND (capacity − 1)Average: O(1) probe at a controlled load factor. Worst case: O(M) if clustering forces a scan of the table.
A blank has score zero but may represent any A–Z. It must not receive one fixed prime. For every subset containing a blank, the candidate generator branches over 26 substitutions, increments that letter count, packs the result, and inserts it into a set. Two blanks branch over letter pairs. Deduplication collapses substitutions that produce the same count vector. During final placement, the move records which rack position was blank so scoring remains zero even though the board displays the chosen letter.
Median warm time in the same persistent worker. This measures subset generation only; full-word lookup still uses the packed database key.
| Rack | Prime | Packed | Speedup |
|---|---|---|---|
| AEINRST | 3.917 µs | 9.935 µs | 2.536× |
| AABBCDE | 2.742 µs | 6.770 µs | 2.470× |
| AAAAAAA | 1.008 µs | 5.657 µs | 5.612× |
All engines returned identical candidate sets. Times are warm, uncached medians including subset generation, index lookup, bucket expansion, deduplication and sorting. They do not include board placement.
| Rack | Words | Prime | Trie | Prime faster |
|---|---|---|---|---|
| AEINRST | 343 | 141.986 µs | 1,283.597 µs | 9.040× |
| AABBCDE | 42 | 22.478 µs | 226.228 µs | 10.064× |
| AAAAAAA | 1 | 6.428 µs | 13.447 µs | 2.092× |
Warm uncached median latency in microseconds; 1,000 iterations × 7 repeats. Lower is better. Every row passed exact candidate-set equivalence before timing.
| Rack | Words | Prime Product | Compact/Numba Packed | Python Memory Hash | SQLite Hash | Packed Trie |
|---|---|---|---|---|---|---|
| AEINRST | 343 | 145.223 | 157.805 | 528.645 | 661.396 | 1,258.651 |
| AABBCDE | 42 | 22.556 | 28.167 | 229.290 | 287.744 | 216.450 |
| AAAAAAA | 1 | 6.498 | 11.426 | 20.364 | 31.195 | 13.226 |
Leave-one-out starts with the complete rack, removes one position, records the remaining multiset, then repeats recursively. For BEGIN the first layer contains EGIN, BGIN, BEIN, BEGN and BEGI. Continuing produces every smaller subset. Sorting or frequency-count encoding is essential: equal letters removed from different positions must not create duplicate work.
LEAVE-ONE-OUT(tiles, seen):
key ← canonical(tiles)
if key in seen: return
seen.add(key); HASH-LOOKUP(key)
for each distinct position i:
recurse(tiles without i, seen)Number rack positions 0…R−1. Integer mask m selects position i when bit i is 1. Iterating from 1 to 2ᴿ−1 generates every non-empty position subset exactly once. Canonical signatures then merge subsets that differ only by exchanging identical tiles.
for mask = 1 .. (1 << R) - 1:
counts = [0] × 26; blanks = 0
for i = 0 .. R - 1:
if mask & (1 << i):
add rack[i] to counts or blanks
signatures.add(counts, blanks)| Method | Strength | Risk |
|---|---|---|
| Leave-one-out | Shows recursion and memoization | Duplicate states without canonical keys |
| Bit mask | Compact, iterative and parallelizable | Position duplicates before deduplication |
| Count-state DP | Works directly with a multiset | More complex indexing |
Hash pipeline: subset → merge fixed board letters → O(L) signature → average O(1) bucket lookup → validate anchor, blank, premium and every cross-word.
After designing a key, students must decide how to persist it, group anagrams, guarantee integrity, and separate a build-time database from a read-optimized runtime index.
The source lexicon contains 267,752 normalized SOWPODS words but only 237,740 distinct signatures. Anagrams belong to the same equivalence class, so storing one row per word would repeat the key. The database instead stores one row per signature and a zero-byte-separated word bucket.
anagrams| Column | Type | Role |
|---|---|---|
| signature | BLOB PK | 13-byte packed count vector |
| words | BLOB NOT NULL | NUL-separated anagram bucket |
| word_count | INTEGER | Bucket cardinality and diagnostics |
| min_length | INTEGER | Early length filtering |
metadata| Column | Type | Example |
|---|---|---|
| key | TEXT PK | schema, source, words |
| value | TEXT | warin.scrabble.hash-lexicon.v1 |
SHA-256 values bind the binary index to the exact normalized input. A mismatched manifest is rejected rather than silently serving a different lexicon.
SQLite tables normally have a hidden integer rowid plus a separate primary-key index. Here the BLOB signature is already the identity and access path. WITHOUT ROWID stores rows in the primary-key B-tree, avoiding a redundant identity and an extra lookup.
SQLite is durable, portable and easy to rebuild, but its B-tree lookup is O(log S), not a true hash lookup. At worker startup all rows are loaded into compact NumPy arrays and an open-addressed table. SQLite becomes the source of truth; the in-memory table becomes the hot read path.
Every mode uses the same board, rack, lexicon and final PHP placement evaluator. Only candidate retrieval changes. One average O(1) probe does not make the complete solver O(1).
A read-only binary prefix tree that prunes impossible prefixes at board anchors. Word lookup is O(L), and this mode never queries SQLite at runtime.
A durable 13-byte letter-count signature maps to an anagram bucket. SQLite uses a primary-key B-tree: O(log S) for S signatures, then expands the bucket.
Loads SQLite rows once into a persistent dictionary. Probes are O(1) on average; exact 13-byte key comparison handles collisions.
The default fast path uses immutable NumPy keys, int32 open-addressing slots, and Numba-compiled subset generation and batch probes.
A=2, B=3, … turns a word into an exact product. Prime numbers are like indivisible pigments: multiplication mixes letters while preserving how many times each pigment occurs. Order disappears—LISTEN and SILENT become one mathematical silhouette—yet unique factorization can recover the multiset. An abstract theorem becomes an elegant, executable index. Seven-tile racks use uint64/Numba; longer board words use exact Python integers.
Complete solve time also includes candidate-Trie construction for Hash modes, anchor traversal, cross-word validation, scoring, sorting and API overhead. In-memory and Prime initialize lazily, so report cold and warm runs separately.
The board is observable but the opponent rack and future draws are latent. Sampling without replacement, conditional probability and expected value turn incomplete information into quantities that can be checked and simulated.
The opponent rack is hidden. The engine never invents it. Instead it subtracts visible board tiles and our rack from the official distribution, then estimates whether a required reply tile occurs in a seven-tile sample without replacement.
Official score with premiums, cross-words and bingo bonus.
Risk EV = P(reply) × counter score
Tests S, ES, ED, ING and other hooks.
Setup EV = P(draw) × future score
Values a useful leave and a hook for our next turn.
Penalizes new anchors leading toward double- or triple-word squares.
A move becomes an explainable feature vector. Students compose or remove heuristic terms, audit the resulting policy, then use self-play data to learn and evaluate weights without hiding the decision process.
Tile draws are dependent: drawing one S changes the chance of drawing another S. A binomial model assumes independent trials and is therefore only an approximation. The hypergeometric distribution exactly counts size-d racks drawn from N unseen tiles containing K useful tiles.
P(X=x) = C(K,x) C(N−K,d−x) / C(N,d)
P(X≥1) = 1 − C(N−K,d) / C(N,d)For a multi-letter extension such as ING, the engine uses a multivariate count: every required I, N and G must be present, with blanks treated as alternative resources.
A 40-point counterattack with probability 0.20 has Risk EV 8. That does not predict an eight-point reply; it says repeated equivalent positions lose eight points on average. Variance matters: a risk-neutral policy compares means, while a risk-averse policy can penalize tail loss or conditional value-at-risk.
Each move becomes a feature vector: immediate score, hook risk, setup value, opening risk, anchor denial, rack leave and premium exposure. A hand-written linear policy ranks moves. Every term is visible, so students can audit why HARN beats HARNS.
Record feature vectors and outcomes from self-play. Fit linear regression to score difference, logistic regression to win probability, or a ranking model to pairwise move preference. Split by complete games—not individual moves—to avoid leakage. Standardize features before learning coefficients, compare against the hand policy, and report confidence intervals across seeds.
An anchor is an empty square adjacent to an existing tile. Perpendicular fixed letters create a pattern. In L_B only A makes a legal word, so its mask contains one bit. A broad mask offers choices; a narrow mask denies them.
allowed(anchor) = letters making
every perpendicular word legal
L _ B → allowed = { A }For each constrained anchor, AI finds the probability that the opponent lacks every allowed letter, then averages it as Anchor Denial. 1-Tile Pass checks the union across the board. Neither is an exact pass probability because a multi-tile word may remain.
Read it this way: high denial means difficult gates; low opening risk means those gates do not point to valuable premiums.
Treat one solve as a message travelling through a small distributed system: the browser serializes board state, the PHP gateway validates and routes it, and a persistent Python service performs the indexed search. Students trace the request across process and container boundaries, distinguish transmission latency from computation time, define timeout and retry policy, and preserve the semantic difference between an empty legal-move set and an unavailable service.
The board is rendered from one state model: 225 cells, two racks, scores, turn, bag and history. Event handlers update state first and render second. Keeping state separate from HTML prevents the visible board from becoming an unreliable database. Responsive CSS preserves square geometry and reading order across desktop and mobile.
state → render(board, rack, score)
user event → validate → update state → renderA Solve click passes through idle → loading → success, empty result or failure. Disable duplicate submission while loading, distinguish “no legal move” from a network error, and render server-provided evidence rather than recomputing it inconsistently in the browser. Controls require labels, keyboard access and visible focus.
fetch(request)
.then(validateHTTP)
.then(renderMoves)
.catch(renderFailure)POST /pages/scrabble-api.php
Content-Type: application/json
{
"board": [15 strings × 15 cells],
"rack": "AEINRST",
"limit": 20,
"engine": "trie" | "sqlite-hash" | "memory-hash"
| "compact-numba" | "prime-product",
"adversarial": true
}The response returns lexicon identity, timing, engine statistics, unseen probabilities and a list of moves. Each move includes coordinates, direction, newly placed tiles, score and optional heuristic decomposition.
GET /health
→ status, backend, signatures,
table_bytes, startup_ms
POST /candidates
{ "board": [...], "rack": "AEINRST" }
→ words, hash_lookups, hash_hits,
signature_ms, hash_query_ms,
worker_ms, cache_hitFastAPI validates exactly 15 ASCII rows and a 1–7 tile rack. The worker loads 237,740 signatures once during lifespan startup, JIT-compiles Numba probes once, then serves warm requests without rebuilding the index.
200 success · 422 invalid client data · 500 internal failure · 502 gateway cannot obtain a valid worker response.
Measure serialization, network transfer, signature generation, hash lookup, placement and rendering separately. Wall time is not algorithm time.
Validate length and character sets at every external boundary. Never trust browser limits alone; clients can send arbitrary HTTP.
Use finite timeouts, health checks and a documented fallback. Do not convert every worker failure into “no legal move”; failure and an empty answer are different states.
Build the laboratory as a stateful single-page interaction without hiding the underlying experiment. Semantic HTML gives the board, controls and result table meaningful structure; responsive CSS keeps 225 squares usable across screens; JavaScript owns turn, rack and pending-request state; Fetch connects that state to the API. Students validate input twice, render loading, error, empty and success states explicitly, prevent duplicate submissions, and keep keyboard and screen-reader interaction equivalent to pointer input.
The board array is the source of truth. Click and keyboard events update that model first; one render function then derives tiles, scores and controls from it. Keeping model and DOM responsibilities separate prevents a square from looking occupied while the solver receives an empty cell. During Fetch, a pending flag disables repeated Solve actions and an AbortController can cancel a stale request after the board changes.
event → validate → update state → render
solve → pending → fetch → parse → render result
error → restore controls → explain failureA robust interface distinguishes idle, editing, loading, success, no-move, validation-error and service-error states. HTTP 200 with an empty array is not HTTP 502; showing both as “no move” teaches the wrong system model. The language parameter, selected engine and form values should also survive predictable navigation and refresh behavior.
Give immediate feedback about rack length, characters and board shape.
This is the authoritative boundary; never trust editable browser state.
Announce progress and errors with focus management and live regions.
Preserve scores, coordinates and sortability—not merely appearance.
Trace Trie nodes and count unique subset signatures.
Prove the prime-product mapping and count unique rack multisets.
Normalize the bucket schema, then compare query plans and storage.
Verify hypergeometric probabilities by simulation and confidence intervals.
Toggle one heuristic at a time, run self-play and measure policy sensitivity.
Separate API latency from solver time and test failure semantics.
Model UI states, validate inputs and test responsive, keyboard-accessible interaction.
I have taught Design and Analysis of Data Structures and Algorithms for many years. I did not want students to meet searching only as formulas and isolated code, so I turned the lesson into a playable engine: every data structure must find a legal Scrabble move, score it, and explain the cost of its search.
SILENT and LISTEN become the same letter-frequency signature. Building the signature is O(n); looking up its bucket in a hash table is O(1) on average.
For BEGIN, remove letters recursively and look up EGIN, BGIN, BEIN … down to GIN or IN. With a seven-tile rack, the subset space is bounded and can be generated before placement checks.
A hash hit only says which words share the available multiset. The engine must still test anchors, direction, premium squares, blanks, and every perpendicular cross-word.
The current Hash path creates signatures, queries SQLite, expands word buckets, builds a temporary candidate Trie, and then runs the same board solver. Packed Trie starts pruning at board anchors immediately, so its smaller constant factors often win on constrained boards. O(1) describes one average bucket lookup - not the complete Scrabble search.
It retrieves complete anagram groups directly, makes subset selection observable, and can beat Trie candidate enumeration for racks with many valid combinations. In a local 1,000-run microbenchmark, in-memory Hash was 2.03× faster for AEINRST candidate retrieval, but only 1.27× for CARTSAA; end-to-end placement may still favor Trie.
Click a square and type A-Z for a custom position. Lowercase board state is reserved for played blanks.
This web laboratory extends ideas documented by four student contributors: make Scrabble playable without waiting for an opponent, use a word index for responsive validation, and make an AI turn observable as a sequence of candidate generation, validation, scoring and selection.
The report begins with a practical learning problem: limited opponents interrupt vocabulary practice. A bot turns the game into an always-available English learning activity.
The team used collaborative UI prototyping, then implemented the board, tile bag, drag-and-drop interaction, word validation and real-time score display as a Unity game.
Their sequence model separates invalid words from valid turns and routes both player and AI moves through the same validation, scoring and game-end checks—the same invariant preserved by this web version.
In a preliminary questionnaire of 35 participants, the student report states that more than 80% viewed the game as supporting new vocabulary, recall and enjoyment. This is project-reported evidence—not an independent controlled trial—and motivates a reproducible classroom study.
Source note: Summarized from the student Capstone report “Scrabble game”. Claims about runtime are intentionally not repeated here unless this web implementation measures them under identical data and workloads.