# Blog

**2018-12-16**

By now, you've probably noticed that I like teaching matchboxes to play noughts and crosses.
Thanks to comments on Hacker News, I discovered that I'm not the only one:
MENACE has appeared in, or inspired, a few works of fiction.

### The Adolescence of P-1

*The Adolescence of P-1*by Thomas J Ryan [1] is the story of Gregory Burgess, a computer programmer who writes a computer program that becomes sentient. P-1, the program in question, then gets a bit murdery as it tries to prevent humans from deactivating it.

The first hint of MENACE in this book comes early on, in chapter 2, when Gregory's friend Mike says to him:

"Because I'm a veritable fount of information. From me you could learn such wonders as the gestation period of an elephant or how to teach a matchbox to win at tic-tac-toe."Taken fromThe Adolescence of P-1by Thomas J Ryan [1], page 27

A few years later, in chapter 4, Gregory is talking to Mike again. Gregory asks:

"... How do you teach a matchbox to play tic-tac toe?""What?""You heard me. I remember you once said you could teach a matchbox. How?""Jesus Christ! Let me think . . . Yeah . . . I remember now. That was an article inScientific Americanquite a few years ago. It was a couple of years old when I mentioned it to you, I think.""How does it work?""Pretty good. Same principal of reward and punishment you use to teach a dog tricks, as I remember. Actually, you get several matchboxes. One for each possible move you might make in a game of tic-tac-toe. You label them appropriately, then you put an equal number of two different coloured beads in each box. The beads correspond to each yes/no decision you can make in a game. When a situation is reached, you grab the box for the move, shake it up, and grab a bead out of it. The bead indicates the move. You make a record of that box and color, and then make the opposing move yourself. You move against the boxes. If the boxes lose the game, you subtract a bead of the color you used from each of the boxes you used. If they win, you add a bead of the appropriate color to the boxes you used. The boxes lose quite a few games, theoretically, and after the bad moves start getting eliminated or statistically reduced to inoperative levels, they start to win. Then they never lose. Something like that. CheckScientific Americanabout four years ago. How is this going to help you?"Taken fromThe Adolescence of P-1by Thomas J Ryan [1], pages 41-42

The article in

*Scientific American*that they're talking about is obviously*A matchbox game learning-machine*by Martin Gardner [2]. Mike, unfortunately, hasn't quite remembered perfectly how MENACE works: rather than having two colours in each box for yes and no, each box actually has a different colour for each possible move that could be made next. But to be fair to Mike, he read the article around two years before this conversation so this error is forgivable.In any case, this error didn't hold Gregory back, as he quickly proceeded to write a program, called P-1 inspired by MENACE.
P-1 was first intended to learn to connect to other computers through their phone connections and take control of their supervisor, but then
Gregory failed to close the code and it spent a few years learning everything it could before contacting Gregory, who was obviously a little
surprised to hear from it.

P-1 has also learnt to fear, and is scared of being deactiviated. With Gregory's help, P-1 moves much of itself to a more secure location.
Without telling Gregory, P-1 also attempts to get control of America's nuclear weapons to obtain its own nuclear deterrent, and starts
using its control over computer systems across America to kill anyone that threatens it.

Apart from a few Literary Review Bad Sex in Fiction Award worthy segments,

*The Adolescence of P-1*is an enjoyable read.### Hide and Seek (1984)

In 1984,

*The Adolescence of P-1*was made into a Canadian TV film called*Hide and Seek*[3]. It doesn't seem to have made it to DVD, but luckily the whole film is on YouTube. About 24 minutes into the film, Gregory explains to Jessica how he made P-1:Gregory: First you end up with random patterns like this. Now there are certain rules: if a cell has one or two neighbours, it reproduces into the next generation. If it has no neighbours, it dies of loneliness. More than two it dies of overcrowding. Press the return key.Jessica: Okay. [pause] And this is how you created P-1?Gregory: Well, basically. I started to change the rules and then I noticed that the patterns looked like computer instructions. So I entered them as a program and it worked.Hide and Seek[3] (1984)

