MENACE

De Wikipedia, la enciclopedia libre
MENACE recreation
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 cajas de fósforos diseñadas y construidas por Donald Michie en 1961. Fue diseñado para jugar a oponentes humanos en juegos de 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[editar]

Donald Michie teaching
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.[1]​ Quince años después, quiso mostrar aún más su destreza matemática y computacional con una red neuronal convolucional temprana. Dado que no se podía obtener equipo informático para tales usos,[2]​ y Michie no tenía una computadora disponible,[3]​ 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.[4]​[5]​[6]​

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.[7]​ 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.[8]​ Michie completó su ensayo sobre MENACE en 1963,[6]​ "Experimentos sobre la mecanización del aprendizaje de juegos", así como su ensayo sobre el algoritmo BOXES, escrito con R. A. Chambers[8]​ y para entonces había construido un Unidad de investigación de IA en Hope Park Square, Edimburgo, Escocia.[9]​

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.[10]​ 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.[6]​ Este modelo comienza como completamente aleatorio y aprende gradualmente.

Composición[editar]

MENACE se hizo a partir de 304 cajas de fósforos pegadas juntas en una disposición similar a una cómoda.[11]​ 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,[6]​ correspondientes a todas las posibles permutaciones que un juego podía atravesar a medida que avanzaba.[10]​[12]​ 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.[13]​

Cada bandeja de caja de cerillas individual contenía una colección de cuentas de colores.[14]​ 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",[11]​ la punta de la "V" apuntando hacia la parte delantera de la caja de cerillas.[12]​ Michie y su equipo de inteligencia artificial llamaron al algoritmo de MENACE "Boxes",[9]​ 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.[15]​

Operación[editar]

MENACE jugó primero, como O, ya que todas las cajas de fósforos representaban permutaciones solo relevantes para el jugador "X".[16]​[13]​ 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.[6]​ 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.[6]​ 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.[13]​

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.[17]​ Estos fueron devueltos a sus respectivas bandejas, fácilmente identificables ya que estaban ligeramente abiertos, así como tres cuentas extra del mismo color.[12]​ 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.[18]​ Si el juego era un empate, se agregaba una cuenta adicional a cada casilla.[12]​

Resultados en la práctica[editar]

Estrategia óptima[editar]

Optimal noughts and crosses strategy
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.[19]​ 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.[20]​ 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.[5]​

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)[6]​ usó una estrategia óptima, y él y la computadora comenzaron a empatar consistentemente después de veinte juegos. El torneo de Michie[21]​ 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:[21]​

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[editar]

Scatter graph of Michie's tournament.
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 gráficos de dispersión de victorias.[6]​ 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.[5]​ 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:

Donde Vi 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, Mn es el multiplicador de la enésima ronda del juego.[6]​

Salida Reforzamiento
Victoria
Empate
Derrota

Legado[editar]

La MENACE de Donald Michie demostró que una computadora puede "aprender" del fracaso y el éxito para volverse buena en una tarea.[22]​ 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 redes neuronales artificiales modernas.[23]​ En 1968, Donald Michie y RA Chambers crearon otro algoritmo basado en "BOXES" llamado GLEE, (Game Learning Expectimaxing Engine)[24]​ que tenía la tarea de aprender a equilibrar un poste en un carro.[25]​

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 de Stanford.[26]​ Michie pasó a crear un programa de simulación de MENACE en una computadora Pegasus 2 con la ayuda de D. Martin.[6]​ 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.[13]​ Su algoritmo convergió más tarde en el algoritmo Q-Learning de Christopher Watkin.[27]​ 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,[28]​[29]​[30]​ incluyendo una demostración bien publicitada del Investigador de Cambridge Matthew Scroggs.[31]​[32]​ Una copia de MENACE construida por Scroggs apareció en las Royal Institution Christmas Lectures de 2019.[33]​[34]​

Véase también[editar]

