304 Matchboxes Filled With Beans Are The Perfect Tic-Tac-Toe Opponent

Illustration for article titled 304 Matchboxes Filled With Beans Are The Perfect Tic-Tac-Toe Opponent

It's tough to find a partner who's always ready and willing to play, so James Bridle attempted to build one. 304 matchboxes and several bags of beans later he had MENACE, a Tic-Tac-Toe playing "machine" designed to learn and improve.


James' MENACE (Matchbox Educable Noughts And Crosses Engine) is based on a manual machine learning concept from back in the 1960s, and frankly I'm not really surprised that I've never heard of it before. The idea behind the "machine" is that the 19,683 possible Tic-Tac-Toe board layouts are condensed into a mere 304 (due to how many are "rotationally identical") and a selection process for moves is put in place. The best part, of course, is that the machine "learns" as the operator adds beans for winning moves and thereby provides indication as to what has worked in the past.

It's a pretty neat low-tech idea, but I think I'll still stick to playing a human opponent instead of a bunch of matchboxes. [Flickr via Short Term Memory Loss via Boing Boing]



A human has to act as a zero-knowledge operator, looking in the appropriate box, counting the beans, making the appropriate move, and moving beans from one box to another. It's not meant to be practical, but to illustrate machine learning. This was featured in the March 1962 Scientific American in an article by Martin Gardner, and the idea later figured in a Fred Saberhagen "Berserker" short story. #mechanicaltictactoe