From A/B to RL (3/3): MENACE and Delayed Rewards

Learning state-dependent policies with MENACE, matchboxes, and beads.

In the previous post in this series, the learner selected among actions online in a one-step bandit. It kept a posterior over each action's expected immediate reward $\theta_a$, and that uncertainty determined how often each action was chosen.

We keep the bandit's idea of choosing actions online, but add two elements of a richer RL problem: the choice now depends on the current board state, and the outcome arrives only when the game ends. In tic-tac-toe, the value of a move depends on the position and the opponent, so one global expected reward per action is no longer enough.

This is the third post in a three-part series:

The Toy Problem

We use tic-tac-toe as a small RL environment. One player, $X$, is the learner; the opponent plays $O$. Whenever $X$ moves, the current board is the state $s$, and choosing a legal square is an action $a$. In tic-tac-toe, we also call this action a move. The chosen action changes the board, and play continues until the game ends.

A complete game is called an episode. Rather than assigning an immediate reward to every move, we use the final win, draw, or loss as the terminal outcome $Y$. In RL terms, $Y$ is the delayed terminal feedback signal. The learner observes the board and the opponent's moves during the game, but receives this learning signal only after the episode ends. That delayed outcome is then used to update the policy for the moves selected earlier in the episode.

In [1]:

MENACE: Matchboxes and Policies

To make this setting concrete, we turn to MENACE, short for Matchbox Educable Noughts and Crosses Engine. Donald Michie built it in the early 1960s as a physical machine that learned to play tic-tac-toe. The original system used matchboxes and colored beads instead of code and arrays.

Photograph of MENACE's original matchbox setup
MENACE, Michie's matchbox-and-bead noughts-and-crosses engine. Source: Figure 2 in Michie's 1963 paper; higher-resolution crop from M. Scroggs. Cleanup: AI-assisted restoration blended with the original.

This physical setup makes MENACE a deliberately simple educational example of reinforcement learning. It extends the series from one-step bandits to state-dependent, delayed-reward learning while keeping the learning process visible.

MENACE uses a matchbox to represent each tracked board state, as shown in the photograph above and the diagram below. Symmetry-equivalent boards share a matchbox. Each bead color in that box represents a possible move. When several empty squares are equivalent under rotation or reflection, one color can represent that group of moves. Drawing a bead selects one of these moves, and MENACE maps it to a square on the current board. After the game, the final result is used to update the beads selected during play; we explain that delayed update below.

MENACE sequence showing board states, matchboxes, colored beads, and arrows
This diagram follows one MENACE game. MENACE plays X: the current board state identifies a matchbox, a colored bead selects the next cross, and the resulting board becomes the next state. Based on this reference diagram, redrawn for clarity.

Here the policy is explicit and physical: the bead counts in each matchbox define how likely each available move is to be selected. Drawing a bead samples an action from that policy, much like drawing from a statistical urn model.

In reinforcement-learning terms, the physical setup looks like this:

  • matchboxes represent tracked board states,
  • bead colors represent legal moves, including groups of symmetry-equivalent moves, from those states,
  • relative bead counts define the probability of each move in a state,
  • the game rules and opponent produce the next board state,
  • one full game is called an episode,
  • only the final win/draw/loss outcome is used for learning.

Here we simulate this physical design in code.

How MENACE Selects a Move

MENACE separates action selection during a game from learning after the game ends. During an episode, it reads the current board, draws a bead from the corresponding matchbox, and plays the selected move. It records the selected beads but leaves their counts unchanged. Once the game ends, it uses the final win, draw, or loss to update those beads.

The figure below zooms in on one move. Read its four panels from left to right: the current board state, the corresponding matchbox and its bead distribution, the sampled bead that selects the move, and the resulting board. It uses a small illustrative matchbox whose bead counts are already uneven, as if earlier games had started to shape the policy.

Let $s$ denote the current board state, let $\mathcal{A}(s)$ be the set of moves represented in the matchbox for that state, and let $a \in \mathcal{A}(s)$ be one such move. MENACE observes the current board and looks up the matching matchbox. In that matchbox, $N(s,a)$ is the bead count for move $a$, so it acts as that move's policy weight. Colors are local to the box: on this board, each color marks one available move.

Inside a matchbox, the probability of selecting each move is its bead-count proportion:

$$ \pi(a \mid s) = \frac{N(s,a)}{\sum_{b \in \mathcal{A}(s)} N(s,b)}. $$

The sampled bead determines the move shown in the figure's third panel, which MENACE maps to a legal square in the final panel. This is the action-selection phase; the bead counts are updated only after the episode outcome is known.