Referencias[editar]

  1. ↑ «Computer Pioneers - Donald Michie». history.computer.org. Consultado el 19 de julio de 2020. 
  2. ↑ Lectures Cultural Informatics Research Group
  3. ↑ Wright, Matt. «Donald Michie: The AI pioneer who tested his computer program with a matchbox and some beads». Scroll.in (en inglés estadounidense). Consultado el 18 de octubre de 2020. 
  4. ↑ «Dr. Donald Michie». IT History Society (en inglés). 21 de diciembre de 2015. Consultado el 18 de octubre de 2020. 
  5. ↑ a b c «Menace: the Machine Educable Noughts And Crosses Engine». Chalkdust (en inglés británico). 13 de marzo de 2016. Consultado el 17 de mayo de 2020. 
  6. ↑ a b c d e f g h i j «Experiments on the mechanization of Game Learning Part 1. Characterization of the model and its parameters» (en inglés). Consultado el 1 de junio de 2020. 
  7. ↑ «Daily Telegraph obituary for Donald Michie». The Daily Telegraph. 9 de julio de 2007. 
  8. ↑ a b Donald, Michie. BOXES: An experiment in adaptive control. University of Edinburgh. p. 137,. «(citeseerx=10.1.1.474.2430)». 
  9. ↑ a b Muggleton, Stephen (10 de julio de 2007). «Obituary for Donald Michie, an article in The Guardian from 2007.». The Guardian. 
  10. ↑ a b «The History of Neural Networks and AI: Part II». Open Data Science - Your News Source for AI, Machine Learning & more (en inglés estadounidense). 23 de mayo de 2018. Consultado el 19 de septiembre de 2020. 
  11. ↑ a b The Science Book, Second Edition, Dorling Kindersley Ltd., 2015, pg. 288
  12. ↑ a b c d Gardner, Martin (1962). «Mathematical Games». Scientific American 206 (3): 138-154. Bibcode:1962SciAm.206c.138G. JSTOR 24937263. doi:10.1038/scientificamerican0362-138. 
  13. ↑ a b c d Matchbox Educable Noughts And Crosses Engine In Empirical Modelling
  14. ↑ core.ac.uk - The Machine Learning Revolution in AI by Luc De Raedt Link Archivado el 12 de junio de 2020 en Wayback Machine.
  15. ↑ Russel, David (2012). Springer Professional - Extract from "The BOXES Methodology". (Chapter 2. The Game Metaphor). London: Springer London. ISBN 9781849965279. 
  16. ↑ «MENACE 2, an artificial intelligence made of wooden drawers and coloured beads». 12 de abril de 2016. 
  17. ↑ Regine (12 de abril de 2016). «MENACE 2, an artificial intelligence made of wooden drawers and coloured beads». We Make Money Not Art (en inglés estadounidense). Consultado el 14 de julio de 2020. 
  18. ↑ Sall, Matt (25 de marzo de 2019). «Teaching 304 Matchboxes To Beat You At Tic-Tac-Toe». Bell of Lost Souls (en inglés estadounidense). Consultado el 14 de julio de 2020. 
  19. ↑ «The best opening move in a game of tic-tac-toe - The Kitchen in the Zoo». blog.maxant.co.uk. Consultado el 14 de julio de 2020. 
  20. ↑ «Tic-Tac-Toe Strategy». Stephen Ostermiller (en inglés estadounidense). 15 de junio de 2004. Consultado el 17 de mayo de 2020. 
  21. ↑ a b Trial and Error, Michie Donald, Penguin Science Surveys 1961 Vol 2
  22. ↑ Dumas, Jacques-Pierre (Jp). «IoT and machine learning are driving network transformation». itbrief.com.au (en inglés). Consultado el 12 de junio de 2020. 
  23. ↑ Yam, Jim Y. F.; Chow, Tommy W. S. (1 de enero de 2000). «A weight initialization method for improving training speed in feedforward neural network». Neurocomputing (en inglés) 30 (1): 219-232. ISSN 0925-2312. doi:10.1016/S0925-2312(99)00127-7. 
  24. ↑ «1.6 History of Reinforcement Learning». incompleteideas.net. Consultado el 1 de agosto de 2020. 
  25. ↑ Sutton, Richard S.; Barto, Andrew G. (13 de noviembre de 2018). Reinforcement Learning: An Introduction (en inglés). MIT Press. p. 753. ISBN 978-0-262-03924-6. 
  26. ↑ «Professor Donald Michie». The Daily Telegraph (en inglés británico). 8 de julio de 2007. ISSN 0307-1235. Consultado el 11 de junio de 2020. 
  27. ↑ 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. p. 27. ISBN 978-0-9765531-9-9. 
  28. ↑ Zhao, Yibo (1 de diciembre de 2013). «Machine Educable Engine on Noughts And Crosses in Modelling Study». University of Warwick. 
  29. ↑ «AI Topics.. Tic-Tac-Toe strategy in Computational Thinking, Introduction, MENACE». 
  30. ↑ Ute Schmid - "Interactive Learning with Mutual Explanations" (How Humans and Machine Learning Systems can Profit From Each Other) - University of Bamberg, Germany Link
  31. ↑ Scroggs, Matthew (3 de julio de 2017). ‘Building a MENACE machine’, Matthew Scroggs, University College London (Youtube) (en inglés). 
  32. ↑ «Inspiring the Next Generation of Computer Scientists | King's Worcester». King's Worcester (en inglés británico). 11 de noviembre de 2019. Consultado el 12 de junio de 2020. 
  33. ↑ Scroggs, Matthew (27 de diciembre de 2019). «Visualising MENACE's learning». mscroggs.co.uk. 
  34. ↑ rsi_science (27 de diciembre de 2019). «Menace Machine-creator pitched up with his 304 matchboxes to explain how he made it.». X (antes Twitter) (tuit) (en inglés). Consultado el 14 de octubre de 2020. 

Enlaces externos[editar]

Obtenido de «https://es.wikipedia.org/w/index.php?title=MENACE&oldid=154142086»