Deep Dive: Matchbox Nim

Learning by Trying and Getting Feedback

In 1.1.1 a model learned patterns in text. In 1.1.2 a model learned from examples that came with the right answers. Here is a third way. A learner takes actions in some situation, finds out whether things went well, and shifts toward the actions that worked. That is reinforcement learning. Nobody hands it the correct answer for each move. It only gets a reward when it does well and a penalty when it doesn't, often long after the move that mattered.

Game-playing systems are the classic example. Programs such as AlphaGo, which beat a top Go champion in 2016, improved in part by playing enormous numbers of games and learning from wins and losses. Some chatbots are also fine-tuned with human feedback on their answers, which is related. The learner in this activity is a hand-built, tiny version of the same idea.

The Game of Nim

Here are the rules, written so there is only one way to read them:

1. Two players share one pile of pieces. The pile starts with 10 to 20 pieces.
2. Players take turns. On your turn you remove at least 1 piece and at most half the pile, rounded down.
3. If only 1 piece is left, the player to move must take it.
4. The player who takes the last piece loses.

Play a few games and try both starting positions. Notice that sometimes the computer seems unbeatable and sometimes it makes a move that looks random. That isn't luck. There is a pattern underneath, and the next section finds it.

Solve It Backward

Work from the end of the game. A pile of 1 is a loss for whoever has to move, because they're forced to take it. So any pile where you can leave a pile of 1 is a win: that's pile 2 (take 1). Keep going. A pile is losing for the player to move if every legal move leaves a pile the other player can win from. A pile is winning if at least one legal move leaves a losing pile.

The losing piles are 1, 3, 7, 15, and the next one is 31. Each is one less than a power of two (2 − 1, 4 − 1, 8 − 1, 16 − 1). If you can leave one of those, you win, because from there the other player can't reach another losing pile without you being able to answer.

Notice how this solution came about. We wrote a short procedure that checks every legal move. That's a search, and it works because Nim is small. A learner in the next section has no such procedure. It has to find the same moves by playing.

A Learner Made of Cups and Beads

In 1961 the British researcher Donald Michie built a machine called MENACE out of a few hundred matchboxes and colored beads that learned to play noughts and crosses. Here is the same idea for Nim, scaled down so you can build it in a few minutes.

• Take one cup for each pile size the learner might face. For our game that's piles 2 to 9: 8 cups.
• Each cup holds beads, one color per legal move. Cup 8 has beads for "take 1," "take 2," "take 3," and "take 4." Start with 3 beads of each color, so every move is equally likely.
• To move: find the cup for the current pile, shake it, draw one bead without looking, and take that many pieces. Set the bead beside the cup.
• After the game: if the learner won, put the beads it used back in their cups and add 2 more of each color it used. If it lost, take away 1 of each color it used, but never take the last bead of a color. That would erase a move for good.

The learner starts out playing at random. Moves that tend to lead to wins pick up extra beads, so they get drawn more often. Moves that tend to lead to losses shrink.

Run 100 games and watch the cups. The bars for the moves that leave a losing pile grow, and the learner starts to win more often. It has never been told about 1, 3, 7, and 15. It found the good moves only by playing.

What the Learner Can and Can't Learn

Switch the Bead Lab to train against a perfect player and play 100 games. Nothing improves. Against a perfect opponent that moves first from 10, the learner is always left in a losing pile, so it never wins, never gets a reward, and only loses beads. A reinforcement learner can only learn from what it experiences, and it needs some successes to reinforce.

Even against a random player the learner can't reach 100%. If the opponent's first move leaves the learner in a losing pile, the learner has to hope for a mistake. The Bead Lab shows the best possible win rate for each opponent, worked out from the game itself.

Asking a Chatbot to Build the Game

Now you'll ask a chatbot to write a Nim page: a single file of HTML and JavaScript you can open in a browser. What you get depends on what you ask for. A prompt that says "make a Nim game" leaves the chatbot to guess the rules, who goes first, and how smart the computer should be. A good prompt states all of them.

Then improve it in rounds. Add one request at a time ("make the computer play to win whenever it can," "show the moves in a log"), and save each result as a new version, like Nim1.html, Nim2.html, Nim3.html, so you can go back. Keep a short log of what you asked and what changed.

Test It. Don't Just Trust It.

Your page will probably run, look good, and beat you a couple of times. That tells you very little. A bug might only show up on pile 13 or pile 19, and you'd have to be lucky to land on it. Friendly code comments don't prove anything either: they describe what the chatbot meant the code to do, not what it does.

A test case is a specific input paired with the answer you expect, written before you run the code. You already have the answers, because you solved the game.

Add edge cases that are easy to get wrong:

• A pile of 2: the only legal take is 1.
• A pile of 1: the player must take it and loses. Does the page say so?
• A losing pile like 7 or 15: the computer should still make some legal move.
• Illegal input: 0, more than half, a letter, a blank. Does the page reject each one?
• The starting piles 10 and 20, the edges of the allowed range.
• Who wins when the computer takes the last piece? It's easy to flip the winner.

How did the chatbot do it?

The chatbot didn't play thousands of games, and it didn't solve the game the way you did. A likely explanation is that it had seen many Nim descriptions, strategy write-ups, and code samples in its training data, and it assembled something that matches those patterns. That's the same next-word prediction from 1.1.1, working on code. We can't look inside the model to be sure, which is one more reason to test the result.

Same habit, bigger stakes

Swap "Nim" for "a payroll calculation" or "a medicine-dosing page" and the lesson gets serious. Code that runs is not code that is correct. The people who use it deserve test cases written by someone who knew the right answers in advance.