Google
 

English|日本語

  

The Shodan Go Bet

I am a natural optimist. A hopeless optimist. I spend hours battling against myself with carefully constructed cynicism, but things still get past my guard. And one day, back in 1997, I made the mistake of putting my money where my mouth is. Let me tell you were it all started.
(The event was played at the end of December 2010; scroll down to the bottom of this page for the results.)

  



Go Bet II     The Bet Is Back!

At the end of 2010 John Tromp, in London, triumphed and I was forced to hand over the $1000. In mid January 2012 John suggested to see if the bots have improved in the past 12 months. Yamato, the author of Zen, was reluctant to take part a year ago, unsure of the outcome (*). Well, this time he agreed and a best of five match was arranged.

The match was played online, on KGS, this time. Players got 90 minutes each, with byo-yomi of 25 stones every 10 minutes. Chinese rules and 7.5pt komi were the same as last time. By the way, no money was wagered this time. Once bitten, twice shy! (But, also, John would not have taken the bet, as he was not confident of victory going in to the match.)

The Games

New York TimeJapan TimeResult
Game 1Fri, Jan 13th, 8pmSat, Jan 14th, 10amWon by John, as white. SGF
A weak opening by Zen, but John failed to take advantage of this, and Zen seemed to be leading for much of the game. Black 61 and 67 (on the left) were weak, but Zen seemed to lose the game with some poor moves from move 120 onwards. Ingo Althöfer used Many Faces to make charts of winning percentages and expected territory; the former, at least, seems to match the expert view of the game.
Game 2Sat, Jan 14th, 8pmSun, Jan 15th, 10amWon by Zen, as white. SGF
The game was close, perhaps favouring white (Zen), but was decided when black's group at the bottom was killed (with white 126, if I've understood the experts). The white 120/122 combination was praised; Zen's earlier move at 74 in that area was not. Charts of winning percentages and expected territory as analyzed by Many Faces (thanks to Ingo again).
Game 3Sun, Jan 15th, 8pmMon, Jan 16th, 10amWon by Zen, as black. SGF
Black tried to make a big centre moyo. At first I thought the consensus was this was too thin and the position was good for white (John); but the stronger dan players disagreed, pointing out that white has his own weaknesses. Black H9 (move 38) was considered good (Crazystone analysis also switched to prefering black at this point). White went in too deeply with L7 and N7 (moves 45 and 47), and Zen handled it well, leaving white well behind. John resigned soon after. Charts of winning percentages and expected territory as analyzed by Many Faces
Game 4Mon, Jan 16th, 8pmTue, Jan 17th, 10amWon by Zen, as white. SGF
A close start, but black 43 at H9 was considered too thin. White 48 at G9 should have been at the key point of H6, thereby giving black a chance to play it. But instead he played N6, white got H6 and black was always behind from then. Black 73 was better at P9? White 74 (M10) was considered a mistake. White 84 was considered a mistake, but in the end white made it live. The semeai was hard enough to make the strong dans disagree, so white 84 may have been a good move after all. John bravely tried to keep the game complicated, but Zen kept his composure making no mistakes big enough to exploit, and John resigned at move 178. Zen won the match 3-1. Charts of winning percentages and expected territory as analyzed by Many Faces

Want more game analysis? Jeff Nowakowski (aka PaperTiger) set up review games and encouraged strong players to comment there. Not so many people for game 1 and game 2, but very useful to understand game 3 and game 4.

Detailed analysis by Remi Coulom's Crazy Stone program (which is about as strong as Zen) is available as a bzip file (132 KB) for game three, showing its prime variation at each move. For game four (399KB) the analysis is improved (and also more accurate, as it used a more powerful machine). Use a very recent browser to see the charts.

David Ormerod wrote about the game on Go Game Guru, and also gave an "over-commented" commentary for game 2.

Hardware

The hardware Zen ran on for this match was operated by Hideki Kato, and was a dual 6-core Xeon X5680 (over-clocked to 4.2Ghz).

With the over-clocking, this hardware is slightly more than twice as fast as the Amazon EC2 instance used for the London go bet. (Six to seven times faster than the notebook used for the first two games in that match.) A doubling in 12 months is a bit ahead of Moore's Law; but we were underpowered last year, relative to what I had hoped to use.