In [2]:
In [3]:
Four-panel illustration of a MENACE move: read the board state, interpret bead-count policy weights, sample the green bead into a V-shaped matchbox holder, and place the selected cross.

Initialization

Before training, MENACE creates a matchbox for each tracked board state where it needs to choose a move. Each matchbox starts with the same number of beads for each available move. In Michie's original setup, that number depends on the move number: 4 beads for MENACE's first move, then 3, 2, and 1 for later moves. Each matchbox therefore starts with a uniform policy over its available moves. Later matchboxes start with fewer beads, so each update has a larger relative effect.

Symmetry reduces both the number of matchboxes and the number of moves they need to represent. Boards related by a rotation or reflection share one state class and one matchbox. Within a given board, empty squares that remain equivalent under a symmetry form one move class. In this post, we use move as shorthand for one of these symmetry-reduced move classes.

The empty board gives the simplest example: all four corners are equivalent, all four sides are equivalent, and the center is unique. Its opening matchbox therefore needs only three move classes: corner, side, and center. As shown in the figure below, it starts with 4 beads for each class. This is uniform over the three move classes, not over the nine physical squares. When MENACE samples a move, it maps that move back to a legal square on the current board.

In [4]:
Initial bead counts in MENACE's opening matchbox before training.

Delayed Reinforcement

During an episode, MENACE records each state–action pair (the current board state and the move it chooses) but leaves the matchboxes unchanged. Once the game ends, the final outcome determines how every recorded move is updated.

MENACE applies the same update to the bead color selected at each visited state:

  • win: add 3 beads
  • draw: add 1 bead
  • loss: remove 1 bead

Let $Y$ denote the final outcome. For every state–action pair $(s_t,a_t)$ selected by MENACE during the episode, the policy weight is updated as:

$$ N(s_t,a_t) \leftarrow \max(0, N(s_t,a_t) + \Delta(Y)), $$

Here, $\Delta(Y)$ is $+3$ for a win, $+1$ for a draw, and $-1$ for a loss. A positive update makes the selected move more likely in that state next time; a negative update makes it less likely. These update values are part of MENACE's design, not quantities learned from the environment.

At the end of each episode, the procedure is:

  1. play the game while recording each state–action pair selected by MENACE,
  2. observe the final outcome $Y$,
  3. update every recorded policy weight by $\Delta(Y)$.

This is delayed credit assignment made physical: the final outcome changes the bead counts for decisions made earlier in the game.

In [5]:

The figure below makes this delayed update concrete. It follows three MENACE moves from one episode: the opponent's intervening moves appear as changes in the board states, the top row shows the matchboxes before updating, the middle row shows the selected beads held aside, and the bottom row shows the same matchboxes after the final outcome has been applied.

In [6]:
Demo episode outcome for MENACE: win
Number of MENACE matchboxes updated: 3
Sequence of three MENACE moves showing matchbox weights before play, sampled beads held aside, the episode outcome, and weights after delayed credit assignment.

The terminal outcome is not available until the whole game has been played. MENACE does not know exactly how each move influenced the final result, so it applies the same win/draw/loss update to every selected bead from that episode.

This differs from the Bayesian updates used in the first post and carried online into the second post. There, counts represented evidence about uncertain rewards or values. Here, bead counts are policy weights: MENACE adds or removes beads to make selected moves more or less likely after delayed feedback.

Learning from Self-Play

Next, we train an opening-player MENACE through repeated games. It plays 5,000 games against a small rotating pool of second-player MENACE agents, with occasional random move perturbations. This is a small self-play setup.

We then evaluate the learned opening-player policy against four fixed opponent policies: random, positional, defensive, and a perfect minimax policy. This keeps the training setup separate from the final evaluation.

We'll inspect a few checkpoints:

  • 25 games: early bead movement; wins and losses begin to reshape the opening policy,
  • 100 games: early policy shaping; common mistakes are being punished, but the policy is not reliable yet,
  • 1,000 games: tactical matchboxes have usually been visited often enough to show clearer preferences,
  • 5,000 games: in this demonstration run, the learned policy mostly draws rather than loses against perfect play.

Michie's original report tracked cumulative bonus and forfeit scores. Here we plot cumulative outcome rates instead, because they connect directly to the win/draw/loss evaluations below.

In [7]:
Training setup: pooled self-play with 5% opponent random moves
Training outcome rates: {'win': 0.449, 'draw': 0.443, 'loss': 0.108}
Perfect-opponent draw rates by checkpoint:
  25 games: draw=0.165, loss=0.835
 100 games: draw=0.180, loss=0.820
