Preface: In 1961, a machine learned to play a game without a single wire, just three hundred matchboxes. Following the previous #AI series and #MarvinMinksy series. This post is co-written with Claude.

On the morning of February 24, 1956, IBM broadcast a live checkers demonstration on television. One of the players was an IBM 701, the company's first large commercial stored-program computer, a machine that filled an entire room.

IBM's founder, Thomas Watson Sr., made a point of having the company's shareholders watch, and predicted that after the demonstration IBM's stock would rise fifteen points. Supposedly it did. A few months later, Watson died. Standing behind the machine was a soft-spoken engineer in his fifties. He wasn't a mathematician or a psychologist. His specialty was vacuum tubes.

Arthur Samuel was born in 1901 in Emporia, Kansas. He studied at the College of Emporia while working on and off at General Electric in Schenectady, New York. He earned a master's degree from MIT in 1926, stayed on as an instructor for two years, and joined Bell Labs in 1928. He spent nearly twenty years there, working mainly on electron tubes, the same vacuum tubes we met in the SNARC post. During the war, he helped develop a key component of radar: a switch that kept the receiver from burning out in the instant the radar fired its powerful pulse.

In 1946 he became a professor of electrical engineering at the University of Illinois and joined a project to build one of the early electronic computers. Samuel came up with an idea: write a program that played checkers and have it challenge the world champion. If it won, there would be no better way to show everyone how powerful electronic computers could be. At the time, he thought it wouldn't be hard.

The computer wasn't finished in time, so the checkers program never got finished at Illinois either. In 1949 Samuel moved to IBM's lab in Poughkeepsie, New York, and took the checkers idea with him. He later said that the problem of writing a program that seemed intelligent took up nearly all his spare time for as long as he was at IBM.

Why Checkers

In 1952, Samuel wrote his first checkers program on the IBM 701.

He chose checkers deliberately. Its rules are much simpler than chess, with only two kinds of pieces, ordinary pieces and kings, yet it has roughly five hundred billion billion possible positions, a 5 followed by twenty zeros. Simple rules meant the program wasn't hard to write, and most of the machine's effort could go into "thinking." So many positions meant there was no way to win by working through all of them. Bellman's curse of dimensionality applied here too. The program had to learn to judge whether the position in front of it was good, without being able to calculate all the way to the end of the game.

This was the same problem Hassabis ran into as a teenager writing his Othello program. Samuel's program also had two parts.

One part looked ahead. The program spread out every possible move, and every reply the opponent could make to each one, layer by layer like the branches of a tree. It looked a few moves ahead, then used minimax, assuming the opponent would always make the move best for them, to carry the scores back from the future to the present.

The other part was the evaluation function. After looking a few moves ahead, the game was still far from over, so the program had to give those future positions a score. Samuel's approach was to pick out a set of features, like how many pieces each side had left, how many kings, who controlled the center of the board, and whose pieces were more exposed to capture, give each feature a weight, and add them up into a total score.

An evaluation function is a formula for scoring a position. It is made up of a number of features, each multiplied by a weight, and the sum is the position's score.

Up to this point, this was only a program that played checkers, not a program that learned. The weights were set by a person. If the person set them well, the program played well; if not, it kept playing badly. What Samuel wanted was for the program to adjust those weights itself.

First Impressions and Second Thoughts

Samuel had the program learn in two ways.

The first he called "rote learning." As it played, the program stored the positions it came across, along with the scores it had worked out for them. The next time it looked ahead and found a position it had seen before at the end of a branch, it didn't need to analyze it again; it simply pulled up the stored score. And that stored score had itself come from looking several moves ahead the last time. In effect, the program could see further than it appeared to. This kind of learning was very slow, but it kept improving, and it was especially useful in the opening and the endgame, where positions repeat most often.

The second kind of learning was more interesting, and it's what earned Samuel his place in the history of reinforcement learning. He called it "generalization learning," and what it adjusted were the weights in the evaluation function.