This hardware cost was about 350,000 yen (which is about US$4375 at current exchange rates).

The Zen cluster used in tournaments (zen19D, zen19S) adds two more machines (another 12 cores, giving 24 cores in total). Hideki Kato estimates it to be about one half to one stone stronger than the 12-core machine (Zen19N) by itself.

The software used in the match was Zen version 8.7.

Trivia

John claimed not to be worried about starting the match on Friday The Thirteenth, as he was born on one! (This proved true, as that was the day of the game he won.)

*: Also restrained by the contract with the publisher of Zen. Not a problem this time because Team DeepZen was operating Zen.

When Shodan?

Take my hand as we travel back, all the way back to 1997. Dolly The Sheep was cloned, China took back control of Hong Kong, Harry Potter was born, Mother Theresa and Princess Diana died. And, in May of that year, Kasparov was defeated by Deep Blue. Big news. The end of human intelligence. Robots are our new masters. Et cetera.

Deep Blue
Deep Blue

Hyperbole aside, a lot of people working in computer chess felt their job was done, and attention moved to go as the new Grand Challenge of Artificial Intelligence. Go, a 2500 year old board game, is considerably harder for computers to tackle than chess. Games last for more moves, and have more choices at each move, making the brute-force techniques that Deep Blue used ineffective.

Shodan can be described
as the level of a
strong amateur player

At the 3rd Fost Cup computer go tournament in Tokyo, in September 1997, the top programs were around 10 kyu, meaning 10 ranks below the level of 1-dan or shodan. Shodan can be described as the level of a serious, strong amateur player. In martial arts terms it means black belt. An absolute beginner is around 25 to 30 kyu. Most people can reach 10 kyu with a few months of serious study of the game; in contrast many keen players never make it to shodan. In other words, just about everyone who plays go seriously could crush the strongest computer program of that time. But shodan? Now that would be a serious opponent.

At that event in September 1997 I took a survey of programmers and other attendees asking when they thought they would see a shodan computer go program. Different countries have some rating drift, so I asked for "international shodan", defining that as roughly 3-dan in Japanese ranking, 2-dan in America, 1-dan European. I got the full range of replies from 1999 to 2050 or beyond, and published it to the computer-go mailing list. (See that email and the list).


John TrompJohn Tromp replied saying:
"I wonder if people would still make such optimistic estimates if they had to back it up with, say, a $1000 bet. I (dutch 1kyu) would happily bet that I won't be beaten in a 10 game match before the year 2011."

I took him up on that bet [1][2]. After all, surely computer go couldn't carry on not progressing forever?