This is a description of a cellular automaton similar to Game of Life, and not a great way to make a machine that learns.
I guess the film's writers have worse memories than Gregory's friend Mike.

In fact, apart from the character names and the murderous machine, the plots of

*The Adolescence of P-1*and*Hide and Seek*don't have much in common.*Hide and Seek*does, however, have a lot of plot elements in common with*WarGames*[4].### WarGames (1983)

In 1983, the film

*WarGames*was released. It is the story of David, a hacker that tries to hack into a video game company's computer, but accidentally hacks into the US governments computer and starts a game of*Global thermonuclear war*. At least David thinks it's a game, but actually the computer has other ideas, and does everything in its power to actually start a nuclear war.During David's quests to find out more about the computer and prevent nuclear war, he learns about its creator, Stephen Falken.
He describes him to his girlfriend, Jennifer:

David: He was into games as well as computers. He designed them so that they could play checkers or poker. Chess.Jennifer: What's so great about that? Everybody's doing that now.David: Oh, no, no. What he did was great! He designed his computer so it could learn from its own mistakes. So they'd be better they next time they played. The system actually learned how to learn. It could teach itself.WarGames[4] (1983)

Although David doesn't explain how the computer learns, he at least states that it does learn, which is more than Gregory managed in

*Hide and Seek*.David's research into Stephen Falken included finding an article called

*Falken's maze: Teaching a machine to learn*in June 1963's issue of Scientific American. This article and Stephen Falken are fictional, but perhaps its appearance in Scientific American is a subtle nod to Martin Gardner and*A matchbox game learning-machine*.*WarGames*was a successful film: it was generally liked by viewers and nominated for three Academy Awards. It seems likely that the creators of

*Hide and Seek*were really trying to make their own version of

*WarGames*, rather than an accurate apatation of

*The Adolescence of P-1*. This perhaps explains the similarities between the plots of the two films.

### Without a Thought

*Without a Thought*by Frank Saberhagen [5] is a short story published in 1963. It appears in a collection of related short stories by Frank Saberhagen called

*Bezerker*.

In the story, Del and his aiyan (a pet a bit like a more intelligent dog; imagine a cross between R2-D2 and Timber) called Newton are in a spaceship fighting against a bezerker. The bezerker has
a mind weapon that pauses all intelligent thought, both human and machine. The weapon has no effect
on Newton as Newton's thought is non-intelligent.

The bezerker challenges Del to a simplified checker game, and says that if Del can play the game while the mind weapon is active, then he
will stop fighting.

After winning the battle, Del explains to his commander how he did it:

But the Commander was watching Del: "You got Newt to play by the following diagrams, I see that. But how could helearnthe game?"Del grinned. "He couldn't, but his toys could. Now wait before you slug me" He called theaiyanto him and took a small box from the animal's hand. The box rattled faintly as he held it up. On the cover was pasted a diagram of on possible position in the simplified checker game, with a different-coloured arrow indicating each possible move of Del's pieces.It took a couple of hundred of these boxes," said Del. "This one was in the group that Newt examined for the fourth move. When he found a box with a diagram matching the position on the board, he picked the box up, pulled out one of these beads from inside, without looking – that was the hardest part to teach him in a hurry, by the way," said Del, demonstrating. "Ah, this one's blue. That means, make the move indicated on the cover by the blue arrow. Now the orange arrow leads to a poor position, see?" Del shook all the beads out of the box into his hand. "No orange beads left; there were six of each colour when we started. But every time Newton drew a bead, he had orders to leave it out of the box until the game was over. Then, if the scoreboard indicated a loss for our side, he went back and threw away all the beads he had used. All the bad moves were gradually eliminated. In a few hours, Newt and his boxes learned to play the game perfectly."Taken fromWithout a Thoughtby Frank Saberhagen [5]

