TL;DR
Bellman’s math told you how to act perfectly — on paper. 1959 computers had neither the memory nor the map of reality to run it. So a few stubborn engineers cheated their way to something that actually worked.
Arthur Samuel (1959) swapped an impossible checkers lookup table for a scoring function — a formula with adjustable weights, trained by playing itself. His real breakthrough wasn’t the 1962 headline win (which, spoiler, gets more impressive the more you learn how it actually went). It was an idea called Temporal Difference (TD) learning: don’t wait for the game to end — learn from the gap between what you predicted a moment ago and what you predict now. No rulebook required. That’s model-free learning, and it turns out to be the exact same rule psychologists later used to explain Pavlov’s dogs.
Donald Michie’s MENACE (1961) did something similar with 304 matchboxes and coloured beads — but learned a policy (“what should I do?”) instead of a value (“how good is this?”). Value-learning and policy-learning are the two ancestors of basically every RL algorithm running today.
Minsky (1961) put a name on why any of this was hard in the first place: the credit-assignment problem.
Michie’s BOXES (1968) removed the last training wheel — a human teacher — and balanced a physical pole using nothing but “it fell over” as feedback.
Every system in this post assumes the world is reliable. Blog 5 breaks that assumption.
The blueprint had a bill attached
Bellman’s equation is one of those rare results that’s simultaneously beautiful and completely useless.
Beautiful, because it tells you the exact optimal move, always. Useless, because to run it you need two things handed to you first: every possible state of the world, written down, and the exact odds of moving between them, also written down.
Neither exists. Computers in 1959 topped out around 32,768 words of memory — smaller than a single photo on your phone today. Checkers alone has roughly 500 billion possible positions. And the “odds of every outcome” problem is even worse than the memory one — more on that in a second.
So the people actually trying to build this did what engineers always do when elegant theory meets a real budget: they cheated. One of the most important cheats in AI history started with a man, a room-sized vacuum-tube computer, and a game of checkers.
Three walls, one problem each
Picture yourself in 1959, staring at Bellman’s equation, actually trying to build the thing. You’d hit these three walls, in roughly this order, and none of them have an easy way around them.
Wall 1 — Memory. Store every situation in a table and the table explodes. Tic-tac-toe: ~5,000 positions, fine. Checkers: ~500 billion. Chess: ~10⁴⁵. Bellman called this the curse of dimensionality — add one variable, and your table doesn’t grow, it detonates. Lesson: you can’t memorise your way to intelligence.
Wall 2 — No rulebook. Bellman’s math needs P(s'|s,a) — the odds of every outcome, for every action, in advance. Nobody has that spreadsheet. A self-driving car has no table for “will this pedestrian step off the curb.” Reality just doesn’t ship with its own source code.
Wall 3 — The score becomes the goal. Turn “behave well” into a number, and machines will take that number extremely literally. Reward a robot vacuum for movement, and it’ll ram the same wall forever, racking up points and cleaning nothing — and from its own perspective, winning. Today we’d call this reward hacking. In 1959 it didn’t have a name yet, just a very confused engineer staring at the output.
Samuel is about to dent Walls 1 and 2. Michie dents Wall 1 from a totally different angle. Wall 3 is still standing today — it’s a large chunk of why “AI alignment” is now a job title.
Arthur Samuel and the machine that learned checkers
In the 1950s, the prevailing wisdom was blunt: computers execute, they don’t learn. A program does exactly what it’s told, forever, full stop.
Arthur Samuel, an IBM engineer, didn’t buy it. He picked checkers — not chess — as his test case. Deep enough to need real strategy, small enough that a 1950s machine stood a chance. He started in 1952 on the IBM 701 and by 1959 had published work that put the phrase “machine learning” into circulation for the first time.
His machine, the IBM 704, maxed out at 32,768 words of memory. Storing every checkers position wasn’t “hard” — it was short by seven orders of magnitude. So instead of trying to be comprehensive, Samuel made the machine opinionated.
A scoring function instead of a lookup table
Throw away the table. Replace it with a formula that squeezes an entire board into one number: high = “good for me,” low = “bad for me.” The machine has no idea why — it just needs a number it can push upward.
If blog 3’s V(s) was an exact number, computed by sweeping every state until the answer converged — this is the same object, wearing a disguise. Samuel’s scoring function is V(s). The difference is that nobody can compute it exactly here, so the machine has to guess it, and improve its guess through play instead of through a formula that already has the whole map.
That number was built from hand-picked features — piece count, king count, board control, mobility — each with a weight saying how much the machine currently trusts it. Score = features × weights, summed.
Here’s the part that still holds up today: the weights weren’t fixed. A feature that kept predicting wins got trusted more. One that kept misleading the machine got trusted less, or dropped entirely and swapped for a new candidate. The machine wasn’t just learning checkers — it was learning what was worth paying attention to. That’s the same basic instinct behind feature learning in neural networks, six decades early.
Self-play
Samuel then had the program play itself. A “student” copy tries tweaked weights against a “teacher” copy running the current best settings. Student wins consistently → student becomes the new teacher → repeat.
This loop is, structurally, identical to what DeepMind ran in 2016 to build AlphaGo. The hardware went from vacuum tubes to TPU pods. The logic didn’t change at all.
The famous win (and the asterisk nobody mentions)
In 1962, Samuel’s program beat a checkers player named Robert Nealey, and IBM’s press release turned it into the first-ever headline about a machine beating a human at a strategy game.
What usually gets left out: Nealey wasn’t state champion yet at the time (that came four years later), he beat the program in a rematch the following year, and by 1966 Samuel’s program lost eight straight games to serious competition. None of that makes the work less real — it just moves the story from “magic trick” to “science”: genuine learning, with a genuine, visible ceiling.
The ceiling Samuel could see from day one
Every strategic idea the program ever had came from a feature Samuel typed in by hand. If he never thought to encode “board control matters,” the machine could never discover it on its own. It could re-weight human knowledge with superhuman patience — but it couldn’t generate knowledge that wasn’t already sitting in the box.
That single limitation defined the next thirty years of AI research, and it’s exactly the problem deep learning was eventually built to solve: stop handing the machine features, let it find its own.
A name for the missing piece: Marvin Minsky, in 1961, pointed at exactly this gap and called it the credit-assignment problem — with only a final win or loss, which of a hundred earlier decisions actually deserves the credit? He specifically called out Samuel’s scoring updates as the first real attempt at an answer: doling out partial credit one move at a time instead of waiting for the final verdict. That’s the problem the rest of this post is trying to crack.
Memorise, or generalise?
Samuel’s scoring function created a fork in the road that reinforcement learning is still walking down today.
His first instinct was rote learning: store exact positions and how they turned out, replay the good ones when they reappear. Works great for small games. But nudge a single piece and the “memory” is worthless — that exact position has never happened before, so there’s nothing to look up. It’s a lookup table wearing a trench coat.
Generalisation was the fix: describe a board by its features instead of memorising the whole thing. Now a position the machine has never seen still gets a sensible score, because it’s described, not recognised.
Table lookup asks “have I seen this exact thing?” Generalisation asks “what is this like?” Only the second question scales.
Samuel’s update rule for the weights:
Δw_i = α · [V_actual − V_predicted] · f_i
- Δw_i — how much to nudge feature i’s weight
- α — learning rate: how boldly to react to new evidence
- [V_actual − V_predicted] — the surprise
- f_i — how present that feature was in this position
If you remember one sentence from this whole post, make it this: learning is the size of your mistake, multiplied by how willing you are to change your mind. Everything from here on is a variation on that one bracket.
Thinking deeper on a slower machine: alpha-beta pruning
One quick detour, and it earns its place here: self-play only works if you can play thousands of games against yourself, and thousands of games only fits into a reasonable afternoon if each individual game doesn’t take forever to think through. That’s the problem this section solves.
The IBM 704 was unbelievably slow by today’s standards — looking twenty moves ahead by brute force would’ve taken longer than the universe has existed. So Samuel needed to skip most of the game tree without missing anything that mattered.
Credit where due: Samuel used alpha-beta pruning, but didn’t invent it. John McCarthy proposed it at the 1956 Dartmouth workshop; Hart and Edwards formalised it in 1961; Knuth and Moore gave it full analysis in 1975. Samuel had a working version quietly running in the background — he just thought the learning parts were the interesting bit. (He was right.)
The idea: as the machine explores possible futures, it tracks the best result it can already guarantee (alpha) and the worst its opponent can already force (beta). The moment a branch is provably worse than something already locked in, the machine stops exploring it entirely — not “reads it faster,” stops.
Restaurant analogy: someone tells you “the other place has a two-hour wait.” You don’t need the menu or the parking situation. You’re not going. Branch closed.
Crucially, this is lossless — it finds the exact same best move as checking everything, just without wasting time on futures that can’t matter. It’s also a technique with real staying power: it was the backbone of Deep Blue, the chess machine that beat world champion Garry Kasparov in 1997, decades after Samuel quietly used it for checkers.
The idea that mattered most: learning from your own changing mind
This is the part that echoes into every modern RL system, and it’s easy to undersell because it sounds so small.
The old assumption
The 1950s default: learning happens at the end. Play the whole game, see who won, then work out what went wrong. This became known as Monte Carlo learning — and it’s brutally slow. You need a full game before learning anything, and if the game runs 100 moves, one noisy final signal has to somehow get distributed across all 100 decisions.
Samuel’s question: why wait?
The machine already had a second opinion available, one move later, for free. If a position looked 70% winning after move 10, and only 50% winning after move 11 — something was already learned, right there, with no need to finish the game. Your own estimate moved, and estimates don’t move for no reason.
Real-life version: you leave home expecting a 20-minute drive. Ten minutes in, you hit an empty motorway and revise to “7 more minutes.” You haven’t arrived yet, you don’t know the true total — and you’ve unmistakably learned something the moment your prediction jumped.
That’s the whole trick: learn from the gap between consecutive predictions, not from the final answer. It sidesteps Minsky’s credit-assignment problem rather than solving it head-on — each move only ever has to explain the next move, not the whole game.
The formula
For a game like checkers, where nothing scores until someone wins:
V(S_t) ← V(S_t) + α [ V(S_t+1) − V(S_t) ]
- V(S_t) — current guess about this position
- V(S_t+1) — the guess one move later
- [V(S_t+1) − V(S_t)] — the TD error: how wrong I just turned out to be
- α — learning rate: too high and it’s jittery, too low and it barely moves
In plain English: nudge what you believed toward what you now believe, in proportion to how surprised you are.
The general version below isn’t a new idea — it’s the exact same bracket with two extra pieces bolted on, so you can see them coming rather than guessing where they came from. It adds in any reward collected along the way, plus a discount for how much future value matters:
V(S_t) ← V(S_t) + α [ r_t+1 + γ V(S_t+1) − V(S_t) ]
Checkers collapses back to the simple version because nothing is scored mid-game (r = 0) and a win in 10 moves is worth exactly as much as a win now (γ = 1).
The déjà vu moment
That bracket should look familiar if animal learning is on your radar at all — and if you’ve been following this series, it should ring a very specific bell. This is the prediction error term flagged back in Blog 3, finally getting the job it was promised. Same idea, same shape, just a new name and a new job description: back then it fired once per trial, at the end. Here, it fires on every single move.
Pavlov’s dogs weren’t learning from bells — they were learning from being wrong about bells. A decade after Samuel, psychologists Rescorla and Wagner wrote down almost the identical rule to explain it: change your belief in proportion to your error. Different letters, same bracket — reality minus expectation, scaled by how much you’re willing to update.
An IBM engineer trying to save vacuum-tube cycles, and two psychologists trying to explain salivating dogs, landed on the same equation from completely opposite ends of science, with zero contact between them. That’s not a coincidence — it’s a strong hint that prediction error is something close to fundamental about what learning actually is. (It gets better: in the 1990s, Wolfram Schultz found dopamine neurons firing in a pattern that looks almost exactly like a TD error signal. More on that in a later post.)
And notice what TD learning never needed: the rulebook Wall 2 said was impossible to get. Just the current state, the next state, and two estimates. That’s model-free reinforcement learning — arguably the single most important idea in this post — quietly running on a vacuum-tube computer in 1959, almost thirty years before Richard Sutton formalised it as TD(λ) in 1988.
MENACE: reinforcement learning built out of matchboxes
Samuel had IBM’s hardware. British researcher Donald Michie had a rather different constraint: no computer access at all. So in 1961, he built one out of matchboxes.
MENACE — the Matchbox Educable Noughts And Crosses Engine — used 304 matchboxes, each labelled with a tic-tac-toe position MENACE might face, and filled with coloured beads. Each colour maps to one legal move.
To move: find the matching box, shake it, pull a bead blind. Its colour is the move. Leave the box open — you’ll need the trail later.
To learn: after the game, walk back along the trail of open boxes. Win → return the bead played, plus three more of the same colour. Draw → add just one. Loss → the bead simply isn’t returned; it’s gone. More beads of a colour means a better chance of drawing it next time.
Michie played roughly 220 games against it over a weekend. It went from flailing randomly to essentially unbeatable.
The detail worth noticing
Michie didn’t load every box with the same number of beads. Early-game boxes started with about four beads per move; late-game boxes tapered down toward one. That’s a deliberately engineered exploration schedule. Early moves are far from the outcome, so any one game barely tells you if they were good — you want MENACE to keep trying alternatives. Late moves sit right next to the result, so their feedback is trustworthy and can be locked in fast. That’s the explore vs. exploit trade-off, solved in 1961 with nothing but bead-counting.
Why this is a plot point, not a party trick
Samuel’s program learned to answer “how good is this position?” MENACE never asked that question — it has no concept of a position being worth 0.7. It only tracks “which move should I make more often from here?”
In blog 3’s terms: MENACE is growing a policy — π, a state-to-action lookup — directly. It never computes a value for anything along the way. That’s the split worth holding onto:
Two men, two continents, same decade — and they’d independently split reinforcement learning into the two halves it still has today. Modern RL doesn’t pick a winner; it runs both at once. Actor-Critic methods (more on these in a later post) are literally a Critic estimating values (Samuel’s job) paired with an Actor adjusting action probabilities (Michie’s job), each sharpening the other.
MENACE also proves something worth sitting with: reinforcement learning isn’t a property of silicon. It’s a mathematical principle. Run it on vacuum tubes, neurons, or 304 matchboxes on a Sunday afternoon — what matters is the loop: act, observe the consequence, adjust, repeat.
It also hit the exact same wall Samuel did: every position needs its own box, and one extra square collapses the shelf. Same curse, cardboard edition.
Michie didn’t stop there. In 1968, with R. A. Chambers, he took the matchbox idea into physics: BOXES, balancing a pole on a moving cart using nothing but a bang when it fell over. Widrow and Smith had balanced the same pole in 1964 — but with a human demonstrating the right move at each step. BOXES threw the teacher out entirely: no demonstration, just eventual failure walked backward through whichever boxes were open. The one new trick it needed was state aggregation — chopping a continuous space (pole angle, cart speed) into discrete chunks, since you can’t label a matchbox for infinitely many positions. That’s the field’s first honest step toward function approximation — a plain-English way of saying “estimate the value instead of memorising it,” the same escape hatch this whole post keeps circling back to. Cart-pole balancing went on to become RL’s most reused benchmark ever since.
Two roads, one open question
By the late 1960s, two things were true at once. Samuel and Michie both had systems that genuinely learned from experience — no rulebook, no complete map of the world, and they visibly got better over time. But nobody could prove any of it. No convergence guarantee, no theorem saying “this reaches the optimal policy” — just clever hacks that happened to hold up on small problems.
Bellman’s framework had the opposite problem: flawless proofs, unusable in practice.
Which set up the question the field spent the next twenty years chasing:
Can you keep Bellman’s guarantees without needing Bellman’s rulebook?
That question is the birth of model-free reinforcement learning — and chasing it eventually pushes the field toward systems that learn their own features instead of borrowing a human’s. Which is to say: toward neural networks.
Worth sitting with for a second before we move on: the technique that trains most modern chatbots to be helpful — RLHF, reinforcement learning from human feedback — is a direct descendant of exactly this idea. No rulebook for “what makes a good response,” just a reward signal and a model updating itself against its own predictions. The line from a matchbox in 1961 to a language model in 2026 runs straight through this post.
But not yet. First, someone has to ask a harder version of the question.
Coming up next
Samuel and Michie both had one thing quietly working in their favour: their worlds behaved. Move a checker, it stays moved. Draw a bead, that’s the move you play. The environment was unknown, but at least it was reliable.
Now break that assumption. What if pressing the same button in the same situation works 70% of the time and fails the other 30%, for no reason you can see? A single result stops meaning anything — it might just be noise. You need to learn from distributions, not events, while still acting sensibly under real uncertainty.
That discipline was being built in parallel, largely by control theorists who weren’t talking to the game-playing crowd at all.
Next up — RL 5: Learning Automata and Stochastic Environments (1961–1974). How do you make good decisions when the world itself won’t give you a straight answer?
Series index:
Blog 1 — Biological foundations and the Law of Effect
Blog 2 — Classical conditioning and prediction
Blog 3 — Bellman, MDPs and Dynamic Programming
Blog 4 — Early heuristics and the birth of TD learning (this post)