MENACE: The Matchbox Marvel of Early Artificial Intelligence

The Matchbox Educable Noughts and Crosses Engine , more commonly known by its acronym MENACE, stands as a peculiar yet profoundly significant artifact in the nascent history of artificial intelligence . Conceived and meticulously constructed in 1961 by the visionary artificial intelligence researcher Donald Michie and his associate Roger Chambers, this ingenious device was not forged from silicon and circuits, but from a surprisingly mundane collection of 304 matchboxes and beads. Its purpose was elegantly simple yet remarkably ambitious: to engage human opponents in games of noughts and crosses (also known as tic-tac-toe), not merely to play, but to learn and refine its strategy through the process of reinforcement learning . MENACE represents one of the earliest and most tangible embodiments of machines designed to exhibit intelligent behavior, predating many of the computational resources that we now take for granted.

The genesis of MENACE was born out of necessity and ingenuity. In an era where sophisticated computing hardware was a rare and inaccessible commodity, particularly for academic researchers, Michie and Chambers circumvented the lack of immediate access to a conventional computer. Their solution was to translate the abstract concepts of artificial intelligence into a physical, tangible form. Each matchbox was ingeniously repurposed to represent a specific, unique configuration of the noughts and crosses grid. This allowed the machine to encode and process the vast number of possible game states. Initially, MENACE’s plays were entirely random, a blank slate of possibility. However, through a process of iterative learning, it began to discard strategies that led to defeat and reinforce those that resulted in victory. This self-improvement mechanism, driven by the outcomes of its games, was a fundamental step towards creating adaptive intelligence. The year 1961 saw Michie himself engage in a tournament against his creation, an experiment designed to test and observe MENACE’s developing strategic capabilities, particularly its response to various opening moves.

The impact of MENACE extended far beyond its immediate demonstration. Following its initial “tournament” against Michie, the engine showcased a remarkable capacity for artificial intelligence, demonstrating a discernible strategic acumen. Michie’s subsequent analyses and essays, which delved into the intricacies of MENACE’s “weight initialisation” – a concept eerily prescient of modern neural network techniques – and the underlying BOXES algorithm , became seminal works within the computer science research community. The profound contributions of Michie to the burgeoning field of machine learning were widely recognized, leading to prestigious commissions, including being tasked twice with programming simulations of MENACE on actual computers, a testament to the enduring significance of his matchbox marvel.

Origin

Donald Michie , a figure whose intellectual journey spanned pivotal moments in 20th-century science and warfare, brought a unique perspective to the challenge of artificial intelligence. Having served as a vital member of the code-breaking team at Bletchley Park during World War II , where he contributed to the decryption of the complex Tunny Code , Michie possessed a deep understanding of intricate systems and logical deduction. Fifteen years after the war, his ambition was to push the boundaries of computational prowess further, exploring concepts that would later be recognized as foundational to convolutional neural networks .

The practical constraints of the early 1960s, specifically the scarcity and cost of advanced computer equipment, presented a significant hurdle. Michie, finding himself without readily available computing resources for his ambitious projects, ingeniously devised an alternative. He decided to manifest his exploration of artificial intelligence in a more unconventional, tangible format: a fully functional mechanical computer ingeniously constructed from humble matchboxes and simple beads. This approach allowed him to not only demonstrate but also experiment with the very essence of machine learning and adaptive behavior.

The very creation of MENACE was, in part, fueled by a spirited bet with a fellow computer scientist who had declared such a machine to be an impossibility. Undeterred, Michie embraced the challenge. What began as a “fun project” to collect and define each unique game state within a matchbox quickly evolved into a sophisticated demonstration tool. By 1963, Michie had not only completed his seminal essay, “Experiments on the mechanization of game-learning,” detailing MENACE’s operation, but also co-authored an essay on the BOXES Algorithm with R. A. Chambers. This period also saw the establishment of a dedicated AI research unit in Hope Park Square, Edinburgh , Scotland , a hub for pioneering work in the field.

MENACE’s learning process was a direct reflection of its operational design. It learned by engaging in numerous games of noughts and crosses. In each instance, the human player, acting as an instructor of sorts, would effectively “confiscate” the beads corresponding to moves that led to a losing outcome. This action served to disqualify those particular strategies. Conversely, winning strategies were reinforced by the addition of extra beads, making those moves more probable in future games. This iterative process constituted an early form of the Reinforcement Loop , a fundamental algorithm that discards unsuccessful strategies and amplifies successful ones. MENACE, from its inception, began as a system operating purely on chance, gradually evolving its decision-making capabilities through experience.

Composition