The question was which way to adjust them. The most direct approach would be to wait until the game was over, then strengthen the judgments used in that game if it was won and weaken them if it was lost. But a game of checkers can run dozens of moves, and by the end there's no way to tell which of the earlier judgments went wrong.

Samuel's idea was: don't wait for the end of the game.

Before every move, the program gave the position in front of it a score. This was its "first impression," what the evaluation function could see at a glance. Then it looked a few moves ahead, spread out the branches, and carried the scores of those future positions back, arriving at a new score. This new score was its "second thought," because it took into account what might happen over the next few moves, and it was usually more accurate than the first impression.

If the two scores differed, the evaluation function's first impression was off. So the program adjusted the weights to bring its next first impression closer to this second thought.

Here's an example. At first glance, the program thinks it has a slight edge in some position and scores it +3. After looking a few moves ahead, it finds the opponent has a double jump coming that will take two of its pieces, and the score carried back is only −5. The gap is 8 points, which means the evaluation function is too optimistic about this kind of position. So the program checks which features produced the +3. Say "control of the center" was weighted too heavily and "how exposed my pieces are" too lightly. It turns the first down a little and the second up a little.

This way, the program learned with every move, without waiting for the game to be decided. Every lookahead was a small test, with the self that thought more deeply correcting the self that thought more shallowly.

The idea is strikingly close to Bellman's equation: the value of a position can be worked out from the positions that follow it. But there is a fundamental difference. Bellman needed to know all the rules of the world in advance and sit down to calculate every situation. Samuel didn't. He had the program estimate the value of each position, step by step, from the experience of actually playing.

Two Selves

To let the program adjust its own weights, Samuel also designed a way for it to play against itself.

He ran two versions of the program at once, one called Alpha and one called Beta. Alpha kept adjusting its evaluation function during every game in the way just described, while Beta stayed fixed. The two played each other. If Alpha won, its adjusted evaluation function was better, so Beta was replaced with Alpha's current version, and the games went on. If Alpha kept failing to win, it had drifted the wrong way and needed a shake-up to start over in a different direction.

This was one of the first attempts to make a machine stronger by having it play itself. More than fifty years later, AlphaGo Zero used the same basic idea, on a scale vastly larger.

In 1959, Samuel published a paper titled "Some Studies in Machine Learning Using the Game of Checkers." In the abstract, he wrote that with only about eight to ten hours of machine playing time, the program could learn to play a better game of checkers than the person who wrote it. The term "machine learning" spread along with the paper.

Three claims about Samuel get repeated more than any others: that he coined the term "machine learning" and gave it its classic definition, "the field of study that gives computers the ability to learn without being explicitly programmed"; that in 1962 his program beat a state checkers champion; and that this was the first time a machine had beaten a human expert at a game of skill. The first is only half right, the second is wrong, and the third needs a heavy discount. That much-quoted definition can't be found in Samuel's 1959 paper. It's a later summary of his work that eventually got attributed to him.

By 1962, Samuel's program had been moved to the faster IBM 7094. In a public match, it played a Connecticut player named Robert Nealey, and won. IBM's promotional materials called Nealey a former Connecticut checkers champion and one of the best players in the country. The news spread nationwide, and many people came away believing that checkers had been conquered by a machine.

It hadn't. At the time of the match, Nealey wasn't a state champion; he didn't win that title until four years later, in 1966. He had never played in top-level events like the U.S. championship, and his reputation came mostly from beating local players. And in that game, Nealey made an obvious blunder. In the rematch that followed, Nealey won one game and drew five, and the program didn't win a single one. In 1965 the program played a few games against the world checkers champion, Walter Hellman. Hellman won all four games played by mail, and the one game played across the board was a draw.

But the impression that checkers had been solved had already taken hold. Researchers moved on to chess, and checkers was largely neglected for more than twenty years. It wasn't until 1994 that Chinook, a program from the University of Alberta in Canada, truly reached world-champion level.

