Man vs Machine showdown in the board game Go

man vs machine board game go 300x240 picture

Can man defeat machine once again in the game of Go?

Do you remember when the world watched IBM’s ‘Deep Blue’ supercomputer challenge grandmaster Garry Kasparov across the chess board?

It was almost 15 years ago now, but it was big news at the time, shocking news for some, because the computer won.

The era of the machine?

Many believed that it marked the beginning of the era of machine supremacy in the realm of board games.

After all, chess is one of the most difficult and elegant board games known to man and the machine defeated our world champion.

The bet

But John Tromp, computer scientist and avid fan of the board game Go, disagreed. What’s more, Tromp boldly put his money where his mouth is, saying:

“I would happily bet that I won’t be beaten in a 10 game match before the year 2011.”

He then put $1000 down on the table to prove he was serious. The game? Go.

board game go 300x200 picture

The board game Go: Ancient, addictive, unsolvable?

The game of Go

But what is Go? It’s an ancient game of strategy which originated in China thousands of years ago and is still played by millions throughout Asia today. It also has a growing following throughout the rest of the world.

Tromp’s challenge proved too tantalizing for Darren Cook, who agreed to what became known as the Shodan Go Bet.

Go uses the same grading system that martial arts do and shodan is basically the Japanese term for black belt.

And John Tromp is a black belt of this mental martial art. A player skilled enough to represent a serious challenge for computers to overcome.

The game was on, but that was way back in 1997, so what happened?

Tromping the machine

Cook wisely waited as long as possible, to give the machines more time to improve, politely refusing whenever Tromp cheekily offered to raise the stakes. The dust finally settled at the end of 2010, or did it?

It was no sure thing, but Tromp put on a good showing, destroying the computer four games to nil. Cook coughed up the money.

However, the story doesn’t end there. Just like the machines challenged Kasparov (who also won his first match) to a rematch, they are now challenging Tromp to one.

This time the challenge comes from Japan, where top Go players can earn millions of dollars playing in the professional leagues.

A new challenger

The challenger is Yoji Ojima’s Zen19 computer program and the games will be held from Friday, January 13 – Wednesday January 18, 2012.

When asked whether he was nervous about starting the match on Friday the 13th, Tromp replied “not at all, I was born on Friday the 13th.”

 

More about the game of Go

As you’ve gathered by now, Go is a fascinating board game that’s been played for thousands of years. It’s also one of the few traditional games that still defy computers.

The rules of Go are simple, and you can learn the basics and start having fun in just a few minutes. However, it takes many years to become a master.

This website is all about Go. If you’d like to find out more about the game you can visit this page. And if you’re interested in learning Go, just click here.

Who do you think will win?

What do you think? Do the odds favor John Tromp or Zen19? Final results:

  • Yes, John Tromp will win. (69%, 250 Votes)
  • No, the computer will win. (31%, 110 Votes)

Results

Zen ended up winning 3 games to 1. Here are the final results:

See a commentary of game 2

If you’d like to see some analysis of one of the games, have a look at my commentary of game 2.

Technical details

For those of you who are interested in the hardware, Zen19 is sporting a dual 6-core Xeon X5680 (overclocked to 4.2Ghz). The approximate cost of the machine is 350,000 yen (about $4375 USD).

Zen19 uses a Monte Carlo Tree Search algorithm, which is now common among all leading computer Go programs.

A special thanks to Darren Cook and John Tromp for providing details and quotes for this article. You can find out more about the Shodan Go Bet on Darren’s website and visit John Tromp’s site to learn more about him.

About David Ormerod

David likes teaching, learning, playing and writing about the game Go. He's taught hundreds of people to play Go, including many children at schools in Australia. In 2010 David was the Australian representative at the 31st World Amateur Go Championships. He's a 5 dan amateur Go player and is the editor of Go Game Guru. You can find David on Google+ and follow Go Game Guru on Facebook, Google+ or Twitter.