The physical manifestation of MENACE was a striking testament to its unconventional construction. It comprised 304 matchboxes , meticulously glued together in an arrangement reminiscent of a compact chest of drawers. Each individual matchbox was assigned a unique code number, serving as a key to a comprehensive chart. This chart contained detailed drawings of tic-tac-toe game grids, illustrating every conceivable configuration of X’s, O’s, and empty squares. These configurations represented all possible permutations that could arise during the progression of a game. After systematically eliminating duplicate arrangements – those that were merely rotations or mirror images of existing patterns – MENACE’s operational framework utilized precisely 304 distinct matchboxes, each corresponding to a unique game state.

Within each matchbox tray, a carefully curated collection of colored beads resided. Each distinct color signified a specific move, corresponding to a particular square on the game grid. Consequently, matchboxes representing game states where certain positions on the grid were already occupied would naturally lack beads for those positions, reflecting the constraints of the game. Adding a further layer of mechanical ingenuity, the front of each tray featured two strategically placed pieces of card, forming a “V” shape. The apex of this “V” was positioned to point directly at the front of the matchbox. Michie and his team referred to MENACE’s core operational logic as the “Boxes” algorithm, a nomenclature directly inspired by the physical apparatus central to its function. The initial phase of the “Boxes” algorithm involved five distinct stages, each meticulously defining and establishing precedents for the rules governing the algorithm’s interaction with the game.

Operation

The operational mechanics of MENACE were a fascinating blend of mechanical action and programmed learning, particularly evident in its gameplay. MENACE assumed the role of the second player, “O,” in the game of noughts and crosses. This convention was established because the matchboxes were designed to represent permutations relevant from the perspective of the “X” player. To determine MENACE’s next move, an operator or the human opponent would first locate the matchbox that corresponded to the current state of the game grid. This also included considering any rotations or mirror images of the grid that might align with a stored configuration. For instance, at the very commencement of a game, the operator would select the matchbox representing a completely empty grid.

Upon identification, the matchbox tray would be carefully withdrawn. A gentle shake of the tray would cause the beads within to shift and move. The bead that ultimately settled at the point of the “V” shape at the front of the tray was the move MENACE had “chosen.” The color of this chosen bead dictated the position on the grid where MENACE would place its “O.” After accounting for any necessary rotations or flips to align the chosen matchbox configuration with the current grid state, the “O” would be marked on the designated square. The human player would then make their move, establishing a new game state, and the process would repeat: locating the corresponding matchbox, selecting a bead, and placing the “O” until the game reached its conclusion.

The critical learning phase occurred once a game had concluded. The human player would observe the outcome – a win, loss, or draw for MENACE. As the game unfolded, each matchbox that had been utilized for MENACE’s turns was left slightly ajar, and the bead that had been selected was set aside. This meticulously recorded MENACE’s sequence of moves and the specific game states they corresponded to. Michie articulated his reinforcement system through the concepts of “reward” and “punishment.” If MENACE emerged victorious, it received a “reward.” The removed beads from the winning sequence were returned to their respective matchbox trays, easily identifiable by their slightly open state. Furthermore, three additional beads of the same color were added to each tray. This “reward” mechanism increased the probability that MENACE would select those same winning moves in future games, thereby reinforcing successful strategies.

Conversely, if MENACE lost a game, the beads corresponding to its moves were not returned. This act of “punishment” decreased the likelihood of MENACE repeating those losing moves. Over time, if a particular bead color became entirely absent from a tray, MENACE would be rendered incapable of making that specific move, effectively learning to avoid detrimental actions. In instances where a game resulted in a draw, a single additional bead was added to each matchbox tray that had been involved in the game, a neutral reinforcement that acknowledged the balanced outcome.

Results in Practice

The performance of MENACE, particularly in its interactions with human players employing different strategies, yielded fascinating insights into the efficacy of its learning mechanism.

Optimal Strategy

The game of noughts and crosses is well-understood to possess an optimal strategy . This strategy dictates that a player must simultaneously block the opponent from forming a winning line while also attempting to create their own. However, when both players adhere strictly to this optimal strategy, the game invariably concludes in a draw. MENACE’s ability to learn this optimal strategy meant that, over time, its games against a human player also employing this strategy would increasingly result in draws. The machine’s probability of winning, naturally, saw a more significant and rapid increase when pitted against an opponent who played randomly, without strategic consideration.

When MENACE engaged with a player consistently employing the optimal strategy, the likelihood of a draw escalated to near certainty. Donald Michie’s own tournament against MENACE in 1961 provided empirical evidence of this phenomenon. After approximately twenty games, both Michie and MENACE achieved a consistent draw rate. Michie’s tournament was meticulously documented, tracking MENACE’s strategic evolution in response to his varied opening moves. Initially, Michie consistently opened with “Variant 0,” the center square. Around the 15-game mark, MENACE began to abandon all opening moves that did not involve a corner square. After approximately 20 games, Michie shifted his consistent opening to “Variant 1,” the bottom-right square. By game 60, he reverted to Variant 0. As the game count approached 80, Michie experimented with “Variant 2,” the top-middle square. At game 110, he moved to “Variant 3,” the top-right square. At 135 games, he adopted “Variant 4,” the middle-right square. Finally, at 190 games, he returned to Variant 1, and by game 210, he was back to Variant 0. This detailed record illustrates MENACE’s adaptability and its gradual learning of optimal responses to different strategic approaches.

