Reinforcement Learning with Cups and Chips
A learning machine you can touch.
Nine cups on the table
There is a moment in our AI training courses that we are rather fond of. We put nine cups on the table, place a few chips next to them and announce that this arrangement is about to learn how to win a game. Nobody believes it at first. Cups are not computers, after all, and chips do not look much like machine learning.
A good half hour later, the arrangement of cups wins every game, against anyone in the room.
The idea of building this game into our courses came from my colleague Carsten Feldmann. It has been a fixture ever since.
What sits on the table is not a model of reinforcement learning. It is reinforcement learning, just without the computer. That is what makes the exercise such a good way in: you can touch the learning steps while you explain them.
In this post I describe the exercise in enough detail to rebuild it. After that I show what happens when the same procedure runs as a simulation, and compare it with Q-learning, the textbook method for the same task.
The game
The game is NIM, more precisely a misère variant with a single pile. Ten objects lie on the table; we use small stones, but matchsticks, paper clips or gummy bears work just as well. The two sides take turns removing one, two or three stones. Whoever has to take the last stone loses.
NIM was one of the first games ever to be given a complete mathematical theory (Bouton 1901). For a training course, though, what matters most is its size: small enough that a game is over in a minute, large enough that the strategy is not immediately obvious.
Why 1, 5 and 9 are losing positions
The strategy fits into a single sentence. That does not make it obvious, and for a training course this is an advantage. You find it by reasoning backwards from the end of the game.
Whoever faces one remaining stone has lost. They have to take it; there is no alternative.
Whoever faces two, three or four stones has won: they can leave their opponent exactly one stone, which puts that opponent in the losing position just described.
It gets interesting at five stones. Take one and four remain. Take two and three remain. Take three and two remain. In all three cases you leave a position from which your opponent wins. There is no good move here, so five is a losing position as well.
From six, seven or eight stones you can leave the five behind and therefore win. At nine even that is no longer possible: what remains is eight, seven or six, and your opponent wins from all three.
That is how the pattern arises. Whoever faces 1, 5 or 9 stones has lost, in other words a multiple of four plus one. The spacing of four has a simple reason: you can top up every one of your opponent’s moves to four. If they take one stone, you take three; if they take two, you take two; if they take three, you take one. Exactly four stones then disappear per round, and whoever has once left one of these numbers behind will leave one behind again afterwards.
Because our machine always moves first and starts at ten stones, it can in theory win every single game: it takes one stone, leaving nine, then five, then one.
It just does not know any of this at the outset.
The machine
For every number of stones the machine can face, there is one cup on the table. They are labelled 2 to 10. No cup is needed for a single stone, because the move is then forced and there is nothing to decide.
Every cup holds chips numbered 1, 2 and 3, one chip for each possible move. The cup labelled 2 holds only the chips 1 and 2, since you cannot take three stones when only two are left.
The game then works like this: one or more people play against the machine, and another person operates it. Operating means carrying out its moves without thinking for it. When the machine is to move, that person reaches into the cup matching the current number of stones, draws a chip blindly and removes as many stones as the chip says. The drawn chip stays in front of its cup until the game is over.
Materials: nine cups (labelled 2 to 10), chips numbered 1, 2 and 3 in each cup (only 1 and 2 in cup 2), and ten stones.
Playing: The machine starts every game. When it is to move, draw a chip blindly from the cup matching the number of stones still on the table and remove as many stones as it says. The chip stays in front of its cup. Then the human moves. Whoever has to take the last stone loses. If a single stone is left and the machine is to move, there is nothing to draw: it has to take the stone and has lost.
After the game:
- The machine won: All chips lying in front of the cups go back in. Nothing changes.
- The machine lost: The chip from the last move is discarded for good. All other chips go back.
- Special case: If that cup holds only this one chip, it stays in play and goes back. The chip from the previous move is discarded instead. If that cup, too, holds only one chip, go back one move further.
End: Play until every cup holds only a single chip. In the simulation this takes 41 games against a perfect opponent and just under 100 against one that moves at random; human opponents fall somewhere in between.
This special case is the actual trick, and we point it out explicitly during the course. When a cup holds only one chip, the machine had no choice there. So it cannot have done anything wrong either. The blame must lie with an earlier move, and that is where the punishment goes.
What is phrased here mechanically as “go back one cup further” is, mathematically, backward induction. The machine learns the end positions first, and once those are settled, the assignment of blame works its way step by step towards the start of the game. Nobody has to calculate any of this; the rule brings it about on its own.
What happens in the room
The machine loses almost all of the first games, and that is the most important part of the exercise. Participants win effortlessly and are accordingly relaxed. Anyone expecting a machine that is superior from the start instead watches nine cups remove stones aimlessly.
After a few games the picture changes. The machine hits the critical positions more often, and eventually it wins for the first time. The progress does not lie in that first win, though. When the machine wins, all the chips go back into the cups and its state afterwards is exactly what it was before. It learns from defeats only: every game lost costs it precisely one chip, every game won costs it nothing. So all of the progress sits in the defeats. The better the machine plays, the more rarely it learns anything new.
The person operating the machine usually notices the change first, because they can see how empty the cups are getting. They carry out the moves without deciding anything, so they are the machine’s hands. Even so, after twenty games people talk about the cups as if they had a plan. All that is behind it is the discarding of chips. How quickly we attribute intentions to software is well worth discussing at this point.
This is already reinforcement learning
Now is a good moment to introduce the vocabulary, because every term points at something visibly lying on the table.
In reinforcement learning, an agent learns through interaction with an environment (Sutton and Barto 2018). The agent here is the arrangement of cups; the environment is the game together with the human opponent. The environment is always in some state, which for us is the number of stones still on the table. Each state has exactly one cup. The agent picks an action, that is, a chip, and at the end of the game receives a reward: won or lost.
All the cups together with their chips are the agent’s strategy, or policy in the jargon. It is not written down anywhere; it simply consists of what is currently in the cups. Learning, in this method, means changing those contents.
Two problems that appear in every textbook on the subject can be demonstrated directly with this exercise.
The first is credit assignment. At the end of a lost game you only know that something went wrong, not which of the three or four moves was at fault. The last move is the obvious suspect, but the actual mistake may have happened much earlier. Our special-case rule is the answer to this, and it is remarkably accurate: in NIM the last move of a lost game is provably a mistake, and if that cup holds only one chip, the move before it was provably to blame.
The second is the conflict between exploration and exploitation. As long as many chips are in a cup, the machine inevitably experiments. The emptier the cups get, the more it exploits what it already knows. In this method the balance takes care of itself, because both depend on the same thing: the number of chips.
The idea is not new, by the way. In 1961 Donald Michie built a machine from 304 matchboxes and coloured beads that learned to play noughts and crosses, and called it MENACE, the Matchbox Educable Noughts And Crosses Engine (Michie 1963). Our cup game is a stripped-down version of it: fewer states, fewer beads, same idea. Anyone wanting to rebuild Michie’s original will find detailed instructions (Child 2016) and an online version to play against (Scroggs 2016).
How fast does the thing learn?
In the course we play to the end, but nobody keeps count. For this post I therefore rebuilt the procedure in R and animated it. Figure 1 shows a complete training run against a perfect opponent. The board runs on the left, the win rate underneath it, and on the right you can see the cups: chips still in a cup are blue, discarded ones are pale.
The result surprised me on the first run: the machine loses exactly 15 times, and never again after that. The last defeat happens in game 41; from game 42 onwards it wins every game.
The 15 follows directly from the number of bad chips in the system. The seven cups from which the machine can force a win hold 20 chips at the start, only seven of which are correct, so 13 have to go. Two more come from the cup labelled 5, which makes 15 in total. Because every defeat is guaranteed to remove exactly one bad chip, that is the end of it. You can therefore calculate this machine’s learning time in advance, which is rarely something one can say about a learning method.
Two cups behave conspicuously at the end, and both cases are instructive.
The cup labelled 5 keeps a random chip rather than the “correct” one. That is exactly right, because 5 is a losing position: no move from five stones leads to a win, and all three chips are equally bad. The machine learns nothing here because there is nothing to learn. Once it plays well, it never ends up in this situation again anyway.
The cup labelled 9 stays completely full; not a single chip was ever removed from it. The reason lies in the setup: the machine starts at ten stones and takes at least one, after which the opponent takes at least one. So it can never be on move at nine stones. A cup that is never used learns nothing either. In a course this is a good moment to talk about training data: a model only learns about situations that actually occur.
The opponent has a say
It gets interesting when you swap out the opponent. Figure 2 shows the same machine under the same rules, but against an opponent who simply moves at random:
Exactly 15 defeats again; that does not change. But they take much longer to arrive: the last one only comes in game 98, more than twice as late as before.
The reason follows directly from the fact that the machine learns from defeats only. Against a weak opponent it wins often enough even with bad chips, simply because the opponent fails to punish the mistake. The bad chips therefore stay in the cups for longer.
So the strong opponent is the better teacher. Whoever only plays against weak opponents learns more slowly despite winning more often. In a course this observation transfers nicely to the question of why one tests models on difficult cases rather than convenient ones.
Q-learning: same idea, different bookkeeping
In textbooks and software libraries, reinforcement learning looks rather different from nine cups on a table. The best-known method is called Q-learning. It rests on the same basic idea as our cup game, but it keeps a record of its experience instead of discarding chips.
Instead of chips in cups, Q-learning maintains a table. For every combination of state and action, that is, for every cup and every chip in it, there is a number: the rating of that move in that position. You can picture the same set of cups, except the chips stay put and each of them carries a mark instead.
In our game these ratings lie between −1 and +1, because there are only two possible outcomes. A value near +1 means “this move wins from this position”, a value near −1 means the opposite, and 0 means “no idea”. At the start all ratings are 0.
That leaves two questions to settle which the cup game still rolled into one: how does the machine pick a move, and how does it then change its ratings? In a cup, the number of chips handled both at once, since anyone reaching in blindly draws rare chips rarely. A table full of numbers, by contrast, does not draw from itself.
Picking a move. Whoever always plays the highest-rated move never tries anything new and gets stuck with whatever happened to look good first. So one mixes in some randomness. The usual approach is \(\varepsilon\)-greedy: with probability \(\varepsilon\) the machine moves at random, and with probability \(1-\varepsilon\) it plays the currently highest-rated move. At the start \(\varepsilon\) is close to 1, so the machine is essentially just rolling dice. Over the course of training \(\varepsilon\) shrinks and the machine increasingly relies on what it has learned; in our simulation it falls by 1.5 per cent from game to game.
Learning. After every move, its rating is nudged towards what actually happened: upwards if the move contributed to a win, downwards if it led into a defeat. The rule for this is the method’s central formula:
\[ Q(s,a) \;\leftarrow\; Q(s,a) \;+\; \alpha \bigl[\, r + \gamma \max_{a'} Q(s',a') - Q(s,a) \,\bigr] \]
What the individual symbols mean:
- \(s\) is the state, for us the number of stones on the table. That is the cup.
- \(a\) is the chosen action, that is, how many stones are taken. That is the chip.
- \(Q(s,a)\) is the rating of that move in that position, the number between −1 and +1 from above. The arrow means that it is replaced by the expression on the right.
- \(r\) is the reward immediately after the move: +1 if the game is won by it, −1 if it is lost, and 0 if play continues. In NIM \(r\) is therefore almost always 0, since points are only awarded at the end of the game.
- \(s'\) is the next position in which the machine is on move again after the opponent’s reply, and \(a'\) stands for the moves available there. \(\max_{a'} Q(s',a')\) is thus the rating of the best move it knows of in that next position.
- \(\alpha\) is the learning rate, 0.3 in our simulation. It determines how strongly a single game shifts the rating. At \(\alpha = 1\) the machine would treat its most recent experience as the whole truth; at \(\alpha = 0\) it would learn nothing at all.
- \(\gamma\) is the discount factor, 1 in our case. It determines how much a late reward counts. With \(\gamma = 1\) a win five moves from now is worth exactly as much as a win right away; smaller values make the machine impatient.
The expression in square brackets is the surprise: the difference between what actually emerges after this move, namely \(r + \gamma \max_{a'} Q(s',a')\), and what the machine had expected beforehand, namely \(Q(s,a)\). If the move turned out better than expected, the bracket is positive and the rating rises. If it turned out worse, the rating falls. Because the rating of the next position feeds into the rating of the current one, information seeps forward from the end of the game, one step per game.
It is striking that \(\varepsilon\) appears nowhere in this formula, even though it visibly governs the machine’s behaviour. The reason sits in the term \(\max_{a'} Q(s',a')\): it always looks at the best move in the next position, no matter which move the machine will actually play there later. So it consistently rates perfect play while still experimenting itself. The jargon for this is off-policy: what is learned concerns a different strategy from the one being acted on. \(\varepsilon\) therefore only determines which positions come up at all, and hence which entries get updated. On the calculation itself it has no effect.
You can certainly bring exploration into the formula, but then you get a different method. In SARSA, the place of the maximum is taken by the rating of the move the machine actually plays next, which may well be a randomly chosen one (Sutton and Barto 2018). It thereby rates its real, still unfinished behaviour rather than perfect play. In NIM this changes little. Where mistakes are expensive it changes a great deal: whoever allows for the fact that they occasionally roll dice will keep a greater safety margin from precarious positions.
Figure 3 shows the same game against the same perfect opponent. On the right, in place of the cups, the Q-table now appears as a heatmap; blue means “good move”, red means “bad move”:
The difference is considerable. Against the same opponent, the cup game loses 15 games and Q-learning loses 98. The cup game is finished after 41 games; Q-learning needs 306.
That does not make Q-learning the worse method. It simply knows less. Three reasons together explain the gap:
- No built-in credit assignment. Our cup rule knows that the last move is to blame, and if not that one, the one before it. Q-learning does not know this. It has to distribute the blame statistically across many games, and the information travels only one step towards the start of the game per game played.
- No hard discarding. The cup throws a bad chip out for good. Q-learning merely shifts a rating, and only by the fraction \(\alpha\). A bad move therefore remains selectable until its rating has dropped far enough.
- Deliberate experimentation. A good share of those 306 games is down to planned exploration. Even when the table has long been correct, \(\varepsilon\) still makes the machine roll dice occasionally, and it loses as a result.
So why bother with Q-learning?
If the cup method is so much faster, one might ask why anyone bothers with the other one. The answer is that our cup rule assumes something that is available almost nowhere else.
It works only because in NIM the last move of a lost game was guaranteed to be a mistake. That guarantee is what makes hard discarding permissible. In most real problems there is no such guarantee. As soon as chance is involved, whether in backgammon, in logistics or in a pricing decision, the same move can lead to success one time and to failure the next. Discarding for good after a single defeat then throws away good options all the time.
Q-learning is built for precisely this. It averages over many experiences instead of taking individual outcomes at face value. It copes with uncertain rewards, with states that are seen only rarely, and in its modern variants with state spaces for which one could never set out enough cups. Robustness against noise costs speed, and in our very clean little game you pay that price without getting anything in return.
The two methods therefore sit at opposite ends of the same scale: how much prior knowledge is built into the learning rule, and how much does the method have to work out for itself? Our cup rule already contains a good chunk of game theory that someone put there when designing the rule. Q-learning contains none of it, and that is exactly why it can be used anywhere.
Conclusion
We like this exercise because it does without metaphor. There is no need to say that machine learning “works a bit like”. On the table stands a machine that learns from experience, and you can watch it do so.
Three things above all stay with us from these courses. First: the moment the machine wins for the first time explains more about reinforcement learning than any slide with a state diagram. Second: the fact that the machine learns from defeats only leads almost by itself to the question of where the feedback actually comes from and who defines it. In the game that is obvious; in a company it rarely is. And third: the cup labelled 9, which nobody ever touches, is the best hook we know for the topic of training data. A machine learns nothing about situations that never occur.
Then it is time to tidy up. Nine cups, a few chips, ten stones and a few dozen games. Considerably less effort than the 304 matchboxes Donald Michie started with.