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 color. 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 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 center in Cambridge, England, 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?
While simple to explain and to learn, Go has subtle gradations of ability. There are hundreds of professionals, mainly in Japan, Korea and China, 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 program is presently only ranked at about 9 kyu (see sidebar).
Why are computers so bad at Go? First, 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 color 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.
"It is very difficult to produce an efficient `static evaluation' function to compute the value of board positions in Go for a particular player," Stern says.
"The reason is that the stones on the Go board influence each other's value in complex ways. The value of a particular stone to a player is derived from its relationships with the surrounding stones, not from itself," he says.
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 showing up.
EASIER FOR HUMANS
David Fotland -- author of the Go-playing program Many Faces of Go, which is still ranked as 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 told the Intelligent Go Web site (www.intelligentgo.org).
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.
Equally, good players also talk of stones and groups having "influence" on other parts of the board, or being "heavy" or "light" or "overextended." More simply, "urgent" moves are those that will bolster the player's position; good players consistently choose the most urgent moves.
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 Web site.
"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; 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," he says. "Moore's Law holds that computing power doubles every 18 months, so that means we might have a computer that could play Go using these techniques sometime in the 22nd century."
Now, though, 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, adding them to a huge database so the program can pick the best available in any given situation.
ALL MOVES
Thore Grapel, of the Speech and Intelligent Systems research group at Microsoft Cambridge, who is helping coordinate the work, says that both the winner's and loser's moves are included.
"From the point of view of the computer, these pros are so much better that any variation in their skills is minimal, compared [with] the computer's playing strength," Grapel says.
In other words, it's better to play like a losing pro than the best computer.
And how well does it perform? Grapel, who is an amateur shodan (the Go equivalent of a black belt), says that the program plays to about the 10 kyu 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 programs, and humans, is speed: "It's fast -- about 10 milliseconds per move," Grapel says.
Other programs can take minutes to consider any board layout.
However Charles Matthews, a 3-dan Go player also based in Cambridge, is unconvinced.
"If you can't beat your computer Go opponent, you are going to be one of the rabbits at the local Go club. But further progress has been by rather small increments. The top programs used to be about 8 kyu; they might have crept up to 7 kyu, but that should mean that I, as a 3 dan, would have a hard time giving them a nine-stone handicap (a nine-turn head start), and that isn't my experience," he said.
While it's hard to know how well humans are playing, Matthews reckons that amateur shodans play at about 90 percent efficiency, and top professionals at about 98 percent efficiency.
"That is with a purely hypothetical notion of `perfect play' being a few handicap stones beyond top pro," he says.
Grapel 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 you should 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," he says.
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: "Perhaps Go will be the final bastion in man's attempts to stave off his inevitable intellectual defeat at the hands of the machine."
Despite humanity's own best efforts to undermine it, the bastion still looks remarkably solid.
As strategic tensions escalate across the vast Indo-Pacific region, Taiwan has emerged as more than a potential flashpoint. It is the fulcrum upon which the credibility of the evolving American-led strategy of integrated deterrence now rests. How the US and regional powers like Japan respond to Taiwan’s defense, and how credible the deterrent against Chinese aggression proves to be, will profoundly shape the Indo-Pacific security architecture for years to come. A successful defense of Taiwan through strengthened deterrence in the Indo-Pacific would enhance the credibility of the US-led alliance system and underpin America’s global preeminence, while a failure of integrated deterrence would
It is being said every second day: The ongoing recall campaign in Taiwan — where citizens are trying to collect enough signatures to trigger re-elections for a number of Chinese Nationalist Party (KMT) legislators — is orchestrated by the Democratic Progressive Party (DPP), or even President William Lai (賴清德) himself. The KMT makes the claim, and foreign media and analysts repeat it. However, they never show any proof — because there is not any. It is alarming how easily academics, journalists and experts toss around claims that amount to accusing a democratic government of conspiracy — without a shred of evidence. These
Taiwan is confronting escalating threats from its behemoth neighbor. Last month, the Chinese People’s Liberation Army conducted live-fire drills in the East China Sea, practicing blockades and precision strikes on simulated targets, while its escalating cyberattacks targeting government, financial and telecommunication systems threaten to disrupt Taiwan’s digital infrastructure. The mounting geopolitical pressure underscores Taiwan’s need to strengthen its defense capabilities to deter possible aggression and improve civilian preparedness. The consequences of inadequate preparation have been made all too clear by the tragic situation in Ukraine. Taiwan can build on its successful COVID-19 response, marked by effective planning and execution, to enhance
Since taking office, US President Donald Trump has upheld the core goals of “making America safer, stronger, and more prosperous,” fully implementing an “America first” policy. Countries have responded cautiously to the fresh style and rapid pace of the new Trump administration. The US has prioritized reindustrialization, building a stronger US role in the Indo-Pacific, and countering China’s malicious influence. This has created a high degree of alignment between the interests of Taiwan and the US in security, economics, technology and other spheres. Taiwan must properly understand the Trump administration’s intentions and coordinate, connect and correspond with US strategic goals.
RSS