Comments

  1. I think that computer will win, but i will on the Tromp’s side, if i get lucky to watch the matches. Zen pretty strong at fighting, it will be Very hard for John to win this match, i believe.

  2. I am a bit surprised this, potentially at least, already can be achieved on such normal hardware. Does that mean it would be a fait accompli on a large multiprocessor array?

    • In fact it’s alitlte bit hard to improve the level of a computer with hardware

      • Not so hard in fact; I remember seeing some interesting graphs from the computer go server which showed rating of various Monte Carlo bots with increasing power and it scaled pretty well, almost linear. Of course there is the issue of how accurate a reflection of strength those ratings were… The Fuego bots on OGS have quite a bit strength difference depending on number of playouts.

  3. Any idea how we can watch the games? Or at least get the sgf files to look through?

  4. Was it Zen who recently beat a pro at a 9×9 game?

  5. ChuckFisher says:

    I’ve seen many of zen’s games and its fascinating to watch. Zen has a very light style, eventually getting huge efficiency out of his stones (especially in the center). Also, last time I checked, zen19D was strong 5d, so Tromp will have his work cut out.

  6. The advantage Tromp has, is that he can study Zen. The question is, is he strong enough to understand Zen and turn his built in limitations to his advantage?

    • David Ormerod says:

      The first game certainly highlights Zen’s weakness in ko, which other people have commented on below too. I’d expect Tromp to make a note of this and exploit it throughout the series.

      Can a player who can’t fight ko effectively really be called a 4 dan yet? ;)

      • Harald Korneliussen says:

        If it is good enough in other areas, yes. Zen is clearly inferior to humans at some things, but it also has strengths in some situations, maybe situations we can’t even identify clearly yet. Its win rate is evidence of that.

        One fairly clear advantage of the computer, is that it now counts territoriy very quickly. This gives it an advantage over humans in fast games. But the game against Tromp is at fairly slow time controls…

      • But starting the ko with s4, that was a beautiful move which I missed. Even despite Zen’s mistakes on the left side I think if I took over and fought that ko, black could win the first game as he has zillions of huge threats. s4 meant that if black won that ko (getting m3 as a ko threat) he could kill the entire lower right corner after white follows up on his ko threat (which probably break the top right area).

  7. I’m at my second year of computer engineering, and I found about this game just today, casually reading about it from a computational point of view.

    Maybe I’m too new in the game to judge anything, but if they are going to play by the professional match rules [a big board and all that], I’d bet from Tromp.

    Go is much harder for a computer than for a human, and the complexity of calculations grows at an exponential rate with the board size, since some parts are NP-hard. Up to this, it seems just as difficult like chess for a computer.

    However, there’s a big drawback. In a chess game, it’s relatively easy to approximate the most interesting moves to analyze given a position. This may involve in quick evaluations of the material (what pieces do you have), the movement freedom, weak spots, and many other possible criteria.

    The Go game seems to lack sufficient criteria to quickly analyze a position, so a computer has to “think” way more to win a Go game against a proficient player than against a chess game.

    So IMO, I don’t think Zen’s machine is powerful enough to win. Can’t say much of the Monte Carlo algorithm without more information, but it must have NP-hard parts.

    • So, you just learned about the game, know nothing about how Monte Carlo works, and just dismiss it out of hand? ok.

      • Please, don’t get me wrong. I have some basic ideas of how Monte Carlo’s algorithms work, it’s like an approximated way of solving hard problems. In the search tree, it probably selects the hopefully best nodes to analyze. But Monte Carlo is a classification of algorithms, there are many of them, and not all involve a Tree. Without knowing more about the implementation, I can’t estimate how complex it is.

        I’m sorry if I offended someone, it’s just that I haven’t seen any comment speaking about how hard is Go for computers, and simply told about what I found today. It’s in your right to skip my comment if you don’t find it interesting to read :)

        • Here is the paper you can read:
          http://www.lri.fr/~sebag/Examens_2008/UCT_ecml06.pdf

          Zen’s machine is very powerful. I use a similar set up for my computational problems. Underestimation at this point is fatal.

        • Harald Korneliussen says:

          DaGal, that Go is NP-hard is really not relevant. It is NP-hard for humans too, we don’t have any special powers to solve such problems (actually, it’s even worse than NP-hard, it is in some higher category in complexity theory, depending on whether you use superko or not).

          Go programming, and monte carlo tree search algorithms in general is a really exciting topic to study. They do things with it which would have been thought pretty impossible ten years ago. You should look into it.

    • Go is more complicated than chess (for computer) because of many reasons, there are many “hard” tasks for computer when deciding next move: complicated furikawari, positional judgement, proper order of moves, appropriate ko-fight, cutting and living/dying groups (status of not completely isolated groups, that can be connected or cutted eventually). Summary: the Value of next move is very hard to compute. And there much more variations (explosion of choices) than in chess (u can compare http://yeschinatour.com/static/photologue/photos/cache/go-game-03_leading.jpg).
      Even in case of computer has Monte Carlo, Patterns, Fuseki knowledge base.. its hard, but go is hard for human too, and human can make mistakes (even professional players) so.. will se the result

    • Actually, more than merely NP-hard, typical games are at least PSPACE-hard. A good rule of thumb: nontrivial single-agent search problems are NPish, nontrivial adversarial (double-agent) search problems are PSPACEish. But computational complexity alone is a very weak way to argue that humans will win. Greater complexity hurts humans too, so you must look at the specifics of the game.

      Go is undoubtedly harder than chess for computers to be good relative to human play, but the gap is closing very quickly. It’s very possible for computers to prune down the search space drastically by heavily biasing good local shapes and patterns (which top programs do with great success), and monte-carlo playouts with local patterns are not a bad evaluator in Go, just like material is not bad in chess.

      Even as few as several hundred playouts on a 9×9 board can produce decent play, which is surprising when you consider the tremendous statistical noise that must occur when these playouts are divided between dozens of possible lines of play as you step even a few moves deep into the possible tactics and variations. They’re obviously worse and more expensive on 19×19, but they’re still pretty good.

  8. he could exploit zen’s weakness with ko or mirror go, but that essentially admits to Zen’s general superiority. European 2-3dan puts him around KGS 3-4dan. in a slower game (55 min), Zen shouldn’t be stronger than KGS 4 dan. The human has pride on the line, so I bet on him.

    • I agree with this and also think that if Tromp focuses on the center he has a really good chance. I have played Zen several times and it does considerably better if you let it develop thickness in the center. Honestly if I were taking black against Zen in this match I would open with tengen. The KGS 5d was a little misleading because of the time settings (which were designed to help Zen as much as possible), so 4d is probably more realistic.

  9. Wow, this will be amazing. I’m old enough to remember the Spassky/Fischer chess match, so to think that a computer has a chance of beating a human Go champion finally is awesome. (I think the computer will lose, though.)

    • John Tromp is a skilled amateur, but not a world champion. There’s still a significant gap between him and the world’s top players in Asia. We may eventually see computers challenge a world champion go player, but they have to get past Tromp first. That’s enough of a challenge for now.

      • Just another item, but relevant here: Hi Paul, here is Paul. Can I infer from this that there is no check on unique name? If I change mine to, say, PaulB, are my previous posts then corrected to the new name?

        Kind regards,
        Paul (the other one)

        • David Ormerod says:

          Hi Paul, there isn’t a check for a unique name because we don’t require you to login to leave a comment. However, when you provide your email address (which is kept secret) it’s used to generate a unique image for your comments that identifies you as being different from other Pauls.

          You might have seen that some people have other pictures displaying next to their comments? If you’d like to use a different image too, you can register the email address you use to comment here at http://gravatar.com and upload an image. Go Game Guru will display that image next to all your comments making it very clear that you are Paul and not Paul :) .

  10. Go Zen19! Is it a coincidence that tomorrow a similar match will begin, between shogi program bonkras and retired pro Yonenaga?

  11. is it broadcast on kgs?

  12. Hideki Kato says:

    Just a correction. The author of Zen is not me but Yoji Ojima (ZenAuthor on KGS). I’m providing the machine for this match.

  13. While shodan may be equivalent to a black belt, it is worth pointing out that there is still a huge gap between shodan and professional level, and while such a contest as this may be fun, it tells more about one player’s judgement of computer development than about whether computers will ever have a chance against the strongest humans.

  14. I’m wondering, will any of these games be commented? I’ve been trying to follow it on KGS, but the commentary there is rather chaotic.

    • David Ormerod says:

      I was going to do some light commentary for the games, but I’ve been sick recently and haven’t had time. We’ll see what we can do.

  15. Yes I too would love to see some commentary attached to the sgf if it is at all possible. From this, the first game I’ve seen by Zen19, it is clear that its style of play is quite different from that of most human players, kind of “random” looking.There appears to be, at first glance, less of an obvious “narrative” in the game. It must be the mont carlo evaluations that cause this (I’m just guessing). If what I am saying makes sense, in that case I wonder if part of the strength of the computer comes from its moves looking more confusing to a human player who has not played the computer before. I myself am about 5-10kyu so it is hard for me gauge Zen19′s strength from this game… In general it is news to me that computers have become so strong! I have only taken up the game again recently. It is both exciting and a bit distressing. I don’t really relish online games getting too polluted by players who may begin using such computers as aids..

    • Persons being aided by computers while playing online: it is certainly a kind of cheating, but only of significance if the result is attributed to the skill of that person, or if it helps him to win some money or recognition. If you see the online opponent as just an unknown entity, you play the board and not the person. I don’t condone cheating at all, what is the fun of it by the way, but for you yourself trying to play the best you can, it should not make a difference whether that unknown opponent is helped or not. I just say this to help you to enjoy your online games without a foul taste in your mouth.

      Kind regards,
      Paul

  16. Hi, I am trying to find out whether the monte carlo methods used by programs like Zen use the whole board or whether they break the 19×19 board into smaller “sub boards” and then try playing random games within those smaller boundaries. It seems incredible to me that a monte carlo approach could be used on the entire 19×19 board. On the other hand, it also seems problematic to use the sub-board approach when it comes to large scale attack and defense. If anyone has insight or references about this, I’d greatly appreciate if it you’d pass it along.

    • It’s the whole board. But the playouts are not entirely random, they tend to use some basic shape knowledge to help e.g. 3-3 squares with things like peep a one-point jump then connect. However at one talk about computer Go I was interested to hear that making the move selection cleverer could actually decrease the strength of the bot overall.

      There’s plenty of literature on Monte Carlo Go, for example Pachi’s author Petr Baudis’ thesis: http://pasky.or.cz/go/prace.pdf. The code is also open source if you want to dig in to the details.

  17. then there is me. wondering where I can purchase a copy to play at home.

  18. It’s over. Zen won the last match today.

    • As i said earlier it is very hard in our days (since 2010-2011 year it is obvious, i think) to compete computers in go. Computer can fight strongly and you should be Top amateur or pro-level to win the game. Computer can just kill, or make it “many weak groups-game” and win.. or if u dont wanna fight, he can win by 0.5 due to excellent counting =)

  19. When i started to play Go (january 2009, 3 years ago) strongest computer was may be about 2 kyu on ordinary PC, or may be 2 dan on cluster with many processors/cores. There were rumours that Go is nice to play cause you easily can beat strongest computers. I was about 30 kyu, than last 3 month i became 10 kyu and obviously cannot beat 2-kyu computer, and than computer’s strength growth quicer than my and now i cannot beat computer again, what a shame )) i’m so unlucky.. why i started to play go?

  20. Don`t worry Nefeste! =) I started playing in 2004~2005 and I am 5k~3k. I think that we have to play and study go frequently (if we stop, we usually forget many things that we learned). Everybody can win against the bot Zen, we just need to keep improving.

    In my opinion, the huge pressure above Tromp help Zen to win the games. I am not saying that Zen didn`t deserved, no, I think Zen is a strong software and who programmed it has my congratulations. What I am trying to say is that if Tromp play again, I think that he can win. (Don’t feel down Tromp, you did well!).

    Zen will be available in KGS for anyone to play against it? I am curious to see which rank in KGS Zen would achieve…

  21. Well, till the computer can play without handicap against … let’s say players like Lee Sedol, Gu li, etc, we have nothing to be afraid of….

    • I am not sure jangalf, they said that Zen is about 4d KGS, and I heard that the difference between 9d KGS and 9p (Lee Sedol, Gu Li etc) isn’t 9 stones, it is something around 3 a 4 stones… I think that Zen with H9 (9 stones of handicap) would put some challenge, or at least, we could see how far is the difference between the strong software and the strongest human (before, this difference was too much far to measure). =)

      • tengen,

        There is a 0 stone difference between 9d KGS and Gu Li, because if Gu Li played on KGS he would be 9d. It is the highest rank, so you can’t just do a direct comparison.

        I think Zen with 9 stones would be really hard to beat for Gu Li. Zen beat a 9p with 6 stones before, and a 6p with 5 stones. 9 stones is ridiculous at high levels of play.

        • Bots can be pretty weak in using handy properly. There are ‘dynamic komi’ and some other techniques allowing bots not to play ‘i can move anywhere, im leading anyway’-moves.
          What about ratings: I think that 9d KGS and 9p (and even those 9p top pros like Gu Li or Lee Sedol) can be about 2-3 handy difference, cause top KGS players is like 2p, and if some reasonable 9p players would play KGS (say 10-20 9p’s) in this case, current 9d KGS players become 8d or 7d very soon and KGS ratings would be recalculated for other players too.

        • Sorry, i mean “reasonable amount of 9p players (say 10-20 9p’s)”, but not only 1 player

        • I remember when kghin points his goal “i wanna be 9d kgs [and 9d tygem]” in account description. This Goal equals to “i wanna be in top-10 [active] KGS players” – its not easy task, cause if other 9d’s not so active, you should constantly beat 7-8 d’s in handy games oO.. Im not satisfied in KGS amount of Very good players and amount of high dans games played, so rating system suffers from this lack of games too. btw there are 10 or 11 dans on KGS if we measure they rating points: Hearts is “10d”, MilanMilan “10d” etc… =)

Speak your mind