TITLE: Old Dreams Live On
AUTHOR: Eugene Wallingford
DATE: September 14, 2009 10:53 PM
DESC: 
-----
BODY:
<P ALIGN="right"><EM>
"Only one, but it's always the right one." <BR/>
-- Jose Raoul Capablanca, <BR/>
when asked how many moves ahead <BR/>
he looked while playing chess
</EM></P>

When I was in high school, I
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2005-12.html#e2005-12-23T10_19_08.htm">
   played a lot of chess</A>.
That's also when I first learned about computer
programming.  I almost immediately was tantalized by
the idea of writing a program to play chess.  At the
time, this was still a novelty.  Chess programs were
getting better, but they couldn't compete with the
best humans yet, and I played just well enough to
know how hard it was to play the game really well.
Like so many people of that era, I thought that
playing chess was a perfect paradigm of intelligence.
It looked like such a wonderful challenge to the
budding programmer in me.

I never wrote a program that played chess well, yet
my programming life often crossed paths with the
game.  My
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2005-10.html#e2005-10-16T21_52_27.htm">
   first program written out of passion</A>
was a program to implement a ratings system for our
chess club.  Later, in college, I wrote a program
to perform the
<A HREF="http://en.wikipedia.org/wiki/Swiss_system">
   Swiss system</A>
commonly used to run chess tournaments as a part of
my senior project.  This was a pretty straightforward
program, really, but it taught me a lot about data
structures, algorithms, and how to model problems.

Though I never wrote a great chessplaying program,
that was the problem that mesmerized me and
ultimately drew me to artificial intelligence and
a major in computer science.

In a practical sense, chess has been "solved", but
not in the way that most of us who loved AI as kids
had hoped.  Rather than reasoning symbolically about
positions and plans, attacks and counterattacks,
Deep Blue, Fritz, and all of today's programs win
by deep search.  This is a strategy that works well
for serial digital computers but not so well for
the human mind.

To some, the computer's approach seems uncivilized
even today, but those of us who love AI ought be
neither surprised nor chagrined.  We have long
claimed that intelligence can arise from any
suitable architecture.  We should be happy to
learn how it arises most naturally for machines
with fast processors and large memories.  Deep
Blue's approach may not help us to understand how
we humans manage to play the game well in the face
of its complexity and depth, but it turns out that
this is another question entirely.

Reading David Mechner's
<A HREF="http://mechner.com/david/compgo/sciences/">
   All Systems Go</A>
last week brought back a flood of memories.  The
Eastern game of Go stands alone these days among
the great two-person board games, unconquered by
the onslaught of raw machine power.  The game's
complexity is enormous, with a branching factor at
each ply so high that search-based programs soon
drown in a flood of positions.  As such, Go
encourages programmers to dream the Big Dream of
implementing a deliberative, symbolic reasoner in
order to create a programs that plays the game well.  
The hubris and well-meaning naivete of AI researchers
have promised huge advances throughout the years,
only to have ambitious predictions go unfulfilled
in the face of unexpected complexity.  Well-defined
problems such as chess turned out to be complex
enough that programs reasoning like humans were
unable to succeed.  Ill-defined problems involving
human language and the interconnected network of
implicit knowledge that humans seem to navigate so
easily -- well, they are even more resistant to our
solutions.

Then, when we write programs to play games like
chess well, many people -- including some AI
researchers -- move the goal line.  Schaefer
<I>et al</I>.
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2007-07.html#e2007-07-19T15_03_47.htm">
   solved checkers</A>
with
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2007-03.html#e2007-03-12T12_34_23.htm">
   Chinook</A>,
but many say that its use of fast search and a
big endgame databases is unfair.  Chess remains
unsolved in the formal sense, but even inexpensive
programs available on the mass market play far,
far better than all but a handful of humans in the
world.  The best program play better than the best
humans.

Not so with Go.  Mechner writes:

<BLOCKQUOTE><EM>
Go is too complex, too subtle a game to yield to
exhaustive, relatively simpleminded computer
searches.  To master it, a program has to think
more like a person.
</EM></BLOCKQUOTE>

And then:

<BLOCKQUOTE><EM>
Go sends investigators back to the basics--to the
study of learning, of knowledge representation, of
pattern recognition and strategic planning.  It
forces us to find new models for how we think, or
at least for how we think we think.
</EM></BLOCKQUOTE>

Ah, the dream lives!

Even so, I am nervous when I read Mechner talking
about the subtlety of Go, the depth of its strategy,
and the impossibility of playing it well in by
search and power.  The histories of AI and CS
have demonstrated repeatedly that what we think
difficult often turns out to be straightforward
for the right sort of program, and that what we
think easy often turns out to be achingly difficult
to implement.  What Mechner calls 'subtle' about Go
may well just be a name for our ignorance, for our
lack of understanding today.  It might be wise for
Go aficionados to remain humble...  Man's hubris
survives only until the gods see fit to smash it.

We humans draw on the challenge of great problems
to inspire us to study, work, and create.  Lance
Fortnow wrote recently about the
<A HREF="http://blog.computationalcomplexity.org/2009/09/mystique-of-open-problem.html">
   mystique of the open problem</A>.
He expresses the essence of one of the obstacles
we in CS face in trying to excite the current
generation of students about our discipline:
"It was much more interesting to go to the moon
in the 60's than it is today."
<A HREF="http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/abstract">
   P versus NP</A>
may excite a small group of us, but when kids
walk around with iPhones in their pockets and
play on-line games more realistic than my real
life, it is hard to find the equivalent of the
moon mission to excite students with the
prospect of computer science.  Isn't all of
computing like Fermat's last theorem:
"Nothing there left to dream there."?

For old fogies like me, there is still a lot
of passion and excitement in the challenge of
a game like Go.  Some days, I get the urge to
ditch my serious work -- work that matters to
people in the world, return to my roots, and
write a program to play Go.  Don't tell me it
can't be done.
-----