View source for Matchbox Educable Noughts and Crosses Engine

{{short description|Mechanical computer made of matchboxes}}
[[File:Mscroggs-MENACE-cropped.jpg|350px|thumb|A recreation of MENACE built in 2015|alt=MENACE recreation]]
The '''Matchbox Educable Noughts and Crosses Engine''' (sometimes called the '''Machine Educable Noughts and Crosses Engine''' or '''MENACE''') was a [[Mechanical computer|mechanical computer]] made from 304 matchboxes designed and built by [[Artificial intelligence|artificial intelligence]] researcher [[Biography:Donald Michie|Donald Michie]] in 1961. It was designed to play human opponents in games of noughts and crosses (tic-tac-toe) by returning a move for any given state of play and to refine its strategy through [[Reinforcement learning|reinforcement learning]].

Michie did not have a computer readily available, so he worked around this restriction by building it out of matchboxes. The matchboxes used by Michie each represented a single possible layout of a noughts and crosses grid. When the computer first played, it would randomly choose moves based on the current layout. As it played more games, through a reinforcement loop, it disqualified strategies that led to losing games, and supplemented strategies that led to winning games. Michie held a tournament against MENACE in 1961, wherein he experimented with different openings.

Following MENACE's maiden tournament against Michie, it demonstrated successful artificial intelligence in its strategy. Michie's essays on MENACE's weight initialisation and the BOXES algorithm used by MENACE became popular in the field of computer science research. Michie was honoured for his contribution to machine learning research, and was twice commissioned to program a MENACE simulation on an actual computer.

