Motor de tres en raya educativo de Matchbox

El Matchbox Educable Noughts and Crosses Engine (a veces llamado Machine Educable Noughts and Crosses Engine o MENACE ) fue una computadora mecánica hecha con 304 cajas de cerillas , diseñada y construida por el investigador de inteligencia artificial Donald Michie y su colega Roger Chambers en 1961. Fue diseñada para jugar contra oponentes humanos al tres en raya, devolviendo una jugada para cualquier estado de juego dado y refinando su estrategia mediante aprendizaje por refuerzo . Este fue uno de los primeros tipos de inteligencia artificial.

Michie y Chambers no tenían acceso inmediato a una computadora; sortearon esta limitación construyendo el motor con cajas de cerillas. ^{[ 1 ]} Cada caja de cerillas que usaron representaba una única disposición posible de una cuadrícula de tres en raya. Cuando la computadora jugaba por primera vez, elegía aleatoriamente los movimientos según la disposición actual. A medida que jugaba más partidas, mediante un bucle de reforzamiento, descartaba las estrategias que llevaban a perder y reforzaba las que llevaban a ganar. Michie organizó un torneo contra MENACE en 1961, donde experimentó con diferentes aperturas.

Tras su primer torneo contra Michie, MENACE demostró una inteligencia artificial eficaz en su estrategia. Los ensayos de Michie sobre la inicialización de pesos de MENACE y el algoritmo BOXES utilizado por este se popularizaron en el campo de la investigación en informática. Michie fue galardonado por su contribución a la investigación en aprendizaje automático y recibió en dos ocasiones el encargo de programar una simulación de MENACE en un ordenador real.

Donald Michie (1923–2007) formó parte del equipo que descifró el código Tunny alemán durante la Segunda Guerra Mundial . ^{[ 2 ]} Quince años después, quiso demostrar aún más su destreza matemática y computacional con una red neuronal convolucional temprana . Dado que no se disponía de equipos informáticos para tales usos, ^{[ 3 ]} y Michie no tenía una computadora a mano, ^{[ 3 ]} decidió mostrar y demostrar la inteligencia artificial en un formato más esotérico y construyó una computadora mecánica funcional con cajas de cerillas y cuentas. ^{[ 4 ] [ 5 ]}

MENACE se construyó como resultado de una apuesta con un colega de ciencias de la computación que postulaba que tal máquina era imposible. ^{[ 6 ]} Michie emprendió la tarea de recolectar y definir cada caja de cerillas como un "proyecto divertido", que luego se convirtió en una herramienta de demostración. ^{[ 1 ]} Michie completó su ensayo sobre MENACE en 1963, ^{[ 5 ]} "Experimentos sobre la mecanización del aprendizaje de juegos", así como su ensayo sobre el algoritmo BOXES, escrito con RA Chambers ^{[ 1 ]} y había creado una unidad de investigación de IA en Hope Park Square, Edimburgo , Escocia . ^{[ 7 ]}

MENACE aprendió jugando partidas sucesivas de tres en raya. En cada ocasión, eliminaba una estrategia perdedora mediante la confiscación por parte del jugador humano de las fichas correspondientes a cada movimiento. ^{[ 5 ]} Reforzaba las estrategias ganadoras aumentando la probabilidad de los movimientos, proporcionando fichas adicionales. ^{[ 8 ]} Esta fue una de las primeras versiones del Bucle de Refuerzo , el algoritmo esquemático que consiste en repetir el algoritmo, descartando las estrategias fallidas hasta que solo queden las ganadoras. ^{[ 5 ]} Este modelo comienza siendo completamente aleatorio y aprende gradualmente. ^{[ 9 ]}

MENACE se construyó con 304 cajas de cerillas pegadas entre sí en una disposición similar a la de una cómoda. ^{[ 10 ]} Cada caja tenía un código numérico que se introducía en una tabla. Esta tabla contenía dibujos de cuadrículas del juego de tres en raya con diversas configuraciones de X , O y casillas vacías, ^{[ 5 ]} correspondientes a todas las permutaciones posibles que podía experimentar el juego a medida que avanzaba. ^{[ 11 ]} Tras eliminar las disposiciones duplicadas (aquellas que eran simplemente rotaciones o imágenes especulares de otras configuraciones), MENACE utilizó 304 permutaciones en su tabla y, por lo tanto, esa cantidad de cajas de cerillas. ^{[ 12 ]}

Cada bandeja de caja de cerillas individual contenía una colección de cuentas de colores. ^{[ 13 ]} Cada color representaba un movimiento en una casilla de la cuadrícula del juego, por lo que las cajas de cerillas con disposiciones donde las posiciones en la cuadrícula ya estaban ocupadas no tendrían cuentas para esa posición. Además, en el frente de la bandeja había dos piezas de cartón adicionales en forma de "V", ^{[ 10 ]} la punta de la "V" apuntando hacia el frente de la caja de cerillas. ^{[ 11 ]} Michie y su equipo de inteligencia artificial llamaron al algoritmo de MENACE "Boxes", ^{[ 7 ]} en honor al aparato utilizado para la máquina. La primera etapa de "Boxes" operaba en cinco fases, cada una estableciendo una definición y un precedente para las reglas del algoritmo en relación con el juego. ^{[ 14 ]}

