mscroggs.co.uk
mscroggs.co.uk

subscribe

# Blog

## Archive

Show me a random blog post
▼ show ▼
2018-04-29

## Building MENACEs for other games

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.
MEME: Machine Educable Morris Engine
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.
COFFIN: COnnect Four Fighting INstrument

### Draughts/Checkers (DOCILE)

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.
DOCILE: Draughts Or Checkers Intelligent Learning Engine
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.
CLAWS: Chess Learning And Winning System
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.
MEGA: Machine Educable Go Appliance
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

A matchbox game learning-machine by Martin Gardner. Scientific American, March 1962. [link]
Solving Nine Men's Morris by Ralph Gasser. Games of No Chance 29, 1996. [link]
Symbolic classification of general two-player games by 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]
Solving the game of Checkers by Jonathan Schaeffer and Robert Lake. Games of No Chance 29, 1996. [link]

### Similar posts

 MENACE MENACE at Manchester Science Festival The Mathematical Games of Martin Gardner Origins of World War I

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

Allowed HTML tags: <br> <a> <small> <b> <i> <s> <sup> <sub> <u> <spoiler> <ul> <ol> <li>
To prove you are not a spam bot, please type "q" then "u" then "i" then "e" then "t" in the box below (case sensitive):
2018-01-05

## Origins of World War I

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

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

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

Allowed HTML tags: <br> <a> <small> <b> <i> <s> <sup> <sub> <u> <spoiler> <ul> <ol> <li>
To prove you are not a spam bot, please type "etogyx" backwards in the box below (case sensitive):
2017-11-14

## MENACE at Manchester Science Festival

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.

### Sunday

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.

### The data

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 The Mathematical Games of Martin Gardner Origins of World War I

Comments in green were written by me. Comments in blue were not written by me.
2018-02-14
On the JavaScript version, MENACE2 (a second version of MENACE which learns in the same way, to play against the original) keeps setting the 6th move as NaN, meaning it cannot function. Is there a fix for this?﻿
Lambert
2017-11-22
what would happen if you loaded the boxes slightly differently. if you started with one bead corresponding to each move in each box. if the bead caused the machine to lose you remove only that bead. if the game draws you leave the bead in play if the bead causes a win you put an extra bead in each of the boxes that led to the win. if the box becomes empty you remove the bead that lead to that result from the box before
Ian
2017-11-17
Hi, I was playing with MENACE, and after a while the page redrew with a Dragon Curves design over the top. MENACE was still working alright but it was difficult to see what I was doing due to the overlay. I did a screen capture of it if you want to see it.
Russ

Allowed HTML tags: <br> <a> <small> <b> <i> <s> <sup> <sub> <u> <spoiler> <ul> <ol> <li>
To prove you are not a spam bot, please type "i" then "g" then "n" then "o" then "r" then "e" in the box below (case sensitive):
2017-03-08

## Dragon curves II

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.
Top: Folding a strip of paper in half four times leads to an order four dragon curve (after rounding the corners). Bottom: A level 10 dragon curve resembling a dragon.
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.
The endpoints of dragon curves of order 1 to 10 with a logarithmic spiral passing through them.
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.
Numbers in base -1+i of ten digits or less plotted on an Argand diagram.
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 MENACE at Manchester Science Festival The Mathematical Games of Martin Gardner MENACE

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

Allowed HTML tags: <br> <a> <small> <b> <i> <s> <sup> <sub> <u> <spoiler> <ul> <ol> <li>
To prove you are not a spam bot, please type "goo" in the box below (case sensitive):
2016-06-05

## Making names in Life

The Game of Life is a cellular automaton invented by John Conway in 1970, and popularised by Martin Gardner.
In Life, cells on a square grid are either alive or dead. It begins at generation 0 with some cells alive and some dead. The cells' aliveness in the following generations are defined by the following rules:
• Any live cell with four or more live neighbours dies of overcrowding.
• Any live cell with one or fewer live neighbours dies of loneliness.
• Any dead cell with exactly three live neighbours comes to life.
Starting positions can be found which lead to all kinds of behaviour: from making gliders to generating prime numbers. The following starting position is one of my favourites:
It looks boring enough, but in the next generation, it will look like this:
If you want to confirm that I'm not lying, I recommend the free Game of Life Software Golly.

### Going backwards

You may be wondering how I designed the starting pattern above. A first, it looks like a difficult task: each cell can be dead or alive, so I need to check every possible combination until I find one. The number of combinations will be $$2^\text{number of cells}$$. This will be a very large number.
There are simplifications that can be made, however. Each of the letters above (ignoring the gs) is in a 3×3 block, surrounded by dead cells. Only the cells in the 5×5 block around this can affect the letter. These 5×5 blocks do no overlap, so can be calculated seperately. I doesn't take too long to try all the possibilities for these 5×5 blocks. The gs were then made by starting with an o and trying adding cells below.

### Can I make my name?

Yes, you can make your name.
I continued the search and found a 5×5 block for each letter. Simply Enter your name in the box below and these will be combined to make a pattern leading to your name!

### Similar posts

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