brainwagon "There is much pleasure in useless knowledge." — Bertrand Russell


Donald Michie, Alan Turing, Martin Gardner, and Tic Tac Toe

As anyone who reads my blog with any regularity will tell you, I like to read and learn new things. The problem with being self taught and also easily distracted means that you often learn a great deal, but don't always perceive the connections and scope of what you are learning. I found another example today while surfing.

Years ago, I remember reading one of Martin Gardner's Mathematical Games columns (from March, 1962, in case you want to look it up) where he described an interesting machine for playing tic-tac-toe. It was made entirely out of matchboxes, each one of which had a tic tac toe position on the top. Inside was a collection of colored beads. Each color specified a possible legal move for the position on top. The idea was that you'd play a game by drawing these beads from the appropriate box, and making the appropriate move. At the end of the game, you'd remove the bead from the last box that sent you along the losing path. Eventually, all the losing moves get removed, and the machine plays perfect tic-tac-toe. Gardner showed how this same idea could be used to create a matchbox computer to play hexapawn, a simple game played with six pawns on a 3x3 board.

I really haven't given it much thought since then. Many of you have probably read this article in one of the collections of Gardner's columns.

But today, I was surfing through links and reread some of the details. I found that the machine was called MENACE (Matchbox Educable Naughts and Crosses Engine) and was invented in 1960 by a gentleman named Donald Michie. And it turns out that he's a pretty interesting guy.

He was a colleague and friend of Alan Turing, and worked with him at Bletchley Park. Apparently Michie, Turing and Jack Good were all involved in the British code breaking efforts, and in the creation of Collosus, the first digital programmable computer which was used to crack the German "Tunny" teleprinter code. (Good and Michie were apparently two of the authors of the General Report on Tunny, a report on the cracking of the code which has only in recent years become declassified). None of this work could have been known by Martin Gardner at the time of this publication. Of course, this was also true of Turing's work as well.

Turing made a huge impact in several related disciplines: in mathematical logic and computation, in his wartime efforts in code breaking, and in his role in creating some of the first digital computers. Turing also became interested in mathematics in biology, writing about the chemical foundations of morphogenesis and predicting oscillatory chemical reactions. Michie received a doctorate in biology from Oxford, but returned to have a profound and lasting influence on artificial intelligence. Oh, and that modest little paper on Tic Tac Toe? One of the first instances of reinforcement learning.

Very cool, to discover that the little bit of reading you did as a teen, which seemed like an insignificant game at the time, actually has profound threads which stretch out into lots of different areas.

Donald Michie's Home Page
Trial and Error, the paper describing MENACE