BROWSE TOPICS
RESOURCESABOUT THIS SITE |
GoAI Programs that Play the Game of Go AITopics > Games & Puzzles > Go
Why the Game is InterestingGo is the last of the classical two player board games where humans are still clearly superior to programs. The rules of the game are very simple but play is complex. Humans have studied this game intensely for centuries, and there are hundred of professional Go players. In Go, no successful evaluation function for evaluating non-terminal positions has ever been found. Therefore, it is very interesting as a test case for AI - to push the boundaries of what is possible with new algorithms such as Monte Carlo methods. Additional Reading- papers, articles, interviews that explore the particular challenges of this game "Excerpt from paper" (Author (YEAR)) Article Title. Media (DATE). "Excerpt" and/or summary [[http://www.guardian.co.uk/technology/2009/apr/30/games-software-mogo | Go, going, gone? Chess has fallen, draughts has been jumped. And a new algorithm has professionals losing the ancient Chinese game to computers for the first time]]. Robert Blincoe, The Guardian (30 April 2009). "If you want to beat the best software in the world at a classic board game, the only one left to you is the strategy game Go. It's long been considered the last bastion of human gaming superiority, holding out against the onslaught of computational brute force and artificial intelligence techniques, while draughts, Othello, backgammon and chess have all fallen. But to be a human winner at Go, you're going to have to get good in a hurry. The end, with computers ruling, is in sight." The Challenge of Go. Jan Krikke, IEEE Computer Journal (January 2007). "Go, which originated in China, is frequently described as “deceptively simple.” Two players take turns putting black and white stones on a board with a 19 19 grid. The aim is to capture and hold territory. A stone or group of stones surrounded by the opponent’s stones are captured and removed from the board. The game ends when both players agree that neither side can improve its position." "Experienced players are said to recognize patterns in strings of stones early in the game that might have strategic implications later in the game, but they rely on intuition and are often unable to explain why they made certain moves" "“Go is particularly appealing for researchers, as it is well defined and constrained by a set of simple rules,” says Thore Graepel of Microsoft Research in Cambridge, England. “We are fascinated by a problem that is simple to state but extremely difficult to solve.”" "s Thore Graepel of Microsoft Research puts it, “Since Go is one of many tasks in which humans can rapidly learn to outperform computers, it does seem likely that the techniques which eventually produce a strong Go playing program will offer insights into machine intelligence in general. For example, one could speculate that methods which are successful at determining the value of Go positions might prove useful for image processing, as the analysis of Go positions is a very visual task.”" HistoryWork on computer Go started in the 1960's and accelerated in the mid 1980's with the appearance of personal computers as well as regular computer Go competitions. Until 2006, programs were based on:
Despite large-scale efforts, progress was limited, and programs remained prone to embarassing blunders caused by gaps and inconsistencies in their knowledge bases. Performance was much better for specialized subtasks than for the full game of Go. Programs could solve difficult endgame puzzles by using a divide and conquer approach based on combinatorial game theory, and became expert in solving so-called Life and Death (tsume Go) problems, which are amenable to deep, exhaustive search. From 2006 on, the new approach of Monte Carlo Tree Search was developed, and it took the world of Computer Go by storm. Programs such as Crazy Stone and MoGo, and techniques such as UCT and RAVE lead to rapid progress, far surpassing the previous state of the art. Programs have almost drawn level with top human professionals on the small 9x9 board. Fuego, an open source program originally developed by the University of Alberta, became the first program to defeat a top human player in an even 9x9 game. On the full 19x19 board, top programs have reached strong amateur master level. In fast games, the commercial program Zen has reached 5 Dan level on the online server KGS. Top programs can now win with occasionally with 7 stones handicap against top human players. Additional ReadingComputers just can't seem to get past Go Charles Arthur, The Guardian, (3 August 2006). "It's the visual element of the game that nobody can quite put into code. Go has a visual element; a high-good level player will reject a potential move because its "shape" - that is, the position of a stone move being considered in relation to the stones already there - "looks bad". They're not intuitively obvious. " "Graepel accepts that gaps remain. But he also thinks there may be a deeper reason why computers remain bad at Go, and humans good. "I believe Go requires certain human characteristics - visual recognition, matching shapes and logical reasoning. You have to do spatial reasoning about which direction should you play. It's all about predator and prey, hunting and chasing, and territory. All these are very basic yet complex human facilities. They're all useful in our natural environment for other things."" In an Ancient Game, Computing's Future Katie Hafner, The New York Times (August 01, 2002) "Deceptively easy to learn, either for a computer or a human, it is a game of such depth and complexity that it can take years for a person to become a strong player. " "Programmers working on Go see it as more accurate than chess in reflecting the ineffable ways in which the human mind works. The challenge of programming a computer to mimic that process goes to the core of artificial intelligence, which involves the study of learning and decision-making, strategic thinking, knowledge representation, pattern recognition and, perhaps most intriguingly, intuition." " Mr. Fotland said, writing a strong Go program will teach us more about making computers think like people than writing a strong chess program." Go For It Michael Brooks, New Scientist (April 13, 2002). AI Advances- what is state-of-the-art? - what techniques feature prominently? - what new techniques have arisen from the research? - survey papers and papers on important developments, more academic than the history section Additional ReadingFrequently Asked QuestionsQ: Can computers dominate humans at Go? Related ResourcesGo Research GroupsComputer Go Group at U of A. The UofA Go program Fuego won Gold and Silver at the Computer Olympiad 2009. Programs: Open source: Fuego OpenSource project pachi Gnu Go (mostly classical, some MCTS player) Commercial or closed source: Zen wiki page Tencho no Igo commercial version of Zen Crazy Stone MoGo My Go Friend The Many Faces of Go Computer Go CompetitionComputer Go A link page for all things Computer Go. Includes links to future and past competitions, a database of researchers in Computer Go and their programs, and lots of related reading. Software and DemosFurther ReadingCiteULike Computer Go library Academic publications related to Computer Go research are regularly added here. Two survey papers discussing the state of the art in "classical" approaches to computer Go are [BouzyCazenave] and [Mueller]. CGT approach to endgames [Mueller1999] Life and Death problems [Wolf, Kishimoto] T. Wolf. Investigating tsumego problems with RisiKo. In D.N.L. Levy and D.F. Beal, editors, Heuristic Programming in Artificial Intelligence 2. Ellis Horwood, 1991. MCTS algorithms [KocsisSz],[GellySilver] Applications to Go [Coulom1+2,MoGo] Recent TCIAIG special issue overview paper [MoGo], system description [Fuego], applications to several other games such as General Game Playing, Hex and Lines of Action. Sensei's Library Wiki for go stuff References(Bouzy and Cazenave (2001)) B. Bouzy and T. Cazenave. Computer Go: an AI-oriented Survey. Artificial Intelligence Journal, vol 132, 2001, pages 39-103, 2001. (pdf) (Gelly and Silver (2007)) S. Gelly and D. Silver. Combining Online and Offline Knowledge in UCT. In ICML, 2007. (pdf) (Mueller (1999)) M. Müller. Decomposition search: A combinatorial games approach to game tree search, with applications to solving Go endgames. In IJCAI-99, volume 1, pages 578-583, 1999 (pdf.gz) (Mueller (2000)) M. Mueller. Review: Computer Go 1984 - 2000. In T. Marsland and I. Frank, editors, Computers and Games 2000, number 2063 in Lecture Notes in Computer Science, pages 426-435. Springer Verlag, 2001 (pdf) (Alphabetical author (YEAR)) Authors. Title. In location, YEAR. (pdf)  |