Why did Samuel's program stop where it did? He gave the answer himself in his 1967 review. Generalization learning was much faster than rote learning and did surprisingly well in the middle game, but its progress soon leveled off. The reason was that all the program could adjust were the weights, while the features themselves, what counted as "control of the center," what counted as "exposed to capture," had all been chosen by a person. If the features a person picked left out something important, no amount of reweighting could make up for it. What the program could learn would never go beyond the angles a person had taught it to look from.

This was the same wall Hassabis's Othello program ran into. He had to write "bonus points for corners" in by hand, and the machine just calculated according to his intuition. It would take AlphaGo for a machine to start deciding for itself what to look at on the board.

Samuel retired from IBM in 1966 and went to Stanford as a lecturer, later becoming a research professor, and taught there until 1982. He kept improving his checkers program until later programs outclassed it completely. He also never stopped writing code. He contributed to Stanford's operating system and to Donald Knuth's TeX typesetting system, and at eighty-six he was still writing programs for multi-font printing, possibly the oldest working programmer in the world at the time. He died at Stanford Hospital in July 1990 from complications of Parkinson's disease, at the age of eighty-eight.

Yet while Samuel was at IBM getting his program to play against itself, on the other side of the Atlantic, an Englishman who had broken German codes at Bletchley Park also wanted to teach a machine to play a game. He had no IBM 701. He didn't even have an electronic computer.

1923: The Codebreaker Born in Rangoon

Donald Michie was born in 1923 in Rangoon, in what was then British Burma. He went to Rugby School and won a scholarship to study classics, Greek and Latin, at Balliol College, Oxford.

The war changed his direction. In 1942, at eighteen, Michie signed up for a course in cryptography and ended up recruited to Bletchley Park, Britain's secret codebreaking center. He was assigned to a section called the Testery, which worked on a teleprinter cipher used by the German high command; the Allies code-named it "Tunny." To break Tunny faster, Bletchley Park built Colossus, one of the world's first programmable electronic computers. Michie was among the first people to operate it.

At Bletchley Park he became a colleague and friend of Alan Turing and Jack Good. The three of them often played chess together, and often talked about a question that sounded far-fetched at the time: could a machine learn to think? The ideas Turing later put into his 1948 report, a machine educated by a schoolmaster pressing keys, were things they had already talked over at Bletchley.

After the war, Michie didn't go on with computers. He returned to Oxford, switched to biology, and became a geneticist. In the 1950s, with his second wife, the biologist Anne McLaren, he studied genetics, fertilization, and embryo transfer in mice, work that later helped lay some of the groundwork for in vitro fertilization. But he never let go of those conversations at Bletchley about learning machines.

1960: MENACE

Around 1960, Michie was working at the University of Edinburgh. He wanted to run an experiment showing that a machine could learn to play a game by trial and error. But in Britain at that time, it wasn't easy for a geneticist to get time on an electronic computer. There were very few of them, they were enormously expensive, and the queue was long. Michie didn't wait. He decided to build his own, out of matchboxes.

He chose the simplest game he could: tic-tac-toe. A three-by-three grid, two players taking turns drawing noughts and crosses, and whoever gets three in a row wins. Tic-tac-toe is simple enough that the number of possible positions is manageable, yet complicated enough that a player who moves at random will certainly lose. He named the machine MENACE, for Matchbox Educable Noughts And Crosses Engine.

MENACE was made up of about three hundred matchboxes. Each matchbox stood for one tic-tac-toe position: one of the ways the board could look when it was MENACE's turn to move. The front of each box showed that position. Tic-tac-toe seems to have a great many positions, but many of them are really the same one. Rotate a board ninety degrees, or flip it left to right, and the game itself hasn't changed at all. Michie merged these essentially identical positions into a single box, which brought the count down from several thousand to about three hundred.

Each box held colored glass beads. Each of the nine squares on the board had its own color. If a box contained beads of a certain color, that meant that in this position, the machine could play in the matching square.

Take one box as an example.

First, give each of the nine squares its own color. For instance:

A red bead always stands for the top-left corner, a cyan bead always for the center, a black bead always for the bottom-right corner, and so on.

Now look at one box. Say the board drawn on the front of this box looks like this:

