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 policy was explicit in a one-step bandit. A Bayesian learner kept a posterior over each action's mean reward, and that uncertainty determined how often each action was chosen.

We keep the bandit's idea of choosing actions online, but two things change: the choice now depends on the current board state, and the win/draw/loss signal arrives only when the game ends. In tic-tac-toe, the best square depends on the position, so one global success probability per action is no longer enough.

We'll use tic-tac-toe, specifically the historical MENACE setup: a matchbox-and-bead learner that illustrates how a policy can be learned directly. The reward signal is delayed: MENACE observes the board and the opponent's moves as the game unfolds, but receives the win/draw/loss signal only when the episode ends. In RL, this final result is called the terminal outcome. Tic-tac-toe is small enough to make both ideas easy to see: the policy depends on the board state, and the final result must be credited to the moves that led to it.

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

In [1]:

MENACE: Matchboxes and Policies

MENACE is 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.

MENACE uses a matchbox to represent each board state it tracks, as shown in the photograph above and the diagram below. It finds the box corresponding to the current board. 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 squares. Drawing a bead samples a move from the policy, and MENACE maps it to a square on the current board. The bead counts determine how likely each move is. 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 vector redraw 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.

That makes MENACE useful here: its policy is visible and physical. It lives in the bead counts inside the matchboxes. Drawing a bead samples an action from the current policy, much like drawing from a statistical urn model. The counts in the box determine how likely each move is on a future visit to that board state.

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

  • matchboxes represent board states,
  • bead colors represent legal moves, or symmetry-distinct move classes, from those states,
  • relative bead counts define the action probabilities for each state,
  • the game rules and opponent produce the next board state,
  • one full game is an episode,
  • only the final win/draw/loss outcome is used for learning.

The original MENACE was made of matchboxes and beads. Here we simulate the same idea in code.

The MENACE Loop

MENACE has two phases. During the game, it samples moves by drawing beads from matchboxes. After the game, it reinforces the bead colors it drew based on the final win, draw, or loss. We start with one sampled move, then look at the delayed update.

MENACE learns the policy itself through repeated play. The bead counts are not posterior beliefs about rewards or estimates of action values. They are policy weights: more beads make a move more likely to be sampled, but a move with fewer beads can still be selected.

The next figure follows one MENACE move. It uses a small illustrative matchbox whose bead counts are already uneven, as if earlier games had started to shape the policy.

MENACE first observes the current board state and looks up the matching matchbox. The beads in that box are the policy weights $N(s,a)$ for the legal moves from that state. Colors are local to the box: on this board, each color marks one legal move class.

Inside a matchbox, the action probabilities are just the bead-count proportions:

$$ \pi(a \mid s) = \frac{N(s,a)}{\sum_b N(s,b)}. $$

Drawing one bead is the physical sampling step. Its color maps back to a board square, and MENACE plays the corresponding move.

This differs from the Thompson-sampling-style policy in the previous post. There, action probabilities came from uncertainty about values. Unlike a value-based learner, MENACE has no explicit value model. It learns a policy directly by storing beads in its matchboxes, then samples an action from that policy by drawing a bead.

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

Initialization

Before training, every matchbox starts with an untrained policy. In Michie's original setup, each available move in a box starts with the same number of beads. MENACE uses 4 beads per available move for its first move, then 3, 2, and 1 beads for later moves.

At initialization, each matchbox samples uniformly over its own move classes. Later-game boxes start with fewer beads, so reinforcement has a larger effect on them.

Symmetry also reduces the number of matchboxes. If one tic-tac-toe board can be rotated or reflected into another, MENACE treats them as the same state. The same idea applies to moves: on the empty board, all four corners are equivalent, all four sides are equivalent, and the center is unique. The opening matchbox therefore needs only three bead colors: corner, side, and center.

