Edición de «MENACE»

[[Archivo:Mscroggs-MENACE-cropped.jpg|alt=MENACE recreation|miniaturadeimagen|350x350px|Una recreación de MENACE construida por Matthew Scroggs.]]
El '''motor Matchbox Educable Noughts and Crosses Engine''' (a veces llamado '''Machine Educable Noughts and Crosses Engine''') o '''MENACE''' era una computadora mecánica hecha de 304 [[Fosforera|cajas de fósforos]] diseñadas y construidas por [[Donald Michie]] en 1961. Fue diseñado para jugar a oponentes humanos en juegos de [[Tres en línea|ceros y cruces]] devolviendo un movimiento para cualquier estado de juego dado y refinando su estrategia a través del [[aprendizaje por refuerzo]].

Michie no tenía una computadora disponible, por lo que evitó esta restricción construyéndola con cajas de cerillas. Cada una de las cajas de fósforos utilizadas por Michie representaba un único diseño posible de una cuadrícula de [[tres en línea]]. Cuando la computadora jugaba por primera vez, elegía movimientos aleatoriamente según el diseño actual. A medida que jugaba más juegos, a través de un ciclo de refuerzo, descalificó las estrategias que llevaron a perder juegos y complementó las estrategias que llevaron a ganar juegos. Michie celebró un torneo contra MENACE en 1961, en el que experimentó con diferentes aperturas.

Después del torneo inaugural de MENACE contra Michie, se demostró que era una computadora exitosa. Los ensayos de Michie sobre la inicialización del peso de MENACE y el algoritmo BOXES utilizado por MENACE se hicieron populares en el campo de la investigación en [[ciencias de la computación]]. Michie fue honrado por su contribución a la investigación del [[aprendizaje automático]] y se le encargó dos veces que programara una simulación de MENACE en una computadora real.

