Computer Go
Computer Go is the field of artificial intelligence dedicated to creating a computer program that plays the traditional board game Go. The field is sharply divided into two eras. Before 2015, programs were weak. The best efforts of the 1980s and 1990s produced only AIs that could be defeated by beginners, and AIs of the early 2000s were intermediate level at best. Professionals could defeat these programs even given handicaps of 10+ stones in favor of the AI. Many of the algorithms such as alpha-beta minimax that performed well as AIs for checkers and chess fell apart on Go's 19x19 board, as there were too many branching possibilities to consider. Creation of a human professional quality program with the techniques and hardware of the time was out of reach. Some AI researchers speculated that the problem was unsolvable without creation of human-like AI.
The application of Monte Carlo tree search to Go algorithms provided a notable improvement in the late 2000s, with programs finally able to achieve a low-dan level: that of an advanced amateur. High-dan amateurs and professionals could still exploit these programs' weaknesses and win consistently, but computer performance had advanced past the intermediate level. The tantalizing unmet goal of defeating the best human players without a handicap, long thought unreachable, brought a burst of renewed interest. The key insight proved to be an application of machine learning and deep learning. DeepMind, a Google acquisition dedicated to AI research, produced AlphaGo in 2015 and announced it to the world in 2016. AlphaGo defeated Lee Sedol, a 9 dan professional, in a no-handicap match in 2016, then defeated Ke Jie in 2017, who at the time continuously held the world No. 1 ranking for two years. Just as checkers had fallen to machines in 1995 and chess in 1997, computer programs finally conquered humanity's greatest Go champions in 2016-2017. DeepMind did not release AlphaGo for public use, but various programs have been built since based on the journal articles DeepMind released describing AlphaGo and its variants.
Overview and history
Professional Go players see the game as requiring intuition, creative and strategic thinking. It has long been considered a difficult challenge in the field of artificial intelligence and is considerably more difficult to solve than chess. Many in the field considered Go to require more elements that mimic human thought than chess. Mathematician I. J. Good wrote in 1965:Prior to 2015, the best Go programs only managed to reach amateur dan level. On the small 9×9 board, the computer fared better, and some programs managed to win a fraction of their 9×9 games against professional players. Prior to AlphaGo, some researchers had claimed that computers would never defeat top humans at Go.
Early decades
The first Go program was written by Albert Lindsey 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.In April 1981, Jonathan K Millen published an article in Byte discussing Wally, a Go program with a 15x15 board that fit 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. Programs for Go were weak; a 1983 article estimated that they were at best equivalent to 20 kyu, the rating of a naive novice player, and often restricted themselves to smaller boards. AIs who played on the Internet Go Server on 19x19 size boards had around 20-15 kyu strength in 2003, after substantial improvements in hardware.
In 1998, very strong players were able to beat computer programs while giving handicaps of 25–30 stones, an enormous handicap that few human players would ever take. There was a case in the 1994 World Computer Go Championship where the winning program, Go Intellect, lost all three games against the youth players while receiving a 15-stone handicap. In general, players who understood and exploited a program's weaknesses could win even through large handicaps.
2007–2014: Monte Carlo tree search
In 2006, Rémi Coulom produced a new algorithm he called Monte Carlo tree search. In it, a game tree is created as usual of potential futures that branch with every move. However, computers "score" a terminal leaf of the tree by repeated random playouts. The advantage is that such random playouts can be done very quickly. The intuitive objection – that random playouts do not correspond to the actual worth of a position – turned out not to be as fatal to the procedure as expected; the "tree search" side of the algorithm corrected well enough for finding reasonable future game trees to explore. Programs based on this method such as MoGo and Fuego saw better performance than classic AIs from earlier. The best programs could do especially well on the small 9x9 board, which had fewer possibilities to explore. In 2009, the first such programs appeared which could reach and hold low dan-level ranks on the KGS Go Server on the 19x19 board.In 2010, at the 2010 European Go Congress in Finland, MogoTW played 19x19 Go against Catalin Taranu. MogoTW received a seven-stone handicap and won.
In 2011, Zen reached 5 dan on the server KGS, playing games of 15 seconds per move. The account which reached that rank uses a cluster version of Zen running on a 26-core machine.
In 2012, Zen beat Takemiya Masaki by 11 points at five stones handicap, followed by a 20-point win at four stones handicap.
In 2013, Crazy Stone beat Yoshio Ishida in a 19×19 game at four stones handicap.
The 2014 Codecentric Go Challenge, a best-of-five match in an even 19x19 game, was played between Crazy Stone and Franz-Jozef Dickhut. No stronger player had ever before agreed to play a serious competition against a go program on even terms. Franz-Jozef Dickhut won, though Crazy Stone won the first match by 1.5 points.
2015 onwards: The deep learning era
, developed by Google DeepMind, was a significant advance in computer strength compared to previous Go programs. It used techniques that combined deep learning and Monte Carlo tree search. In October 2015, it defeated Fan Hui, the European Go champion, five times out of five in tournament conditions. In March 2016, AlphaGo beat Lee Sedol in the first three of five matches. This was the first time that a 9-dan master had played a professional game against a computer without handicap. Lee won the fourth match, describing his win as "invaluable". AlphaGo won the final match two days later. With this victory, AlphaGo became the first program to beat a 9 dan human professional in a game without handicaps on a full-sized board.In May 2017, AlphaGo beat Ke Jie, who at the time was ranked top in the world, in a three-game match during the Future of Go Summit.
In October 2017, DeepMind revealed a new version of AlphaGo, trained only through self play, that had surpassed all previous versions, beating the Ke Jie version in 89 out of 100 games.
After the basic principles of AlphaGo were published in the journal Nature, other teams have been able to produce high-level programs. Work on Go AI since has largely consisted of emulating the techniques used to build AlphaGo, which proved so much stronger than everything else. By 2017, both Zen and Tencent's project Fine Art were capable of defeating very high-level professionals some of the time. The open source Leela Zero engine was created as well.
Challenges for strategy and performance for classic AIs
For a long time, it was a widely held opinion that computer Go posed a problem fundamentally different from computer chess. Many considered a strong Go-playing program something that could be achieved only in the far future, as a result of fundamental advances in general artificial intelligence technology. Those who thought the problem feasible believed that domain knowledge would be required to be effective against human experts. Therefore, a large part of the computer Go development effort was during these times focused on ways of representing human-like expert knowledge and combining this with local search to answer questions of a tactical nature. The result of this were programs that handled many specific situations well but which had very pronounced weaknesses in their overall handling of the game. Also, these classical programs gained almost nothing from increases in available computing power. Progress in the field was generally slow.;Size of board
The large board is often noted as one of the primary reasons why a strong program is hard to create. The large board size prevents an alpha-beta searcher from achieving deep look-ahead without significant search extensions or pruning heuristics.
In 2002, a computer program called MIGOS completely solved the game of Go for the 5×5 board. Black wins, taking the whole board.
;Number of move options
Continuing the comparison to chess, Go moves are not as limited by the rules of the game. For the first move in chess, the player has twenty choices. Go players begin with a choice of 55 distinct legal moves, accounting for symmetry. This number rises quickly as symmetry is broken, and soon almost all of the 361 points of the board must be evaluated.
;Evaluation function
One of the most basic tasks in a game is to assess a board position: which side is favored, and by how much? In chess, many future positions in a tree are direct wins for one side, and boards have a reasonable heuristic for evaluation in simple material counting, as well as certain positional factors such as pawn structure. A future where one side has lost their queen for no benefit clearly favors the other side. These types of positional evaluation rules cannot efficiently be applied to Go. The value of a Go position depends on a complex analysis to determine whether or not the group is alive, which stones can be connected to one another, and heuristics around the extent to which a strong position has influence, or the extent to which a weak position can be attacked. A stone placed might not have immediate influence, but after many moves could become highly important in retrospect as other areas of the board take shape.
Poor evaluation of board states will cause the AI to work toward positions it incorrectly believes favor it, but actually do not.
;Life and death
One of the main concerns for a Go player is which groups of stones can be kept alive and which can be captured. This general class of problems is known as life and death. Knowledge-based AI systems sometimes attempted to understand the life and death status of groups on the board. The most direct approach is to perform a tree search on the moves which potentially affect the stones in question, and then to record the status of the stones at the end of the main line of play. However, within time and memory constraints, it is not generally possible to determine with complete accuracy which moves could affect the 'life' of a group of stones. This implies that some heuristic must be applied to select which moves to consider. The net effect is that for any given program, there is a trade-off between playing speed and life and death reading abilities.