There's already an X in the top-left corner and an O in the center. It's MENACE's turn, and it can't play on a square that's already taken, only on one of the seven empty ones. So this box holds beads in only seven colors: orange, yellow, green, blue, purple, white, and black. There's no red and no cyan, because those two squares are already occupied.

Drawing a bead means choosing a move. The operator reaches into this box and pulls out a bead at random. Say it's yellow: MENACE puts an X in the top-right corner. The number of beads is each move's chance. If the box holds ten yellow beads and only one green one, a yellow bead is far more likely to come out, so MENACE is far more likely to play the top-right corner. Learning means the beads for good moves keep multiplying, and the beads for bad moves keep dwindling.

When it was MENACE's turn, the operator found the box showing the current position, gave it a shake, and drew out a bead without looking. Whatever the bead's color, that's where the move went. The bead was then set down next to the box rather than put back. After the opponent replied, the operator found the box for the next position and drew another bead. By the end of a game, there would be a row of open boxes on the table, each with the bead just drawn from it sitting beside it.

At first, every box held roughly equal numbers of each color, so MENACE was basically playing at random. Michie also stocked the boxes differently depending on how far into the game they came: boxes for the first move got four beads of each color, boxes for the third move three, the fifth move two, and the seventh move one. The earlier the position, the more beads and the more variety.

When a game was over, the operator dealt with the row of open boxes according to the result.

If MENACE won, each box it had used got its bead back plus three more of the same color. If the game was a draw, the bead went back with one more. If MENACE lost, the bead didn't go back at all. That was all there was to it. After a win, every move made in that game became more likely to be drawn next time; after a loss, every move became less likely. Over many games, the beads for winning moves multiplied and the beads for losing moves dwindled, and MENACE grew more and more likely to draw a good move.

This was Thorndike's Law of Effect turned, quite literally, into a tableful of things you could see and touch. The number of beads was how deeply a move had been "stamped in." SNARC kept track of this with knobs, MENACE with beads; SNARC's knobs needed a bomber's motor to turn them, while MENACE's beads needed only a hand.

Michie played a tournament against MENACE himself, 220 games over two days, with MENACE moving first. At the start, Michie beat it easily. But after seventeen games, MENACE had abandoned every opening but one: its first move always went in a corner. By around the twentieth game, it was drawing consistently. Michie began deliberately playing odd variations, trying to set traps for it, and MENACE slowly learned to handle those too. Finally, after losing eight games out of ten in a row, Michie stopped.

A machine made of matchboxes and glass beads had gone from playing completely at random to almost never losing, in two days. It knew nothing about tic-tac-toe beyond the rules. It had no idea what "take the corner" or "block your opponent" meant, and no one had taught it any strategy. All of its skill came from the changing number of beads.

In 1961, Michie described MENACE in the Penguin Science Survey. In 1962, Martin Gardner, America's most popular mathematics columnist, wrote about it in Scientific American and designed a smaller version that used twenty-four matchboxes to learn a game called hexapawn. Readers built their own at home. One turned it into a carnival game, handing out bigger prizes as the machine got better. Another ate a piece of candy every time her machine lost a game, and said that was how she learned the game faster than the machine did. In 1963, Michie published a paper describing MENACE in detail, and that same year he founded one of Britain's first artificial intelligence research units at the University of Edinburgh.

1961: Naming the Problem

In 1961, Minsky published a long paper titled "Steps Toward Artificial Intelligence," a systematic survey of the field that had only just been given its name. In it, he singled out one particular difficulty: in a complex process made up of many steps, when success or failure finally arrives, how do you divide up the credit or blame among all the decisions that came before? He called it the credit assignment problem.

Over the course of a decade, this problem had been run into from four directions. SNARC used leaking capacitors to give the credit to the last few steps before the reward. Bellman used an equation to work values backward from the end, but he needed to know all the rules of the world in advance. Samuel used later judgments to correct earlier ones, without waiting for the end of the game. MENACE had every move in a game share equally in the result.

Each approach worked on some problem, but none could do two things at once: learn without knowing the rules of the world in advance, and reliably trace credit back to a step taken long before. Samuel came closest, but his method was never distilled into a general rule.

