Man vs Machine Go Match

In 1997, when the strongest Go-playing programs were around 1-kyu, Darren Cook made a survey of Go programmers' and others' opinions on when a 1-dan program would first appear. John Tromp responded "I wonder if people would still make such optimistic estimates if they had to back it up with, say, a $1000 bet. I (dutch 1-kyu) would happily bet that I won't be beaten in a 10 game match before the year 2011".

Darren took him up on this bet. You can read about it at http://dcook.org/gobet/. John and Darren have agreed that the bet is to be resolved on the last four days of December 2010, during and in the same building as the London Open Go Tournament. The London Open Go Tournament will be open to quiet visitors, who may also visit the viewers' room of the Man vs Machine Go Match.

The games will be played during, and in the same premises as, the London Open Go Tournament.

The schedule, and the time limits, for the seven games will be exactly the same as for the main human tournament of the London Open: 90 minutes of main time, with Canadian overtime of 20 moves in five minutes. This schedule is:

These times are given in GMT, also known as UTC.

Relay

The games will be relayed live on KGS. To see them, connect to KGS, go to the English Game Room, and look for a game owned by user 'BGAmatches'.

The venue is the International Students House, 229 Great Portland Street, London W1W 5PN. This is straight across Great Portland Street from Great Portland Street underground station, and less than 200 yards east of Regent's Park underground station.

The London Open Go Tournament will be held on the same dates, in the basement of these premises, from December 28th through 31st.

The Shodan Go Challenge will be held on the first floor (second floor, to Americans) of the same premises and over the same period. The match itself will be played in the Fitzroy Room (up the stairs from the ground floor, turn left, and go through where the internet café used to be). It will not be open to the public.