== Origin ==
[[File:Donald Michie 1986.jpg|275px|thumb|Donald Michie, 1986|alt=Donald Michie in 1986]]
[[Biography:Donald Michie|Donald Michie]] (1923–2007) had been on the team decrypting the German [[Engineering:Lorenz cipher|Tunny Code]] during [[Social:World War II|World War II]].<ref>{{Cite journal|last=Boden|first=Margaret|date=2007-08-15|title=Donald Michie (1923–2007)|url=https://www.nature.com/articles/448765a|journal=Nature|language=en|volume=448|issue=7155|pages=765|doi=10.1038/448765a|pmid=17700692|s2cid=5239830|issn=1476-4687}}</ref> Fifteen years later, he wanted to further display his mathematical and computational prowess with an early [[Convolutional neural network|convolutional neural network]]. Since computer equipment was not obtainable for such uses,<ref name=":9" /> and Michie did not have a computer readily available,<ref name=":9">{{Cite web|last=Wright|first=Matt|date=2020-03-31|title=Donald Michie: The AI pioneer who tested his computer program with a matchbox and some beads|url=https://scroll.in/article/955960/donald-michie-the-ai-pioneer-who-tested-his-computer-program-with-a-matchbox-and-some-beads|url-status=live|access-date=18 October 2020|website=Scroll.in|language=en-US|archive-date=20 October 2020|archive-url=https://web.archive.org/web/20201020023848/https://scroll.in/article/955960/donald-michie-the-ai-pioneer-who-tested-his-computer-program-with-a-matchbox-and-some-beads}}</ref> he decided to display and demonstrate artificial intelligence in a more esoteric format and constructed a functional [[Mechanical computer|mechanical computer]] out of matchboxes and beads.<ref name=":1">{{Cite web |title=Menace: the Machine Educable Noughts And Crosses Engine |url=http://chalkdustmagazine.com/features/menace-machine-educable-noughts-crosses-engine/ |date=13 March 2016 |website=Chalkdust |language=en-GB |access-date=17 May 2020 |last=Child |first=Oliver |archive-date=12 May 2020 |archive-url=https://web.archive.org/web/20200512131724/http://chalkdustmagazine.com/features/menace-machine-educable-noughts-crosses-engine/ |url-status=live }}</ref><ref name=":2" />

MENACE was constructed as the result of a bet with a computer science colleague who postulated that such a machine was impossible.<ref>{{Cite news |date=9 July 2007 |title=Daily Telegraph obituary for Donald Michie |work=The Daily Telegraph |url=https://www.telegraph.co.uk/news/obituaries/1556846/Professor-Donald-Michie.html |access-date=2021-05-25 |archive-date=11 June 2020 |archive-url=https://web.archive.org/web/20200611200812/https://www.telegraph.co.uk/news/obituaries/1556846/Professor-Donald-Michie.html |url-status=live }}</ref> Michie undertook the task of collecting and defining each matchbox as a "fun project", later turned into a demonstration tool.<ref name=":6">{{Cite book |last=Donald |first=Michie |title=BOXES: An experiment in adaptive control |publisher=University of Edinburgh |url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.474.2430&rep=rep1&type=pdf |citeseerx=10.1.1.474.2430 |page=137 |year=1968 |access-date=31 July 2020 |archive-date=26 June 2020 |archive-url=https://web.archive.org/web/20200626152630/http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.474.2430&rep=rep1&type=pdf |url-status=live }}</ref> Michie completed his essay on MENACE in 1963,<ref name=":2" /> "Experiments on the mechanization of game-learning", as well as his essay on the BOXES Algorithm, written with R. A. Chambers<ref name=":6" /> and had built up an AI research unit in Hope Park Square, [[Place:Edinburgh|Edinburgh]], Scotland.<ref name=":7" />

MENACE learned by playing increasing matches of noughts and crosses. Each time, it would eliminate a losing strategy by the human player confiscating the beads that corresponded to each move.<ref name=":2" /> It reinforced winning strategies by making the moves more likely, by supplying extra beads.<ref name=":11">{{Cite journal|last1=Hardingham|first1=Samantha|last2=Frazer|first2=John|last3=Jones|first3=Emma Letizia|date=2012|title=John Frazer in conversation with Samantha Hardingham|url=https://www.jstor.org/stable/41762307|journal=AA Files|issue=64|pages=69–77|jstor=41762307|issn=0261-6823}}</ref> This was one of the earliest versions of the [[Reinforcement learning|Reinforcement Loop]], the schematic algorithm of looping the algorithm, dropping unsuccessful strategies until only the winning ones remain.<ref name=":2" /> This model starts as completely random, and gradually learns.<ref>{{Cite web|date=2018-10-05|title=How 300 Matchboxes Learned to Play Tic-Tac-Toe Using MENACE|url=https://opendatascience.com/menace-donald-michie-tic-tac-toe-machine-learning/|access-date=2021-05-15|website=Open Data Science|language=en-US|last=Wylie|first=Caspar|archive-date=15 May 2021|archive-url=https://web.archive.org/web/20210515182903/https://opendatascience.com/menace-donald-michie-tic-tac-toe-machine-learning/|url-status=live}}</ref>

==Composition==
MENACE was made from 304 matchboxes glued together in an arrangement similar to a chest of drawers.<ref name="sci">The Science Book, Second Edition, Dorling Kindersley Ltd., 2015, pg. 288</ref> Each box had a code number, which was keyed into a chart. This chart had drawings of [[Tic-tac-toe|tic-tac-toe]] game grids with various configurations of X's, O's and empty squares,<ref name=":2" /> corresponding to all possible permutations a game could go through as it progressed.<ref name=":4">{{Cite journal |last=Gardner |first=Martin |title=Mathematical Games |year=1962 |journal=Scientific American |volume=206 |issue=3 |pages=138–154 |doi=10.1038/scientificamerican0362-138 |jstor=24937263 |bibcode=1962SciAm.206c.138G}}</ref> After removing duplicate arrangements (ones that were simply rotations or mirror images of other configurations), MENACE used 304 permutations in its chart and thus that many matchboxes.<ref name=":0" />

Each individual matchbox tray contained a collection of coloured beads.<ref>De Raedt, Luc. "[https://core.ac.uk/download/pdf/80808274.pdf The Machine Learning Revolution in AI]". [https://web.archive.org/web/20200612080944/https://core.ac.uk/download/pdf/80808274.pdf Archived] from the original on 12 June 2020.</ref> Each colour 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. Additionally, at the front of the tray were two extra pieces of card in a "V" shape,<ref name="sci" /> the point of the "V" pointing at the front of the matchbox.<ref name=":4" /> Michie and his artificial intelligence team called MENACE's algorithm "Boxes",<ref name=":7">{{Cite web |last=Muggleton |first=Stephen |date=10 July 2007 |title=Obituary for Donald Michie, an article in The Guardian from 2007. |url=https://www.theguardian.com/science/2007/jul/10/uk.obituaries1 |website=The Guardian |access-date=2021-05-22 |archive-date=1 October 2020 |archive-url=https://web.archive.org/web/20201001090905/https://www.theguardian.com/science/2007/jul/10/uk.obituaries1 |url-status=live }}</ref> 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|algorithm]] in relation to the game.<ref>{{Cite book |last=Russel |first=David |title= Extract from "The BOXES Methodology". (Chapter 2. The Game Metaphor) |publisher=Springer Professional |year=2012 |isbn=978-1849965279 |location=London }}</ref>

==Operation==
[[File:MENACE_example.svg|thumb|An example game played by MENACE (O) and a human (X) using beads of Michie's original colours &ndash; {{nowrap|as MENACE lost}} this game, all the beads shown are removed from their respective boxes<ref>http://chalkdustmagazine.com/features/menace-machine-educable-noughts-crosses-engine</ref><ref>http://people.csail.mit.edu/brooks/idocs/matchbox.pdf</ref>]]
MENACE played first, as O, since all matchboxes represented permutations only relevant to the "X" player.<ref name=":0" /><ref name=":10">{{Cite web |url=https://we-make-money-not-art.com/menace-2-an-artificial-intelligence-made-of-wooden-drawers-and-coloured-beads/ |title=MENACE 2, an artificial intelligence made of wooden drawers and coloured beads |date=12 April 2016 |access-date=2021-05-22 |archive-date=12 July 2020 |archive-url=https://web.archive.org/web/20200712014446/https://we-make-money-not-art.com/menace-2-an-artificial-intelligence-made-of-wooden-drawers-and-coloured-beads/ |url-status=live }}</ref> To retrieve MENACE's choice of move, the opponent or operator located the matchbox that matched the current game state, or a rotation or mirror image of it. For example, at the start of a game, this would be the matchbox for an empty grid. The tray would be removed and lightly shaken so as to move the beads around.<ref name=":2" /> 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.<ref name=":2" /> Its colour 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 current grid, the O would be placed on that square. Then the player performed their move, the new state was located, a new move selected, and so on, until the game was finished.<ref name=":0" />

When the game had finished, the human player observed the game's outcome. As a game was played, each matchbox that was used for MENACE's turn had its tray returned to it ajar, and the bead used kept aside, so that MENACE's choice of moves and the game states they belonged to were recorded. Michie described his reinforcement system with "reward" and "punishment". Once the game was finished, if MENACE had won, it would then receive a "reward" for its victory. The removed beads showed the sequence of the winning moves.<ref name=":10" /> These were returned to their respective trays, easily identifiable since they were slightly open, as well as three bonus beads of the same colour.<ref name=":4" /> In this way, in future games MENACE would become more likely to repeat those winning moves, reinforcing winning strategies. If it lost, the removed beads were not returned, "punishing" MENACE, and meaning that in future it would be less likely, and eventually incapable if that colour of bead became absent, to repeat the moves that cause a loss.<ref name=":1" /><ref name=":11" /> If the game was a draw, one additional bead was added to each box.<ref name=":4" />

==Results in practice==
===Optimal strategy===
[[File:Tictactoe-X.svg|thumb|Optimal strategy for player X if starting in a corner. In each grid, the shaded red X denotes the optimal move, and the location of O's next move gives the next subgrid to examine.|alt=Optimal noughts and crosses strategy]]
Noughts and crosses has a well-known optimal strategy.<ref name=":5">{{Cite web|last=Cappiell|first=Emily|date=2020-11-30|title=How to Win Tic-Tac-Toe: The Strategies You Need to Master|url=https://www.rd.com/article/how-to-win-tic-tac-toe/|access-date=2021-02-06|website=Reader's Digest|language=en-US|archive-date=22 January 2021|archive-url=https://web.archive.org/web/20210122024352/https://www.rd.com/article/how-to-win-tic-tac-toe/|url-status=live}}</ref> A player must place their symbol in a way that blocks the other player from achieving any rows while simultaneously making a row themself. However, if both players use this strategy, the game always ends in a draw.<ref name=":5" /> If the human player is familiar with the optimal strategy, and MENACE can quickly learn it, then the games will eventually only end in draws. The likelihood of the computer winning increases quickly when the computer plays against a random-playing opponent.<ref name=":1" />

When playing against a player using optimal strategy, the odds of a draw grow to 100%. In Donald Michie's official tournament against MENACE in 1961<ref name=":2" /> he used optimal strategy, and he and the computer began to draw consistently after twenty games. Michie's tournament<ref name=":3">Trial and Error, Michie Donald, Penguin Science Surveys 1961 Vol 2</ref> had the following milestones: Michie began by consistently opening with "Variant 0", the middle square. At 15 games, MENACE abandoned all non-corner openings. At just over 20, Michie switched to consistently using "Variant 1", the bottom-right square. At 60, he returned to Variant 0. As he neared 80 games, he moved to "Variant 2", the top-middle. At 110, he switched to "Variant 3", the top right. At 135, he switched to "Variant 4", middle-right. At 190, he returned to Variant 1, and at 210, he returned to Variant 0.

The trend in changes of beads in the "2" boxes runs:<ref name=":3" />
{| {{Table|sort|class=floatcenter}}
! 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 ===
[[File:Michie-MENACE-graph.png|thumb|A scatter graph showing the results of Donald Michie's games against MENACE|alt=Scatter graph of Michie's tournament.]]
Depending on the strategy employed by the human player, MENACE produces a different trend on [[Scatter plot|scatter graphs]] of wins.<ref name=":2" /> Using a random turn from the human player results in an almost-perfect positive trend. Playing the optimal strategy returns a slightly slower increase.<ref name=":1" /> The reinforcement does not create a perfect standard of wins; the algorithm will draw random uncertain conclusions each time. After the ''j''-th round, the correlation of near-perfect play runs:

<math>{1-D \over D-D^{(j+2)}}\sum_{i=0}^j D^{(ji+1)} V_i</math>

Where ''V<sub>i</sub>'' is the outcome (+1 is win, 0 is draw and -1 is loss) and ''D'' is the decay factor (average of past values of wins and losses). Below, ''M<sub>n</sub>'' is the multiplier for the ''n''-th round of the game.<ref name=":2" />
{| class="wikitable"
|+
!Outcome
!Reinforcement
|-
|Won
|<math>R_n=M_n^{-\mu+1}</math>
|-
|Draw
|<math>R_n=M_n^{-\mu}</math>
|-
|Lost
|<math>R_n=M_n^{-\mu-1}</math>
|}

==Legacy==
Donald Michie's MENACE proved that a computer could learn from failure and success to become good at a task.<ref name=":10" /> It 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 are then selected at random, creates a learning behaviour similar to weight initialisation in modern artificial neural networks.<ref>{{Cite journal |last1=Yam |first1=Jim Y. F. |last2=Chow |first2=Tommy W. S. |date=1 January 2000 |title=A weight initialization method for improving training speed in feedforward neural network |url=http://www.sciencedirect.com/science/article/pii/S0925231299001277 |journal=Neurocomputing |language=en |volume=30 |issue=1 |pages=219–232 |doi=10.1016/S0925-2312(99)00127-7 |issn=0925-2312}}</ref> In 1968, Donald Michie and R.A Chambers made another BOXES-based algorithm called GLEE (Game Learning Expectimaxing Engine) which had to learn how to balance a pole on a cart.<ref>{{Cite book |last1=Sutton |first1=Richard S. |url=https://books.google.com/books?id=6DKPtQEACAAJ |title=Reinforcement Learning: An Introduction |last2=Barto |first2=Andrew G. |year= 2018 |publisher=MIT Press |isbn=978-0262039246 |language=en|page=753}}</ref>

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 [[Company:IBM|IBM]] Computer for use at [[Organization:Stanford University|Stanford University]].<ref>{{Cite news |date=8 July 2007 |title=Professor Donald Michie |journal=The Daily Telegraph |language=en-GB |url=https://www.telegraph.co.uk/news/obituaries/1556846/Professor-Donald-Michie.html |access-date=11 June 2020 |issn=0307-1235 |archive-date=11 June 2020 |archive-url=https://web.archive.org/web/20200611200812/https://www.telegraph.co.uk/news/obituaries/1556846/Professor-Donald-Michie.html |url-status=live }}</ref> Michie created a simulation program of MENACE on a Pegasus 2 computer with the aid of D. Martin.<ref name=":2">{{Cite web |title=Experiments on the mechanization of Game Learning Part 1. Characterization of the model and its parameters |url=https://www.gwern.net/docs/rl/1963-michie.pdf |language=en |access-date=1 June 2020 |last=Michie |first=Donald |archive-date=21 November 2019 |archive-url=https://web.archive.org/web/20191121220626/https://www.gwern.net/docs/rl/1963-michie.pdf |url-status=live }}</ref> There have been multiple recreations of MENACE in more recent years, both in its original physical form and as a computer program.<ref name=":0">{{Cite web|url=https://warwick.ac.uk/fac/sci/dcs/research/em/publications/web-em/10/cs405_-_1362452_-_menaceem.pdf|title= Matchbox Educable Noughts And Crosses Engine In Empirical Modelling|access-date=2021-05-22|publisher=University of Warwick}}</ref> Its algorithm was later converged into Christopher Watkin's Q-Learning algorithm.<ref>{{Cite book |last=Scaruffi |first=Piero |title=Intelligence is not Artificial – ''Why the Singularity is not coming any time soon and other Meditations on the Post-Human Condition and the Future of Intelligence'' |year=2014 |isbn=978-0976553199 |page=27|publisher=Omniware}}</ref> Although not as a functional computer, in examples of demonstration, MENACE has been used as a teaching aid for various neural network classes,<ref>{{Cite web |last=Zhao |first=Yibo |date=1 December 2013 |title=Machine Educable Engine on Noughts And Crosses in Modelling Study |url=https://warwick.ac.uk/fac/sci/dcs/research/em/teaching/cs405/web-em-10-abstracts/yibo/ |publisher=University of Warwick |access-date=2021-05-22 |archive-date=11 June 2020 |archive-url=https://web.archive.org/web/20200611193844/https://warwick.ac.uk/fac/sci/dcs/research/em/teaching/cs405/web-em-10-abstracts/yibo/ |url-status=live }}</ref><ref>{{Cite web |title=AI Topics.. Tic-Tac-Toe strategy in Computational Thinking, Introduction, MENACE |url=https://aitopics.org/class/Industry/Leisure%20&%20Entertainment/Games/Tic-Tac-Toe |access-date=2021-05-22 |archive-date=8 February 2021 |archive-url=https://web.archive.org/web/20210208045635/https://aitopics.org/class/Industry/Leisure%20%26%20Entertainment/Games/Tic-Tac-Toe |url-status=live }}</ref><ref>Ute Schmid – "Interactive Learning with Mutual Explanations" (How Humans and Machine Learning Systems can Profit From Each Other) – University of Bamberg, Germany<nowiki/> [https://www.universiteitleiden.nl/binaries/content/assets/science/dso/ute-schmid_mutualexplleiden-1.pdf Link]</ref> including a public demonstration from University College London Researcher Matthew Scroggs.<ref>{{Cite AV media |url=https://www.youtube.com/watch?v=hK25eXRaBdc |title=‘Building a MENACE machine’, Matthew Scroggs, University College London |date=3 July 2017 |last=Scroggs |first=Matthew |type=Youtube |language=en}}</ref><ref>{{Cite web|date=11 November 2019|title=Inspiring the Next Generation of Computer Scientists {{!}} King's Worcester|url=https://www.ksw.org.uk/inspiring-the-next-generation-of-computer-scientists/|access-date=12 June 2020|website=King's Worcester|language=en-GB|archive-date=12 June 2020|archive-url=https://web.archive.org/web/20200612083443/https://www.ksw.org.uk/inspiring-the-next-generation-of-computer-scientists/|url-status=live}}</ref> A copy of MENACE built by Scroggs was featured in the 2019 Royal Institution Christmas Lectures,<ref>{{Cite web |last=Scroggs |first=Matthew |date=27 December 2019 |title=Visualising MENACE's learning |url=https://www.mscroggs.co.uk/blog/71 |website=mscroggs.co.uk |access-date=30 July 2020 |archive-date=11 July 2020 |archive-url=https://web.archive.org/web/20200711112050/http://www.mscroggs.co.uk/blog/71 |url-status=live }}</ref><ref>{{Cite tweet |user=rsi_science |number=1210666302890754049 |access-date=14 October 2020 |title=Menace Machine-creator pitched up with his 304 matchboxes to explain how he made it. |via=Twitter |language=en |date=27 December 2019}}</ref> and in a 2023 episode of QI XL.<ref>{{Cite web|date=6 January 2023|title=QI XL Series T, Ticks Tax Toes|url=https://www.bbc.co.uk/programmes/m001grhs|website=BBC|access-date=4 February 2023}}</ref>

== See also ==
* Hexapawn

== References ==<!--- See Wikipedia:Footnotes on how to create references using<ref></ref> tags which will then appear here automatically -->
{{Reflist}}

== Sources ==
* {{citation |last1=Michie |first1=D. |last2=Chambers |first2=R. A. |chapter=BOXES: An Experiment in Adaptive Control |title=Machine Intelligence |publisher=Oliver and Boyd |place=Edinburgh, UK |year=1968 |s2cid=18229198 |via=Semantic Scholar}}, Michie and R. A Chambers' paper on the AI implications of BOXES and MENACE.
* {{citation |last=Russell |first=David W.|year=2012 |title=The BOXES Methodology: Black Box Dynamic Control |publisher=Springer London |isbn=978-1849965286}}, a book on the "Boxes" algorithm employed by MENACE.

== External links ==
<!-- Use the format: * [http://www.example.com/ example.com] -->
* [https://www.mscroggs.co.uk/menace/ Online simulation of MENACE]

<!--- Categories --->
[[Category:Machine learning]]
[[Category:Mechanical computers]]

{{Sourceattribution|Matchbox Educable Noughts and Crosses Engine}}