It's a good thing the checkers game was simplified, as otherwise the number of boxes needed to play would be
way too big.

Overall,

*Without a Thought*is a good short story containing an actually correctly explained machine learning algorithm. Good job Fred Saberhagen!#### References

[4]

**. 1993.***WarGames*### Similar posts

Building MENACEs for other games | MENACE | MENACE at Manchester Science Festival | The Mathematical Games of Martin Gardner |

### Comments

Comments in green were written by me. Comments in blue were not written by me.

**2018-04-29**

Two years ago, I built a copy of MENACE (Machine Educable Noughts And Crosses Engine). Since then, it's been to many Royal Institution masterclasses, visted Manchester and met David Attenborough. When I'm not showing them off, the 304 matchboxes that make up my copy of MENACE live in this box:

This box isn't very big, which might lead you to wonder how big MENACE-style machines would be for other games.

### Hexapawn (HER)

In

*A matchbox game learning-machine*by Martin Gardner [1], the game of Hexapawn was introduced. Hexapawn is played on a 3×3 grid, and starts with three pawns facing three pawns.The pieces move like pawns: they may be either moved one square forwards into an empty square, or take another pawn diagonally (the pawns are not allowed to move forwards two spaces on their first move, as they can in chess).
You win if one of your pawns reaches the other end of the board. You lose if none of your pieces can move.

The game was invented by Martin Gardner as a good game for his readers to build a MENACE-like machine to play against, as there are only 19 positions that can face player two, so only 19 matchboxes are needed to make HER (Hexapawn Educable Robot). (HER plays as player two, as if player two plays well they can always win.)

### Nine Men's Morris (MEME)

In Nine Men's Morris, two players first take turns to place pieces on the board, before taking turns to move pieces to adjacent spaces. If three pieces are placed in a row, a player may remove one of the opponent's pieces. It's a bit like Noughts and Crosses, but with a bit more chance of it not ending in a draw.

In

*Solving Nine Men's Morris*by Ralph Gasser [2], the number of possible game states in Nine Men's Morris is given as approximately \(10^{10}\). To build MEME (Machine Educable Morris Engine), you would need this many matchboxes. These boxes would form a sphere with radius 41m: that's approximately the length of two tennis courts.As a nice bonus, if you build MEME, you'll also smash the world record for the largest matchbox collection.

### Connect 4 (COFFIN)

In

*Symbolic classification of general two-player games*by Stefan Edelkamp and Peter Kissmann [3], the number of possible game states in Connect 4 is given as 4,531,985,219,092. The boxes used to make COFFIN (COnnect Four Fighting INstrument) would make a sphere with radius 302m: approximately the height of the Eiffel Tower.In

*Solving the game of Checkers*by Jonathan Schaeffer and Robert Lake [4], the number of possible game states in Draughts is given as approximately \(5\times10^{20}\). The boxes needed to build DOCILE (Draughts Or Checkers Intelligent Learning Engine) would make a sphere with radius 151km.If the centre of DOCILE was in London, some of the boxes would be in Sheffield.

### Chess (CLAWS)

The number of possible board positions in chess is estimated to be around \(10^{43}\). The matchboxes needed to make up CLAWS (Chess Learning And Winning System) would fill a sphere with radius \(4\times10^{12}\)m.

If the Sun was at the centre of CLAWS, you might have to travel past Uranus on your search for the right box.

### Go (MEGA)

The number of possible positions in Go is estimated to be somewhere near \(10^{170}\). To build MEGA (Machine Educable Go Appliance), you're going to need enough matchboxes to make a sphere with radius \(8\times10^{54}\)m.

The observable universe takes up a tiny space at the centre of this sphere. In fact you could fit around \(10^{27}\) copies of the universe side by side along the radius of this sphere.

It's going to take you a long time to look through all those matchboxes to find the right one...

#### References

[3]

