HOUSE_OVERSIGHT_015696.jpg

6 Are the Androids Dreaming Yet?

king, gets up, and leaves the room. Kasparov has resigned, Deep Blue has
beaten him 3½ to 2½ points and is now the most powerful chess player
on the planet.
Later, when interviewed about his experience, Kasparov thought
Deep Blue must have been assisted by humans during the games because
the program appeared to play intuitively. The rules of the tournament
allowed humans to work on the program between matches, but not
during actual play. The argument has never been settled, and Deep
Blue was long ago dismantled. These days chess players avoid big public
matches against computers, arguing it is really a different sort of game.
A computer’s ability to crunch mathematically through all the many
possibilities means a chess player must play without error against a
machine, but can play a more interesting and fluid match against a fellow
human.
Chess is computer-friendly because it is a finite problem. You always
win, lose or draw. The game can’t go on forever because any position that
repeats itself more than three times is declared a draw, and if a player
makes 50 moves without moving a pawn or taking a piece, the game
is also declared a draw. In a typical game, each player makes 40 moves,
and on each turn you can choose from 30 possible moves. Although this
equates to a huge number of options, it is still a finite number.
It is possible, therefore, to create a perfect chess-playing machine.
Such a machine would project any position it encountered through
every permutation to the endgame. But, although chess is solvable using
brute force this might not be practical in our Universe. The storage
required to hold all the possible positions being analyzed would be
vast – needing most of the atoms in the Universe. You would need to
pack this information into a small enough space to allow fast retrieval in
order to play the first 40 moves in two hours. This would require storing
all the information within a sphere no larger than three light minutes.
Putting that much data in such a small space would exceed the Hawking
Bekenstein bound – a limit on the information carrying capacity of
space-time put forward by Stephen Hawking and Jacob Bekenstein
– causing the region of space-time to collapse to a black hole! Despite
these minor technical problems, an ingenious algorithm could be made
that was unbeatable: chess is essentially computable.
The term algorithm will often arise in the book, so it is worth giving
a little history. The word comes from the name of an 8th Century Persian
mathematician, Al-Khwarizmi, and means a step-by-step procedure. We
use one whenever we do long division or look up a phone number on

HOUSE_OVERSIGHT_015696