== Origen ==
[[Archivo:Donald_Michie_teaching.jpg|alt=Donald Michie teaching|miniaturadeimagen|275x275px|[[Donald Michie]] enseñando a un grupo de estudiantes en el [[Instituto Turing]].]]
[[Donald Michie]] había estado en el equipo que estaba descifrando el [[código Lorenz]] durante la [[Segunda Guerra Mundial]].<ref>{{Cite web|url=https://history.computer.org/pioneers/michie.html|title=Computer Pioneers - Donald Michie|website=history.computer.org|access-date=2020-07-19}}</ref> Quince años después, quiso mostrar aún más su destreza matemática y computacional con una [[Redes neuronales convolucionales|red neuronal convolucional]] temprana. Dado que no se podía obtener equipo informático para tales usos,<ref>[http://www.cdpa.co.uk/UoP/HoC/Lectures/HoC_07b.PDF Lectures] Cultural Informatics Research Group</ref> y Michie no tenía una computadora disponible,<ref>{{Cite web|url=https://scroll.in/article/955960/donald-michie-the-ai-pioneer-who-tested-his-computer-program-with-a-matchbox-and-some-beads|title=Donald Michie: The AI pioneer who tested his computer program with a matchbox and some beads|last=Wright|first=Matt|website=Scroll.in|language=en-US|access-date=2020-10-18}}</ref> decidió exhibir y demostrar [[inteligencia artificial]] en un formato más esotérico y construyó una computadora mecánica funcional con cajas de cerillas y cuentas.<ref name=":9">{{Cite web|url=https://www.ithistory.org/honor-roll/dr-donald-michie|title=Dr. Donald Michie|date=2015-12-21|website=IT History Society|language=en|access-date=2020-10-18}}</ref><ref name=":1">{{Cite web|url=http://chalkdustmagazine.com/features/menace-machine-educable-noughts-crosses-engine/|title=Menace: the Machine Educable Noughts And Crosses Engine|date=2016-03-13|website=Chalkdust|language=en-GB|access-date=17 May 2020}}</ref><ref name=":2" />

Según se informa, MENACE se construyó como resultado de una apuesta con un colega de informática que postuló que tal máquina era imposible.<ref>{{Cite news|date=2007-07-09|title=Daily Telegraph obituary for Donald Michie|work=The Daily Telegraph|url=https://www.telegraph.co.uk/news/obituaries/1556846/Professor-Donald-Michie.html}}</ref> Michie asumió la tarea de recopilar y definir cada caja de fósforos como un "proyecto divertido", que luego se convirtió en una herramienta de demostración.<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|cita=(citeseerx=10.1.1.474.2430)|p=137,}}</ref> Michie completó su ensayo sobre MENACE en 1963,<ref name=":2" /> ''"Experimentos sobre la mecanización del aprendizaje de juegos"'', así como su ensayo sobre el algoritmo BOXES, escrito con R. A. Chambers<ref name=":6" /> y para entonces había construido un Unidad de investigación de IA en Hope Park Square, [[Edimburgo]], [[Escocia]].<ref name=":7" />

MENACE "aprendió" jugando cada vez más partidas de ceros y cruces. Cada vez, eliminaría una estrategia perdedora por parte del jugador humano confiscando las cuentas que correspondían a cada movimiento.<ref name=":8" /> Reforzó las estrategias ganadoras al hacer que los movimientos fueran más probables, al proporcionar cuentas adicionales. Esta fue una de las primeras versiones del [[aprendizaje por refuerzo]], el algoritmo esquemático de hacer un bucle del algoritmo, descartando estrategias fallidas hasta que solo quedan las ganadoras.<ref name=":2" /> Este modelo comienza como completamente aleatorio y aprende gradualmente.

== Composición ==
MENACE se hizo a partir de 304 cajas de fósforos pegadas juntas en una disposición similar a una [[cómoda]].<ref name="sci">The Science Book, Second Edition, Dorling Kindersley Ltd., 2015, pg. 288</ref> Cada casilla tenía un número de código, que estaba tecleado en un cuadro. Esta tabla tenía dibujos de cuadrículas de juegos de tic-tac-toe con varias configuraciones de X, O y cuadrados vacíos,<ref name=":2" /> correspondientes a todas las posibles permutaciones que un juego podía atravesar a medida que avanzaba.<ref name=":8">{{Cite web|url=https://opendatascience.com/the-history-of-neural-networks-and-ai-part-ii/|title=The History of Neural Networks and AI: Part II|date=23 May 2018|website=Open Data Science - Your News Source for AI, Machine Learning & more|language=en-US|access-date=2020-09-19}}</ref><ref name=":4">{{Cite journal|title=Mathematical Games|journal=Scientific American|volume=206|issue=3|pages=138–154|bibcode=1962SciAm.206c.138G|doi=10.1038/scientificamerican0362-138|year=1962|last=Gardner|first=Martin|jstor=24937263}}</ref> Después de eliminar arreglos duplicados (los que eran simplemente rotaciones o imágenes en espejo de otras configuraciones), MENACE usó 304 permutaciones en su gráfico y, por lo tanto, muchas cajas de cerillas.<ref name=":0" />

Cada bandeja de caja de cerillas individual contenía una colección de cuentas de colores.<ref>core.ac.uk - ''The Machine Learning Revolution in AI'' by Luc De Raedt 
 [https://core.ac.uk/download/pdf/80808274.pdf Link] {{Wayback|url=https://core.ac.uk/download/pdf/80808274.pdf |date=20200612080944 }}</ref> Cada color representaba un movimiento en un cuadrado en la cuadrícula del juego, por lo que las cajas de fósforos con arreglos donde las posiciones en la cuadrícula ya estaban tomadas no tendrían cuentas para esa posición. Además, en la parte delantera de la bandeja había dos tarjetas adicionales en forma de "V",<ref name="sci" /> la punta de la "V" apuntando hacia la parte delantera de la caja de cerillas.<ref name=":4" /> Michie y su equipo de inteligencia artificial llamaron al algoritmo de MENACE "Boxes",<ref name=":7">{{Cite web|url=https://www.theguardian.com/science/2007/jul/10/uk.obituaries1|title=Obituary for Donald Michie, an article in The Guardian from 2007.|last=Muggleton|first=Stephen|date=2007-07-10|website=The Guardian}}</ref> honor al aparato utilizado para la máquina. La primera etapa "Boxes" operó en cinco fases, cada una estableciendo una definición y un precedente para las reglas del [[algoritmo]] en relación con el juego.<ref>{{Cite book|last=Russel|first=David|title=Springer Professional - Extract from "The BOXES Methodology". (Chapter 2. The Game Metaphor)|url=https://archive.org/details/boxesmethodology0000russ|publisher=Springer London|year=2012|isbn=9781849965279|location=London}}</ref>

== Operación ==
MENACE jugó primero, como O, ya que todas las cajas de fósforos representaban permutaciones solo relevantes para el jugador "X".<ref>{{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=2016-04-12}}</ref><ref name=":0" /> Para recuperar la elección de movimiento de MENACE, el oponente u operador localizó la caja de cerillas que coincidía con el estado actual del juego, o una rotación o una imagen reflejada de la misma. Por ejemplo, al comienzo de un juego, esta sería la caja de cerillas de una cuadrícula vacía. La bandeja se retiraría y se agitaría ligeramente para mover las cuentas.<ref name=":2" /> Entonces, la cuenta que se había enrollado en la punta de la forma de "V" en la parte delantera de la bandeja fue el movimiento que MENACE había elegido hacer.<ref name=":2" /> Luego, su color se usó como la posición para jugar y, después de tener en cuenta las rotaciones o giros necesarios en función de la relación de la configuración de la caja de fósforos elegida con la cuadrícula actual, la O se colocaría en ese cuadrado. Luego, el jugador realizó su movimiento, se ubicó el nuevo estado, se seleccionó un nuevo movimiento, y así sucesivamente, hasta que el juego terminaba.<ref name=":0" />

Cuando el juego terminó, el jugador humano observó el resultado del juego. A medida que se jugaba un juego, cada caja de fósforos que se usó para el turno de MENACE tenía su bandeja entreabierta, y la cuenta utilizada se mantuvo a un lado, de modo que se registraron la elección de movimientos de MENACE y los estados del juego al que pertenecían. Michie describió su sistema de refuerzo con "recompensa" y "castigo". Una vez finalizado el juego, si MENACE hubiera ganado, recibiría una "recompensa" por su victoria. Las cuentas retiradas mostraban la secuencia de los movimientos ganadores.<ref>{{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|last=Regine|date=2016-04-12|website=We Make Money Not Art|language=en-US|access-date=2020-07-14}}</ref> Estos fueron devueltos a sus respectivas bandejas, fácilmente identificables ya que estaban ligeramente abiertos, así como tres cuentas extra del mismo color.<ref name=":4" /> De esta manera, en juegos futuros, MENACE tendría más probabilidades de repetir esos movimientos ganadores, reforzando las estrategias ganadoras. Si se perdía, las cuentas extraídas no se devolvían, "castigando" a MENACE, lo que significa que en el futuro sería menos probable, y eventualmente incapaz si ese color de cuenta se volvía ausente, repetir los movimientos que causan una pérdida.<ref name=":5">{{Cite web|url=https://www.belloflostsouls.net/2019/03/teaching-304-matchboxes-to-beat-you-at-tic-tac-toe.html|title=Teaching 304 Matchboxes To Beat You At Tic-Tac-Toe|last=Sall|first=Matt|date=2019-03-25|website=Bell of Lost Souls|language=en-US|access-date=2020-07-14}}</ref> Si el juego era un empate, se agregaba una cuenta adicional a cada casilla.<ref name=":4" />

== Resultados en la práctica ==
=== Estrategia óptima ===
[[Archivo:Tictactoe-X.svg|alt=Optimal noughts and crosses strategy|miniaturadeimagen|Estrategia óptima para el jugador X si comienza en una esquina. En cada cuadrícula, la X roja sombreada denota el movimiento óptimo, y la ubicación del próximo movimiento de O da la siguiente subcuadrícula para examinar.]]
''Tres en línea'' tiene una estrategia óptima bien conocida.<ref>{{Cite web|url=http://blog.maxant.co.uk/pebble/2018/04/07/1523086680000.html|title=The best opening move in a game of tic-tac-toe - The Kitchen in the Zoo|website=blog.maxant.co.uk|access-date=2020-07-14}}</ref> Implica una ubicación estratégica para bloquear al otro jugador y al mismo tiempo ganar. Sin embargo, si ambos jugadores usan esta estrategia, siempre termina en empate.<ref>{{Cite web|url=https://blog.ostermiller.org/tic-tac-toe-strategy/|title=Tic-Tac-Toe Strategy|date=2004-06-15|website=Stephen Ostermiller|language=en-US|access-date=17 May 2020}}</ref> Esto crea un estancamiento. Si el jugador humano está familiarizado con la estrategia óptima y MENACE puede aprenderla rápidamente, los juegos eventualmente terminarán en empates. Cuando la computadora comienza y juega con un oponente que juega al azar, tiene las probabilidades de que la computadora gane el turno rápidamente a su favor.<ref name=":1" />

Cuando se juega contra un jugador que usa una estrategia óptima, las probabilidades de empate aumentan al 100%. En el torneo oficial de [[Donald Michie]] contra MENACE, (1961)<ref name=":2" /> usó una estrategia óptima, y él y la computadora comenzaron a empatar consistentemente después de veinte juegos. El torneo de Michie<ref name=":3">Trial and Error, Michie Donald, Penguin Science Surveys 1961 Vol 2</ref> tuvo los siguientes hitos: Michie comenzó abriendo constantemente con la "Variante 0", el cuadro del medio. En 15 juegos, MENACE abandonó todas las aperturas que no eran de esquina. Con poco más de 20 años, Michie pasó a usar constantemente la "Variante 1", el cuadrado inferior derecho. A los 60, regresó a la Variante 0. A medida que se acercaba a los 80 juegos, pasó a la "Variante 2", el medio superior. A los 110, cambió a "Variante 3", arriba a la derecha. A los 135, cambió a "Variante 4", en el medio a la derecha. A los 190, retornó a la Variante 1, y a los  210, retornó a la Variante 0.

La tendencia en los cambios de cuentas en las casillas "2" es la siguiente:<ref name=":3" />
{| class="wikitable"
!Variante
!Número de juegos
!Cambio de cuentas en caja "2"
|-
!Variante 0
|0
|0
|-
!Variante 1
|20
| -5
|-
!Variante 0
|60
|5
|-
!Variante 2
|70
|10
|-
!Variante 3
|110
|20
|-
!Variante 4
|135
|25
|-
!Variante 1
|190
|100
|-
!Variante 0
|210
|120
|-
|}

=== Correlación ===
[[Archivo:Michie-MENACE-graph.png|alt=Scatter graph of Michie's tournament.|miniaturadeimagen|Un gráfico de dispersión que muestra los resultados de las partidas de Donald Michie contra MENACE]]
Dependiendo de la estrategia empleada por el jugador humano, MENACE produce una tendencia diferente en los [[Diagrama de dispersión|gráficos de dispersión]] de victorias.<ref name=":2" /> Usar un turno aleatorio del jugador humano da como resultado una tendencia positiva casi perfecta. Jugar la estrategia óptima devuelve un aumento ligeramente más lento.<ref name=":1" /> El refuerzo no crea un estándar perfecto de victorias; el algoritmo sacará conclusiones inciertas al azar cada vez. Después del '''''j-'' ésimo,''' la correlación del juego casi perfecto se ejecuta:

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

Donde '''''V<sub>i</sub>''''' es el resultado (+1 es victoria, 0 es empate y -1 es pérdida) '''''D''''' es el factor de deterioro (promedio de los valores pasados de victorias y derrotas). A continuación, '''''M<sub>n</sub>''''' es el multiplicador de la enésima ronda del juego.<ref name=":2" /> 
{| class="wikitable"
|+
!Salida
!Reforzamiento
|-
|Victoria
|<math>R_n=M_n^{-\mu+1}</math>
|-
|Empate
|<math>R_n=M_n^{-\mu}</math>
|-
|Derrota
|<math>R_n=M_n^{-\mu-1}</math>
|}

== Legado ==
La MENACE de Donald Michie demostró que una computadora puede "aprender" del fracaso y el éxito para volverse buena en una tarea.<ref>{{Cite web|url=https://itbrief.com.au/story/iot-and-machine-learning-are-driving-network-transformation|title=IoT and machine learning are driving network transformation|last=Dumas|first=Jacques-Pierre (Jp)|website=itbrief.com.au|language=en|access-date=2020-06-12}}</ref> También utilizó lo que se convertiría en principios básicos dentro del campo del aprendizaje automático antes de que se hubieran teorizado adecuadamente. Por ejemplo, la combinación de cómo MENACE comienza con el mismo número de tipos de cuentas en cada caja de fósforos, y cómo se seleccionan al azar, crea un comportamiento de aprendizaje similar a la inicialización del peso en las [[Red neuronal artificial|redes neuronales artificiales]] modernas.<ref>{{Cite journal|url=http://www.sciencedirect.com/science/article/pii/S0925231299001277|title=A weight initialization method for improving training speed in feedforward neural network|last1=Yam|first1=Jim Y. F.|last2=Chow|first2=Tommy W. S.|date=2000-01-01|journal=Neurocomputing|volume=30|issue=1|pages=219–232|language=en|issn=0925-2312|doi=10.1016/S0925-2312(99)00127-7}}</ref> En 1968, Donald Michie y RA Chambers crearon otro algoritmo basado en "BOXES" llamado GLEE, (Game Learning Expectimaxing Engine)<ref>{{Cite web|url=http://incompleteideas.net/book/first/ebook/node12.html|title=1.6 History of Reinforcement Learning|website=incompleteideas.net|access-date=2020-08-01}}</ref> que tenía la tarea de aprender a equilibrar un poste en un carro.<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.|date=2018-11-13|publisher=MIT Press|isbn=978-0-262-03924-6|language=en|p=753}}</ref>

Después de la rotunda recepción de MENACE, Michie fue invitado a la Oficina de Investigación Naval de Estados Unidos, donde se le encargó la construcción de un programa de ejecución "Boxes" para una computadora [[IBM]] para su uso en la [[Universidad Stanford|Universidad de Stanford]].<ref>{{Cite news|date=2007-07-08|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=2020-06-11|issn=0307-1235}}</ref> Michie pasó a crear un programa de simulación de MENACE en una computadora Pegasus 2 con la ayuda de D. Martin.<ref name=":2">{{Cite web|url=https://www.gwern.net/docs/rl/1963-michie.pdf|title=Experiments on the mechanization of Game Learning Part 1. Characterization of the model and its parameters|language=en|access-date=2020-06-01}}</ref> Ha habido múltiples recreaciones de MENACE en años más recientes, tanto en su forma física original como en un programa de computadora.<ref name=":0">[https://warwick.ac.uk/fac/sci/dcs/research/em/publications/web-em/10/cs405_-_1362452_-_menaceem.pdf Matchbox Educable Noughts And Crosses Engine In Empirical Modelling]</ref> Su algoritmo convergió más tarde en el algoritmo Q-Learning de Christopher Watkin.<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''|url=https://archive.org/details/isbn_9780976553199|year=2016|isbn=978-0-9765531-9-9|pages=[https://archive.org/details/isbn_9780976553199/page/n28 27]}}</ref> Aunque no como una computadora funcional, en ejemplos de demostración, MENACE se ha utilizado como una ayuda didáctica para varias clases de redes neuronales,<ref>{{Cite web|url=https://warwick.ac.uk/fac/sci/dcs/research/em/teaching/cs405/web-em-10-abstracts/yibo/|title=Machine Educable Engine on Noughts And Crosses in Modelling Study|last=Zhao|first=Yibo|date=2013-12-01|publisher=University of Warwick}}</ref><ref>{{Cite web|url=https://aitopics.org/class/Industry/Leisure%20&%20Entertainment/Games/Tic-Tac-Toe|title=AI Topics.. Tic-Tac-Toe strategy in Computational Thinking, Introduction, MENACE}}</ref><ref>Ute Schmid - "Interactive Learning with Mutual Explanations" (How Humans and Machine Learning Systems can Profit From Each Other) - University of Bamberg, Germany [https://www.universiteitleiden.nl/binaries/content/assets/science/dso/ute-schmid_mutualexplleiden-1.pdf Link]</ref> incluyendo una demostración bien publicitada del Investigador de Cambridge Matthew Scroggs.<ref>{{Cita vídeo|url=https://www.youtube.com/watch?v=hK25eXRaBdc|title=‘Building a MENACE machine’, Matthew Scroggs, University College London|date=2017-07-03|last=Scroggs|first=Matthew|type=Youtube|language=en}}</ref><ref>{{Cite web|url=https://www.ksw.org.uk/inspiring-the-next-generation-of-computer-scientists/|title=Inspiring the Next Generation of Computer Scientists {{!}} King's Worcester|date=2019-11-11|website=King's Worcester|language=en-GB|access-date=2020-06-12}}</ref> Una copia de MENACE construida por Scroggs apareció en las [[Royal Institution Christmas Lectures]] de 2019.<ref>{{Cite web|url=https://www.mscroggs.co.uk/blog/71|title=Visualising MENACE's learning|last=Scroggs|first=Matthew|date=2019-12-27|website=mscroggs.co.uk}}</ref><ref>{{Cite tweet|user=rsi_science|number=1210666302890754049|access-date=2020-10-14|title=Menace Machine-creator pitched up with his 304 matchboxes to explain how he made it.|via=Twitter|language=en|date=2019-12-27}}</ref>

== Véase también ==
* [[Hexapawn]]
*[[OXO]]
*[[Lista de proyectos de inteligencia artificial]]

== Referencias ==
{{listaref|2}}

== Enlaces externos ==
* [https://www.mscroggs.co.uk/menace/ Simulación en línea de MENACE]
*[https://books.google.co.uk/books?id=3o89gfE9pS0C&printsec=frontcover&dq=the+boxes+methodology&hl=en&sa=X&ved=2ahUKEwil1MTA3I7sAhWxTBUIHfX1AQ8Q6AEwAHoECAUQAg#v=onepage&q&f=false The BOXES Methodology], un libro sobre el algoritmo "Boxes" empleado por MENACE.
* [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.474.2430&rep=rep1&type=pdf BOXES: An Experiment in Adaptive Control], documento de Michie y R. A. Chambers sobre las implicaciones de BOXES y MENACE en la IA.

{{Control de autoridades}}
[[Categoría:Videojuegos para PC]]
[[Categoría:Aprendizaje automático]]
[[Categoría:Inteligencia artificial]]
[[Categoría:Computadoras analógicas]]