The changes observed in the beads within the “2” boxes, which likely corresponded to specific game states or move sequences, provided a quantitative measure of MENACE’s learning. The trend in these bead changes across different variants and game numbers is as follows:

This table highlights how MENACE adjusted its internal “weights” (represented by bead counts) based on the outcomes of games played with different opening strategies.

Correlation

The patterns of MENACE’s wins and losses, when plotted on scatter graphs , revealed distinct trends that were directly influenced by the strategy employed by its human opponent. When playing against an opponent who made random moves, MENACE demonstrated an almost perfectly positive correlation, indicating a high rate of success. In contrast, when playing against an opponent utilizing the optimal strategy, the correlation for wins showed a slower, more gradual increase, reflecting the inherent difficulty of converting draws into wins in such a scenario.

It is crucial to note that MENACE’s reinforcement learning did not guarantee a perfectly deterministic outcome in every instance. The algorithm retained an element of randomness, leading to uncertain conclusions in certain situations. After the j-th round of learning, the correlation for near-perfect play could be mathematically approximated. The formula provided is:

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

Here, $V_i$ represents the outcome of the game at round i (+1 for a win, 0 for a draw, and -1 for a loss), and D is a decay factor, calculated as the average of past win and loss values. Furthermore, $M_n$ denotes the multiplier for the n-th round of the game, influencing the reinforcement applied. The specific reinforcement applied based on the game’s outcome is detailed as follows:

• Won: $R_{n}=M_{n}^{-\mu +1}$
• Draw: $R_{n}=M_{n}^{-\mu }$
• Lost: $R_{n}=M_{n}^{-\mu -1}$

These formulas illustrate the mathematical underpinnings of how MENACE adjusted its “confidence” in certain moves based on past results, a foundational concept in reinforcement learning.

Legacy

Donald Michie’s MENACE stands as a landmark achievement, unequivocally demonstrating that a machine could indeed learn from its experiences – both successes and failures – to improve its performance in a given task. It embodied core principles that would later become central tenets of machine learning , even before these concepts were formally theorized and widely recognized. The method by which MENACE began with an equal distribution of different bead types in each matchbox, and subsequently made random selections from these, mirrors the fundamental concept of weight initialization in modern artificial neural networks , a sophisticated technique used to kickstart the learning process.

The profound impact of MENACE led to further groundbreaking work. In 1968, Donald Michie, collaborating again with R.A. Chambers, developed another algorithm based on the BOXES methodology, named GLEE (Game Learning Expectimaxing Engine). GLEE was designed to tackle a more complex challenge: learning to balance a pole on a moving cart, pushing the boundaries of machine learning into control problems.

Following the significant reception of MENACE, Michie was invited to the Office of Naval Research in the United States. There, he was commissioned to develop a program capable of running the BOXES algorithm on an IBM Computer, intended for use at Stanford University . Michie also successfully created a simulation of MENACE on a Pegasus 2 computer, with invaluable assistance from D. Martin. The enduring fascination with MENACE has spurred numerous recreations in recent years, both in its original physical matchbox form and as sophisticated computer programs. Its core algorithm, the BOXES method, is recognized as a precursor and influence on Christopher Watkin’s Q-Learning algorithm, a cornerstone of modern reinforcement learning.

While not a functional computer in the contemporary sense, MENACE has found a valuable role as an educational tool for teaching the principles of neural networks. Its tangible, accessible nature makes complex concepts understandable to students. Demonstrations, such as those conducted by University College London researcher Matthew Scroggs, have brought MENACE to life for new generations. A replica of MENACE, meticulously built by Scroggs, was prominently featured in the prestigious Royal Institution Christmas Lectures in 2019. More recently, its story and significance were highlighted in a 2023 episode of the popular BBC quiz show QI XL .

MENACE’s influence has also permeated the realm of fiction. It is referenced in Fred Saberhagen ’s 1963 short story Without A Thought , a tale exploring artificial intelligence and its implications. The machine also makes an appearance in Thomas J Ryan’s 1977 novel The Adolescence of P-1 . More recently, in her 2023 book The Future, author Naomi Alderman included a fictional lecture that provides a detailed and engaging overview of MENACE, ensuring its continued relevance in discussions about the evolution of artificial intelligence.

See also

• Hexapawn
• Reinforcement learning