The opening board makes this concrete. Because it is MENACE's first move, the opening matchbox starts with 4 beads for each of the three move classes. That is uniform over move classes, not over the nine physical board squares. When a bead is drawn, MENACE maps the class back to a corresponding square on the current board.

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

Delayed Reinforcement

During the game, MENACE records each bead it selects but does not change the matchboxes. It waits until the episode is over, then updates those beads using the final win, draw, or loss.

That outcome determines how each visited matchbox is updated. MENACE adds or removes beads of the same color as the selected bead:

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

In compact notation, let $O$ be the final episode outcome: win, draw, or loss. For each visited state-action pair $(s_t,a_t)$, MENACE updates the policy weight $N(s_t,a_t)$ by an amount $\Delta(O)$ determined by that outcome:

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

Read $\Delta(O)$ as the reinforcement strength, or the amount by which the policy weight changes. It is $+3$, $+1$, or $-1$ for a win, draw, or loss. A positive value makes the selected move more likely in that state next time; a negative value makes it less likely. This number is part of MENACE's algorithm design, not something learned from the environment.

The loop is:

  1. sample moves from the current matchbox policies,
  2. observe the final outcome $O$,
  3. for every selected move, update its policy weight by $\Delta(O)$.

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

In [5]:

The next figure follows all three moves selected by MENACE in one example episode. The opponent's intervening moves are encoded in the changing board states. The first row shows the matchbox bead counts before the final update, including the board state and chosen square. The middle row shows the bead sampled and kept aside until the final outcome is known. The bottom row shows the same matchbox after delayed credit assignment: MENACE has added or removed beads of the sampled colors.

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 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 MENACE through repeated games. The opening-player MENACE plays 5,000 games against a rotating pool of second-player MENACE agents, a small self-play setup.

We then evaluate the learned opening-player policy against several fixed opponents. 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 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 settle without becoming completely saturated, 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 move classes, 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.

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 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…

How This Relates to Thompson Sampling

It is useful to compare MENACE with Thompson sampling because both can produce stochastic actions, but the randomness comes from different places.

A Thompson-style learner stores uncertainty about a model or value function. It samples one plausible version and then acts greedily in that sampled world:

posterior over values -> sample plausible values -> choose the action with highest sampled value

In that case, action probabilities are induced by uncertainty about values. If an action is often best across posterior samples, it is chosen often.

MENACE stores policy weights directly. It does not keep a posterior over action values, and it does not choose the best action under a sampled value table. It stores bead counts:

bead counts -> action probabilities -> sample action from beads

The final action-selection step looks similar because both methods sample an action. But the probabilities mean different things. In Thompson-style value sampling, they come from uncertain value estimates. In MENACE, they are the learned object itself: updating the beads updates the policy directly.

The two approaches can be summarized like this:

Method What is stored? What is sampled? What the policy probabilities mean
Thompson-style value sampling posterior over action values plausible values, then choose max how often each action is best under sampled values
Induced Bayesian policy posterior over action values action from $P(a \text{ is best})$ posterior probability that each action is best
MENACE bead counts / policy weights action directly from beads learned tendency to play each move

MENACE is closer to direct policy reinforcement than to Bayesian value learning. The learned object is the state-dependent stochastic policy itself.

Summary

MENACE makes policy learning visible in tic-tac-toe:

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

The reward arrives only at the end of the episode. MENACE then applies that final win/draw/loss update to all selected moves that led to the outcome. That is the delayed-credit part.

The second point is what MENACE learns. It does not learn a posterior over values or an environment model of how moves lead to future boards. It learns the policy directly: more beads make an action more likely, while fewer beads make it less likely.

This gives us a useful contrast with the Bayesian bandit policy view from the previous post. MENACE's randomness lives directly in the learned policy, not in sampled posterior values. More broadly, tic-tac-toe has the structure of a Markov decision process: states, actions, transitions to new states, and feedback after an episode. MENACE acts inside that environment, but it does not learn an MDP representation. It learns a state-dependent stochastic 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