Jump to content

Matchbox Educable Noughts and Crosses Engine

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by JuPitEer (talk | contribs) at 05:57, 30 July 2020. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Michie teaching a group of students at Turing Institute.

The Matchbox Educable Noughts and Crosses Engine (stylised as the Machine Educable Noughts And Crosses Engine) or MENACE was an analogue computer made up of 304 matchboxes designed and built by Donald Michie in the 1960s. It was designed to play human opponents in games of tic-tac-toe by returning a move for any given state of play and to refine its strategy through reinforcement learning.[1]

Origin

Donald Michie had been on the team decrypting the German Tunny Code during World War II.[2] 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 such uses,[3] he decided to display and demonstrate artificial intelligence in a more esoteric format and constructed a working model out of matchboxes and beads.[1][4]

MENACE was reportedly constructed as the result of a bet with a computer science colleague who postulated that such a machine was impossible.[5]

Composition

MENACE was made up of 304 matchboxes glued together in an arrangement similar to a chest of drawers.[6] Each box had a code number, which was keyed into a chart. This chart had drawings of tic-tac-toe game grids with various configurations of X's, O's and empty squares,[4] corresponding to all 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.[7]

Each individual matchbox tray contained a collection of coloured beads.[8] 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. Additionally, at the front of the tray were two extra pieces of card in a "V" shape,[6] the point of the "V" pointing at the front of the matchbox. Michie and his artificial intelligence team called MENACE's algorithm "Boxes",[9] 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.[10]

Operation

Playing a game

MENACE played first,[11][7] 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 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.[4] 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.[4] Its 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 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.[7]

Finishing a game

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 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.[12] These were returned to their respective trays, easily identifiable since they were slightly open, as well as three bonus beads of the same colour. 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.[13]

Results in practice

Optimal strategy

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.

Noughts and Crosses has a well-known optimal strategy.[14] It involves strategic placing to block the other player while simultaneously taking the win. However, if both players use this strategy, it always ends in a draw.[15] 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 and plays a random-playing opponent, it has the odds of the computer winning turn quickly in its favour.[16]

When playing against a player using optimal strategy, the odds of a draw grow to 100%. In Donald Michie's official tournament against MENACE, (1961)[4] he used optimal strategy, and he and the computer began to draw consistently after twenty games. Michie's tournament[17] had the following milestones:

  • Michie began by consistently opening with "Variant 0":
Variation 0
Variation 0
  • At 15 games, MENACE abandoned all non-corner openings.
  • At just over 20, Michie switched to consistently using "Variant 1":
Variation 1
Variation 1
  • At 60, he returned to Variant 0.
  • In the late 70s, he moved to "Variant 2":
Variation 2
Variation 2
  • At 110, he switched to "Variant 3":
Variation 3
Variation 3
  • At 135, he switched to "Variant 4":
Variation 4
Variation 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:[17]

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 produces a different trend on scatter graphs of wins.[16] Using a random turn from the human player results in an almost-perfect positive trend. Playing the optimal strategy returns a slightly slower increase.[1]

Legacy

Donald Michie's MENACE proved that a computer could "learn" from failure and success to become good at a task.[18] 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 are then be selected at random, creates a learning behavior similar to weight initialisation in modern artificial neural networks.[19]

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.[20] Michie went on to create a simulation program of MENACE on a Pegasus 2 computer with the aid of D. Martin.[4]

Modern recreations

There have been multiple recreations of MENACE in more recent years, both in its original physical form and as a computer program.[7][21] Although not as a functional computer, in examples of demonstration, MENACE has been used as a teaching aid[22] for various neural network classes, including a well-publicised demonstration from Cambridge Researcher Matthew Scroggs.[23]

See also

