Computers Learn to Play Go

Posted by jrosenhouse on March 12, 2009
(27)
More »

We chess players have had to put up with taunts from our Go playing counterparts for quite some time. First there was the jibe that Go is so much easier to learn than chess. Then the dubious charge that Go is actually more complex than chess. Some have argued that the superiority of Go over chess represents he difference between Eastern and Western values. (In Go you start with an empty board and gradually build up structures that control territory. Chess is just a bloodbath where rival armies try to slaughter the other guy’s leader.) And then there was the undeniable fact that chess-playing computers have been humiliating top-level human competition for some time, while the best Go playing software had it’s work cut out for it beating the average dog.

Well no more!

Just a few years ago, the best Go programs were routinely beaten by skilled children, even when given a head start. Artificial intelligence researchers routinely said that computers capable of beating our best were literally unthinkable. And so it was. Until now.

“It’s a silly human conceit that such a domain would exist, that there’s something only we can figure out with our wetware brains,” said David Doshay, a University of California at Santa Cruz computer scientist. “Because at the same time, another set of humans is just as busily saying, ‘Yes, but we can knock this problem into another domain, and solve it using these machines.’”

In February, at the Taiwan Open — Go’s popularity in East Asia roughly compares to America’s enthusiasm for golf – a program called MoGo beat two professionals. At an exhibition in Chicago, the Many Faces program beat another pro. The programs still had a head start, but the trend is clear.

Take that!

Kidding aside, like most mathematicians I went through a Go phase in graduate school, an interest that was recently revived when some friends of mine got interested in the game. It’s a terrific game, no question about it. It undoubtedly comes out on top when measured by the ratio of richness of play divided by ease of learning to play. It’s just that, having already spent so much time learning to play chess, it’s hard to find time to start learning yet another game.

Keywords: , ,
(27)
More »