I requested that it does not have to be my own program and does not have to be a commercially available program. John gave the additional condition that it can be any hardware that can be brought to the playing site. (See that email, my acceptance, and John's reply).

Darren Cook

The Dark Years

During the years that followed computer go did not really make much progress. Of course Moore's Law [3] was still in effect. Machines got faster. But faster machines generally just meant the programs played more quickly - they were not really making good use of the extra power. The strongest programs of the time were expert systems [4], trying to play go the same way a human plays it. Expert rules are time-consuming to add, and it is hard to resolve conflicts between them.

the programs ... were not really
making good use of the extra power

It has been my belief all along that what go needed was to find its own version of brute force, something that takes advantage of the computer's strengths. My hunch was huge pattern libraries: millions and millions of patterns (pattern meaning a certain arrangement of stones on the board that tell you how good a move there would be). But my own experiments in this direction did not work very well. Or very deep narrow search to get past the difficulties in estimating the score accurately in early and middle game, using patterns and heuristics [5] to guide the search to play out the most likely continuation. That did not work very well either [6].

I tried to hold out hope, but the couple of times that John suggested increasing the size of the bet I politely refused.

MCTS: glimmer of hope

In early 2006 MCTS (Monte Carlo Tree Search [7]) started being used to make strong 9x9 programs. The idea was crazy - have the computer play out random games, play out a lot of them, and choose the move leading to the position where randomness wins more. I would still say it is crazy, except for the inescapable fact that it works.

The algorithm scales - it is making
use of new computer power.

By the Autumn of 2008 all the world's strongest go programs, whether on 9x9 or 19x19, used MCTS. The change in strength has not been a small incremental step but a jump: perhaps five ranks. Even more important is that the algorithm scales - it is making use of new computer power. We just have to hang around, not do any more coding, and computer go programs will keep getting stronger.

Mogo, one of the strongest MCTS programs, has beaten high-ranking professionals in handicap games, using a large cluster (for instance around 15 Teraflops, using 55 minutes of thinking time to beat an 8-dan professional at a 9-stone handicap). Another program, Crazy Stone, has beat a 4-dan professional at 7 stone handicap, running on an 8-core computer. These results are all pointing to strength above shodan level, and then at the end of 2009 Zen played four even games with a 5-dan amateur and won one; Zen may have lost the other three but this is a promising result.

A Close Thing

Suddenly the bet looks like even odds. Or is that my optimism showing through again? John is now 2-dan (European), going on 3-dan, understands computer go, and will certainly know how to exploit any known weaknesses of the computer. The bet requires "hardware that can brought to the playing site", but is a supercomputer needed to get the level of play required?

We held a vote (now closed) to see what site visitors thought...

 


Please give your opinion on the other half of that original survey: when will a computer program beat the world's strongest player at go? In other words when will computer go be at where chess was in May 1997?
You can add comments after viewing results.




Latest News

Dec 29th, 2010: The final result was 4-0, which was disappointing, but not unreasonable. See to the left for a short summary of each game. We got good attendance on KGS, over 430 observers in some games. A big thanks to everyone for their interest and support!

Dec 28th, 2010: The first two games will be played today... John and I have both arrived in London safely, and are keen to get started. Results will be posted on this page, but John is the clear favourite (58% of the voting, with 21% for too close to call, and 21% for the computer). I am expecting it will be 4-1 to John, with 4-0 and 4-2 also possible.

June 2010: We have arranged to hold the match in London at the end of December - taking the “within 2010” deadline to the limit!

Thanks to the British Go Association we will be sharing the venue of the London Open Go Tournament. See the Competition Details page for more.

The voting, your opinion on who will win the bet, was neck and neck for a while, but recently John has pulled ahead with a quite distinctive lead. Well, at the time of writing I disagree with 78.5% of you as I still think it is Too Close To Call, but a warm Thank-You to the 30.3% who voted for me! Opinion on when computers will be at world champion level is all over the place. If you've not voted yet, please scroll down and do so.




Results!

WhenBlackWhiteResultHardware
Dec 28th, 12:15pm
SGF
Many FacesJohn TrompWhite won (by resignation)notebook
It started off promising, but black played a few weak moves between about move 35 and 60; it still thought the game was close past move 80, but then its groups started dying. By move 140 or so its win estimate was around 15%, and it was probably behind by 100+ points, so I resigned on its behalf.
Dec 28th, 4pm
SGF
John TrompMany FacesBlack won (by resignation)notebook
Many Faces seemed to come out of the opening ahead, and managed to hold its lead until move 120 or so (at least according to the computer and some kibbitzers on KGS), with the players each killing a large group of the other. Unfortunately the computer then got into a complex semeai and lost a corner group, thereby losing the game. It then thrashed around a lot before resigning at move 261. (White 122 at S17 instead of O13 looks like it would have been hard for white to then lose the game.)
Dec 29th, 10am
SGF
Many FacesJohn TrompWhite won (by resignation)EC2-gui
Many Faces played a strange opening at the bottom, quickly falling behind, but then coming back later and perhaps being ahead between moves 60 and 160. Then it started playing weird moves; perhaps it thought it had lost by half a point and was trying to complicate the game?
Dec 29th, 2pm
SGF
John TrompMany FacesBlack won (by resignation)EC2-gtp
Many Faces played two bad corners at the bottom, but then came out okay from a big complex fight in the left. But not enough to win. It held on for a long time in a lost position, thinking it was winning, then finally resigned.
The log file (328K zipped) that Many Faces produces is available for just this game; it shows in full detail what it thought at each move, the prime variation, alternative moves it considered, how many playouts it used for each move, etc. Published with David Fotland's permission.

The SGF files are from KGS, containing comments from the kibbitzers (people viewing and commenting on the game), with just minor fixes by me. The above short comments on each game are a mix of personal viewpoint (I am weaker than both players), and comments picked up in after-match discussion.

The "notebook" was i17-740QM (4 cores, running at 1.7Ghz; actually set to use 7 of 8 hyperthreaded cores). Linux operating system, and the 32-bit GUI version of ManyFaces, running under wine, using up to 1.5Gb of memory. About 10,000 playouts/second.

"EC2" was an "m2.4xlarge" instance on Amazon EC2, meaning 26 ECUs, 8 cores and 68.4Gb of memory. I'm guessing that means a dual xeon, 3.2Ghz CPU, or similar. OS was Windows Server. "EC2-gui" means the 32-bit GUI version, using up to 1.5Gb of memory. "EC2-gtp" means the 64-bit commandline version, set to use 12 Gb of memory. The EC2 hardware was doing about 20,000 playouts/second; that is twice as fast as my notebook but only very slightly stronger in real terms. See the Using Amazon EC2 page for more details on the setup.




More...

Related Links and references

Competition Details

Using Amazon EC2

Notes

[1]: Incidentally, looking at the mailing list archives I see I wasn't the only other optimist. John Clarke also wrote: "Emphatically yes! Although it'll be almost a crime to take your money. I wasn't one of the speculators on that list but I think it's an absolute certainty that there'll be very strong programs by then." However, I don't believe this was taken as a serious acceptance of the bet.

[2]: This kind of bet may be illegal in certain countries. Therefore the actual bet, and exchange of money, will take place in a place where this is not the case.

[3]: http://en.wikipedia.org/wiki/Moore%27s_law

[4]: http://en.wikipedia.org/wiki/Expert_system

[5]: http://en.wikipedia.org/wiki/Heuristic

[6]: With the benefit of hindsight, my mistake was trying to find a single most likely path. MCTS also uses the idea of very deep narrow search, but with hardly any guidance at all. It makes up for this by trying lots of alternatives, and that seems to be key.

[7]: At that time MCTS was still called UCT, which stands for Upper Confidence bounds applied to Trees. The MCTS term was coined to describe the more general technique, because it turned out programs were not using "upper confidence bounds" any more.

Acknowledgements

Thanks to everyone who has left a comment or voted above. A big thanks to Yasuhiro Ike for the Japanese translation. Thanks to Paul Dickinson and Eduardo Galvani for feedback on the design, and to numerous people who have given me feedback on the content. (If anything isn't clear, please do let me know!)

 

About The Author

Darren CookDarren Cook is a freelance software developer and researcher, British, but living and working in Tokyo for well over a decade now.

His main research interests are computer go, financial trend analysis and machine translation, and he approaches all with the belief that patterns enhanced with contextual clues are the answer to everything. He is still trying to prove that. In recent years much of his computer go research effort has been a study of the opening on the 9x9 board. Unfortunately this was of no use towards winning The Shodan Go Bet (which took place on a 19x19 board). But sometimes you just have to follow where your curiosity leads you.

His software development work centres around doing things with data, usually large amounts of it. Whether it be analyzing stock exchange ticks, finding and fixing inconsistencies in large databases, or building web sites to collect and process customer demographics. He mainly works in PHP, C++, R and Javascript. He is a great believer in open source and runs a few open source projects (such as MLSN).

You can learn more about Darren's skills and experience at http://dcook.org/work, and can get in contact with him at darren@dcook.org (put "computer go" or "go bet" in the subject to have more chance of getting past the spam filters!).


© Copyright 2009-2012, Darren Cook <darren@dcook.org>

Go board and Deep Blue images from Wikipedia.

Revision History
2009-05-26: First public release
2009-06-17: Minor tweaks; Japanese translation.
2010-06-20: Announce venue; minor tweaks.
2010-12-29: Results section, closing voting.
2011-01-24: Add EC2 link, various tidyup.
2012-01-12: Add GoBet II information.


P.S. All income from advertising revenue on this page will directly fund more of my computer-go articles and open-source development. Please take a look at the ads and if you see something of interest, give it a click! Thanks!