MENACE
# MENACE

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

Donald Michie había estado en el equipo que estaba descifrando el código Lorenz durante la Segunda Guerra Mundial. 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, y Michie no tenía una computadora disponible, 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.

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

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. 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. 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. 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, correspondientes a todas las posibles permutaciones que un juego podía atravesar a medida que avanzaba. 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.

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

## Operación

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

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

## Resultados en la práctica

### Estrategia óptima

Tres en línea tiene una estrategia óptima bien conocida. 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. 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.

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

| 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

Dependiendo de la estrategia empleada por el jugador humano, MENACE produce una tendencia diferente en los gráficos de dispersión de victorias. 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. 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:

${1-D \over D-D^{(j+2)})}\sum _{i=0}^{j}D^{(ji+1)}V_{i}$

Donde $V_i$ 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_n$ es el multiplicador de la enésima ronda del juego.

| Salida | Reforzamiento |
| - | - |
| Victoria | $R_{n}=M_{n}^{-\mu +1}$ |
| Empate | $R_{n}=M_{n}^{-\mu }$ |
| Derrota | $R_{n}=M_{n}^{-\mu -1}$ |

## Legado

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

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

