🚀 go-pugleaf

In article <1992Sep25.220728.26568@unixg.ubc.ca> ramsay@unixg.ubc.ca (Keith Ramsay) writes:
>If I remember correctly, "generalized chess" is known to be PSPACE
>complete. Perhaps someone knows a reference?
>
> [ ... stuff deleted ... ]
>
>The same result is known for various other board games (I think it
>includes Go and Checkers). This suggests that they might be difficult
>to analyze exhaustively.
>
> [ ... stuff deleted ... ]
>

Actually, NxN checkers and NxN go are considered NP-complete.  They
are provably NP-hard.  Since I am posting from home, I don't have the
reference handy.  If you are extremely curious, e-mail me and I will
send you a reference when I am next in my office.

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?

  To answer this question, it is important to know what solvable
  means.  It does not mean a machine can be built that can hold all
  the possible positions.  Nor, does it mean that a forced win for
  white can be found before the year 2000.  In the context of chess,
  solvability means that the best lines of play can be determined
  for both sides (and hence the eventual outcome of the game).  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.

  Also necessary to answering this question is an agreement as to what
  game we are referring to when we say chess.  Here we are specifically
  addressing the argument that if you disallow certain drawing rules the
  game is infinite and hence unsolvable.  There are three rules here of
  interest: insufficient material, repetition, and the 50-move rule.  It
  should be apparent that cases of insufficient material should be
  treated as drawn.  It should also be apparent the three fold repetition
  should be treated as a drawing condition.  (Remember, we define
  solvability in terms of best play that produces a known result.  Thus,
  any position which repeats thrice should be treated as a draw since
  a decisive line, if one does exist, is reachable via a shorter path.)

  This leaves only one other drawing criteria--the 50-move rule.
  Fortunately, this rule is not necessary to show solvability.  Remember,
  that given any starting game state, there are a finite number of game
  states which may be derived from the starting state.  Although the
  number of legal sequences of games states may be infinite, the number
  of sequences which much be considered is bounded.  (From our conclusion
  above, the longest legal sequence of game states that we need to consider
  is 3n where n is the number of derivable game states.  The proof of
  this is quite simple, and is left as an exercise for the reader.)  Hence,
  the depth of the game tree is also bounded.

  With this in mind, it is clear that chess is a solvable game.  It is a
  relatively simple task of tree traversal.  Note, we have said chess is
  solvable; this does not mean chess is computable, tractable or anything
  else.  It means only that the information necessary to answer the question
  is bounded, and therefore the problem is solvable given infinite resources.

2.  Is chess computable?

  Strictly speaking, the question of computability is also answered in
  the context of infinite resources.  Simply put, if you can build a
  theoretical Turing machine that can run a program to solve the problem,
  the problem is computable.  Showing chess satisfies this definition of
  computability is pretty straight forward.  The more interesting question
  is can we envisage a Turing machine that will compute the result within
  bounded resources.

  To this end, we now consider the variation of the chess problem which
  enforces the 50-move rule (and its various exceptions).  We justify the
  inclusion of this rule with two arguments:
   a) Just as we consider the issue of bounded resources interesting from
      a practical perspective, we consider the issue of the played game
      from a practical perspective--that is we are limiting the problem
      to games that are of practical (read might be played out in a
      normal tournament environment) interest.  Thus, the fact that a
      forced mate in 1000 may exist from a given position is of theoretical
      interest, but on no practical value since we assume any pair of
      reasonable players would end the game in a draw.
   b) Given a N-move rule solution which works in bounded space, it is
      easy to shown that an N+1-move rule solution will work in bounded
      (albeit larger) workspace.  Thus, we are merely choosing a bounding
      point for the solution.

  Now, consider a generating function M(s,n) which generates the nth
  legal game state immediately reachable (1-move away) from game state
  s.  (Constructing such a function is of course trivial.)  Given this
  function, it is possible to produce a tree traversal algorithm for
  chess which does not need to store the entire tree at any given time.
  Since this a somewhat straightforward but long exercise, the construction
  of this algorithm will not be shown here, but a brief summary of the
  main points is:
    - For any given n-move move rule condition, there is a maximally long
      sequence of game states.  (For the usual 50-move rule, that maximum
      is around 5700 moves or just under 12000 game states.)
    - For each game state, in the current sequence under examination, we
      need only save the game state and the last move number (parameters s
      and n to our generating function).
    - A recursive procedure can be expressed which traverses the game tree
      by enumeration of all possible paths in the order determined by the
      generating function M.

  In any event, it should be clear that chess is computable within bounded
  workspace.

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.  We shall avoid a theoretical discussion of
  the relevance of P & NP space here, since it is my intent to inform,
  not befuddle.)
  
  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, let's consider how long it would take to examine all the nodes.
  (Since I don't know the number nodes in the full game tree, I will
  use an arbitrary figure of 10^140 for this discussion.  I believe
  the actually number is sufficiently large that the answer to the 
  tractability question will not change.  This justification should
  also suffice for those who will cry foul because I am not considering
  mini-max pruning.)  There are 31,536,000 seconds in a year (roughly
  10^7.5).  Let us assume, our hypothetical machine can visit a billion
  nodes per second (10^9).  This means it would take approximately 10^122
  years to solve the problem.  This would render chess intractable under
  most definitions of reasonable time.

4. Are chess computers an instance of artificial intelligence?

  Unfortunately, there is not a definitive answer here.  There are
  two major schools of thought for what defines artificial intelligence.
  One school defines AI as modeling intelligent thought processes.
  The other defines AI as solving problems that are normally considered
  to require intelligence.  Whether or not you consider computer chess
  a AI application, depends upon the school with which you are in agreement.

5. Does any of this really matter?

  Not really.

Hope you enjoyed reading this.


-- 
James W. Todhunter, Director, Research & Development
jim%uvmark@merk.com
VMark Software, Inc.  30 Speen Street  Framingham, MA  01701-1800 USA
Telphone: (508) 879-3311  Facsimile: (508) 879-3332