Teaching a computer to learn

[Łukasz Kaiser] programmed a computer to play Tic-tac-toe. That doesn’t sound very remarkable until you realize he never told his computer the rules of Tic-tac-toe. The computer learned the rules by itself after watching a video of two people playing the game (link to actual paper - PDF warning).

[Łukasz] wrote a small program in C++ to recognize the placement of objects on a Tic-tac-toe, Connect 4, and Breakthough board. This program sifts through winning and losing games along with illegal moves to generate a Lambda calculus-like rule set for the relevant game. Even though [Łukasz] has only programmed a computer to learn simple games such as Tic-tac-toe, Connect 4, and Breakthrough, he plans to move up to more complex games such as Chess.

The fact that [Łukasz] programmed a computer to actually learn the rules of a game gives us pause; in one of the fabulous lectures [Richard Feynman] gave to freshman physics students in 1964, the subject of Chess came up. [Feynman] drew parallels between learning Chess and performing research. Every move is hypothesis testing, and when a very strange move occurs – castling, en passant, and the promotion of a pawn, for instance – the theory of the rules of the game must be reworked. Likewise, when extremely strange stuff happens in physics – particle/wave duality, and the existence of black holes – scientific theory is advanced.

Yes, teaching a computer to learn the rules of Tic-tac-toe may seem irrelevant, but given the same learning process can be applied to other fields such as medicine, economics, and just about every science, it’s not hard to see how cool [Łukasz]‘ work is.

via extremetech

