El Matchbox Educable Noughts and Crosses Engine (a veces llamado Machine Educable Noughts and Crosses Engine o MENACE ) fue una computadora mecánica hecha de 304 cajas de cerillas diseñada y construida por el investigador de inteligencia artificial Donald Michie en 1961. Fue diseñado para jugar con oponentes humanos en juegos de tres en raya devolviendo un movimiento para cualquier estado de juego dado y para refinar su estrategia a través del aprendizaje de refuerzo .
Michie no tenía una computadora disponible, así que resolvió esta restricción construyéndola con cajas de cerillas. Las cajas de cerillas que utilizó Michie representaban cada una una única disposición posible de una cuadrícula de tres en raya. Cuando la computadora jugó por primera vez, elegía movimientos al azar en función de la disposición actual. A medida que jugaba más partidas, a través de un ciclo de refuerzo, descalificaba las estrategias que conducían a partidas perdedoras y complementaba las estrategias que conducían a partidas ganadoras. Michie organizó un torneo contra MENACE en 1961, en el que experimentó con diferentes aperturas.
Tras el primer torneo de MENACE contra Michie, la inteligencia artificial demostró ser eficaz en su estrategia. 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 informática. Michie fue galardonado por su contribución a la investigación del aprendizaje automático y recibió dos encargos para programar una simulación de MENACE en una computadora real.
Donald Michie (1923–2007) había formado parte del equipo que descifró el código alemán Tunny durante la Segunda Guerra Mundial . [1] Quince años después, quiso demostrar aún más su destreza matemática y computacional con una red neuronal convolucional temprana . Como no se podía conseguir equipo informático para tales usos, [2] y Michie no tenía un ordenador disponible, [2] decidió mostrar y demostrar la inteligencia artificial en un formato más esotérico y construyó un ordenador mecánico funcional a partir de cajas de cerillas y cuentas. [3] [4]
MENACE fue construido como resultado de una apuesta con un colega informático que postuló que una máquina así era imposible. [5] 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. [6] Michie completó su ensayo sobre MENACE en 1963, [4] "Experimentos sobre la mecanización del aprendizaje de juegos", así como su ensayo sobre el algoritmo BOXES, escrito con RA Chambers [6] y había construido una unidad de investigación de IA en Hope Park Square, Edimburgo , Escocia . [7]
MENACE aprendió a jugar partidas cada vez más largas de ceros y cruces. Cada vez, eliminaba una estrategia perdedora, ya que el jugador humano confiscaba las cuentas que correspondían a cada movimiento. [4] Reforzaba las estrategias ganadoras haciendo que los movimientos fueran más probables, al proporcionar cuentas adicionales. [8] Esta fue una de las primeras versiones del Reinforcement Loop , el algoritmo esquemático de bucle del algoritmo, descartando las estrategias fallidas hasta que solo quedan las ganadoras. [4] Este modelo comienza como completamente aleatorio y aprende gradualmente. [9]
MENACE se creó a partir de 304 cajas de cerillas pegadas entre sí en una disposición similar a la de una cómoda. [10] Cada caja tenía un número de código, que se introducía en un diagrama. Este diagrama tenía dibujos de cuadrículas de juego de tres en raya con varias configuraciones de X , O y casillas vacías, [4] correspondientes a todas las posibles permutaciones por las que podía pasar un juego a medida que avanzaba. [11] Después de eliminar las configuraciones duplicadas (las que eran simplemente rotaciones o imágenes especulares de otras configuraciones), MENACE utilizó 304 permutaciones en su diagrama y, por lo tanto, esa misma cantidad de cajas de cerillas. [12]
Cada bandeja individual de la caja de cerillas contenía una colección de cuentas de colores. [13] Cada color representaba un movimiento en un cuadrado de la cuadrícula de juego, por lo que las cajas de cerillas con disposiciones en las que las posiciones en la cuadrícula ya estaban ocupadas no tendrían cuentas para esa posición. Además, en la parte delantera de la bandeja había dos piezas de cartón adicionales en forma de "V", [10] la punta de la "V" apuntando hacia la parte delantera de la caja de cerillas. [11] Michie y su equipo de inteligencia artificial llamaron al algoritmo de MENACE "Cajas", [7] en honor al aparato utilizado para la máquina. La primera etapa, "Cajas", funcionó en cinco fases, cada una de las cuales estableció una definición y un precedente para las reglas del algoritmo en relación con el juego. [14]
MENACE jugó primero, como O, ya que todas las cajas de cerillas representaban permutaciones solo relevantes 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 reflejada de la misma. Por ejemplo, al comienzo de un juego, esta sería la caja de cerillas para una cuadrícula vacía. Se quitaría la bandeja y se agitaría ligeramente para mover las cuentas. [4] Luego, la cuenta que había rodado hasta la punta de la forma de "V" en la parte delantera de la bandeja era el movimiento que MENACE había elegido hacer. [4] Luego, su color se usaba como la posición para jugar y, después de tener en cuenta las rotaciones o giros 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 había terminado, el jugador humano observaba el resultado del juego. A medida que se jugaba, cada caja de cerillas que se usaba para el turno de MENACE tenía su bandeja devuelta a ella entreabierta, y la cuenta utilizada se dejaba a un lado, de modo que la elección de movimientos de MENACE y los estados del juego a los que pertenecían quedaban registrados. Michie describió su sistema de refuerzo con "recompensa" y "castigo". Una vez que el juego terminaba, si MENACE había ganado, recibirí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, así como tres cuentas de bonificación del mismo color. [11] De esta manera, en futuras partidas MENACE tendría más probabilidades de repetir esos movimientos ganadores, reforzando las estrategias ganadoras. Si perdía, las cuentas retiradas no se devolvían, "castigando" a MENACE, y significando que en el futuro sería menos probable, y eventualmente incapaz si ese color de cuenta desapareciera, de repetir los movimientos que causan una pérdida. [3] [8] Si el juego era un empate, se añadía una cuenta adicional a cada casilla. [11]
El juego de tres en raya tiene una estrategia óptima bien conocida. [18] Un jugador debe colocar su símbolo de manera que impida que el otro jugador complete filas y, al mismo tiempo, él mismo complete una fila. Sin embargo, si ambos jugadores usan esta estrategia, el juego siempre termina en empate. [18] Si el jugador humano está familiarizado con la estrategia óptima y MENACE puede aprenderla rápidamente, entonces los juegos eventualmente terminarán solo en empate. La probabilidad de que la computadora gane aumenta rápidamente cuando la computadora juega contra un oponente que juega al azar. [3]
Cuando se juega contra un jugador que utiliza una estrategia óptima, las probabilidades de un empate aumentan al 100%. En el torneo oficial de Donald Michie contra MENACE en 1961 [4] utilizó una estrategia óptima, y él y la computadora comenzaron a empatar consistentemente después de veinte juegos. El torneo de Michie [19] tuvo los siguientes hitos: Michie comenzó abriendo consistentemente con la "Variante 0", la casilla central. A los 15 juegos, MENACE abandonó todas las aperturas que no fueran de esquina. A poco más de 20, Michie cambió a usar consistentemente la "Variante 1", la casilla inferior derecha. A los 60, regresó a la Variante 0. Cuando se acercaba a los 80 juegos, pasó a la "Variante 2", la casilla superior central. A los 110, cambió a la "Variante 3", la casilla superior derecha. A los 135, cambió a la "Variante 4", la casilla central derecha. A los 190, regresó a la Variante 1, y a los 210, regresó a la Variante 0.
La tendencia en los cambios de cuentas en las cajas "2" es: [19]
Dependiendo de la estrategia empleada por el jugador humano, MENACE produce una tendencia diferente en los gráficos de dispersión de victorias. [4] El uso de un turno aleatorio del jugador humano da como resultado una tendencia positiva casi perfecta. Jugar con la estrategia óptima da como resultado un aumento ligeramente más lento. [3] El refuerzo no crea un estándar perfecto de victorias; el algoritmo extraerá conclusiones aleatorias e inciertas cada vez. Después de la ronda j , la correlación del juego casi perfecto es:
Donde V i es el resultado (+1 es victoria, 0 es empate y -1 es derrota) y D es el factor de decaimiento (promedio de los valores pasados de victorias y derrotas). A continuación, M n es el multiplicador para la ronda n del juego. [4]
El algoritmo MENACE de Donald Michie demostró que un ordenador podía aprender de los fracasos y los éxitos para convertirse en un buen ordenador en una tarea. [17] Utilizó lo que se convertirían en principios básicos en el campo del aprendizaje automático antes de que se hubieran teorizado adecuadamente. Por ejemplo, la combinación de cómo MENACE comienza con la misma cantidad de tipos de cuentas en cada caja de cerillas 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 . [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 palo en un carro. [21]
Después de la resonante recepción de MENACE, Michie fue invitado a la Oficina de Investigación Naval de los EE. UU., 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. [4] Ha habido múltiples recreaciones de MENACE en años más recientes, tanto en su forma física original como como programa de computadora. [12] Su algoritmo fue posteriormente convergido 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] incluida una demostración pública del investigador del University College de Londres, Matthew Scroggs. [27] [28] Una copia de MENACE construida por Scroggs apareció en las Conferencias de Navidad de la Royal Institution de 2019 , [29] [30] y en un episodio de 2023 de QI XL . [31]
MENACE se menciona en el cuento Without A Thought de Fred Saberhagen de 1963 y en la novela The Adolescence of P-1 de Thomas J. Ryan de 1977. [32] En su libro de 2023 The Future , la autora Naomi Alderman incluye una conferencia ficticia con una descripción detallada de MENACE.
