Re:chess questions

[Subbarao Kambhampati <rao@asu.edu>]

From: Ryan Stephens <dryanstephens@yahoo.com>
Subject: Re: On the disconnectedness of the 8-puzzle search space (or Learning
 lessons the hard way)+History of sliding tile puzzles
Date: Tue, 02 Oct 2001 20:53:07 -0700 (PDT)
Message-ID: <20011003035307.17727.qmail@web20009.mail.yahoo.com>

dryanstephens> 
dryanstephens>  A couple of things: Something I forgot to ask during
dryanstephens> class was the result of two computers playing one
dryanstephens> another using the same algorithms.  This would
dryanstephens> essentially be a merger of two complete algorithms,
dryanstephens> assuming they were both using some form of minimax,
dryanstephens> which is complete.  I imagine the end result would be
dryanstephens> an incomplete game (infinitely long unless there were
dryanstephens> some cutoffs) at least some of the time, since, for
dryanstephens> example, if both players were down to a king each they
dryanstephens> would potentially chase each other around the board
dryanstephens> forever.  I don't see a feature of minimax or a-b
dryanstephens> pruning that would identify an infinite path without
dryanstephens> some artificial counter being introduced.  Is there a
dryanstephens> way that this can be identified in the algorithm or
dryanstephens> does it require some cutoff?

You mean the "what happens if the irresistible force meets the
immovable object" angle? ;-) Basically if the search is on complete
gametrees (i.e.., all leaf nodes are terminal nodes), we should expect 
a draw always. If the search is on a depth-limited search tree (to be
discussed next class), then it is possible that two moves which have
equal backed up value are actually quite different in reality, and
based on the way ties are broken one machien might win sometimes.  


dryanstephens> Issue #2 - This Kasparov vs Deep Blue thing was a giant
dryanstephens> commercial for IBM and chess.  Deep Blue didn't beat
dryanstephens> Kasparov, a team of engineers beat Kasparov and they
dryanstephens> used a giant calculator to do it.  If, instead, the
dryanstephens> machine played Kasparov on a regular basis for some
dryanstephens> period of time until it "learned" to beat him--without
dryanstephens> the intervention of engineers to introduce tweaks--that
dryanstephens> could be considered a true win.  I don't doubt that
dryanstephens> such an event will happen in my lifetime, but this
dryanstephens> thing was a silly marketing idea that people took too
dryanstephens> seriously: "man vs machine".  You didn't get into your
dryanstephens> personal opinion of the event in the lecture; I
dryanstephens> wondered what your thoughts were.  

I sent a op-ed piece by Drew McDermott that I basically agree with. 

Regarding your specific point, yes this is a commercial for IBM, but
it is a well-deserved one IMHO--the folks who build DeepBlue had been
working in computer chess for years; they are all first class
researchers.