There will be a relay, via the internet, to the Gulbenkian room (up the stairs from the ground floor, turn right, first room on the right. This room will be open to the public, and while a game is being played will have computer screens with videos links to the game, a screen showing the current state of the game, and a board with the position laid out, for people to discuss.

Once Darren has selected a program and learned what rule sets it supports, he will pick a rule set. This is likely to use area scoring and some form of superko rule: AGA rules are possible.

Tournament Director is Nick Wedd.

Time Limits

The original plan was for the games to be played with 40 minutes each and Fischer time of 20 seconds per move. However, Go servers (or at least, those familiar to English-speakers) do not support Fischer time. A proposal to use 40 minutes sudden death instead was rejected, 40 minutes is too fast. The games are to be played with an operator (probably Darren) conveying the moves in both directions betweeen a physical board and a computer; and, at least in the board-computer direction, there is no easy way to correct an error. Assuming that the operator takes five seconds per move so as to be sure there is no error, and that a game lasts for 240 moves, that is 1200 seconds = 20 minutes consumed, before we consider the time actually used by the program.

Also, John rejected the idea of three relatively fast games a day. He responded "I had hoped I could play exactly 2 games every day, for 8 games total, and at longer time control". I agree that 40 minutes each, with a human operator transfering the moves from a real board to a computer and back, is too fast.

There is also an issue of how to let the program know how much time it has left. As a physical clock is to be used, what matters is how much time is on the physical clock, and the program won't know this unless someone (i.e. its operator) tells it. One solution is to ensure that the program plays fast enough that the clock won't be an issue; another is for the program's operator to tell it how much time it has left at regular intervals. I see this as a problem for Darren.

Also, some programs play on long after the game is decided. For example, in the last KGS bot tournament, the program Aya lost on time by failing to make move 546 within the overtime allowed. However I hope this will not be an issue, and either John, or Darren on behalf of the program, will resign once the result is clear. Neverthless, I recommend some Canadian overtime, say 20 moves in five minutes.

I am pleased to say that the players have now agreed on slower time limits, of 90 minutes main time with Canadian overtime of 20 moves in five minutes.

The Computer that runs the Program

The original terms of the bet did not, and could not, specify how powerful a computer might be used. They said "you may run any program on any hardware you can bring to the playing site". So it has to be physically present, a remote computer connected via the internet is not allowed. Darren has said "My take on this is hardware a serious computer nerd might have at home. A couple of networked high-end machines would be (borderline) reasonable; a cluster of 20 machines would not." John has said he is okay with Darren using a cluster of machines networked together, and agrees that a $5000 limit on the value of hardware is reasonable.

At the time of writing (2010-11-02) the program, and the computer it runs on, are still being selected. Many Faces of Go is a possibility for the program.

At the time of writing (2010-12-18) the program, or programs, are still being decided by Darren. He may choose a different program for each round if he wishes. (I guess that Many Faces of Go will be used at least once.)

ALso, Darren has not yet decided on the hardware he will use. He and John have agreed on a compromise: the first two rounds must be played using a computer physically present in the playing room; for the other five rounds he may use an internet connection to a remote computer.

John Tromp John is Dutch, but lives and works in New York. He has been European 2-dan for a number of years. For more information see John Tromp's home page. His Go strength was listed (earlier this year, he is no longer listed) by the European Go Database as 2231. That correponds to strong (European) 2-dan.

Darren Cook Darren is British, but has lived in Tokyo for the past 15 years. He learnt to play go at the Norwich Go Club over 20 years ago; despite that length of time, and despite living in Japan, he is a relatively weak player, maybe around European 5-kyu. He works as a freelance software developer and researcher, and has been researching computer go since 1993, ever since hearing about how hard it was on an episode of Tomorrow's World! For more information on Darren, see Darren's Go Bet page: Shodan Go Bet - who will win? About Darren and his work Darren's blogs and articles

Early events involving Go-playing computers were all matches or tournaments between computers. They played so badly that even beginners could beat them easily, so games between humans and computers were of no interest.

The first "official" event that we know of was held in Cambridge, England, in 1970. It was a game between two programs. The programmers were Jon Diamond and Jack Davies. Jon Diamond is now president of the British Go Association. The winner is not recorded.

The first tournament that we know of, the Acornsoft Computer Go Tournament, was held in London, England, in 1984. It was sponsored by Acornsoft, and the programs all used their popular "BBC Micro" microcomputers. The name of the winning program is not recorded; its programmer was Bronyslaw Przybyla.

Later that year, the Unix user group Usenix sponsored the first of a series of Computer Go tournaments. You can read about these and many more Computer Go - Past Events. This 1984 event was won by Bruce Wilcox's "Nemesis", which later evolved into the commercial product "Ego".

In 1987 the Ing Foundation of Taiwan sponsored the first of a series of annual Computer Go tournaments. They provided generous sponsorship, with the winner of each annual tournament competing, using handicap stones, against inseis (trainee professional players, with strengths around amateur 6-dan) for further prizes. The fewer the handicap stones needed by the program, the bigger the prize it could win, on a progressive scale with a maximum of 40,000,000 Taiwanese dollars (worth over US $1,000,000) for a program able to win against the inseis with no handicap. This "million-dollar prize" was never won, the sponsorship from the Ing Foundation ended after the 2001 tournament, with only the prizes for handicaps of 11 stones and more ever claimed.

In 2003, Go++ beat a 5-kyu amateur in a 9-stone-handicap 19×19 game.

In 2006, advances in the strength of computer Go programs were still being made, though the rate of advance had slowed. Processor speeds were continuing to double every two years in accordance with Moore's Law, but this did not help, as the algorithms used by the best programs did not scale well, if at all. However, in this year Kocsis and Szepesvári published their seminal paper Bandit based Monte-Carlo Planning. This describes a Monte-Carlo based algorithm that was effective for computer Go (in fact a French team was working on a closely-related algorithm at the same time). This not only led to a rapid advance in the the strength of Computer Go programs over the next few years, it allowed them to use a method that did scale well, so now Moore's Law was working with the programmers again.

In 2008, MoGo, developed by the French team mentioned above, beat an 8-dan professional in a 9-stone-handicap 19×19 game. It was running on an 800-node supercomputer.

In 2009 the computer Go program "Zen" playing on the KGS Go server achieved a rating of 3-dan, playing 19×19 games against human opponents. The KGS rating scale is slightly weaker than the European rating scale, close to the American scale, and rather stronger than the Japanese scale.

The last paragraph above implies that Zen ought to be able to beat John. However, when Zen plays on KGS (its account name there is "Zen19") it rarely plays against the same opponent more than twice. We can expect Darren to play many training games against his opponent for the match. He will learn its weaknesses from these training games; and it will "learn" nothing by playing him. Also, Zen's author has said that it will not be playing in the challenge. Other leading programs, including Many Faces of Go (whose author David Fotland will allow it to play) are probably not as strong as Zen.

The consensus of those who have given opinions on who will win is in favour of John: Who will win the bet? - Results.

References

Past Human-Computer challenges

Wikipedia on Computer Go

Sensei's Library on Computer Go