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]

Comments

  1. kirov says:

    hackaday finally has a worthy hack.

  2. thethirdmoose says:
  3. Jason says:

    How is it there is not one WOPR joke in here?

  4. cyrozap says:

    @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.”

  5. Ken says:

    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.

  6. Sam says:

    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.

  7. Oxin says:

    (In my best TTS voice) Would you like to play a game?

  8. John Berube says:

    came for the wargames references left mildly satisfied.

  9. some dude says:

    CAN we say adem from ‘WAR GAMES’

  10. mrbob says:

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

  11. Robotguy says:

    This is the way P-1 was brought to life…
    http://en.wikipedia.org/wiki/The_Adolescence_of_P-1

  12. tj says:

    @Jason: I was just about to do that..

    Was this conference held in Las Vegas by any chance?

  13. monkeyslayer56 says:

    that is really cool :)

  14. MacK says:

    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!

  15. Almost_There says:

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

  16. Karl says:

    How about that – an organic impilmentation of a “Fuzzy” logic network / computer

  17. sly says:

    “Shall we play a game?”

  18. Sean says:

    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.

  19. Mic says:

    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.

  20. gehan g says:

    @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….

  21. blue carbuncle says:

    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.

  22. Alex Dodge says:

    @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

  23. Sean says:

    @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.)

  24. Alex Dodge says:

    @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

  25. Zahlman says:

    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?

  26. Leigh says:

    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?

  27. gyro_john says:

    @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.

  28. Kiyoshi says:

    “How about a nice game of chess?”

  29. Steve says:

    I was involved in building one while at school in about 1972/73 – Chippenham School – Wiltshire – UK

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

Follow

Get every new post delivered to your Inbox.

Join 91,277 other followers