1968: BOXES

After MENACE, Michie applied the same idea to a harder problem. In 1968, he and his colleague Roger Chambers published a system called BOXES, which taught a machine to balance a pole standing upright on a cart.

Picture balancing a broom upright on the palm of your hand: whichever way the broom starts to fall, you move your hand that way to keep it standing. That's what BOXES had to learn. If the pole is falling to the left, should the cart be pushed left or right?

BOXES had no physical form, and that was its biggest difference from MENACE. The cart and pole were simulated on a computer. No hardware was ever built; the pole's length, weight, and friction were simply tuned to resemble a real apparatus. The algorithm itself had been written as a FORTRAN program as early as 1961, born at about the same time as MENACE.

Here's how to picture it: a track with a cart on it, and on the cart a pole that can tip to the left or right. At every moment the machine can do only one thing: push the cart left or push it right, always with the same force. No gentle nudges, no holding still, only left or right. If the pole falls over, or the cart runs into the end of the track, that run counts as a failure. The machine watches four things: where the cart is on the track, how far the pole is leaning, how fast the cart is moving, and how fast the pole is falling. Michie cut position into 5 levels, angle into 5, and each of the two speeds into 3: 5 × 5 × 3 × 3, for 225 cells in all. At any moment, the state of the cart and pole falls into one of these cells, just as a tic-tac-toe position falls into one matchbox.

Each box is home to a little "demon", and each demon holds a left-right switch and a scoreboard, recording how long the pole lasted after it last chose left, how long after it chose right, and how many times each side has been chosen. When the system enters its box, the demon checks the scoreboard and picks whichever side has the better record. There is also a "global demon." It looks at the big picture, tracking the average performance across all the boxes, and gives each little demon a "target score." When a little demon makes its choice, it weighs its own scoreboard against this target. The point is to keep any one box from settling on a direction too early and never trying the other side again. Each time the pole falls and a run ends, every box used during that run updates its scoreboard according to how long the pole lasted after that decision: the longer it lasted, the higher the decision scores. Old results are multiplied by 0.99 after each run, so the older the experience, the less it counts. The inverted pendulum went on to become one of the classic test problems in reinforcement learning research. Fifteen years later, Barto, Sutton, and their colleagues used BOXES as the point of comparison when they demonstrated their new method.

Silence

In the second half of the 1960s, mainstream artificial intelligence turned in another direction. Researchers believed the key to intelligence lay in logic and reasoning: write down enough rules and knowledge for a machine, and it would be able to think like a person. Chess programs, theorem provers, and later expert systems all went down this road. On this road, a machine didn't need to learn from experience. People would tell it everything.

In 1969, Minsky and Seymour Papert published Perceptrons, which laid out the fundamental mathematical limits of simple neural networks. The book's influence went far beyond its actual arguments. Funding for neural network research all but dried up, and the field went into a slump, a story we covered in "The Unsolvable XOR Gate."

Reinforcement learning, caught between the two, was carried on by almost no one. Samuel was still improving his checkers program, and Michie had turned to robotics and automated planning in Edinburgh. The idea that had grown out of animal experiments, that a machine could learn to do things on its own from experience, through reward and punishment, was all but forgotten by the entire field for the better part of the next decade.

In 1977, a young postdoctoral researcher named Andrew Barto arrived at the University of Massachusetts Amherst to join a research project. The project started from an idea nobody at the time took seriously: that every neuron in the brain might be a tiny hedonist. 🧪

Sources:

• IEEE Computer Society — Arthur Lee Samuel

• Samuel 1967 — Some Studies in Machine Learning Using the Game of Checkers II

• Chinook — Arthur Samuel's Legacy

• AI Impacts — English draughts

• Martin Gardner — A Matchbox Game-Learning Machine

• Wikipedia — Donald Michie

• NYU — Donald Michie

• The Scotsman — Michie and Edinburgh AI

• Michie & Chambers 1968 — BOXES: An Experiment in Adaptive Control