The KGS Go Server , known until 2006 as the Kiseido Go Server , is a game server first developed in 1999 and established in 2000 for people to play Go . The system was developed by William M. Shubert and its code is now written entirely in Java . In Spring of 2017, Shubert transferred ownership to the American Go Foundation.
115-489: A list of the top 100 players, sorted by KGS calculated rank, is regularly updated and maintained. International tournament games and national championship games are relayed on this server. Monthly Computer Go tournaments are held in the Computer Go room on KGS. The KGS Go Server is distinguished by a kibitz culture. Kibitzes are common and popular in high-level games, and may include off-topic discussions though this
230-430: A seki state of mutual life, and so forth in their representation of the state of the game. Historically, symbolic artificial intelligence techniques have been used to approach the problem of Go AI. Neural networks began to be tried as an alternative approach in the 2000s decade, as they required immense computing power that was expensive-to-impossible to reach in earlier decades. These approaches attempt to mitigate
345-415: A "database" of moves to play. As one of the creators of AlphaGo explained: Although we have programmed this machine to play, we have no idea what moves it will come up with. Its moves are an emergent phenomenon from the training. We just create the data sets and the training algorithms. But the moves it then comes up with are out of our hands—and much better than we, as Go players, could come up with. In
460-450: A 70% chance to win the game. Lee followed up with a strong move at white 82. AlphaGo's initial response in moves 83 to 85 was appropriate, but at move 87, its estimate of its chances to win suddenly plummeted, provoking it to make a series of very bad moves from black 87 to 101. David Ormerod characterised moves 87 to 101 as typical of Monte Carlo-based program mistakes. Lee took the lead by white 92, and An Younggil described black 105 as
575-421: 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
690-691: 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
805-656: A better player and to see things he had not previously seen. By March 2016, Wired reported that his ranking had risen from 633 in the world to around 300. Go experts found errors in AlphaGo's play against Fan, particularly relating to a lack of awareness of the entire board. Before the game against Lee, it was unknown how much the program had improved its game since its October match. AlphaGo's original training dataset started with games of strong amateur players from internet Go servers, after which AlphaGo trained by playing against itself for tens of millions of games. AlphaGo
920-692: A branch of applied mathematics , is a topic relevant to computer Go. John H. Conway suggested applying surreal numbers to analysis of the endgame in Go. This idea has been further developed by Elwyn R. Berlekamp and David Wolfe in their book Mathematical Go . Go endgames have been proven to be PSPACE-hard if the absolute best move must be calculated on an arbitrary mostly filled board. Certain complicated situations such as Triple Ko, Quadruple Ko, Molasses Ko, and Moonshine Life make this problem difficult. (In practice, strong Monte Carlo algorithms can still handle normal Go endgame situations well enough, and
1035-474: A cluster version of Zen running on a 26-core machine. In 2012, Zen beat Takemiya Masaki (9p) by 11 points at five stones handicap, followed by a 20-point win at four stones handicap. In 2013, Crazy Stone beat Yoshio Ishida (9p) 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 (6d). No stronger player had ever before agreed to play
1150-872: A competitive program. For example, GNU Go was competitive until 2008. Human novices often learn from the game records of old games played by master players. AI work in the 1990s often involved attempting to "teach" the AI human-style heuristics of Go knowledge. In 1996, Tim Klinger and David Mechner acknowledged the beginner-level strength of the best AIs and argued that "it is our belief that with better tools for representing and maintaining Go knowledge, it will be possible to develop stronger Go programs." They proposed two ways: recognizing common configurations of stones and their positions and concentrating on local battles. In 2001, one paper concluded that "Go programs are still lacking in both quality and quantity of knowledge," and that fixing this would improve Go AI performance. In theory,
1265-434: 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. Prior to 2015,
SECTION 10
#17327826672751380-402: A difficult challenge in the field of artificial intelligence (AI). It is considerably more difficult to solve than chess . Many in artificial intelligence consider Go to require more elements that mimic human thought than chess . Mathematician I. J. Good wrote in 1965: Go on a computer? – In order to program a computer to play a reasonable game of Go, rather than merely a legal game – it
1495-411: A fighting chance and was declared to look like a blatant mistake by commentators. An Younggil said, "So when AlphaGo plays a slack looking move, we may regard it as a mistake, but perhaps it should more accurately be viewed as a declaration of victory?" AlphaGo (white) won the third game. After the second game, players still had doubts about whether AlphaGo was truly a strong player in the sense that
1610-579: A full-sized Go board in a transposition table, a hashing technique for mathematically summarizing is generally necessary. Zobrist hashing is very popular in Go programs because it has low collision rates, and can be iteratively updated at each move with just two XORs , rather than being calculated from scratch. Even using these performance-enhancing techniques, full tree searches on a full-sized board are still prohibitively slow. Searches can be sped up by using large amounts of domain specific pruning techniques, such as not considering moves where your opponent
1725-458: A generalization of the Elo rating system . The most famous example of this approach is AlphaGo, which proved far more effective than previous AIs. In its first version, it had one layer that analyzed millions of existing positions to determine likely moves to prioritize as worthy of further analysis, and another layer that tried to optimize its own winning chances using the suggested likely moves from
1840-430: A good opportunity for society to start discussing preparations for the possible future impact of machines with general purpose intelligence . In March 2016, AI researcher Stuart Russell stated that "AI methods are progressing much faster than expected, (which) makes the question of the long-term outcome more urgent," adding that "to ensure that increasingly powerful AI systems remain completely under human control... there
1955-443: A human might be. The third game was described as removing that doubt, with analysts commenting that: AlphaGo won so convincingly as to remove all doubt about its strength from the minds of experienced players. In fact, it played so well that it was almost scary ... In forcing AlphaGo to withstand a very severe, one-sided attack, Lee revealed its hitherto undetected power ... Lee wasn't gaining enough profit from his attack ... One of
2070-558: 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 decade , 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
2185-450: A large database of professional games, or play many games against itself or other people or programs. These algorithms are then able to utilize this data as a means of improving their performance. Machine learning techniques can also be used in a less ambitious context to tune specific parameters of programs that rely mainly on other techniques. For example, Crazy Stone learns move generation patterns from several hundred sample games, using
2300-431: A lesser handicap. The series of Ing prizes was set to expire either 1) in the year 2000 or 2) when a program could beat a 1-dan professional at no handicap for 40,000,000 NT dollars . The last winner was Handtalk in 1997, claiming 250,000 NT dollars for winning an 11-stone handicap match against three 11–13 year old amateur 2–6 dans. At the time the prize expired in 2000, the unclaimed prize was 400,000 NT dollars for winning
2415-465: A machine was "inevitable" but stated that "robots will never understand the beauty of the game the same way that we humans do." Lee called his game four victory a "priceless win that I (would) not exchange for anything." In response to the match the South Korean government announced on 17 March 2016 that it would invest 1 trillion won (US$ 863 million) in artificial-intelligence (AI) research over
SECTION 20
#17327826672752530-590: A major championship. The match was a five-game match with one million US dollars as the grand prize, using Chinese rules with a 7.5-point komi . For each game there was a two-hour set time limit for each player followed by three 60-second byo-yomi overtime periods. Each game started at 13:00 KST (04:00 GMT ). The match was played at the Four Seasons Hotel in Seoul , South Korea in March 2016 and
2645-625: A nine-stone handicap match. Many other large regional Go tournaments ("congresses") had an attached computer Go event. The European Go Congress has sponsored a computer tournament since 1987, and the USENIX event evolved into the US/North American Computer Go Championship, held annually from 1988 to 2000 at the US Go Congress. Japan started sponsoring computer Go competitions in 1995. The FOST Cup
2760-417: A series of moves described by Ormerod as "unusual... but subtly impressive", which gained a slight advantage. Lee tried a Hail Mary pass with moves 167 and 169, but AlphaGo's defence was successful. An Younggil noted white moves 154, 186, and 194 as being particularly strong, and the program played an impeccable endgame, maintaining its lead until Lee resigned. Live video of the games and associated commentary
2875-565: 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. AlphaGo , 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
2990-500: 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
3105-402: 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 (MIni GO Solver) completely solved the game of Go for the 5×5 board. Black wins, taking the whole board. Continuing the comparison to chess, Go moves are not as limited by
3220-409: 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. The large board (19×19, 361 intersections) is often noted as one of the primary reasons why
3335-616: A terminal leaf of the tree by repeated random playouts (similar to Monte Carlo strategies for other problems). 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
3450-439: 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
3565-403: Is a computer program developed by Google DeepMind to play the board game Go . AlphaGo's algorithm uses a combination of machine learning and tree search techniques, combined with extensive training, both from human and computer play. The system's neural networks were initially bootstrapped from human game-play expertise. AlphaGo was initially trained to mimic human play by attempting to match
KGS Go Server - Misplaced Pages Continue
3680-628: Is a lot of work to do." Some scholars, such as physicist Stephen Hawking , warn that some future self-improving AI could gain actual general intelligence, leading to an unexpected AI takeover ; other scholars disagree: AI expert Jean-Gabriel Ganascia believes that "Things like 'common sense'... may never be reproducible", and says "I don't see why we would speak about fears. On the contrary, this raises hopes in many domains such as health and space exploration." Richard Sutton said, "I don't think people should be scared... but I do think people should be paying attention." The DeepMind AlphaGo Team received
3795-488: Is already strong, and selective extensions like always considering moves next to groups of stones which are about to be captured . However, both of these options introduce a significant risk of not considering a vital move which would have changed the course of the game. Results of computer competitions show that pattern matching techniques for choosing a handful of appropriate moves combined with fast localized tactical searches (explained above) were once sufficient to produce
3910-428: Is comparable to the 1997 chess match when Garry Kasparov lost to IBM computer Deep Blue . Kasparov's loss to Deep Blue is considered the moment a computer became better than humans at chess. AlphaGo is significantly different from previous AI efforts. Instead of using probability algorithms hard-coded by human programmers, AlphaGo uses neural networks to estimate its probability of winning. AlphaGo accesses and analyses
4025-436: Is discouraged by the administrators. The two players cannot see kibitzers' comments until after the game. There are several client programs to connect to KGS. CGoban 3 is for normal use, on any system that supports Java. As of 2018, it supports 30 languages. CGoban 3 can also be used as a Smart Game Format (SGF) file editor and viewer. kgsGtp is another java program, for use by Go-playing programs. KGS Client for Android
4140-641: Is for mobile phones that use the Android operating system ; it supports several languages, but not as many as CGoban 3. KGS used to offer a Java applet version of CGoban, but applet support was removed in early 2016 or late 2015. KGS allows games on any square size board from 2x2 up to 38x38, including the 19x19, 13x13 and 9x9 boards. There are several game types offered on KGS: In addition, non-ranked games may be marked private. KGS offers 4 time controls : None, Absolute, Canadian, and Byo-yomi. Correspondence type games are possible if both players are present at
4255-422: Is how to represent the current state of the game. The most direct way of representing a board is as a one- or two-dimensional array, where elements in the array represent points on the board, and can take on a value corresponding to a white stone, a black stone, or an empty intersection. Additional data is needed to store how many stones have been captured, whose turn it is, and which intersections are illegal due to
4370-405: Is necessary to formalise the principles of good strategy, or to design a learning program. The principles are more qualitative and mysterious than in chess, and depend more on judgement. So, I think it will be even more difficult to program a computer to play a reasonable game of Go than of chess. Prior to 2015, the best Go programs only managed to reach amateur dan level. On the small 9×9 board,
4485-479: Is partly because it has traditionally been difficult to create an effective evaluation function for a Go board, and partly because the large number of possible moves each side can make each leads to a high branching factor . This makes this technique very computationally expensive. Because of this, many programs which use search trees extensively can only play on the smaller 9×9 board, rather than full 19×19 ones. There are several techniques, which can greatly improve
4600-404: Is ranked 9 dan professional. Computer programs Zen and Crazy Stone have previously defeated human players ranked 9 dan professional with handicaps of four or five stones. Canadian AI specialist Jonathan Schaeffer , commenting after the win against Fan, compared AlphaGo with a "child prodigy" that lacked experience, and considered, "the real achievement will be when the program plays a player in
4715-572: Is that Go playing software, which usually communicates using the standardized Go Text Protocol (GTP), will not always agree with respect to the alive or dead status of stones. AlphaGo versus Lee Sedol AlphaGo versus Lee Sedol , also known as the DeepMind Challenge Match , was a five-game Go match between top Go player Lee Sedol and AlphaGo , a computer Go program developed by DeepMind , played in Seoul , South Korea between 9 and 15 March 2016. AlphaGo won all but
KGS Go Server - Misplaced Pages Continue
4830-400: Is to use machine learning techniques. In these, the only thing that the programmers need to program are the rules and simple scoring algorithms of how to analyze the worth of a position. The software will then automatically generates its own sense of patterns, heuristics, and strategies, in theory. This is generally done by allowing a neural network or genetic algorithm to either review
4945-452: Is to use a minimax tree search . This involves playing out all hypothetical moves on the board up to a certain point, then using an evaluation function to estimate the value of that position for the current player. The move which leads to the best hypothetical board is selected, and the process is repeated each turn. While tree searches have been very effective in computer chess , they have seen less success in Computer Go programs. This
5060-484: The American Go Association , reached an average 80 thousand viewers with a peak of 100 thousand viewers near the end of game 1. AlphaGo's victory was a major milestone in artificial intelligence research. Go had previously been regarded as a hard problem in machine learning that was expected to be out of reach for the technology of the time. Most experts thought a Go program as powerful as AlphaGo
5175-501: The International Go Federation , both reason that in the future, Go players will get help from computers to learn what they have done wrong in games and improve their skills. After game three, Lee apologized for his losses and stated, "I misjudged the capabilities of AlphaGo and felt powerless." He emphasized that the defeat was "Lee Se-dol's defeat" and "not a defeat of mankind". Lee said his eventual loss to
5290-509: The Internet Go Server (IGS) 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
5405-519: The Ko rule . In general, machine learning programs stop there at this simplest form and let the organic AIs come to their own understanding of the meaning of the board, likely simply using Monte Carlo playouts to "score" a board as good or bad for a player. "Classic" AI programs that attempted to directly model a human's strategy might go further, however, such as layering on data such as stones believed to be dead, stones that are unconditionally alive, stones in
5520-609: The subset sum problem . Several annual competitions take place between Go computer programs, including Go events at the Computer Olympiad . Regular, less formal, competitions between programs used to occur on the KGS Go Server (monthly) and the Computer Go Server (continuous). Many programs are available that allow computer Go engines to play against each other; they almost always communicate via
5635-405: The "losing move" and Andy Jackson of the American Go Association considered that the outcome had already been decided by move 35. AlphaGo had gained control of the game by move 48, and forced Lee onto the defensive. Lee counterattacked at moves 77/79, but AlphaGo's response was effective, and its move 90 succeeded in simplifying the position. It then gained a large area of control at the bottom of
5750-407: The 2001 survey put it, "just one bad move can ruin a good game. Program performance over a full game can be much lower than master level." One major alternative to using hand-coded knowledge and searches is the use of Monte Carlo methods . This is done by generating a list of potential moves, and for each move playing out thousands of games at random on the resulting board. The move which leads to
5865-438: The 2007 Computer Olympiad and won one (out of three) blitz game against Guo Juan, 5th Dan Pro, in the much less complex 9x9 Go. The Many Faces of Go won the 2008 Computer Olympiad after adding UCT search to its traditional knowledge-based engine. Monte-Carlo based Go engines have a reputation of being much more willing to play tenuki , moves elsewhere on the board, rather than continue a local fight than human players. This
SECTION 50
#17327826672755980-495: The European Go champion Fan Hui five to zero. 29.4 million positions from 160,000 games from KGS's game archive, played by 6 to 9 dan human players, were used to train AlphaGo's policy network. Computer Go Computer Go is the field of artificial intelligence (AI) dedicated to creating a computer program that plays the traditional board game Go . The field is sharply divided into two eras. Before 2015,
6095-467: The Go Text Protocol (GTP). The first computer Go competition was sponsored by Acornsoft , and the first regular ones by USENIX . They ran from 1984 to 1988. These competitions introduced Nemesis, the first competitive Go program from Bruce Wilcox , and G2.5 by David Fotland, which would later evolve into Cosmos and The Many Faces of Go. One of the early drivers of computer Go research was
6210-636: The Inaugural IJCAI Marvin Minsky Medal for Outstanding Achievements in AI. "AlphaGo is a wonderful achievement, and a perfect example of what the Minsky Medal was initiated to recognise", said Professor Michael Wooldridge , Chair of the IJCAI Awards Committee. "What particularly impressed IJCAI was that AlphaGo achieves what it does through a brilliant combination of classic AI techniques as well as
6325-538: The Ing Prize, a relatively large money award sponsored by Taiwanese banker Ing Chang-ki , offered annually between 1985 and 2000 at the World Computer Go Congress (or Ing Cup). The winner of this tournament was allowed to challenge young players at a handicap in a short match. If the computer won the match, the prize was awarded and a new prize announced: a larger prize for beating the players at
6440-662: 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. 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,
6555-528: The best set of random games for the current player is chosen as the best move. No potentially fallible knowledge-based system is required. However, because the moves used for evaluation are generated at random it is possible that a move which would be excellent except for one specific opponent response would be mistakenly evaluated as a good move. The result of this are programs which are strong in an overall strategic sense, but are imperfect tactically. This problem can be mitigated by adding some domain knowledge in
6670-523: The board, strengthening its position with moves from 102 to 112 described by An as "sophisticated". Lee attacked again at moves 115 and 125, but AlphaGo's responses were again effective. Lee eventually attempted a complex ko from move 131 without forcing an error from the program, and he resigned at move 176. Lee (white) won the fourth game. Lee chose to play a type of extreme strategy, known as amashi , in response to AlphaGo's apparent preference for Souba Go (attempting to win by many small gains when
6785-583: The bottom right. These moves unnecessarily lost ko threats and aji, allowing Lee to take the lead. Michael Redmond (9p) speculated that perhaps AlphaGo had missed black's "tombstone squeeze" tesuji . Humans are taught to recognize the specific pattern, but it is a long sequence of moves, made difficult if computed from scratch. AlphaGo then started to develop the top of the board and the centre and defended successfully against an attack by Lee in moves 69 to 81 that David Ormerod characterised as over-cautious. By white 90, AlphaGo had regained equality and then played
6900-430: The computer fared better, and some programs managed to win a fraction of their 9×9 games against professional players. Before AlphaGo, some researchers had claimed that computers would never defeat top humans at Go. Elon Musk , an early investor of Deepmind, said in 2016 that experts in the field thought AI was 10 years away from achieving a victory against a top professional Go player. The match AlphaGo versus Lee Sedol
7015-418: The computer's game as being more aggressive than against Fan. According to 9-dan Go grandmaster Kim Seong-ryong, Lee seemed stunned by AlphaGo's strong play on the 102nd stone. After watching AlphaGo make the game's 102nd move, Lee mulled over his options for more than 10 minutes. AlphaGo (black) won the second game. Lee stated afterwards that "AlphaGo played a nearly perfect game", "from very beginning of
SECTION 60
#17327826672757130-488: The early game, Lee concentrated on taking territory in the edges and corners of the board, allowing AlphaGo to gain influence in the top and centre. Lee then invaded AlphaGo's region of influence at the top with moves 40 to 48, following the amashi strategy. AlphaGo responded with a shoulder hit at move 47, sacrificing four stones elsewhere and gaining the initiative with moves 47 to 53 and 69. Lee tested AlphaGo with moves 72 to 76 without provoking an error, and by this point in
7245-423: The entire online library of Go, including all matches, players, analytics, literature, and games played by AlphaGo against itself and other players. Once set up, AlphaGo is independent of the developer team and evaluates the best pathway to solving Go (i.e., winning the game). By using neural networks and Monte Carlo tree search , AlphaGo calculates colossal numbers of likely and unlikely probabilities many moves into
7360-415: The final losing move. Despite good tactics during moves 131 to 141, AlphaGo could not recover during the endgame and resigned. AlphaGo's resignation was triggered when it evaluated its chance of winning to be less than 20%; this is intended to match the decision of professionals who resign rather than play to the end when their position is felt to be irrecoverable. An Younggil at Go Game Guru concluded that
7475-478: The first layer. AlphaGo used Monte Carlo tree search to score the resulting positions. A later version of AlphaGo, AlphaGoZero, eschewed learning from existing Go games, and instead learnt only from playing itself repeatedly. Other earlier programs using neural nets include NeuroGo and WinHonte. Computer Go research results are being applied to other similar fields such as cognitive science , pattern recognition and machine learning . Combinatorial Game Theory ,
7590-442: 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
7705-544: The five games and an additional $ 20,000 for winning one game). After the match, The Korea Baduk Association awarded AlphaGo the highest Go grandmaster rank – an "honorary 9 dan ". It was given in recognition of AlphaGo's "sincere efforts" to master Go. This match was chosen by Science as one of the runners-up for Breakthrough of the Year , on 22 December 2016. Go is a complex board game that requires intuition, creative and strategic thinking. It has long been considered
7820-401: The fourth game; all games were won by resignation. The match has been compared with the historic chess match between Deep Blue and Garry Kasparov in 1997. The winner of the match was slated to win $ 1 million. Since AlphaGo won, Google DeepMind stated that the prize would be donated to charities, including UNICEF , and Go organisations . Lee received $ 170,000 ($ 150,000 for participating in
7935-470: The future . Related research results are being applied to fields such as cognitive science , pattern recognition and machine learning . AlphaGo defeated European champion Fan Hui , a 2 dan professional, 5–0 in October 2015, the first time an AI had beaten a human professional player at the game on a full-sized board without a handicap. Some commentators stressed the gulf between Fan and Lee, who
8050-575: The game I did not feel like there was a point that I was leading". One of the creators of AlphaGo, Demis Hassabis, said that the system was confident of victory from the midway point of the game, even though the professional commentators could not tell which player was ahead. Michael Redmond ( 9p ) noted that AlphaGo's 19th stone (move 37) was "creative" and "unique". It was a move that no human would've ever made. Lee took an unusually long time to respond. An Younggil (8p) called AlphaGo's move 37 "a rare and intriguing shoulder hit" but said Lee's counter
8165-409: The game was "a masterpiece for Lee Sedol and will almost certainly become a famous game in the history of Go". Lee commented after the match that he considered AlphaGo was strongest when playing white (second). For this reason, he requested that he play black in the fifth game, which is considered more risky. David Ormerod of Go Game Guru stated that although an analysis of AlphaGo's play around 79–87
8280-443: The game, commentators had begun to feel Lee's play was a lost cause. However, an unexpected play at white 78, described as "a brilliant tesuji ", turned the game around. The move developed a white wedge at the centre, and increased the game's complexity. Gu Li (9p) described it as a " divine move " and stated that the move had been completely unforeseen by him. AlphaGo responded poorly on move 79, at which time it estimated it had
8395-430: The game, such as joseki. Some examples of programs which have relied heavily on expert knowledge are Handtalk (later known as Goemate), The Many Faces of Go, Go Intellect, and Go++, each of which has at some point been considered the world's best Go program. However, these methods ultimately had diminishing returns, and never really advanced past an intermediate level at best on a full-sized board. One particular problem
8510-413: The greatest virtuosos of the middle game had just been upstaged in black and white clarity. According to An Younggil (8p) and David Ormerod, the game showed that "AlphaGo is simply stronger than any known human Go player." AlphaGo was seen to capably navigate tricky situations known as ko that did not come up in the previous two matches. An and Ormerod consider move 148 to be particularly notable: in
8625-494: 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. One of
8740-438: The intermediate (single-digit kyu ) 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 ,
8855-475: The journal articles DeepMind released describing AlphaGo and its variants. 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 (AI) 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: Go on
8970-414: 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
9085-399: The match against Lee, AlphaGo used about the same computing power as it had in the match against Fan Hui, where it used 1,202 CPUs and 176 GPUs . The Economist reported that it used 1,920 CPUs and 280 GPUs. Google has also stated that its proprietary tensor processing units were used in the match against Lee Sedol. Lee Sedol is a professional Go player of 9 dan rank and is one of
9200-475: The match, but AlphaGo gained the advantage in the final 20 minutes, and Lee resigned. Lee stated afterwards that he had made a critical error at the beginning of the match; he said that the computer's strategy in the early part of the game was "excellent" and that the AI had made one unusual move that no human Go player would have made. David Ormerod, commenting on the game at Go Game Guru, described Lee's seventh stone as "a strange move to test AlphaGo's strength in
9315-413: The middle of a complex ko fight, AlphaGo displayed sufficient "confidence" that it was winning the game to play a significant move elsewhere. Lee, playing black, opened with a High Chinese formation and generated a large area of black influence, which AlphaGo invaded at move 12. This required the program to defend a weak group, which it did successfully. An Younggil described Lee's move 31 as possibly
9430-609: The most complicated classes of life-and-death endgame problems are unlikely to come up in a high-level game.) Various difficult combinatorial problems (any NP-hard problem) can be converted to Go-like problems on a sufficiently large board; however, the same is true for other abstract board games, including chess and minesweeper , when suitably generalized to a board of arbitrary size. NP-complete problems do not tend in their general case to be easier for unaided humans than for suitably programmed computers: unaided humans are much worse than computers at solving, for example, instances of
9545-408: The move generation and a greater level of search depth on top of the random evolution. Some programs which use Monte-Carlo techniques are Fuego, The Many Faces of Go v12, Leela, MoGo, Crazy Stone , MyGoFriend, and Zen. In 2006, a new search technique, upper confidence bounds applied to trees (UCT), was developed and applied to many 9x9 Monte-Carlo Go programs with excellent results. UCT uses
9660-405: The moves of expert players from recorded historical games, using a KGS Go Server database of around 30 million moves from 160,000 games by KGS 6 to 9 dan human players. Once it had reached a certain degree of proficiency, it was trained further by being set to play large numbers of games against other instances of itself, using reinforcement learning to improve its play. The system does not use
9775-483: The opening", characterising the move as a mistake and AlphaGo's response as "accurate and efficient". He described AlphaGo's position as favourable in the first part of the game, considering that Lee started to come back with move 81 before making "questionable" moves at 119 and 123, followed by a "losing" move at 129. Professional Go player Cho Hanseung commented that AlphaGo's game had greatly improved from when it beat Fan Hui in October 2015. Michael Redmond described
9890-423: The opportunity arises), taking territory at the perimeter rather than the center. By doing so, his apparent aim was to force an "all or nothing" style of situation – a possible weakness for an opponent strong at negotiation types of play, and one which might make AlphaGo's capability of deciding slim advantages largely irrelevant. The first 11 moves were identical to the second game, where Lee also played white. In
10005-492: The performance of search trees in terms of both speed and memory. Pruning techniques such as alpha–beta pruning , Principal Variation Search , and MTD(f) can reduce the effective branching factor without loss of strength. In tactical areas such as life and death, Go is particularly amenable to caching techniques such as transposition tables . These can reduce the amount of repeated effort, especially when combined with an iterative deepening approach. In order to quickly store
10120-553: The problems of the game of Go having a high branching factor and numerous other difficulties. The only choice a program needs to make is where to place its next stone. However, this decision is made difficult by the wide range of impacts a single stone can have across the entire board, and the complex interactions various stones' groups can have with each other. Various architectures have arisen for handling this problem. Popular techniques and design philosophies include: One traditional AI technique for creating game playing software
10235-500: The programs of the era 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
10350-423: The results of the play outs collected so far to guide the search along the more successful lines of play, while still allowing alternative lines to be explored. The UCT technique along with many other optimizations for playing on the larger 19x19 board has led MoGo to become one of the strongest research programs. Successful early applications of UCT methods to 19x19 Go include MoGo, Crazy Stone, and Mango. MoGo won
10465-433: 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. 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
10580-655: 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 (5p). 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
10695-454: The start of the game, "None" is used for time control, and the game type is free. However, they should be completed within 6 months, since the server will automatically delete games when they are 6 months old. The players on KGS may be rated, using levels from 30 kyu to 9 dan , according to their results in ranked games. In addition, certified professional players may use their professional ranks. In October 2015, AlphaGo from DeepMind beat
10810-568: The state-of-the-art machine learning techniques that DeepMind is so closely associated with. It's a breathtaking demonstration of contemporary AI, and we are delighted to be able to recognise it with this award". Go is a popular game in South Korea, China, and Japan. This match was watched and analyzed by millions of people worldwide. Many top Go players characterized AlphaGo's unorthodox plays as seemingly-questionable moves that initially befuddled onlookers but made sense in hindsight: "All but
10925-489: 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. An issue that all Go programs must tackle
11040-474: The strongest players in the history of Go . He started his career in 1996 (promoted to professional dan rank at the age of 12), winning 18 international titles since then. He is a "national hero" in his native South Korea, known for his unconventional and creative play. Lee Sedol initially predicted he would defeat AlphaGo in a "landslide". Some weeks before the match he won the Korean Myungin title,
11155-458: The system explained, AlphaGo does not attempt to maximize its points or its margin of victory, but tries to maximize its probability of winning. If AlphaGo must choose between a scenario where it will win by 20 points with 80 percent probability and another where it will win by 1 and a half points with 99 percent probability, it will choose the latter, even if it must give up points to achieve it. In particular, move 167 by AlphaGo seemed to give Lee
11270-455: The system has ways to determine which heuristic is more important and applicable to the situation. Most of the relatively successful results come from programmers' individual skills at Go and their personal conjectures about Go, but not from formal mathematical assertions; they are trying to make the computer mimic the way they play Go. Competitive programs around 2001 could contain 50–100 modules that dealt with different aspects and strategies of
11385-420: 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. For a long time, it was a widely held opinion that computer Go posed a problem fundamentally different from computer chess . Many considered
11500-586: 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
11615-469: The true top echelon." He then believed that Lee would win the match in March 2016. Hajin Lee , a professional Go player and the International Go Federation 's secretary-general, commented that she was "very excited" at the prospect of an AI challenging Lee, and thought the two players had an equal chance of winning. In the aftermath of his match against AlphaGo, Fan Hui noted that the game had taught him to be
11730-478: The use of expert knowledge would improve Go software. Hundreds of guidelines and rules of thumb for strong play have been formulated by both high-level amateurs and professionals. The programmer's task is to take these heuristics , formalize them into computer code, and utilize pattern matching and pattern recognition algorithms to recognize when these rules apply. It is also important to be able to "score" these heuristics so that when they offer conflicting advice,
11845-404: The very best Go players craft their style by imitating top players. AlphaGo seems to have totally original moves it creates itself." AlphaGo appeared to have unexpectedly become much stronger, even when compared with its October 2015 match against Fan Hui where a computer had beaten a Go professional for the first time without the advantage of a handicap. China's number one player, Ke Jie , who
11960-451: The way that they used to. Deep Blue 's Murray Campbell called AlphaGo's victory "the end of an era... board games are more or less done and it's time to move on." When compared with Deep Blue or with Watson , AlphaGo's underlying algorithms are potentially more general-purpose and may be evidence that the scientific community is making progress toward artificial general intelligence . Some commentators believe AlphaGo's victory makes for
12075-410: 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. In 2006 (with an article published in 2007), 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"
12190-399: Was "exquisite". He stated that control passed between the players several times before the endgame, and especially praised AlphaGo's moves 151, 157, and 159, calling them "brilliant". AlphaGo showed anomalies and moves from a broader perspective, which professional Go players described as looking like mistakes at first sight but an intentional strategy in hindsight. As one of the creators of
12305-405: Was at least five years away; some experts thought that it would take at least another decade before computers would beat Go champions. Most observers at the beginning of the 2016 matches expected Lee to beat AlphaGo. With games such as checkers, chess, and now Go won by computer players, victories at popular board games can no longer serve as significant milestones for artificial intelligence in
12420-480: Was at the time the top-ranked player worldwide, initially claimed that he would be able to beat AlphaGo, but declined to play against it for fear that it would "copy my style". As the matches progressed, Ke Jie went back and forth, stating that "it is highly likely that I (could) lose" after analyzing the first three matches, but regaining confidence after the fourth match. Toby Manning, the referee of AlphaGo's match against Fan Hui, and Hajin Lee, secretary general of
12535-461: Was broadcast in Korean, Chinese, Japanese, and English. Korean-language coverage was made available through Baduk TV. Chinese-language coverage of game 1 with commentary by 9-dan players Gu Li and Ke Jie was provided by Tencent and LeTV respectively, reaching about 60 million viewers. Online English-language coverage presented by US 9-dan Michael Redmond and Chris Garlock, a vice-president of
12650-452: Was described as being close. Hassabis stated that the result came after the program made a "bad mistake" early in the game. Lee, playing black, opened similarly to the first game and began to stake out territory in the right and top left corners – a similar strategy to the one he employed successfully in game 4 – while AlphaGo gained influence in the centre of the board. The game remained even until white moves 48 to 58, which AlphaGo played in
12765-647: Was held annually from 1995 to 1999 in Tokyo. That tournament was supplanted by the Gifu Challenge, which was held annually from 2003 to 2006 in Ogaki, Gifu. The Computer Go UEC Cup has been held annually since 2007. When two computers play a game of Go against each other, the ideal is to treat the game in a manner identical to two humans playing while avoiding any intervention from actual humans. However, this can be difficult during end game scoring. The main problem
12880-422: Was not yet available, he believed it resulted from a known weakness in play algorithms that use Monte Carlo tree search . In essence, the search attempts to prune less relevant sequences. In some cases, a play can lead to a particular line of play which is significant but which is overlooked when the tree is pruned, and this outcome is therefore "off the search radar". AlphaGo (white) won the fifth game. The game
12995-427: Was often perceived as a weakness early in these program's existence. That said, this tendency has persisted in AlphaGo's playstyle with dominant results, so this may be more of a "quirk" than a "weakness." The skill level of knowledge-based systems is closely linked to the knowledge of their programmers and associated domain experts. This limitation has made it difficult to program truly strong AIs. A different path
13110-434: Was overall game strategy. Even if an expert system recognizes a pattern and knows how to play a local skirmish, it may miss a looming deeper strategic problem in the future. The result is a program whose strength is less than the sum of its parts; while moves may be good on an individual tactical basis, the program can be tricked and maneuvered into ceding too much in exchange, and find itself in an overall losing position. As
13225-664: Was video-streamed live with commentary; the English language commentary was done by Michael Redmond (9-dan professional) and Chris Garlock. Aja Huang , a DeepMind team member and amateur 6-dan Go player, placed stones on the Go board for AlphaGo, which ran through the Google Cloud Platform with its server located in the United States. AlphaGo (white) won the first game. Lee appeared to be in control throughout
#274725