Comments

  1. #1 The Science Pundit
    March 12, 2009

    Take that!

    Yeah! In your face, Dalai Lama! :-P

  2. #2 Shadow Caster
    March 12, 2009

    Never heard of Go.

  3. #3 Alpha
    March 12, 2009

    As an ardent go player, I can’t help but note that these programs only won against pros when given pretty sizable handicaps!

  4. #4 Sam K.
    March 12, 2009

    To put the handicap issue into perspective, at the professional level, each pro rank is about 1/3 of a stone, so a 1p pro and 9p pro have a difference of about 3 stones. That’s less than HALF the handicap than MoGo got! 4 more stones (the 7 it got) is probably somewhere around a 4-5d amateur, which is a relatively strong amateur, but still not that close to pro. Go is a great game because it *has* handicaps, and the difficulty scales very naturally without changing the nature of the game (unlike removing pawns, rooks, etc. in Chess), but this is a far cry from a Go program beating a pro. That being said, computer Go has certainly progressed a lot, especially with the onslaught of pure UCT and hybrid UCT based programs.

  5. #5 Jason Rosenhouse
    March 12, 2009

    Shadow Caster -

    Rent A Beautiful Mind. It’s the game their playing in the scene where Russell Crowe gets disgusted over losing.

    Alpha and Sam K -

    The first time a computer beat a master at chess people said, well, they’ll never beat a grandmaster. Then the computers beat a grandmaster and people said well, they’ll never beat a top grandmaster. Then they did that, and people said well, they’ll never beat a world champion. Then they did that.

    Today they’re winning games with huge handicaps. Tomorrow it’s nine-dan, shmine-dan.

    Also, Sam, did you mean a 4-5k amateur and a 9d pro?

  6. #6 tbell
    March 12, 2009

    when they can beat the 9d pros, i’ll be looking forward to them teaching the humans how to play 21×21 and larger board sizes.

  7. #7 Juuro
    March 13, 2009

    I’m looking forward to the day when a given AI can play go (at any level), diagnose the bawling coming from the kids’ room, juggle cookies in and out of the oven, answer the door, all in unscripted real time.

  8. #8 HennepinCountyLawyer
    March 13, 2009

    I think it’s really cool when humans can build something that can do what humans can’t do.

    Sort of like the first time my son built a tower of blocks taller than he was.

  9. #9 Malcolm
    March 13, 2009

    @Jason Rosenhouse
    “Also, Sam, did you mean a 4-5k amateur and a 9d pro?”

    I think Sam meant what he wrote. Rankings low to high go:
    25k – 1k, 1d – 9d, 1p – 9p

    where ‘d’ ranks are amateur dans, and ‘p’ ranks are Pro.

    And there’s a big difference between the Am and Pro standards..

  10. #10 Cannonball Jones
    March 13, 2009

    I love Go and always took some sort of pride in the fact that it was just too complex for computers to handle. At least if Terminator ever happened we’d be able to challenge the machines to a game for control of the world. No more. Damn.

  11. #11 Thony C.
    March 13, 2009

    Some have argued that the superiority of Go over chess represents he difference between Eastern and Western values.

    Given that chess like Go is an Eastern game this argument is a more than a little bit dumb.

  12. #12 Duke York
    March 13, 2009

    Given that chess like Go is an Eastern game this argument is a more than a little bit dumb.

    So what game has the West given us? Bridge?

    Hmmm… Aren’t computers even worse at card games than Go? We still have a chance against our robot overlords!

    Duke

  13. #13 Sam K.
    March 13, 2009

    @Jason Rosenhouse
    Malcolm is correct, I meant 4-5 [amateur] dan. I don’t disagree with your basic point– this is definitely huge; I was just saying that the story is somewhat misleading.

  14. #14 James W
    March 13, 2009

    Duke –

    bridge is a fabulous game – I love it very much – but thinking about the mechanics of it, I reckon a decent AI could kick humanity’s ass at it.

    Now poker – that may save us yet.

    In fact, I’m sure there’s a significant number of sci-fi TV show pots essentially predicated on this very issue – that computers can’t manage that quintessentially human skill of bluffing.

    And if it’s true in sci-fi, it MUST be true.

    James

  15. #15 Thony C.
    March 13, 2009

    Given that chess like Go is an Eastern game this argument is a more than a little bit dumb.

    So what game has the West given us? Bridge?

    Hmmm… Aren’t computers even worse at card games than Go?

    It would appear that playing cards were also invented in China ;)

  16. #16 Johan
    March 13, 2009

    “Now poker – that may save us yet. ”

    Alas, no. See http://www.cs.ualberta.ca/~games/poker/

  17. #17 Jason Rosenhouse
    March 13, 2009

    Malcolm –

    Thanks for he clarification on the rankings. I was unaware of the professional ratings.

    Thony C –

    It’s true that chess is originally an Eastern game, but at least since the nineteenth century chess has been far more popular in the West. Even today China is the only Asian country with a significant presence in world chess, and that’s a very recent thing. Meanwhile, Go is far more popular in Asia than it is in the West. In light of that I don’t think it’s unreasonable to describe chess as a Western game and Go as an Eastern one.

  18. #18 Thony C.
    March 14, 2009

    It’s true that chess is originally an Eastern game, but at least since the nineteenth century chess has been far more popular in the West. Even today China is the only Asian country with a significant presence in world chess, and that’s a very recent thing. Meanwhile, Go is far more popular in Asia than it is in the West. In light of that I don’t think it’s unreasonable to describe chess as a Western game and Go as an Eastern one.

    Jason:

    Chess is more widespread and popular than Go in East Asia, however it is Chinese chess and not so-called western or international chess. Like western chess, Chinese chess is “just a bloodbath where rival armies try to slaughter the other guy’s leader” so I stick to my view that the statement “Go characterizes Eastern values and chess Western ones” is bovine manure ;)

  19. #19 Jason Rosenhouse
    March 14, 2009

    Thony C –

    I certainly agree that it is silly to describe Go as characterizing Eastern values and chess Western ones. I was simply defending the characterization of Go as an Eastern game and chess as a Western one.

    And somehow I don’t think there was really any confusion about which sort of chess I was referring to in my earlier comment. :)

  20. #20 Thony C.
    March 14, 2009

    So-called international chess is a westernized (castrated!) version of an eastern game ;-)

  21. #21 Erik 12345
    March 14, 2009

    Even today China is the only Asian country with a significant presence in world chess, and that’s a very recent thing.

    Hmmm… for example Vishy Anand and Koneru Humpy are Asian.

  22. #22 Thony C.
    March 15, 2009

    Even today China is the only Asian country with a significant presence in world chess…

    …for example Vishy Anand…[is] Asian

    Ouch!

  23. #23 Jason Rosenhouse
    March 15, 2009

    Thony C and Erik -

    So this is how it’s going to be? You’re really going to show up to nitpick me to death?

    The word “Asian” does not mean just “Located on the continent of Asia.” It is also the polite term for what used to be called the Orient, which in context was clearly what I was talking about.

    Koneru Humpy, strong as she is, is not among the top players in the world. Not even close. And Anand is a lonely exception in India, which has some strong players but is not a major force in international chess. At the recently completed chess olympiad in Dresden, for example, China had the third highest rated team overall, behind only Russia and Ukraine. Inida was ranked thirteenth.

  24. #24 Erik 12345
    March 16, 2009

    If you want more than nitpicking, you have to make bigger and more mistakes :)

    I didn’t know Americans use ‘Asian’ to mean ‘East Asian’ (Wikipedia confirms it).

    I disagree about India and Koneru Humpy. Being 13th in the olympiad is pretty good, as is being 8th on the men’s, and 5th on the women’s, country rating list (average rating of each country’s top 10 players). Koneru Humpy is number 2 on the women’s January 2009 rating list and she recently finished second in a competition that only lacked Polgar. India is in the top, though it lacks breadth.

  25. #25 Thony C.
    March 16, 2009

    When used colloquially, as you wish to be considered as using it, Asian in English English, as opposed to American English, refers not to East Asians but to South Asians i.e. Indians, Pakistanis etc.; isn’t language a wonderful thing? ;)

  26. #26 Jason Rosenhouse
    March 16, 2009

    Erik -

    Okay, so maybe I was a bit hard on India.

    Thony C -

    Yes, language is indeed a wonderful thing. I didn’t know that about the differences between American English and English English.

  27. #27 jose
    April 21, 2009

    Did they use better algorhytms or better hardware?