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.)
|New York Time||Japan Time||Result|
|Game 1||Fri, Jan 13th, 8pm||Sat, Jan 14th, 10am||Won 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 2||Sat, Jan 14th, 8pm||Sun, Jan 15th, 10am||Won 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 3||Sun, Jan 15th, 8pm||Mon, Jan 16th, 10am||Won 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 4||Mon, Jan 16th, 8pm||Tue, Jan 17th, 10am||Won 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.
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.
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.
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.
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 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 . 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).
The Dark Years
During the years that followed computer go did not really make much progress. Of course Moore's Law  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 , 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  to guide the search to play out the most likely continuation. That did not work very well either .
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 ) 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?
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.
|Dec 28th, 12:15pm|
|Many Faces||John Tromp||White 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|
|John Tromp||Many Faces||Black 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|
|Many Faces||John Tromp||White 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|
|John Tromp||Many Faces||Black 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.
Related Links and references
Using Amazon EC2
: 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.
: 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.
: 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.
: 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.
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 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.
You can learn more about Darren's skills and experience at http://dcook.org/work, and can get in contact with him at firstname.lastname@example.org (put "computer go" or "go bet" in the subject to have more chance of getting past the spam filters!).