NEWSGD.COM
Home | About Us | Contact Us | Site Map | Chinese
News | Biz | Pearl River Delta | Enjoy Life | Culture | Travelling | Pics | Cities & Towns | Gov Info | Specials
Current Home > Culture/Life/Edu > Culture News
Perhaps Go will be man's final bastion to beat machine
Latest Updated by 2006-08-14 11:27:00
Related News
[Computer vs Chess Master Match] Why passion does not compute
Culture & Life
[People & Life]Nobel laureate admits Nazi service
[Culture News] "Living Buddhas" concerned of prospect of Tibetan Buddhism
[Arts & Artists] [Shenzhen] Farida Girls in guitar concert (Aug 12)
[Education] 10-year-old university student evokes controversy

Related Story: [Computer vs Chess Master Match] Why passion does not compute

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.

It sounds superficially easy. The board is a 19 by 19 grid of intersecting lines. The pieces (called "stones") are black or white, and identical.

Once placed on the board, they do not move (unless surrounded and captured) or change colour. The object is to use one's stones to surround as many blank intersections (called "territory") as possible. And that's about it.

Even the lure of a US$1 million prize for the first programme to beat a human professional went uncollected after the deadline passed in 2000. No programme 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 programme 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?

A board of possibilities

While simple to explain and to learn, Go has subtle gradations of ability. There are hundreds of professionals, mainly in China, Japan and South Korea.

Yet even the best computer version is only as good as an average European club player, who is as far from being professional as the average tennis club player is from playing at Wimbledon. Even the best Go-playing programme is presently only ranked about 9kyu. Why are computers so bad at Go? Firstly, playing Go plunges a computer into a sea of possibilities in which most drown. A chess board, with 64 squares, is comparatively tiny: each turn offers about 30 possible legal moves. In Go, with 361 points, few moves are illegal, offering more possibilities on average, about 200 per turn. Thus the total number of possible moves in chess is between 1,060 and 1,070; in Go it is about 10,250.

Secondly, according to David Stern of the Cavendish Laboratory in Cambridge, who is working on a doctorate on computer Go with the team at Microsoft, it is very hard to determine, for each move, what its effects will be. Although the stones do not move, their presence affects the value and "strength" of the others; adjacent stones of the same colour form "groups" which are harder to capture.

That's unlike chess, where it is comparatively easy to determine the "static value" of all the pieces at any time, because there are only 32 at most, where a Go board constantly fills with new pieces.

"The value of a particular stone to a player is derived from its relationships with the surrounding stones, not from itself," Stern said.

The effect is that in Go there are many non-ideal moves at any point. But because games last longer typically about 200 moves (100 stones placed by each side) rather than 70 (35 by both sides) in chess it's harder to look far ahead enough to see a non-ideal move's defects show up.

David Fotland author of the Go-playing programme "Many Faces of Go," still ranked one of the strongest available reckons that for humans, reading ahead is actually easier in Go than in chess.

"People are visual, and the board configuration and relationships change less from move to move than they do in chess," he said.

It's the visual element of the game that nobody can quite put into code. A high-good level player will reject a potential move because its "visual 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. Equally, good players also talk of stones and groups having "influence" on other parts of the board, or being "heavy" or "light" or "overextended."

But computer 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. "A very rough estimate might be that the evaluation function (for computer Go) is, at best, 100 times slower than chess, and the branching factor is four times greater at each play," he explained.

"Taken together, the performance requirements for a chess-like approach to Go can be estimated as 1,027 times greater than that for computer chess.

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.

So far they have fed in around 180,000 games.

Speed advantage

Thore Grapel, who is an amateur shodan (the Go equivalent of a black belt) and is helping coordinate the Microsoft sponsored project , says that the new programme plays to about 10kyu level.

Improvement will rely on getting better at recognizing when groups of stones are at risk of being surrounded and captured. But one thing it does have over rival programmes, and humans, is speed. "It's fast about 10 milliseconds per move," Grapel says. Other programmes can take minutes to consider any board layout. However, Charles Matthews, a 3-dan Go player also based in Cambridge, is unpersuaded.

"If you can't beat your computer Go opponent, you are going to be one of the rabbits at the local Go club," Matthews said. "But further progress has been by rather small increments.

Grapel 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," Grapel explained.

"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."

The implication is that computers are bad at Go because they're still bad at being human. Which might come as some relief.

In 2002, David Levy, one of the earliest drivers of computer chess, wrote (in "Do not pass Go," October 24, 2002): "Perhaps Go will be the final bastion in man's attempts to stave off his inevitable intellectual defeat at the hands of the machine."

Editor: Wing

By: Source: China Daily Website
Previous:  "Living Buddhas" concerned of prospect of Tibetan Buddhism  Next:Foreign cartoons to be banned in prime time


Gift from Belgium


Foreign teens wrap up goodwill tour


Enjoying sunlight and sea in Zhuhai Islands


Phase III of Pazhou Exhibition Complex


Craig vows to be "baddest" Bond
This site contains material from other media for content enrichment purpose only.
The Southcn.com website do not endorse such content and do not bear the joint responsibility of their copyright infringement.
The views expressed in written material posted to the bulletin boards of Southcn.com are those of the authors and/or publishers. The Southcn.com website does not endorse information products posted by organizations and individuals here. The originators of these information products are solely responsible for their content.
For copyright infringement issues, you shall contact Southcn.com within thirty (30) days. Email: falv@southcn.com
If you find any error in this page, please drag your mouse to mark the text with error, then press "CTRL" and "ENTER", to inform us. Thanks for your help!
Home  |  About Us  |   Contact Us  |  Site Map  |  Chinese
©2005 WWW.NEWSGD.COM. All rights reserved.registered number 020074 Terms of Use | Advertise | ICP Certificate No.B2-20050252
Guangdong Gov Link
Guangdong Gov Brief
State Structure
Guangdong in Brief
Laws & Regulations
Exchange Rate
Guangdong Guide
   
Museum Museum
University University
Eat Eat
Shopping Duting
Night Life Night Life
Weather Weather
Phone No. Phone Num
Consulate Consulate
Airport Airport
Travel Tips Tours Tips