🚀 go-pugleaf

In article <1992Sep26.190032.62552@uvmark.uucp> jim@uvmark.uucp (Jim Todhunter) writes:

I presume those not theoretically inclined have already killed
this thread.  For the rest ...

>Since little usually comes from threads as this, I have been trying
>to stay out of this discussion.  However, I can resist the urge to
>post no longer.

>Many people have been throwing around terms without regard for the
>meaning of those terms.  These expressions include: solvable, 
>intractable, computable, and AI.  So in an attempt to set the record
>straight, I am going to place these words correctly in this context
>with respect to their meaning.

>1.  Is chess solvable?

>  While
>  this may not be the tradition phrasing of the question, it can easily
>  be shown to be an equivalent problem with respect to decidability.

Agreed.  And there are finite positions, so it's decidable.  I
would add that a program for determining if a given position
is a win, loss, or draw can run in constant time.  The smallest
such program might be larger than the physical universe, but
that's a minor detail generally ignored by Theory of Computation
types.

>2.  Is chess computable?

[Yes, and with bounded resources.  I can give a constructive
 argument for this one, rather than the nonconstructive one
 given.]

>3. Is chess intractable?

>  Intractability has a very specific meaning as applied to computer
>  algorithms.  Specifically, a problem is considered intractable if it
>  is so hard that no polynomial time algorithm can possibly solve it.
>  (The name given to this property is NP-completeness.  Formally, a
>  problem is NP-complete if it is polynomially reducible to the
>  decidability problem.  ...
  
Typo.  Substitute "satisfiability" for "decidability".  There are
several technically incorrect statements here.  In some areas
pseudo-polynomial-time algorithms are considered tractable.  NP-
complete problems are considered intractable, but haven't been
proved to be.  Almost the only thing that could get a CS theorist's
picture on the cover of Time is solving proving "P=NP" one way or
the other (and proving P=NP true would be a *real* shocker).

Specifically, a problem is NP-complete if it is no harder nor easier
than NP.  NP-hard means at least as difficult as any problem in NP,
and that is usually proved by reducing satisfiability to the problem
at hand, not the other way around.  NP-easy (or "in NP") means
no harder than any NP-hard problem, and can be shown in several
ways.  None of this has any bearing on chess on a limited board.

>  However, the theoretical notion of intractability stems from a need
>  to answer a basic question: can I solve this given problem efficiently?
>  So if we can show that a solution for chess is not computable in a 
>  reasonable period of time, then we have shown the problem to be so
>  large as to be intractable in the practical sense.

>  Given that solving chess requires visiting every node in the game
>  tree, [Analysis based on that assumption]

First of all, it is not necessary to visit every node in the game tree.
Period.  Alpha-beta pruning yields the same result as min-max, provided
each works with the same assumptions.  That is, an alpha-beta search
of the entire game tree yields the same result as min-max, while cutting
of many branches without analysis.  That's a minor point, though, since
A-B doesn't promise an easy solution either.

Second, many problems can be solved without exhaustive search.  There
is no reason to believe chess is among them, but there is no proof
that it isn't.  I give you the following (unlikely) possibility:

a. There is a static evaluation function S(P) that given a position
   returns W, L, or D.  It returns D for the opening position and
   for the position after white's first move.
b. There is a proof that from a position with evaluation D, whatever
   the opponent moves, there is a reply that restores an evaluation
   of D.
c. All positions in which mate can be given on the next move evaluate
   to W.
d. All positions in which mate on opponent's next move is unavoidable
   evaluate to L.

The existance of such an evaluation function would prove chess a draw.
Note that a program based on such a function would not necessarily
play winning chess.  A naive implementation would assiduously avoid
winning.  But it would solve the game.

>4. Are chess computers an instance of artificial intelligence?

>  Unfortunately, there is not a definitive answer here.

>5. Does any of this really matter?

>  Not really.

Amen.

>Hope you enjoyed reading this.

Me too.  I enjoy this sort of thing.  It has little to do with
chess as it is played by either people or computers, though.

-- Don Varvel (varvel@cs.utexas.edu)