TOOLBOXBROWSE TOPICS
RESOURCESABOUT THIS SITEpmwiki.org |
Go(a subtopic of Games & Puzzles)
Good Places to StartCracking GO - Brute-force computation has eclipsed humans in chess, and it could soon do the same in this ancient Asian game. By Feng - Hsiung Hsu. IEEE Spectrum Online (October 2007). " In 1957, Herbert A. Simon, a pioneer in artificial intelligence and later a Nobel Laureate in economics, predicted that in 10 years a computer would surpass humans in what was then regarded as the premier battleground of wits: the game of chess. Though the project took four times as long as he expected, in 1997 my colleagues and I at IBM fielded a computer called Deep Blue that defeated Garry Kasparov, the highest-rated chess player ever. You might have thought that we had finally put the question to rest -- but no. Many people argued that we had tailored our methods to solve just this one, narrowly defined problem, and that it could never handle the manifold tasks that serve as better touchstones for human intelligence. These critics pointed to weiqi, an ancient Chinese board game, better known in the West by the Japanese name of Go, whose combinatorial complexity was many orders of magnitude greater than that of chess. Noting that the best Go programs could not even handle the typical novice, they predicted that none would ever trouble the very best players. Ten years later, the best Go programs still can't beat good human players. Nevertheless, I believe that a world-champion-level Go machine can be built within 10 years, based on the same method of intensive analysis -- brute force, basically -- that Deep Blue employed for chess. I've got more than a small personal stake in this quest. At my lab at Microsoft Research Asia, in Beijing, I am organizing a graduate student project to design the hardware and software elements that will test the ideas outlined here. ..."
Artificial intelligence - Winning ways. Computers have started to outperform humans in games they used to lose. The Economist (January 25, 2007). "Researchers in the field of artificial intelligence have long been intrigued by games, and not just as a way of avoiding work. Games provide an ideal setting to explore important elements of the design of cleverer machines, such as pattern recognition, learning and planning. They also hold out the tantalising possibility of fame and fortune should the program ever clobber a human champion. ... Deep Blue and its successors beat Mr Kasparov using the 'brute force' technique. ... In the past two decades researchers have explored several alternative strategies, from neural networks to general rules based on advice from expert players, with indifferent results. Now, however, programmers are making impressive gains with a technique known as the Monte Carlo method. ... MoGo, a [Go] program developed by researchers from the University of Paris, has even beaten a couple of strong human players on the smaller of these boards -- unthinkable a year ago. It is ranked 2,323rd in the world and in Europe's top 300."
Why computers can't surpass Go and collect $1 million - There’s one game where artificial intelligence can’t beat humans. Comment by Ben Macintyre. Times Online (june 29, 2007). "Ten years ago last month, to the dismay of many chess enthusiasts, the IBM supercomputer program Deep Blue beat the world chess champion Gary Kasparov: the greatest chess mind alive was elbowed aside by raw computing muscle. ... The computer is now dominant in almost every board and card game devised by man. ... Yet there is one game in which the computer is still no match for Man, a game in which a competent teenager can beat the world’s most sophisticated computer program with ease: and that is the ancient Chinese board game Go, the oldest game in the world, and the only one at which man remains the undisputed champion. ... Go is seen as a key to unlocking the secret of artificial intelligence (AI). If computers can “learn” the game, some scientists believe, mankind would be a huge step closer to replicating human thought processes, with great scientific benefits. ... A Taiwanese organisation has offered $1 million for the first computer program to defeat a junior Go champion, yet despite some recent advances, none has yet reached that skill level." To Test A Powerful Computer, Play an Ancient Game. By George Johnson. New York Times (July 29, 1997) / available from Prof. Charles Schmidt's Cognition and Computation course materials. "Deep Blue defeated the world chess champion by leveraging a moderate amount of chess knowledge with a huge amount of blind, high-speed searching power. But this roughshod approach is powerless against the intricacies of Go, leaving computers at a distinct disadvantage. 'Brute-force searching is completely and utterly worthless for Go,' said David Fotland, a computer engineer for Hewlett-Packard, who is the author of one of the strongest programs, called The Many Faces of Go. 'You have to make a program play smart like a person.'" Computer Go Glossary. Just one of the many resources from Martin Müller at the University of Alberta. Readings OnlineComputers just can't seem to get past Go - Chess is a doddle compared to this ancient oriental game of strategy that has programmers and scientists scratching their heads. By Charles Arthur. The Guardian & Guardian Unlimited Technology (August 3, 2006). "When Garry Kasparov was beaten, to his furious humiliation, by IBM's Deep Blue chess computer in 1997, it left human players pondering their future. Draughts, Othello, backgammon, Scrabble: by the start of this century, each had been all but conquered by machines. But don't worry. Almost a decade later, with Moore's Law still at work, there is still a board game in which humans reign supreme. The game is Go, an oriental game of strategy. ... Even the lure of a US$1 million prize for the first program to beat a human professional went uncollected after the deadline passed in 2000. No program has yet come close to meeting the challenge. Now, however, there may be a new attack on this outpost of humanity. At Microsoft's research centre in Cambridge, scientists are taking a simpler approach to working out how to beat the best humans. They're telling their program what the best humans did against each other in thousands of games, providing a vast repertoire of millions of moves. Are computers about to invade another piece of our gameplaying territory? ... [C]omputer chess games don't understand chess; they just got better at crunching moves. Won't brute force do the job on Go, as it did in other games? No, says Bob Myers, who runs the Intelligent Go website. ... Now, though, [David] Stern and the Microsoft team are trying a different tack. Instead of wondering how to get a computer to beat a human, they are showing the computer how humans beat each other - by creating a huge database of moves and positions from professional games." Go, digital - The Chinese game has programmers on a quest for an algorithm to defeat other computers -- and then lead to artificial intelligence applications. By Brendan Borrell. The Oregonian (August 16, 2006). "For the past four years, [Peter] Drake and his [Lewis & Clark College] students tried nearly every novel approach out there: neural networks, cellular automata, and genetic algorithms. Their victory with this ingenious algorithm marked a turning point for Orego and was the latest application of a promising new strategy in artificial intelligence. ... Go is a board game that originated in China more than 2,000 years ago. ... The challenges of Go are more representative of the real world problems humans face: The pieces may be black and white, but the solutions never are. Drake says that solving this class of problems will help in designing electronic circuits, controlling flows in a sewage plant, or building cars that can drive themselves. 'It's considered an open question in artificial intelligence,' he adds. ... The night that Orego beat JacquelineGo ... Drake was using a new strategy pioneered by Remi Coulom at Universite Charles de Gaulle in Lille, France. Drake says, 'Rather than trying to come up with some special rules that are specific to Go and require lots of time and an expert player to come up with, you just say, "Well, I'm at this position, and I will play the rest of this game out randomly a hundred times or a thousand times and if black usually wins then this is a good position for black."' Mathematicians call this a Monte Carlo method because of its likeness to games of chance found in that European city's casinos." AI Invades Go Territory. By Brendan Borrell. Wired News (September 16, 2006). "Chess was once the pinnacle of geekdom, but then the artificial intelligence geeks got too smart for chess and turned to Go. Why Go? ... In the past year, a new strategy implemented by computer scientist Rémi Coulom at the Université de Lille in France, has revolutionized the way these programmers have approached the problem. Coulom's program Crazy Stone won a gold medal at the 2006 Computer Olympiad in Torino, Italy. Recently, Coulom spoke to Wired News to explain some of the challenges of Go and what makes Crazy Stone work so well. Wired News: What makes programming go so much tougher than chess? ..." Comparing Baduk and Chess. By Nam Chi-hyung. The Korea Times July 7, 2005). "For more than 2,500 years, Baduk has meant so much more than just a game to many people; it is regarded as an art, science and even a pedagogy in Korea, China and Japan, and has spread to the western world. Now, it offers not only entertainment and the thrill of competition, but it also provides a useful tool for studying human mental faculties and artificial intelligence. Baduk is often compared with Chess, which is also a popular ancient game. ... [I]n Baduk, the ultimate goal of securing the world as one’s own is achieved through competition, rather than by the destruction of the opponent."
In an Ancient Game, Computing's Future. By Katie Hafner. The New York Times, August 1, 2002. "Go is different. 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. To date, no computer has been able to achieve a skill level beyond that of the casual 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. 'A good Go player could make a move and other players say, 'Yes, that's a good move,' but they can't explain to you why it's a good move, or how they even know it's a good move,' said Dr. John McCarthy, a professor emeritus at Stanford University and a pioneer in artificial intelligence." Computers Play Chess; Humans Play Go. James Hendler's Letter from the Editor. IEEE Intelligent Systems 21(4): July/August 2006, 2-3. "The future of AI must involve exploring and understanding the parts of human intelligence we haven’t been looking at that much -- the stuff at the heart of human thought. To do this, we need to stop looking for new ways to solve well-defined problems and start looking for ways to combine the things we know how to do, and then see if this helps us explore problems with more diversity and scope. In fact, I’m encouraged to see a few developments that are taking us in the right direction. Ron Brachman, in his AAAI 2005 presidential address and in his role as a DARPAoffice director (see 'Systems That Know What They’re Doing,' Nov./Dec. 2002,pp. 67–71), advocated large AI projects that would force people from different parts of AI to work together to achieve, in consortium, what no approach could achieve alone." Chess - Man vs. Machine Plays Out. By Tania Hershman. Wired News (October 21, 2002). "So why wasn't the Kasparov-Deep Blue match enough to settle the issue of who's superior, humans or machines? 'As a scientist, a single data point that is unrepeatable (because Deep Blue has since been dismantled) is useless,' said Jonathan Schaeffer of the University of Alberta Department of Computer Science's Games Group at the symposium, Man vs. Machine: The Experiment. 'Now we have two more matches ... and we will get new data to see whether the machine is better than the man.' ... Schaeffer, who is the author of the world-champion checkers computer program, believes that researchers should broaden their game-playing horizons. 'If you want to understand intelligence, the game of Go is much more demanding,' he said. 'It doesn't have the silver bullet: deep search. Chess has somewhat outlived its usefulness. It turned out to be easier than we thought.'" Do not pass Go. Computers can beat the world's best chess players but have yet to master other classic games like Go. By David Levy. The Guardian (October 24, 2002). "Ever since Garry Kasparov's sensational 1997 loss to the IBM chess monster Deep Blue, the chess world has thirsted for revenge. But the first opportunity ended in failure in Bahrain on Saturday, when Kasparov's former pupil and successor as World Champion, Vladimir Kramnik, could only draw an 8-game match against one of the world's leading chess engines, Fritz. But this was just the latest in a long series of human versus computer encounters that illustrate the inexorable march of artificial intelligence (AI). It's a story that began at a Dartmouth University conference in 1956, when several of the founding fathers of AI defined the goals of that infant science. One of them was to create a computer program that could defeat the world chess champion. Success would, those scientists believed, reach to the very core of human intellectual endeavour. By the early 1990s, due in no small part to the successes achieved in computer chess, the interest of the AI community had spread to many other games of skill, including backgammon, bridge, Go and Scrabble. Where exactly are we now in this fascinating struggle? ... Two games proving even tougher to crack than chess are bridge and Go." Martin Müller's publications, many of which relate to Go.
Complicacy of Baduk Easily Decoded in New Book. By Kim Tae-jong. The Korea Times (October 30, 2006). "Baduk, also known as Go, must have irresistible appeals given its legendary 4,000-year history and complicated rules and required skills.Baduk professor Nam Chi-hyung of Myongji University says that it is just that intellectual complicacy that strongly attracts players to the board game.'Other board games, including chess, have been already been conquered by computers. Human intelligence can’t beat a simple program. But when it comes to baduk, artificial intelligence is still in its infant stage because of the game’s range of different strategies and variables,' Nam told The Korea Times. ... Nam, who holds a master's degree in English literature from Seoul National University, published Korea's first English book on baduk in 2000 and released a baduk dictionary called 'Contemporary Go Terms: Definition & Translation' in 2005." Related Web SitesThe American Go Association has a comprehensive collection of Computer Go resources as well as other helpful materials for the GO enthusiast. At the British Go Association's site you'll find a good introduction to the game of Go, a nice collection of Computer Resources for Go Players, a link to their Junior Go Page, and much more. GNU Go: "a free program that plays the game of Go. GNU Go has played thousands of games on the NNGS Go server. GNU Go is now also playing regularly on the Legend Go Server in Taiwan, on the WING server in Japan, and many volunteers run GNU Go clients on KGS. GNU Go has established itself as the leading non-commercial go program in the recent tournaments that it has taken part in." "Intelligent Go Foundation website, online home of the non-profit organization devoted to the promotion of computer Go." Be sure to see Bob Myers' Overview of Computer Go, which covers the topics: Why is Computer Go Hard?; A Brief History of Computer Go; Cognitive Science; How Computer Go Programs Work; and, Future research directions. Introduction to the Computer Go Field & Associated Internet Resources. By Jay Burmeister and Janet Wiles, Departments of Computer Science and Psychology, University of Queensland, Australia. Jean-loup's Go Page. Information and resources, including various programs, await you at this beautiful site. The Many Faces of Go. From David Fotland & Smart Games. "2002 World Computer Go Champion, 1998 World Computer Go Champion, and ten time US Computer Go Champion."  Mick's Computer Go Page. Maintained by Dr. Michael Reiss. Extensive online information, a huge bibliography, news, and links to other Go websites. "OpenGo is intended as a workbench for programmers interested in the challenges of writing automated Go opponents." Related Pages
More ReadingsGinsberg, Matthew L. Computers, Games and the Real World. Scientific American (special issue: Exploring Intelligence - Winter 1998). "More than just competing with people, game-playing machines complement human thinking by offering alternative methods to solving problems." Kierulf, A., K. Chen, and J. Nievergelt. 1990. Smart Game Board and Go Explorer: A Study in Software and Knowledge Engineering. Communications of the ACM 33 (2): 152-167. Levy, David N. L., editor. 1988. Computer Games II. New York: Springer-Verlag. Chapter 5 offers a dozen papers on programing computers to play Go. Mechner, David. A. 1998. All Sytems Go. The Sciences 38 (Jan/Feb 1998): 32-7. Shirayanagi, K. 1990. Knowledge Representation and its Refinement in Go Programs. In Computers, Chess, and Cognition, ed. Marsland, A. T. and J. Schaeffer, 287-300. New York: Springer-Verlag. Wilcox, Bruce 1984. Computer Go. In Computer Games II, ed. Levy, David L., 94-135. New York: Springer Verlag, 1988. The article begins by comparing programming challenges in Go to those of chess. The second part of the article is a readable overview of programming attempts and descriptions of their strengths and weaknesses |
