Matchbox Educable Noughts And Crosses Engine

The Matchbox Educable Noughts And Crosses Engine (sometimes incorrectly referred to as the Machine Educable Noughts and Crosses Engine), shortened as MENACE, was an analogue computer made up of 304 matchboxes designed and built by Donald Michie in the 1960's. It was designed to play against human opponents in games of Tic-tac-toe, by returning a move for any given state of play, and would "learn" to refine its strategy over time through reinforcement learning.
== Origin ==
Donald Michie had been on the team decrypting the German Tunny Code during World War II. Fifteen years later, he wanted to further display his mathematical and computational prowess with an early Convolutional Neural Network. Since computer equipment was not available for uses such as thesehttp://www.cdpa.co.uk/UoP/HoC/Lectures/HoC_07b.PDF, he decided to display and demonstrate Artificial Intelligence in a more esoteric format, and constructed a working model out of matchboxes and beads.
MENACE was reportedly constructed as the result of a bet with a fellow computer science colleague, who postulated that such a machine was impossible.
==Composition==
MENACE itself was made up of 304 matchboxes glued together in an arrangement similar to a chest-of-drawersThe Science Book, Second Edition, Dorling Kindersley Ltd., 2015, pg. 288. Each box had a code number, which was keyed into a chart. This chart had drawings of Tic-tac-toe game grids with differing configurations of X's, O's and empty squares, all corresponding to possible permutations a game could go through as it progressed. After removing duplicate arrangements (ones that were simply rotations or mirror-images of other configurations) MENACE used 304 permutations in its chart, and that many matchboxes.
Each individual matchbox tray contained a collection of colored beads.core.ac.uk - The Machine Learning Revolution in AI by Luc De Raedt
https://core.ac.uk/download/pdf/80808274.pdf Each color represented a move on a square on the game grid, and so matchboxes with arrangements where positions on the grid were already taken would not have beads for that position.As well as this, at the front of the tray were two extra pieces of card in a "V" shape, the point of the "V" pointing at the front of the matchbox. Michie and his artificial intelligence team called MENACE's algorithm "Boxes", after the apparatus used for the machine. The first stage "Boxes" operated in five phases, each setting a definition and a precedent for the rules of the algorithm in relation to the game.
==Operation==
===Playing a Game===
MENACE played firsthttps://we-make-money-not-art.com/menace-2-an-artificial-intelligence-madegetgetting ridting rid-of-wooden-drawers-and-coloured-beads/, as O, since all matchboxes represented permutations that only one playing as O could ever see.
To retrieve MENACE's choice of move, the opponent or operator first found the matchbox that matched the current game state, or a rotation/mirror-image of it. For example, at the start of a game, this would be the matchbox for an entirely empty grid. The tray would be removed, and lightly shaken so as to move the beads around. Then, the bead that had rolled into the point of the "V" shape at the front of the tray was the move MENACE had chosen to make. It's color was then used as the position to play on, and after accounting for any rotations or flips needed based on the chosen matchbox configuration's relation to the actual grid, the O would be placed on that square. Then the player performed their move, the new state was read, a new move selected, and so on, until a win, loss or draw for MENACE.
===Finishing a game===
When the game had finished, the human player/operator observed the game's outcome, which would be one of three possibilities:
*The Human Player had won.
*The Computer Player had won.
*It was a draw.
As a game was played, every matchbox that was used for MENACE's turn had its tray returned to it slightly open, and the bead used kept aside, so that MENACE's choice of moves and the game states they belonged to were recorded. Once the game was done, if MENACE had won, it would then receive a "reward" for its victory. The removed beads showed the sequence of the winning moves. These were returned to their respective trays, easily identified by the open tray, as well as three bonus beads of the same color. In this way, in future games, MENACE would be much more likely to repeat those winning moves, reinforcing a winning strategy. If it lost, the removed beads were not returned, "punishing" MENACE, and meaning that in future it would be less likely, or incapable, if that color of bead became absent, to repeat the moves that caused a loss.
==Results in practice==
===Optimal strategy===
Noughts and Crosses has a well-known optimal strategy. It involves strategic placing in order to block the other player while simultaneously taking the win.
However, in an ordinary game of Noughts and Crosses, if both players lead this strategy, it will always end in a draw. This creates a stagnation. If the human player is familiar with the optimal strategy, and the MENACE can quickly learn it, then the games will eventually only end in draws. When the computer begins, it will slowly eschew the odds:
Amount of turns to win	Combinations	Probability
5 Turns 	1440 	0.6%
6 Turns 	5328 	2.1%
7 Turns 	47952 	18.8%
8 Turns 	72576 	28.4%
9 Turns 	81792 	32.1%
Draw 	46080 	18.1%
But to a player playing with the optimal strategy against the computer, the odds of draw change to 100%. In Donald Michie's official tournament against MENACE, he used optimal strategy, and he and the computer began to draw consistently after twenty games. Playing the optimal strategy will return a slightly slower increase. From Michie's tournamentTrial and Error , Michie Donald , Penguin Science Surveys 1961 Vol 2, we observe the following milestones:
* Michie began by consistently opening with "Variant 0":
* At 15 games, MENACE abandoned all non-corner openings.
* At just over 20, Michie switched to consistently using "Variant 1":
* At 60, he returned to Variant 0.
* In the late 70s, he moved to "Variant 2":
* At 110, he switched to "Variant 3":
* At 135, he switched to "Variant 4":
* At 190, he returned to Variant 1.
* At 210, he returned to Variant 0.
The trend in changes of beads in the "2" boxes runs:
Variant 	Match number	Bead change in "2" box
Variant 0	0 	0
Variant 1	20 	-5
Variant 0	60 	5
Variant 2	70 	10
Variant 3	110 	20
Variant 4	135 	25
Variant 1	190 	100
Variant 0	210 	120
=== Correlation ===
Depending on the strategy employed by the human player, MENACE will produce a different trend on scatter graphs of wins. Using a random turn from the human player will result in an almost perfect positive trend. Playing the optimal strategy will return a slightly slower increase.
==Variations==
As aforementioned, MENACE runs on a reinforcement punishment algorithm, removing beads that create a losing strategy and duplicating those that help it to draw and win. However, a couple of proposed variations of MENACE employ other systems.
=== Punish draws ===
In the default punishment system, the computer is rewarded for draws. In this system, draws are punished by removing beads. The result is similar to default, but displays a more ruthless form of cognitive AI training.
=== Increase starting beads ===
Michie suggested this as a way to increase MENACE's capacity for learning strategy in a different way. This variation returns a very similar graph to default settings.
==Legacy==
Donald Michie's MENACE proved that a computer could "learn" from failure and success in order to become good at a task. It also used what would become core principles within the field of machine learning before they had been properly theorised. For example, the combination of how MENACE starts with equal numbers of types of beads in each matchbox, and how these will then be selected at random, creates a learning behavior similar to weight initialization in modern artificial neural networks. MENACE's idea of a self-reinforcing algorithm has now been replicated countless times, and changed the face of Computational thinking.
===Computer simulation===
After the resounding reception of MENACE, Michie was invited to the US Office of Naval Research, where he was commissioned to build a "Boxes"-running program for an IBM Personal Computer, for use at Stanford University. Michie went on to create a simulation program of MENACE on a Pegasus 2 computer with the aid of D. Martin
===Modern recreations===
There have been multiple recreations of MENACE in more recent years, both in its original, physical form and as a computer programhttps://warwick.ac.uk/fac/sci/dcs/research/em/publications/web-em/10/cs405_-_1362452_-_menaceem.pdf. Although not as a functional computer, in examples of demonstration, MENACE has been used as a teaching aidUte Schmid - "Interactive Learning with Mutual Explanations" (How Humans and Machine Learning Systems can Profit From Each Other) - University of Bamberg, Germanyhttps://www.universiteitleiden.nl/binaries/content/assets/science/dso/ute-schmid_mutualexplleiden-1.pdf for various prestigious Neural Network classes, including a well-publicised demonstration from Cambridge Researcher Matthew Scroggs.Matthew Scroggs Lecture on MENACE - https://www.youtube.com/watch?v=hK25eXRaBdc
==In the media==
<youtube width="300" height="300">R9c-_neaxeU</youtube>  
<youtube width="300" height="300">sw7UAZNgGg8</youtube>  
<youtube width="300" height="300">lk_G7FkqAgw</youtube>  
<youtube width="300" height="300">hK25eXRaBdc</youtube>
== References ==
== External links ==
* [Online simulation of MENACE
* Menace: the Machine Educable Noughts And Crosses Engine
* mscroggs.co.uk Blog: MENACE - Matthew Scroggs
* mscroggs/MENACE: Machine Educable Noughts And ... - GitHub
* Matchbox Educable Noughts And Crosses Engine (MENACE) in C++
* Teaching 304 Matchboxes To Beat You At Tic-Tac-Toe - Bell
* Matchbox Tic-Tac-Toe - Classic Computer Magazine
Category:Analog computers
Category:Matchboxes
Category:1960s software
Category:Computer-related introductions in 1960
Category:Tic-tac-toe
Category:Reinforcement learning
Category:Machine learning
Category:Artificial neural networks
Category:Convolutional neural networks