History of Go-playing Programs

Go has long been considered a difficult challenge in the field of Artificial Intelligence (AI) and is considerably more difficult to solve than chess. Mathematician I. J. Good wrote in 1965:
Go on a computer? – In order to programme a computer to play a reasonable game of Go, rather than merely a legal game – it is necessary to formalise the principles of good strategy, or to design a learning programme. The principles are more qualitative and mysterious than in chess, and depend more on judgment. So I think it will be even more difficult to programme a computer to play a reasonable game of Go than of chess. (http://www.chilton-computing.org.uk/acl/literature/reports/p019.htm)

The first Go program was probably written by Albert Zobrist in 1968 as part of his thesis on pattern recognition. It introduced an Influence function to estimate territory and Zobrist hashing to detect ko. It could just beat a beginner. [There are references to Go-playing programs by H Remus (only partially complete in 1962) and D Lefkovitz in 1960 but no more information about them is known.]

Jon Ryder produced a program in 1971, which lost to a novice, so was probably no stronger.

The first computer-computer match was between the programs written by Jon Diamond (Institute of Computer Science, London University) and Jack Davies (University of Cambridge) in 1973 - the game was unfinished and no record of it has been found. Jon's program was probably the first to use the alpha-beta search algorithm and also beat a beginner. In strength it was about 20-25 kyu.

In 1978 Walter Reitman and Bruce Wilcox reported on their Interim.2 program, having started on it in 1972. It beat a 22 kyu player and used lookahead which was not full-board, rather it was a selective, goal-driven process.

In April 1981 Jonathan K Millen published an article in Byte discussing Wally, a Go program with a 15x15 board that fitted within the KIM-1 microcomputer's 1K RAM. Bruce F. Webster published an article in the magazine in November 1984 discussing a Go program he had written for the Apple Macintosh, including the MacFORTH source.

The first computer tournament that we know of, the Acornsoft Computer Go Tournament, was held in London in 1984 with the British Go Association as organiser. It was sponsored by Acornsoft, and the programs all used their popular BBC Micro microcomputers on 13x13 boards. The name of the winning program is not recorded; its programmer was Bronyslaw Przybyla.

Allan Scarff produced MicroGo1, also for the BBC Micro, and competed successfully in subsequent years with MicroGo2.

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

The first time a computer competed in a human Go tournament was in the 1980s, Nemesis at the Massachusetts Go Club.

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 million Taiwanese dollars (worth over US $1 million) for a program able to win against the inseis with no handicap. This "million-dollar prize" was never won and the sponsorship from the Ing Foundation ended after the 2001 tournament, with only the prizes for handicaps of 11 stones and more having been won.

GNU Go was published in 1989 as the first open source program and a version for the Nintendo Games Machine by Allan Scarff sold 140,000 copies.

In 1998, very strong players were still able to beat programs while giving handicaps of 25–30 stones, an enormous handicap that few human players would ever take. There was also a case in the 1994 World Computer Go Championship where the winning program, Go Intellect, lost all 3 games against the youth players while receiving a 15-stone handicap. In general, players who understood and exploited a program's weaknesses could win giving much larger handicaps than typical players.

The Computer Go Olympiad, organised by the International Computer Games Association, was started in 1989 for 9x9 boards and in 2000 for 19x19, with the initial tournaments both being held in London and won by Dragon Go (9x9) and Goemate (19x19).

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

WinHonte in 2005 appears to be the first program using neural networks, although Allan Scarff was working on an Acolyte Artificial Neural Net System when he died.

In 2006, advances in the strength of 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 an algorithm, now known as Monte Carlo Tree Search (MCTS), 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 strength of 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. Crazy Stone used MCTS in winning the gold medal on a 9x9 board at the Computer Olympiad.

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. He estimated the playing strength of Mogo as being in the range of 2–3 amateur dan. In the same year the program Crazy Stone running on an 8-core personal computer won against a 4-dan professional, receiving a handicap of eight stones.

Zen playing on the KGS Go server in 2010 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.] MoGo and Many Faces of Go beat professionals taking a 7 stone handicap.

Through 2010 and 2011 programs showed steady improvement with Zen beating a professional with 6 stones. In July 2010 MoGoTW won an even 9×9 game as white against a top professional. However, at the end of 2010 John Tromp, approximately 1 dan, beat Many Faces of Go in a $1000 challenge in a best-of-5 match; he lost a rerun against Zen in early 2012 comprehensively.

In March 2012 Zen beat top professional Takemiya Masaki 9p at 5 stones by eleven points, followed by a stunning twenty point win at a 4 stone handicap. Takemiya remarked "I had no idea that computer go had come this far." It also reached the rank of 6 dan on the KGS Go Server playing games of 15 seconds per move. However, it's not clear how seriously professionals have been taking these exhibition matches.

At the 27th Annual Conference of the Japanese Society for Artificial Intelligence in June 2013, Zen defeated another top professional with a 3 stone handicap with a time setting of 60 minutes plus 30 seconds byoyomi. In March Crazy Stone beat Yoshio Ishida with four handicap stones.

In 2014 for the codecentric go challenge a best-of-five match was played between Crazy Stone and eleven-times German Go champion Franz-Jozef Dickhut, 6 dan amateur, without a handicap. Dickhut won as was expected by most observers and himself before the match. However Crazy Stone won the first game by 1.5 points, which was a resounding mark that the top programs have reached top amateur level.

This was reprised in October 2015, this time with Zen playing and Dickhut won again 3-1 with Zen winning the first game, again by 1.5 points.

Zen has been champion of the Computer Olympiad from 2011 to 2015 in all board sizes, but it should be noted that Crazy Stone did not take part.

It's announced in December 2015 that a tournament in Japan is planned in 2016 to have a computer participant amongst the human ones.

In January 2016 both Facebook and Google DeepMind publish papers about their programs. DeepMind reports that AlphaGo beat the European Champion and Chinese professional Fan Hui by five games to none in an even game match, which took place in October 2015. A first for a computer program! We have a full report on this match here. AlphaGo used two types of Convoluted Neural Networks together with MCTS.

In March 2016 AlphaGo beats the top 9 dan Korean professional Lee Sedol 4:1 in a five game match in Seoul to world-wide publicity.

January 2017 provides another land-mark, with AlphaGo playing anonymously as Master on several Oriental servers against the very top professionals scoring a resounding 60 wins and no defeats, albeit with short time-limits. So there is no longer any doubt that computers can now play Go better than humans.

March 2017 provided a final match for AlphaGo Master, being retired from competition after beating the acknowledged world's best player, the Chinese Ke Jie, 3-0.

In October 2017 it was announced that AlphaGo Zero, armed with just the rules, had in 40 days become even better at Go than the original AlphaGo, without the help of game records!

We have collected together all our reports on AlphaGo.

This article was originally synthesised from a number of sources in December 2015, with a few additions, mainly from Jon Diamond's files.

These sources were: the Computer Go pages on Wikipedia, Sensei's Library, Jay Burmeister and Janet Wiles Technical report (good for historic material up to about 1996), Obituary of Allan Scarff and computer-go.info for more details, the references and discussion of the problems and techniques involved in programming Go.