**by***Symbolic classification of general two-player games***Stefan Edelkamp and Peter Kissmann**. in Advances in Artificial Intelligence (edited by A.R. Dengel, K. Berns, T.M. Breuel, F. Bomarius, T.R. Roth-Berghofer), 2008. [link][4]

**by***Solving the game of Checkers***Jonathan Schaeffer and Robert Lake**. Games of No Chance 29, 1996. [link]### Similar posts

MENACE | MENACE in fiction | MENACE at Manchester Science Festival | The Mathematical Games of Martin Gardner |

### Comments

Comments in green were written by me. Comments in blue were not written by me.

**2018-11-16**

**Add a Comment**

**2018-01-05**

In 1969, Sid Sackson published his

*magnum opus*:*A Gamut of Games*, a collection of 38 games that can all be played with pen and paper or a pack of cards.One of the best games I've tried so far from the book is James Dunnigan's

*Origins of World War I*. The original version from the book gets you to start by drawing a large table to play on, and during play requires a fair bit of flicking backwards and forwards to check the rules. To make playing easier, I made this handy pdf that contains all the information you need to play the game.### The rules

#### Starting

*Origins of World War I*is a game for five players (although it can be played with 3 or 4 people; details at the end). To play you will need a printed copy of the pdf, a pen or pencil, and a 6-sided dice.

Each player picks one of the five nations along the top of the board: Britain, France, Germany, Russia, or Austria–Hungary.
Once you've picked your countries, you are ready to begin.

#### Taking a turn

The countries take turns in the order Britain, France, Germany, Russia, or Austria–Hungary: the same order the countries are written
across the top and down the side of the board. A player's turn involves two things: (1) adding "political factors";
(2) carrying out a "diplomatic attack".

First the player adds political factors (PFs). On their turn, Britain adds 14 PFs, France adds 12 PFs, Germany adds 16 PFs, Russia adds 10 PFs,
and Austria–Hungary adds 10 PFs. These numbers are shown under the names of the countries on the left hand side of the board. A player
can add at most 5 PFs to each country per turn, although they may add as many PFs as they like to their own country. The number of PFs
a player adds to each country should be written in the boxes in the players column.

For example, Britain may choose to add 5 PFs in Italy, 2 in the Far East and 12 in Britain. This would be added to the board by writing
the relevant numbers in the Italy, Far East and Britain rows of the Britain column.

After adding PFs, a player may choose to carry out a diplomatic attack. If so the player chooses one of the other four players to attack,
and a country in which this attack takes place. Both players must have some PFs in the country where the attack takes place. The dice is rolled.
The outcome of the attack depends on how much the attacker outnumbers the defender and the value rolled: these are shown to the right of the board.
The three possible outcomes are: Attacker Eliminated (AE), which causes the attacker's PFs in this country to be reduced to 0;
Exchange (EX), which causes both players' PFs in this country to be reduced by the same amount so that one player is left with 0;
and Defender Eliminated (DE), wich causes the defender's PFs in this country to be reduced to 0.

For example, Britain may choose to attack Germany in Africa. If Britain and Germany have 10 and 4 PFs in Africa (respectively), then Britain
outnumbers Germany 2 to 1. The dice is rolled.
If a 1 is rolled, the attacker (Britain) is eliminated, leaving Britain on 0 and Germany on 4.
If one of 2-5 is rolled, the players exchange, leaving Britain on 6 and Germany on 0.
If a 6 is rolled, the defender (Germany) is eliminated, leaving Britain on 10 and Germany on 0.

The game ends after each play has played 10 turns. The number of turns may be kept track of by crossing out a number in the Turn Counter
to the right of the board after each round of 5 turns.

### Scoring

If a player has 10 or more PFs in a country, then they have Treaty Rights (TR) with that country. Each player scores point by achieving TR
with other countries. TR are not symmetric: if Russia has TR with Germany, then this does not mean that Germany automatically has TR with Russia.