MENACE jugaba primero, como O, ya que todas las cajas de cerillas representaban permutaciones relevantes solo para el jugador "X". ^{[ 12 ] [ 17 ]} Para recuperar la elección de movimiento de MENACE, el oponente u operador localizaba la caja de cerillas que coincidía con el estado actual del juego, o una rotación o imagen especular del mismo. Por ejemplo, al comienzo de un juego, esta sería la caja de cerillas para una cuadrícula vacía. Se retiraba la bandeja y se agitaba ligeramente para mover las cuentas. ^{[ 5 ]} Entonces, la cuenta que había rodado hasta la punta de la forma de "V" en el frente de la bandeja era el movimiento que MENACE había elegido hacer. ^{[ 5 ]} Su color se utilizaba entonces como la posición para jugar, y, después de tener en cuenta las rotaciones o volteos necesarios según la relación de la configuración de la caja de cerillas elegida con la cuadrícula actual, se colocaba la O en esa casilla. Luego el jugador realizaba su movimiento, se localizaba el nuevo estado, se seleccionaba un nuevo movimiento, y así sucesivamente, hasta que terminaba el juego. ^{[ 12 ]}

Cuando el juego terminó, el jugador humano observó el resultado. A medida que se desarrollaba el juego, cada caja de cerillas utilizada en el turno de MENACE volvía a colocar su bandeja entreabierta, y la cuenta utilizada se guardaba aparte, de modo que se registraban las elecciones de movimientos de MENACE y los estados del juego a los que pertenecían. Michie describió su sistema de refuerzo con "recompensa" y "castigo". Una vez finalizado el juego, si MENACE había ganado, recibía una "recompensa" por su victoria. Las cuentas retiradas mostraban la secuencia de los movimientos ganadores. ^{[ 17 ]} Estas se devolvían a sus respectivas bandejas, fácilmente identificables ya que estaban ligeramente abiertas, junto con tres cuentas de bonificación del mismo color. ^{[ 11 ]} De esta manera, en juegos futuros, MENACE tendría más probabilidades de repetir esos movimientos ganadores, reforzando así las estrategias ganadoras. Si perdía, las cuentas retiradas no se devolvían, "castigando" a MENACE, lo que significaba que en el futuro sería menos probable, y eventualmente incapaz si faltaba una cuenta de ese color, de repetir los movimientos que causaban una derrota. ^{[ 4 ] [ 8 ]} Si el juego terminaba en empate, se añadía una cuenta adicional a cada casilla. ^{[ 11 ]}

MENACE, de Donald Michie, demostró que una computadora podía aprender de los fracasos y los éxitos para mejorar en una tarea. ^{[ 17 ]} Utilizó principios que se convertirían en fundamentales en el campo del aprendizaje automático antes de que se teorizaran adecuadamente. Por ejemplo, la combinación de cómo MENACE comienza con un número igual de tipos de cuentas en cada caja de cerillas, y cómo estas se seleccionan al azar, crea un comportamiento de aprendizaje similar a la inicialización de pesos en las redes neuronales artificiales modernas . ^{[ 20 ]} En 1968, Donald Michie y RA Chambers crearon otro algoritmo basado en BOXES llamado GLEE (Game Learning Expectimaxing Engine) que tenía que aprender a equilibrar un poste sobre un carro. ^{[ 21 ]}

Después de la rotunda recepción de MENACE, Michie fue invitado a la Oficina de Investigación Naval de los Estados Unidos , donde se le encargó construir un programa que ejecutara BOXES para una computadora IBM para su uso en la Universidad de Stanford . ^{[ 22 ]} Michie creó un programa de simulación de MENACE en una computadora Pegasus 2 con la ayuda de D. Martin. ^{[ 5 ]} 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. ^{[ 12 ]} Su algoritmo convergió más tarde en el algoritmo Q-Learning de Christopher Watkin . ^{[ 23 ]} Aunque no como una computadora funcional, en ejemplos de demostración, MENACE se ha utilizado como ayuda didáctica para varias clases de redes neuronales, ^{[ 24 ] [ 25 ] [ 26 ]} incluyendo una demostración pública del investigador del University College London Matthew Scroggs. ^{[ 27 ] [ 28 ]} Una copia de MENACE construida por Scroggs apareció en las Conferencias Navideñas de la Royal Institution de 2019 , ^{[ 29 ] [ 30 ]} y en un episodio de QI XL de 2023. ^{[ 31 ]}

MENACE se menciona en el cuento de Fred Saberhagen de 1963 , Without A Thought , y en la novela de Thomas J Ryan de 1977, The Adolescence of P-1 . ^{[ 32 ]} En su libro de 2023 , The Future , la autora Naomi Alderman incluye una conferencia ficticia con una descripción detallada de MENACE.

• Hexapawn
• Aprendizaje por refuerzo

• Michie, D.; Chambers, RA (1968), "BOXES: Un experimento en control adaptativo", Machine Intelligence , Edimburgo, Reino Unido: Oliver and Boyd, S2CID 18229198 – vía Semantic Scholar , el artículo de Michie y R. A. Chambers sobre las implicaciones de IA de BOXES y MENACE.
• Russell, David W. (2012), La metodología BOXES: Control dinámico de caja negra , Springer London, ISBN 978-1849965286, un libro sobre el algoritmo "Boxes" empleado por MENACE.

• Simulación en línea de MENACE