Encoding tic-tac-toe in 15 bits
Encoding a tic-tac-toe board as compactly as possible becomes a playground for information theory, with people exploring schemes from simple base‑3 encodings (15 bits for 9 cells) down to 13 bits by enumerating only valid, reachable game states. Others push further by encoding entire game histories in under 20 bits or exploiting symmetry and optimal play to prune impossible or redundant states, while debating when such compression is actually useful versus when it just complicates code. Along the way, the thread touches on related ideas like lookup tables vs. algorithmic encodings, genetic algorithms that evolve perfect players, and analogies to more complex games and puzzles such as chess, Connect‑4, and mechanical brainteasers.
Board-state encoding & bit counts
- Core article encodes a tic‑tac‑toe board in 9 base‑3 digits → 15 bits.
- Multiple commenters show further compression:
- Counting all reachable legal boards gives 5,478 states, so 13 bits suffice without symmetry.
- One implementation encodes boards into [0, 6045] via combinations (“choose filled cells, then choose O’s among them”), also fitting in 13 bits.
- Others note that a naive “10‑bit for 765 states” scheme assumes symmetry‑deduplicated boards; real games need extra bits for orientation (rotation/flip), pushing back to ~13 bits.
Symmetry, legality, and edge cases
- Symmetry handling is tricky: some boards need 3 bits to disambiguate rotation+reflection, some fewer, some zero (fully symmetric).
- Counting only “legal, reachable” boards (respecting turn order and not playing past a win) is required; initial scripts had bugs in diagonal‑win detection, slightly inflating counts.
- There are unreachable states (both players having a winning line, or disjoint multiple wins), which must be excluded.
Encoding full game histories
- Several schemes for encoding entire play sequences:
- Simple factorial-based bound: 9! ≈ 19 bits for all move permutations; pruning invalid games saves only ~1 bit.
- One commenter rigorously argues 18 bits cannot encode all possible sequences (needs ≥19 bits); another 18‑bit proposal is shown to misuse “spare” bit patterns.
- Other ideas:
- Variable-length encodings that stop when someone wins.
- Exploiting symmetry to reduce the first move choices (corner/edge/center equivalence).
Strategies, AI, and human play
- Discussion of minimax play: optimal play leads to at least a draw; some argue that for human opponents, non‑minimax “trap‑setting” may win more often.
- Historical/educational systems appear: matchbox‑based reinforcement learner, boolean‑logic strategies, genetic algorithms over all game states.
Representations, lookup tables, and trade-offs
- Debate over whether lookup tables are “cheating”: condition chains and arrays are functionally equivalent; judging solutions by total bits of data+code is suggested.
- Some note that even if 10‑bit canonical encodings exist, practical systems might keep a mapping table to a more convenient 13–18‑bit structure.
- Clarifications about trits vs bits: 9 trits fit into 15 binary bits; no ternary hardware is assumed.