The number of points scored by a player for obtaining TR with other countries are printed in the boxes on the board. The numbers in brackets
are only scored if the TR are exclusive: ie if no other country also has TR with that country. Additionally, points are awarded to Britain, France and Germany
if the objectives in the boxes at the foot of their columns are satisfied.

For example, Britain scores 3 points if they have TR with Italy, 1 point if they have TR with Greece, 2 points if they have TR with Turkey.
and 4 points if they have exclusive TR with the Far East. Britain also scores 10 points if no other nation has more than 12 points.

### Alliances

During the game, players are encouraged to make deals with other players: for example, Britain may agree to not add PFs in Serbia if
Russia agrees to carry diplomatic attacks against Germany in Bulgaria. Deals can of course be broken by either player later in the game.

Two players may also enter into a more formal alliance, leading to their two nations working together for the rest of the game. These
alliances may not be broken. If two players are allied, then at the end of the game, their scores are added: if this total is higher than the
scores of the other three players combined, then the allies win; if not, then the highest score among the other three wins.

During a game, it is possible for two different alliances to form (these must be between two different pairs of nations: a country cannot form
two alliances, and three countries cannot form a three-way alliance). In this case, a pair of allies wins if their combined score is larger
than the combined score of the other three players. If neither pair of allies scores this high, the unallied player wins.

### Playing with 3 or 4 players

Alliances can be used to play

*Origins of World War I*with fewer than 5 players. To play with four players, an alliance can be formed at the start of the game, with one player playing both nations in the alliance. To play with three players, the game can be started with two alliances already in place.If you've ready this far, then you're now fully prepared to play

*Origins of World War I*, so print the pdf, invite 4 friends over, and have a game...### Similar posts

MENACE in fiction | Building MENACEs for other games | MENACE at Manchester Science Festival | The Mathematical Games of Martin Gardner |

### Comments

Comments in green were written by me. Comments in blue were not written by me.

**Add a Comment**

**2017-11-14**

A few weeks ago, I took the copy of MENACE that I built to Manchester Science Festival, where it played around 300 games against the public while learning to play Noughts and Crosses. The group of us operating MENACE for the weekend included Matt Parker, who made two videos about it. Special thanks go to Matt, plus
Katie Steckles,
Alison Clarke,
Andrew Taylor,
Ashley Frankland,
David Williams,
Paul Taylor,
Sam Headleand,
Trent Burton, and
Zoe Griffiths for helping to operate MENACE for the weekend.

As my original post about MENACE explains in more detail, MENACE is a machine built from 304 matchboxes that learns to play Noughts and Crosses. Each box displays a possible position that the machine can face and contains coloured beads that correspond to the moves it could make. At the end of each game, beads are added or removed depending on the outcome to teach MENACE to play better.

### Saturday

On Saturday, MENACE was set up with 8 beads of each colour in the first move box; 3 of each colour in the second move boxes; 2 of each colour in third move boxes; and 1 of each colour in the fourth move boxes. I had only included one copy of moves that are the same due to symmetry.

The plot below shows the number of beads in MENACE's first box as the day progressed.

Originally, we were planning to let MENACE learn over the course of both days, but it learned more quickly than we had expected on Saturday, so we reset is on Sunday, but set it up slightly differently. On Sunday, MENACE was set up with 4 beads of each colour in the first move box; 3 of each colour in the second move boxes; 2 of each colour in third move boxes; and 1 of each colour in the fourth move boxes. This time, we left all the beads in the boxes and didn't remove any due to symmetry.

The plot below shows the number of beads in MENACE's first box as the day progressed.

You can download the full set of data that we collected over the weekend here. This includes the first two moves and outcomes of all the games over the two days, plus the number of beads in each box at the end of each day. If you do something interesting (or non-interesting) with the data, let me know!

### Similar posts

MENACE | Building MENACEs for other games | MENACE in fiction | The Mathematical Games of Martin Gardner |

### Comments

Comments in green were written by me. Comments in blue were not written by me.

**2017-11-22**

**Add a Comment**

**2017-03-08**

