I used to be really into a good ‘ol game of chess. I still am, I
suppose. But it got old. There’s only so many possibilities —
Shannon’s number gives the lower bound to be only 10^3^, to be
precise, and the upper bound has been calculated at less than
2^155^, which is less than 10^46.7^. That’s factoring in all possible,
legal moves, and factoring out invalid or illegal moves. It doesn’t
factor in that human players are not the most logical creatures and
their playing can quickly become predictable. I mean, if you take a look
at game theory, in “Guess Two Thirds of the Average” as played in the
general population,[it’s statistically shown that humans do not think
beyond three logical iterations]. Chess is grand, and a good match is
always appreciated. But it just got old after a while.
Lately, I’ve been really into playing Go. Go is amazing, and I still
suck at it. I could probably waste my life away learning Go strategy,
and still not master the game. To compare it with chess, the maximum
number of legal moves in Go is 2.08168199382×10^170^, more than 130
orders of magnitude higher. That’s also more than double the amount of
particles in the universe. While super chess computers, such as Deep
Blue, can beat World Champion chess players, young children can often
beat even the best Go computers. However, as artificial intelligence
continually develops to higher levels,that trend is beginning to
change, which makes a computer’s aptitude for the game a useful
measurement of its capability for human-like thought.
Faced with such extraordinary complexity, our brains somehow find a
path, navigating the possibilities using mechanisms only dimly
understood by science. Both of the programs that have recently
defeated humans used variations on mathematical techniques originally
developed by Manhattan Project physicists to coax order from pure randomness.
Called the Monte Carlo method, it has driven computer programs to
defeat ranking human players six times in the last year. That’s a far
cry from chess, the previous benchmark of human cognitive prowess, in
which Deep Blue played Garry Kasparov to a panicked defeat in 1997,
and Deep Fritz trounced Vladimir Kramnik in 2006. To continue the golf
analogy, computer Go programs beat the equivalents of Chris Couch
rather than Tiger Woods, and had a multi-stroke handicap. But even six
victories was inconceivable not too long ago, and programmers say it
won’t be long before computer domination is complete.
There is, however, an asterisk to the programs’ triumphs. Compared to
the probabilistic foresight of our own efficiently configured
biological processor — sporting 10^15^ neural connections, capable of
10^16^ calculations per second, times two — computer Go programs are
inelegant. They rely on what Deep Blue designer Feng-Hsiung Hsu
called the “substitution of search for judgment.” They crunch numbers.
“People hoped that if we had a strong Go program, it would teach us
how our minds work. But that’s not the case,” said Bob Hearn, a
Dartmouth College artificial intelligence programmer. “We just threw
brute force at a program we thought required intellect.”
If only we knew what our own brains were doing.
Inasmuch as human Go prowess is understood, it’s explained in terms
of pattern recognition and intuition. “When there are groups of stones
arranged in certain ways, you can build visual analogies that work
very well. You can think, ‘This configuration radiates influence to
that part of the board’ — and it turns out it’s a useful concept,”
said Hearn. “The revolutionary people in the field have an intuitive
sense, and can look at things completely differently from other people.”
Image-based neuroscience supports this explanation, albeit vaguely.
When University of Minnesota researchers led by cognitive scientist
Michael Atherton scanned the brains of people playing chess and
compared them to Go-playing brains, they found heightened
activation in the Go players’ parietal lobes, a region responsible
for processing spatial relationships. But these observations,
saidAtherton, were rudimentary. “The higher-level stuff, we didn’t
figure out,” he said.
In a more recent brain-scanning study, Japanese researchers
compared professional and amateur Go players as they
contemplated opening- and end-stage moves. Both displayed parietal
lobe activity. During the end stages, however, professionals had
extremely high activity in their precuneus and cerebellum regions,
where the brain integrates a sense of space with our bodies and motions.
Put another way, professionals fuse their consciousness into the
decision tree of the game.
Go players have an ability “to think creatively and prune the search
tree in an aesthetic sense,” said Atherton. “They have a feel for the game.”
Artificial intelligence researchers historically tried to harness this
pattern-based approach, however poorly understood, to their Go
programs. It wasn’t easy. “When I’ve talked to Go professionals
about how they come to their decisions, it’s been difficult for them
to describe why a move is right,” said Doshay at UCSC, who designed a
Go computer program called SlugGo. “Go is a game of living
things, and you talk about it that way, as if the patterns might be alive.”
But if turning cryptic statements from Go masters into working
algorithms for determining the statistical health of game patterns was
impossible, there didn’t seem to be any other way of doing it. “It was
possible to sidestep the cognitive issues by throwing brute force at
chess,” said Hearn, “but not at Go.”
Compared to the challenge posed to a Go program, Deep Blue’s
computations — possible moves in response to a move, carried 12 cycles
into the future — are back-of-the-napkin scribblings. “If you look at
the game trees, there’s about 30 possible moves you can make from a
typical position. In Go, it’s about 300. Right away, you get
exponential scaling,” said Hearn.
With every anticipated move, the possibilities continue to scale
exponentially — and unlike chess, where captured pieces are counted
immediately, Go territory can switch hands until the game’s end.
Running a few branches down the tree is useless: take one step, and it
needs to be pursued, exponential scale by scale, until the game end.
According to Doshay, the number of Go’s end-states — 10^171^ — is
almost inconceivably smaller than the 10^1100^ different ways of
getting there. Without patterns to eliminate whole swaths of choices
from the outset, computers simply can’t cope with it, at least not
within time frames contained by the universe’s remaining existence.
But to Doshay, guiding computers with human-rules patterns was wrong
from the beginning.
“If you want computers to do something well, you concentrate on the
ways computers do things well,” he said. “Computers can generate
enormous quantities of random numbers very rapidly.”
Enter the Monte Carlo method, named by its Manhattan Project pioneers
for the casinos where they gambled. It consists of random simulations
repeated again and again until patterns and probabilities emerge: the
characteristics of an atomic bomb explosion, phase states in quantum
fields, the outcome of a Go game. Programs like MoGO and Many
Faces simulate random games from start to finish, over and over and
over again, with no concern for figuring out which of any given move
is best.
“At first, I was dismissive,” said Hearn. “I didn’t think there was
anything to be gained from random playouts.” But the programmers had
one extra trick: they crunched the accumulated statistics, too. Once a
few million random games are modeled, probabilities take form. Thus
informed, the programs devote extra processing power to promising
branches, and less power to less-promising alternatives.
The resulting game style looks human, but aside from a few rough human
heuristics, the patterns articulated by our intuitions are
unnecessary. “The surprising, mysterious thing to me is that these
algorithms work at all,” said Hearn. “It’s very puzzling.”
Puzzling it might be, but the game is almost over. Hearn and others
say that, having started to beat human professionals, Monte
Carlo-based programs will only get better. They’ll incorporate the
results of earlier games to their heuristic arsenal, and within a few
years — a couple decades at the most — be able to beat our best.
What is the larger significance of this? When computers finally
triumphed at chess, the world was shocked. To some, it seemed that
human cognition was less special than before. But to others, the
competition is an illusion. After all, behind every machine is the
hand that made it.
“There’s a strong tendency in humans to have a conceit about how far
we’ve advanced,” said Doshay. “But we’ve only really started
programming computers.”
While Go can be used to measure the intellectual capacity of artificial
intelligences, it can also be used to study self-replicating systems.
The British mathematician Conway, while studying von Neumann’s
algorithms for self-replicating machines, invented the Game of Life,
a cellular automata, with a Go board. The rules are incredibly simple:
[it’s statistically shown that humans do not think beyond three
logical iterations]: http://www.patternsinthevoid.net/blog/2011/06/game-theory-anarchism-ii-how-information-can-smash-the-state/
