8 August
2005—It seems the scales are finally tipping in the
decades-long struggle of human grand masters and chess machines.
The humans are looking increasingly like the palookas that
impresarios used to pit against champion boxers, just to attract
spectators. And in the one sphere where grand masters always
claimed an advantage—playing interesting and fun-to-watch
games—the gap also seems to be closing. The machines'
play, once marked by bizarre, inscrutable moves, increasingly
resembles the play of humans—very smart humans.
The turning
of the tide began last October, in Bilbao, Spain, when a special-purpose
machine called Hydra and a commercially available program
called Fritz, running on a laptop, creamed a bevy of top-ranked
grand masters. Hydra and Fritz each scored 3.5 points out
of a possible 4. Then, in June, in a match webcast from London,
Hydra humiliated Britain's Mickey Adams, the seventh-ranked
grand master in the world, with a score of 5.5 out of 6. The
same week, a version of Fritz, downloadable for free as part
of the Accoona Toolbar (a device that searches a PC's hard
drive) drew a one-game exhibition match against Uzbekistan's
champion, Rustam Kasimdzhanov.
What explains
the rise of the machines? First, the best humans now playing
are simply not as good as the former bearer of humanity's
torch, Garry Kasparov, the highest-rated player in history.
Kasparov recently retired from professional play to devote
himself to unseating Vladimir Putin as president of Russia.
Second, the machines are getting smarter. Their programmers
are learning how to counter anticomputer strategies. These
strategies generally involve closing up the computer's
position with pawns. That way, the pieces have less mobility,
and the machines cannot exploit their fearsome calculating
power.
Kasimdzhanov
managed to obtain just such a position in his match against
the Accoona version of Fritz. But to convert his strategic
advantage to a win he had to open things up at some point,
potentially allowing the computer more freedom to move. It
seems he did so prematurely. At move 21, grand master Lev
O. Alburt, who was watching from the audience, said that Kasimdzhanov's
winning chances would be around 80 percent if he were playing
the same position against another top grand master. Two moves
laterAlburt said the win—if there still was one—would
be hard to work out in the time the harried human had left.
Seventeen moves later and down to less than 3 minutes versus
the computer's 35 minutes, Kasimdzhanov offered to repeat
the position again and again. The computer—perhaps not
programmed to exploit an advantage time on the clock—allowed
the draw.
Off in
London, Adams had no such luck against Hydra, deemed the best
chess computer, in large part because of its intimidating
hardware. Based in Abu Dhabi, United Arab Emirates, it yokes
together 64 computers, each with an Intel Xeon 3.06-gigahertz
processor. The computer cluster boasts a total of 512 gigabytes
of memory. You'd expect that so much computing power would
lead to high-level play, but what's unusual is the character
of the play. As Adams said after the match, in an interview
published on the Web site of ChessBase GmbH, in Hamburg, Germany,
which produces the Fritz software: "Hydra plays very well
indeed. Very often it plays human-style chess, which is strange."
Chessbase
is putting new emphasis on making Fritz, its signature program,
play more like a human being. This involves playing according
to discernible plans or at least seeming to do so, particularly
in positions with no immediate threats. In these so-called
quiet positions, computers have been wont to shuffle their
pieces about without obvious purpose (but with a high tendency
to win, nonetheless). According to Frederic Friedel, a principal
of Chessbase, the company decided about 18 months ago to start
programming in more "chess knowledge."
Formerly,
Friedel says, when Fritz entered quiet positions, it evaluated
millions of possible end positions only to decide that several
continuations were almost exactly equal. It would then often
select a strange-looking but serviceable move no master would
favor because, Friedel says, "it rated the move a millionth
of a pawn better than the alternatives." Now Chessbase
has devised a way to structure the data generated in the look-ahead
phase to encourage the computer to favor lines that end up
moving its pieces to better squares—say, by getting
a knight to a central outpost supported by one of its own
pawns.
Friedel
recalls that Bell Laboratories' Ken Thompson, a pioneer
in computer chess and many other aspects of programming, used
to joke that no matter how much knowledge you implement, it
won't compensate for the loss of one move in search
depth. Fritz now looks about 16 moves deep (that's eight
moves by white and eight by black). The question was what
fraction of a play would have to be sacrificed to make Fritz
act like a human.
"We
knew implementing more knowledge might weaken Fritz's
results against other computers, but that has only one purpose:
to beat Shredder [a rival program] by 52 percent," he
says. "We once had to do that to survive commercially,
but we felt it was no longer so important."
In the
end, the programming changes did not make Fritz measurably
weaker than rival programs. They have, however, managed to
spook some grand masters. After losing to it in Bilbao, Bulgaria's
Veselin Topalov, ranked third in the world, asked, "What
have you done to Fritz?"