Computer learns from tic-tac-toe

menace-tic-tac-toe-computer

MENACE, the Matchbox Educable Noughts And Crosses Engine, is a fancy name for a machine that plays Tic-Tac-Toe. The concept is a product of Professor [Donald Mitchie]‘s work in the 1960′s and was featured as an example in the “A New THEORY of AWESOMENESS and MIRACLES” talk given at this year’s UK games conference.

[James Bridle] built this fascinating example of how a computational system can learn from its successes and failures. Each box corresponds to one of 304 different board layouts. The operator uses an index sheet to locate the box that corresponds to the current state, shakes the box, then looks to see which bean has randomly fallen into a partition in the box. The color/type of bean corresponds to a space that the machine has “chosen” for that move. If MENACE won the game a bead matching the move that was played would be added to each box used. If MENACE lost, a bead would be removed from each box used. This way the machine cannot make the exact same mistakes twice, and is more likely to repeat successful solutions.

[James] notes that he couldn’t find any evidence of this machine actually being built before. It is possible that this was always a theoretical device but now we’ve seen an actual build. We consider this to be a computer because it is calculating moves based on probability of success but what do you think? If you’re thirsting for more pictures there’s plenty to see in the Flickr set he’s posted.

[via BoingBoing]

29 thoughts on “Computer learns from tic-tac-toe

  1. @Jason
    That’s exactly what I was thinking!
    It doesn’t just play tick-tac-toe, It learns from its mistakes; and then stops playing altogether because it realizes that it is futile to try to win.

    It is “A strange game. The only winning move is not to play.”

  2. This sounds a lot like the game Fred Saberhagen described in his first(?) Berserker story. a 3×3 matrix, boxes with colored beads to select moves based on a match to the current layout, moves in wining games are returned to the boxes, losing moves discarded.

  3. Jason and cyrozap. I imagine two possible reasons for this. Either Mr. Szczys has not seen the film (it was from 1983), for he probably deserves a bit of good-natured ribbing from us (it is one of the earliest films which exposed the world to hacking and actually got a few details right), or he intentionally left it out in order to let the commenters run with all of the Wargames gags.

  4. First to make a program that runs a simulation to create the AI with theoretical matchboxes and beads will win over 9000 internets.

  5. I’ve built this before: in 6th grade. But we used paper cups with a board position written on it and the next moves drawn with colored arrows. Inside the cup were candies whose colors corresponded to the arrows. A move consisted of locating the cup, shaking it, chosing a candy, and following the arrow to the next cup. If a move lost the game, you ate the candy!

  6. This is just a variant of Genetic Programming and a Neural Network; there are whole series of books written on the subject.

  7. It has memory (programmed and organized by choosing which games you win or lose) and a logic function (IF). However… I cannot find a way to make it conditionally branch or copy the contents of one bit of memory to an arbitrary other bit, so my vote is “Not a computer”.

    I haven’t found a way to do it with two machines playing each other repeatedly either, whatever I run in my head just ends up with both machines ending up with memory contents that repeat with fixed period regardless of initial state.

  8. The match box go engine also on his site, is hilarious. Made of beans and match boxes it is slightly bigger than the crab nebula. According to math.

  9. @thethirdmoose

    That was my first thought. I had marvin’s book, ‘The hangmans noose….’. He talks about the matchbox bean engine in that book too. I specifically remembering him talking about a kid who built one but one and ate a jelly bean each time the “computer” lost….

  10. PT Barnum would be jealous. No one else had shitty parents in the 80s that bought one of these things from a yard sale? I have a merlin right now but it is circuit-bent for MIDI sequencing. Or how about “Greetings professor Falcon, would you like to play a game?” The answer is still no Joshua and the attention whore who thought this was somehow original and post-worthy or even worth the ram on a digicam lmao.

  11. @Sean

    “However… I cannot find a way to make it conditionally branch or copy the contents of one bit of memory to an arbitrary other bit, so my vote is ‘Not a computer’.”

    Your definition of computer makes no sense. It performs a computation. It is a computer. It doesn’t have to be Turing complete. A slide rule is a computer.

    Alex Dodge

  12. @Alex Dodge
    No specific definition of computer was given, so I arbitrarily chose one (my bad). Admittedly there are other definitions, I’ve tried to come up with a more interesting argument that relies on fewer assumptions:

    As far as I can tell the machine has two functions: “Output random number from 1-N”, and “Store a given value for N at a given address”. If the machine is capable of computation, I’m not sure what that computation would be, since that first function is not computable (and of high entropy)! The second function is just memory.

    Thanks for the reply, I enjoyed thinking about this! (Also I still use a slide rule.)

  13. @Sean

    First of all, sorry for being a dick last night. I was a lot harsher than I meant to be, on rereading it. I must have been overtired.

    You have a point. Maybe randomness does change the game.

    I’m used to dealing with cognition, not computation, and “learn from your mistakes” does seem like a cognitive task.

    Since neurons are just tiny analogue computers, I’m tempted to say that anything that’s a cognitive task is also a computation. But, I could be mixing up the definitions. I guess it all depends on whether your theory of computation allows for probabilistic outcomes. (Quantum computing?)

    Tangentially relevant quotation:

    “The question of whether a computer can think is no more interesting than the question of whether a submarine can swim.” –Dijkstra

    Alex Dodge

  14. The system consisting of the matchboxes and the person doing the bean removal/addition might qualify as a computer, but the boxes themselves do not.

    @Mic: Where would you find matchboxes big enough to hold the hundreds of beans representing all possible moves for a go position?

  15. I remember something similar called Socrates and Mr. Hound, involving a deck of cards where each suit was a cardinal directional move for Socrates the fox, and Mr. Hound plodded along a square track near the edge of the board. Whenever Mr. Hound caught Socrates, the last n cards would be removed and reshuffed. Eventually, Socrates would learn to outwit Mr. Hound. I built it out of Lego in the early 1970′s.

    Anybody remember what book this was from?

  16. @Robotguy:

    Yes! That’s how the character Greg Burgess learned to write software that could learn, leading to his creation of the self-aware networked AI in the book ‘The Adolescence of P-1′.

    I hunted up the book and read it because it was reviewed in Byte magazine back in the early ’80s. A very good read.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s