This post appeared in issue 05 of

*Chalkdust*. I strongly recommend reading the rest of*Chalkdust*.Take a long strip of paper. Fold it in half in the same direction a few times. Unfold it and look at the shape the edge of the paper
makes. If you folded the paper \(n\) times, then the edge will make an order \(n\) dragon curve, so called because it faintly resembles a
dragon. Each of the curves shown on the cover of issue 05 of

*Chalkdust*is an order 10 dragon curve.The dragon curves on the cover show that it is possible to tile the entire plane with copies of dragon curves of the same order. If any
readers are looking for an excellent way to tile a bathroom, I recommend getting some dragon curve-shaped tiles made.

An order \(n\) dragon curve can be made by joining two order \(n-1\) dragon curves with a 90° angle between their tails. Therefore, by
taking the cover's tiling of the plane with order 10 dragon curves, we may join them into pairs to get a tiling with order 11 dragon
curves. We could repeat this to get tilings with order 12, 13, and so on... If we were to repeat this

*ad infinitum*we would arrive at the conclusion that an order \(\infty\) dragon curve will cover the entire plane without crossing itself. In other words, an order \(\infty\) dragon curve is a space-filling curve.Like so many other interesting bits of recreational maths, dragon curves were popularised by Martin Gardner in one of his

*Mathematical Games*columns in*Scientific American*. In this column, it was noted that the endpoints of dragon curves of different orders (all starting at the same point) lie on a logarithmic spiral. This can be seen in the diagram below. Although many of their properties have been known for a long time and are well studied, dragon curves continue to appear in new and
interesting places. At last year's Maths Jam conference, Paul Taylor gave a talk about my favourite surprise occurrence of
a dragon.

Normally when we write numbers, we write them in base ten, with the digits in the number representing (from right to left) ones, tens,
hundreds, thousands, etc. Many readers will be familiar with binary numbers (base two), where the powers of two are used in the place of
powers of ten, so the digits represent ones, twos, fours, eights, etc.

In his talk, Paul suggested looking at numbers in base -1+i (where i is the square root of -1; you can find more adventures of i here) using the digits 0 and 1. From right to left, the columns of numbers in this
base have values 1, -1+i, -2i, 2+2i, -4, etc. The first 11 numbers in this base are shown below.

Number in base -1+i | Complex number |

0 | 0 |

1 | 1 |

10 | -1+i |

11 | (-1+i)+(1)=i |

100 | -2i |

101 | (-2i)+(1)=1-2i |

110 | (-2i)+(-1+i)=-1-i |

111 | (-2i)+(-1+i)+(1)=-i |

1000 | 2+2i |

1001 | (2+2i)+(1)=3+2i |

1010 | (2+2i)+(-1+i)=1+3i |

Complex numbers are often drawn on an Argand diagram: the real part of the number is plotted on the horizontal axis and the imaginary part
on the vertical axis. The diagram to the left shows the numbers of ten digits or less in base -1+i on an Argand diagram. The points form
an order 10 dragon curve! In fact, plotting numbers of \(n\) digits or less will draw an order \(n\) dragon curve.

Brilliantly, we may now use known properties of dragon curves to discover properties of base -1+i. A level \(\infty\) dragon curve covers
the entire plane without intersecting itself: therefore every Gaussian integer (a number of the form \(a+\text{i} b\) where \(a\) and
\(b\) are integers) has a unique representation in base -1+i. The endpoints of dragon curves lie on a logarithmic spiral: therefore
numbers of the form \((-1+\text{i})^n\), where \(n\) is an integer, lie on a logarithmic spiral in the complex plane.

If you'd like to play with some dragon curves, you can download the Python code used
to make the pictures here.

### Similar posts

Dragon curves | Harriss and other spirals | MENACE at Manchester Science Festival | The Mathematical Games of Martin Gardner |

### Comments

Comments in green were written by me. Comments in blue were not written by me.

**Add a Comment**

Add a Comment