1,000 games: draw=0.661, loss=0.339
5,000 games: draw=0.931, loss=0.069
    Random: win=0.886, draw=0.075, loss=0.039
Positional: win=0.923, draw=0.018, loss=0.059
 Defensive: win=0.004, draw=0.932, loss=0.064
   Perfect: win=0.000, draw=0.914, loss=0.086
In [8]:
Cumulative win, draw, and loss rates during MENACE self-play at several training stages.
Two-panel evaluation of MENACE after training: draw and loss rates against a perfect opponent across checkpoints, and final outcome fractions against fixed opponents.

These plots serve two purposes. The training curves summarize the games MENACE experienced during self-play, while the evaluation plot checks the learned policy against a few fixed opponents. Against a perfect tic-tac-toe opponent, the best possible result is a draw, so the useful signal is whether losses disappear, not whether wins appear.

Learned State-Dependent Policies

In the bandit examples, there was only one state, so one action distribution was enough. In tic-tac-toe, the right move depends on the board. MENACE handles this with a separate policy for each tracked board state, represented by that state's matchbox and bead counts.

The next figure shows three states after 1,000 training games. At this point, the policy has started to favor some moves without assigning nearly all probability to one move, and the tactical matchboxes have been visited often enough to show meaningful preferences.

  • the empty opening board,
  • a state where $X$ can win immediately,
  • a state where $X$ must block an immediate threat from $O$.

The first row shows bead counts; the second shows the action probabilities induced by those counts. For the opening board, we show only the symmetry-distinct moves, matching the physical matchbox.

In [9]:
State-dependent MENACE policies after 1,000 games, showing bead counts and implied move probabilities for an opening, winning, and blocking board.

These plots play the same role for MENACE as the posterior and policy plots did in the previous post. There are no density curves here. The learned object is the policy itself, visible in the bead counts and in the action probabilities they imply.

How This Relates to Thompson Sampling

In the previous post in this series, Thompson sampling used posterior uncertainty about each action's expected reward to choose online. With independent posterior draws, the selected action is the one with the largest draw; equivalently, each action is selected in proportion to its posterior probability of being best.

MENACE takes a different approach. It is not a typical modern RL algorithm; we use it here for its illustrative value. It learns a policy directly, making that policy physical and intuitive: bead counts in a matchbox act as policy weights, and drawing a bead samples an action. MENACE therefore does not maintain a posterior over rewards or a separate value model.

The two approaches store different things, so their action probabilities have different meanings:

Method What is stored? How is an action selected? What do the probabilities mean?
Thompson sampling posterior over action values draw one value from each posterior and choose the largest posterior probability that the action is best
MENACE bead counts / policy weights sample directly from the normalized bead counts the learned tendency to choose each move

Both methods produce stochastic actions, but the source of that randomness is different: posterior uncertainty in Thompson sampling, and directly learned policy weights in MENACE.

Play Against the Learned Policy

The plots above are static snapshots. The widget below freezes the trained opening-player MENACE after 5,000 games and lets you play against it.

You play O and MENACE plays X. On MENACE's turn, the colored squares show the move probabilities represented by its symmetry-reduced matchbox policy. If several legal squares are equivalent by rotation or reflection, the widget shows one representative square for that bead class. The vertical fill shows the class probability: taller fill means the class is more likely to be sampled. Click Sample MENACE move to draw one bead from the current matchbox and play the representative square for that class.

The widget is for inspection, not training. It does not add or remove beads while you play.

In [10]:

Interactive visualization loading…

Summary

MENACE is a simple physical illustration of reinforcement learning that makes policy learning visible in tic-tac-toe:

  • a board position is the state, with symmetry-equivalent positions sharing one tracked state,
  • a legal move is an action,
  • a matchbox stores the policy for one tracked board state as colored beads, where each bead color represents a legal move,
  • bead-count proportions define the policy $\pi(a \mid s)$,
  • one full game is called an episode,
  • the final win/draw/loss outcome updates the beads selected during that episode.

The terminal learning signal arrives only at the end of the episode. MENACE uses that outcome to update every selected move, making delayed credit assignment physical.

MENACE learns the policy directly rather than a posterior over values or an environment model: more beads make a move more likely, while fewer beads make it less likely. That is the key step beyond bandits: a delayed game outcome shapes a state-dependent policy.

References

Further Reading

In [11]:
Python: 3.13.12
numpy: 2.4.6
matplotlib: 3.11.0
seaborn: 0.13.2

This post is generated from an IPython notebook file. Link to the full IPython notebook file