Comments

  1. jon says:

    Give it a crack at go, rules are simple, but the game is extremely complicated.

  2. Aaron says:

    the same learning process can be applied to other fields such as medicine, economics, and just about every science

    Sure, because drug discovery, for example, isn’t any more complicated than chess…

    • Bazu says:

      Yes, and no, depending on if you’re working with a machine that can run simulations, or not. I don’t know anything about drug discovery, but take economics. Have the machine form a hypothesis, have a feed to plug in real time numbers and shift for the best predicted results at your action and you can have a pretty good guess at what the effect would be. If drug discovery is anything like the number crunching in economics, then chess is a very simple form of the same thing, which is guessing a chain of events that happen after an action or a string of actions….. baby steps, man. baby steps =)

  3. Montaray Jack says:

    Sussman attains enlightenment

    In the days when Sussman was a novice, Minsky once came to him as he sat hacking at the PDP-6.

    “What are you doing?”, asked Minsky.

    “I am training a randomly wired neural net to play Tic-Tac-Toe” Sussman replied.

    “Why is the net wired randomly?”, asked Minsky.

    “I do not want it to have any preconceptions of how to play”, Sussman said.

    Minsky then shut his eyes.

    “Why do you close your eyes?”, Sussman asked his teacher.

    “So that the room will be empty.”

    At that moment, Sussman was enlightened.

  4. Bob says:

    If you are telling what moves are illegal then by elimination you are telling it what moves are legal, it is not machine learning it is just obfuscating. So either this has been misreported, or he has fooled you and/or himself.

  5. Montaray Jack says:

    Instead of the flippant reply (And Al-Koan see http://catb.org/jargon/html/koans.html ) I gave above, One of the approaches to AI that I liked was the method Douglas Hofstadtler documents in Fluid Concepts and Creative Analogies, trying to make a computer program solve the Junior Jumble the same way we humans often do it, by gloming likely vowels and connsonents together than those gloms together and so on.

    A lot of different approaches to AI has been tried, most of it written in Lisp.

    • Weapons from an elegant age…
      http://xkcd.com/297/

      Warning: Following post will be incomprehensible.

      Lots of AI was written in things besides lisp, and much of it was non-public, non-hyped and pretty effective for every application except stock market picks and other random walk problems where the problem domain is really vast!

      It’s like fuzzy logic – no longer loved, but bayesian filters (popular these days) are basically the same thing.

      Classical AI is often thought by the public to be a way to get “intellect in a box”… but in fact, AI is simply thinking about thinking, and then implementing some of what we thought while thinking about thinking. The problem was the hype – caused by a few individuals trying to make a buck by telling people that they were thinking about thinking about thinking, and they thought that if those people thought about the fact that they were thinking about thinking about thinking, they would provide a lot of funding for anyone who could…

      Well, it all fizzled out when the hype was distilled, and ended up being nothing more than classical symbolic manipulation and a bit of heuristic cheating.

      I remain a true believer, and if biochemists ever figure out how to get a functional ATP (or whatever molecular magic thrills you the most) transport mechanism to emulate lisp primitives, then we’re on.*

      *[insert small caveat about sustainable reaction cycles left to readers who dabble in biochemistry and know about implementation issues...]

  6. Notn4 says:

    All I can think of right now is Wargames :D

    Soon that computer will be calling himself Johsua and wanting to simulate Global Thermonuclear War :)

    Damn, gotta go watch that movie now, bye

    • Bradley says:

      That movie just came on AMC only a day ago. C64′s unite!

      • I have the same computer. I had a perfect IMSAI system, which was glorious in it’s completeness – hazeltines, quad 8″ floppies (1.2MB on a disk!) and a wonderful decwriter which I loved.

        I loaned it to a guy who built a museum, and the bastard promptly did a lot of thing that ended up with my beautiful system getting sold for $3k on ebay. I found out much later, through a third party who lost a Digital system.

        Now all I have is a crappy system, with a smoked power switch – the idiots at imsai ran 120VAC power through the front panel. I guess I should fix it up before fischer-freitas vanishes into thin air.

        Loved that movie.

  7. Dr. DFTBA says:

    I’d like to see this released as a computer program that sees through the webcam. It would be cool to see it play games like Tsuro or something.

  8. Chris C. says:

    Learning a fixed set of exact rules? Boring, even if it can do it for Chess.

    It’s only interesting if it can come up with a *new* rule that wasn’t previously known to us. Something that allows it to solve a complex problem with less reliance on brute-force testing of every possibility. That’s what’s needed for real-world advances in medicine, economics, and science. And real-world problems typically have fuzzy inputs and rules, not the exact ones of board games.

    Nothing to see here, move along.

    • LongFist says:

      Your comments would be valid except for one important point: it matters not that “you’ve seen it before” – this is a different approach. Where’s yours? You make it sound like something *anybody* can do, so where are the rest of them, all lame and boring? Your argument is invalid.

      MAYBE this is a different approach — I haven’t seen them mention LISP yet (except in passing, in the comments), but I *did* see a direct mention of C++. A DIFFERENT approach already! And sometimes it’s just good to celebrate somebody else’s breakthrough, because without them, we wouldn’t have been able to read your critical-yet-baseless remarks.

      And we eagerly await your release of an awesome AI system – one that does “something exciting”. Whatever that turns out to be.

      Hats off to you, [Łukasz Kaiser]: Keep on hacking! o/

      • Chris C. says:

        1) I didn’t say I’d seen it before, or that it was easy. You entirely made that up. I just said it was boring.
        2) Language is irrelevant. You can write anything, in any Turing-complete language. Just because something is written in C++ instead of LISP doesn’t make it a new approach.
        3) Whether I personally have an “awesome AI system” is also irrelevant. It’s just a tired old technique to try and divert attention to the other party, when you have nothing intelligent to say.

        Maybe I was overly critical. Fine, it’a a neat hack.

        But it is NOT anywhere near a “learning process can be applied to other fields such as medicine, economics, and just about every science”. It does NOT make the computer any better at playing those games than programming the rules into Toss by hand. It is NOT even referred to as AI by Łukasz.

        And it’s important that people understand that about what is actually presented here, without any hype or hyperbole. Which is critical, but not baseless as you claim.

        If Łukasz can eventually extend this into something truly groundbreaking, then he’s going to do so. I’m sure his feelings aren’t so fragile as yours, and he’s not going to stop just because I called it boring.

  9. caedisius says:

    One of the professors as UCSC has done a lot of interesting work on having a program learn chess from the ground up, Morph

  10. steve d says:

    This was written about in 1977 book “The Adolescence of P-1″. Concept is from a March 1962 article on game theory and how to teach matchboxes to play tic-tac-toe.

    Very good project!! I hope you carry it further.

  11. SuperNurd says:

    Now my question is if it can learn how to love?

    Just kidding but it would be intresting to see it play tic tac toe against a bot pre programed (I.E. what already exists as a computer in versus).

    Can it learn the ability to guess, also is it restricted to know only as much as it’s teacher taught it or can it infer and surpass the teacher!

    • I suspect that robotic asian massage parlors can’t be that far away. They should appear at about the same time McDonald’s figures out how to replace 40% of their workforce with sandwich making robots – again, no big deal.

      However, their primitive soft drink automation system is bullshit. Who designed that thing? It’s as bad as those 1960′s coffee/cocoa dispensers.

      I can only assume that patents are to blame.

  12. Julien says:

    I just lost the game!

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