References

  1. ^ a b c "Menace: the Machine Educable Noughts And Crosses Engine". Chalkdust. 2016-03-13. Retrieved 2020-05-17.
  2. ^ "Computer Pioneers - Donald Michie". history.computer.org. Retrieved 2020-07-19.
  3. ^ Lectures Cultural Informatics Research Group
  4. ^ a b c d e f "Experiments on the mechanization of Game Learning Part 1. Characterization of the model and its parameters" (PDF). Retrieved 2020-06-01.
  5. ^ "Daily Telegraph obituary for Donald Michie". Daily Telegraph. 2007-07-09.{{cite news}}: CS1 maint: url-status (link)
  6. ^ a b The Science Book, Second Edition, Dorling Kindersley Ltd., 2015, pg. 288
  7. ^ a b c d Matchbox Educable Noughts And Crosses Engine In Empirical Modelling
  8. ^ core.ac.uk - The Machine Learning Revolution in AI by Luc De Raedt https://core.ac.uk/download/pdf/80808274.pdf
  9. ^ Muggleton, Stephen (2007-07-10). "Obituary for Donald Michie, an article in The Guardian from 2007". theguardian.com.{{cite web}}: CS1 maint: url-status (link)
  10. ^ Russel, David (2012). Springer Professional - Extract from "The BOXES Methodology",. https://www.springerprofessional.de/en/introduction-to-boxes-control/1967928: Springer London. ISBN 9781849965279. {{cite book}}: External link in |location= (help)CS1 maint: location (link)
  11. ^ "MENACE 2, an artificial intelligence made of wooden drawers and coloured beads". April 12, 2016.
  12. ^ Regine (2016-04-12). "MENACE 2, an artificial intelligence made of wooden drawers and coloured beads". We Make Money Not Art. Retrieved 2020-07-14.
  13. ^ Sall, Matt (2019-03-25). "Teaching 304 Matchboxes To Beat You At Tic-Tac-Toe". Bell of Lost Souls. Retrieved 2020-07-14.
  14. ^ "The best opening move in a game of tic-tac-toe - The Kitchen in the Zoo". blog.maxant.co.uk. Retrieved 2020-07-14.
  15. ^ "Tic-Tac-Toe Strategy". Stephen Ostermiller. 2004-06-15. Retrieved 2020-05-17.
  16. ^ a b Science, ODSC-Open Data (2018-10-23). "How 300 Matchboxes Learned to Play Tic-Tac-Toe Using MENACE". Medium. Retrieved 2020-05-17.
  17. ^ a b Trial and Error , Michie Donald , Penguin Science Surveys 1961 Vol 2
  18. ^ Dumas, Jacques-Pierre (Jp). "IoT and machine learning are driving network transformation". itbrief.com.au. Retrieved 2020-06-12.
  19. ^ Saurabh Yadav (2020-01-17). "Weight Initialization Techniques in Neural Networks". Medium. Retrieved 2020-07-14.
  20. ^ "Professor Donald Michie". 2007-07-08. ISSN 0307-1235. Retrieved 2020-06-11.
  21. ^ Scaruffi, Piero (2016). 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. https://www.scaruffi.com/singular/download.pdf. p. 30. ISBN 978-0-9765531-9-9. {{cite book}}: External link in |location= (help)CS1 maint: location missing publisher (link)
  22. ^ Zhao, Yibo (1 December 2013). "Machine Educable Engine on Noughts And Crosses in Modelling Study". University of Warwick.{{cite web}}: CS1 maint: url-status (link); "AI Topics.. Tic-Tac-Toe strategy in Computational Thinking, Introduction, MENACE".{{cite web}}: CS1 maint: url-status (link); Ute 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; "Inspiring the Next Generation of Computer Scientists | King's Worcester". King's Worcester. 2019-11-11. Retrieved 2020-06-12.
  23. ^ Matthew Scroggs Lecture on MENACE - https://www.youtube.com/watch?v=hK25eXRaBdc

Sources

The BOXES Methodology, a book on the "Boxes" algorithm employed by MENACE.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Matchbox_Educable_Noughts_and_Crosses_Engine&oldid=970252445"