Is chess in NP?
Antti Juhani Ylikoski
An individual recently asked whether chess is in NP. This posting
contains some simple considerations dealing with that question.
The classical theory of the NP problems, or, the theory of
nondeterministic Turing machines, mostly deals with decision problems,
in other words problems which have a YES/NO answer, and not function
problems such as the calculation of the optimal answer to a problem,
for example the calculation of the optimal move in chess.
The reason for this is the behaviour of the nondeterministic Turing
machine (NDTM). From its starting state with its input data, it may
execute several different computations (that is the meaning of
"nondeterminism" in the term "nondeterministic TM"). Hence, it is
easy to use NDTM as language acceptors, by defining that the NDTM
accepts its input if there is one accepting computation among the set
of different computations that it may execute, and rejects its input
if there is no accepting computation amongst the nondeterministically
chosen set of computations. But it is not totally evident how we
should define the result that an NDTM computes because there may be
several different nondeterministically computed ones.
However, it is possible to define the result that an NDTM computes.
Several definitions are possible:
Definition A. Let the result that is computed be the result of one
nondeterministically chosen computation amongst the ones that the NDTM
may execute, chosen at random.
Definition B. Let the result be the sequence of all possible results
that the NDTM may nondeterministically compute.
Definition C. Require that only one computation by the NDTM ends in
the state "ACCEPT", and all other nondeterministic computations end in
the state "REJECT". Then, the result that is computed is the result
computed by the one computation that ended at the state "ACCEPT".
Now, for chess. With Definition A the result is not very interesting.
Chess is in NP, and an NDTM can play chess by nondeterministically
choosing its move. (If we only could make it nondeterministically
choose the best possible move! But that would require making the NDTM
even more magical than it is.)
With Definition B, we cannot play chess ... a sequence of
nondeterministically generated moves is not good for a move against an
opponent.
With Definition C, we could use some chess algorithm such as the
alpha-beta algorithm. But, then, the nondeterminism does not bring us
any advantage, and we might just as well use a deterministic Turing
machine. Anyway, with Definition C chess is in NP, but this result is
not too exciting.
Hence, chess is in principle in NP, but this result is not very
interesting. But it would be very interesting if someone could show
that chess is an NP-complete problem, where the size of the problem
could for example be the depth of the game tree to be examined.
cheers, Andy Ylikoski
graduate student
Helsinki Univ of Tech
Jasper Phillips
In article <svyafli...@alpha.hut.fi>,
Antti Juhani Ylikoski <ylik...@alpha.hut.fi> wrote:
[stuff about NP and chess snipped]
Well, I seem to remember that there are more possible positions in
chess than there are atoms in the universe, presumably making it
impossible to "solve" -- which would make it at least as hard
as any NP complete problem.
-Jasper
--
/\ Jasper Phillips (Pit Fiend) ______,....----,
/VVVVVVVVVVVVVV|==================="""""""""""" ___,..-'
`^^^^^^^^^^^^^^|======================----------""""""
\/ http://www.engr.orst.edu/~philljas/
Patrick Juola
In article <svyafli...@alpha.hut.fi> Antti Juhani Ylikoski <ylik...@alpha.hut.fi> writes:
>An individual recently asked whether chess is in NP. This posting
>contains some simple considerations dealing with that question.
>
>The classical theory of the NP problems, or, the theory of
>nondeterministic Turing machines, mostly deals with decision problems,
>in other words problems which have a YES/NO answer, and not function
>problems such as the calculation of the optimal answer to a problem,
>for example the calculation of the optimal move in chess.
I think you're on the wrong track with this sort of reasoning.
The usual formulation for NP-style queries on game trees is
"Is this position a forced win for the first player?" and/or
"Is this position a forced draw for the first player?"(*) Phrased
in this fashion, it's easy enough to see how a nondeterministic
machine could "guess" the right answer. If I determine that
the starting position *is* a forced win for white, then by simply
running through the (constant-bounded) possible moves for white
and determining which of them still result in a forced-win, I've
determined an optimal move.
On the other hand, there's a lot more to NP than simply running something
on an NDTM.
The first property is that the running time of this algorithm (on an
NDTM) has to be polynomial with the size of the problem. It's not
clear what the size of a chess problem is -- or, more accurately,
it seems that chess has a fixed size (the board is 8x8, there
are at most 32 pieces, &c.) and so it's not really possible to define
something "twice as big" as chess. Or it is, but then we're no
longer talking about how hard chess is -- we're talking about how
hard chess is compared to a 16x16 version of chess.
Because chess has a constant size, there is a constant-time algorithm
for it (the unbuildable table lookup).
The other factor is that even if we were willing to examine the
question "how hard is a NxN version of chess", it's still not in
NP -- at least, to the best of our ability.
It's possible for an NDTM to guess the best move for white -- but it
then has to calculate every possible black response to confirm that
it is, in fact, the best move. Simply guessing a sequence of moves
that leads to a white win is insufficient, as, even if white played
those moves exactly, black wouldn't (especially if he knows that
this sequence results in loss).
>We could use some chess algorithm such as the
>alpha-beta algorithm. But, then, the nondeterminism does not bring us
>any advantage, and we might just as well use a deterministic Turing
>machine. Anyway, with Definition C chess is in NP, but this result is
>not too exciting.
This statement is wrong. Just because a program runs on an NDTM
doesn't mean that it's in NP. It needs to run *in polynomial time*
on an NDTM -- which alpha/beta does not.
And, in fact, if it could be shown that chess *were* in NP, that
would be a theoretical breakthrough of the first water.
-kitten
Hans Bodlaender
In <5me75s$k...@news.ox.ac.uk> pat...@gryphon.psych.ox.ac.uk (Patrick Juola) writes:
>
>And, in fact, if it could be shown that chess *were* in NP, that
>would be a theoretical breakthrough of the first water.
>
Chess can be solved in constant time, so is in NP. If we talk about
generalized chess, i.e., chess on larger boards, then it has been shown that
the game is PSPACE-complete, which means that it is very unlikely to be in NP,
as when you can show that generalized chess is in NP, then you would have
proven NP=PSPACE - expect a tremendous lot of fame as a theoretical computer
scientist then.
--
Hans Bodlaender - Department of Computer Science - Utrecht University
P.O. Box 80.089 - 3508 TB Utrecht - the Netherlands
ha...@cs.ruu.nl http://www.cs.ruu.nl/~hansb/index.html
Patrick Juola
In article <5meaa4$l9u$1...@krant.cs.ruu.nl> ha...@cs.ruu.nl (Hans Bodlaender) writes:
>In <5me75s$k...@news.ox.ac.uk> pat...@gryphon.psych.ox.ac.uk (Patrick Juola) writes:
>>
>>And, in fact, if it could be shown that chess *were* in NP, that
>>would be a theoretical breakthrough of the first water.
>>
>
>Chess can be solved in constant time, so is in NP. If we talk about
>generalized chess, i.e., chess on larger boards, then it has been shown that
>the game is PSPACE-complete, which means that it is very unlikely to be in NP,
>as when you can show that generalized chess is in NP, then you would have
>proven NP=PSPACE - expect a tremendous lot of fame as a theoretical computer
>scientist then.
Actually, I don't think that generalized chess is known to be PSPACE-complete
as it's not known to be *in* PSPACE. 8-)
-k.
Mike ROBSON
ha...@cs.ruu.nl (Hans Bodlaender) writes:
>In <5me75s$k...@news.ox.ac.uk> pat...@gryphon.psych.ox.ac.uk (Patrick Juola) writes:
>>
>>And, in fact, if it could be shown that chess *were* in NP, that
>>would be a theoretical breakthrough of the first water.
>>
>Chess can be solved in constant time, so is in NP. If we talk about
>generalized chess, i.e., chess on larger boards, then it has been shown that
>the game is PSPACE-complete, which means that it is very unlikely to be in NP,
>as when you can show that generalized chess is in NP, then you would have
>proven NP=PSPACE - expect a tremendous lot of fame as a theoretical computer
>scientist then.
>--
>Hans Bodlaender - Department of Computer Science - Utrecht University
>P.O. Box 80.089 - 3508 TB Utrecht - the Netherlands
>ha...@cs.ruu.nl http://www.cs.ruu.nl/~hansb/index.html
No. Generalised chess has been shown to be Exptime-complete[1]. So showing it
to be in NP would indeed be a great breakthrough but showing it to
be PSPACE-complete would also be a great breakthrough (though not
quite as great).
[1] A.S. Fraenkel and D. Lichtenstein, Computing a perfect strategy
for n x n chess requires time exponential in n, J. Combinatorial Theory
Series A, vol 31, 1981, p 199-213.
--
J.M. Robson
LaBRI, Universite de Bordeaux 1
Hans Bodlaender
Apologies. I was indeed wrong: I had remembered the Fraenkel-Lichtenstein
result wrong; probably mixing up a few of the `complexity of games' results in
this area.
Ilias Kastanas
In article <5mdtln$81t$1...@news.nero.net>,
Jasper Phillips <phil...@tn.ENGR.ORST.EDU> wrote:
>In article <svyafli...@alpha.hut.fi>,
>Antti Juhani Ylikoski <ylik...@alpha.hut.fi> wrote:
>
>[stuff about NP and chess snipped]
>
>Well, I seem to remember that there are more possible positions in
>chess than there are atoms in the universe, presumably making it
>impossible to "solve" -- which would make it at least as hard
>as any NP complete problem.
Hmm, too bad for all the atoms in the universe -- the notion of NP
doesn't even apply to chess. You need N x N chess (or go, or checkers..),
i.e. variable-size problem instances. And N x N chess, however defined,
is not chess.
Ilias
Andy Ylikoski
In this thread, Patrick Juola mentioned the use of an NDTM for
examining the (horribly large) chess game tree.
It is a nontrivial research question whether the magical quality of an
NDTM to nondeterministically guess answers to problems would speed up
such a traditional deterministic game tree algorthm as the alpha-beta
algorithm, which is inherently exponential (BTW the use of alpha-beta
pruning diminishes the exponent to a half). [Of course P.J. is
correct about my NDTM/alpha-beta mistake. I had a spell of
absent-mindedness late in the evening.]
Of course we could have the NDTM nondeterministically generate the
entire game tree and "define" that it accepts chess if White has a
forced win and rejects chess if Black can force a draw but this is not
a very interesting application of the magic of nondeterminism.
best regards, Andy Ylikoski
indigo
In article <5mdtln$81t$1...@news.nero.net>,
Jasper Phillips <phil...@tn.ENGR.ORST.EDU> wrote:
>In article <svyafli...@alpha.hut.fi>,
>Antti Juhani Ylikoski <ylik...@alpha.hut.fi> wrote:
>
>[stuff about NP and chess snipped]
>
>Well, I seem to remember that there are more possible positions in
>chess than there are atoms in the universe, presumably making it
>impossible to "solve" -- which would make it at least as hard
>as any NP complete problem.
Not really. A problem that runs in O(n^10000) time will likely generate
one of those "all the atoms in the universe type numbers, yet will
still not be NP complete, as it runs in polynomial time.
Chess is not NP complete. In fact, it can be solved in constant time.
NP completeness, and algorithmic running time in general, is related
to how the running time grows as the input size increases. It is a measure
of what the algorithm can guarantee. If you give me n pieces of data,
and I can guarantee I can process them in (C * n^2) operations, regardless
of n, then my algorithm is said to run in O(n^2) time.
What does this have to do with chess? Well, nothing. Chess doesn't have
varible input sizes...every position can be derived from one fixed board
size, one set of fixed pieces, one fixed starting position, and games
that for all intents and purposes, have fixed lengths. Because of
this, it only takes a constant amount of time to perform a full breadth
mimimax search to some depth corresponding to the longest possible game,
somewhere around 10,000 ply I think.
So basically, with some fixed number of operations, I can solve any position
you care to give me. Granted, this number is very, very large, and has
nothing to do with a practical solution, but it is nevertheless, a constant.
yo...@sympatico.ca
On 27 May 1997 09:42:28 GMT, ha...@cs.ruu.nl (Hans Bodlaender) wrote:
>Chess can be solved in constant time, so is in NP.
Wouldn't you have to ascertain first that the steady state theory of
the universe is correct, and that the universe will not collapse upon
itself eventually?
If the latter *is* the case, then you'll never get chess solved; There
won't be time.
Dave Bowers
*********
Do not respond to yo...@sympatico.ca
Rather, insert "shire" between york and @ and then respond.
Steve Robbins
> contains some simple considerations dealing with that question.
>
> The classical theory of the NP problems, or, the theory of
> nondeterministic Turing machines, mostly deals with decision problems,
> in other words problems which have a YES/NO answer, and not function
> problems such as the calculation of the optimal answer to a problem,
> for example the calculation of the optimal move in chess.
Actually, it's even more complicated than that. Complexity theory
concerns itself with running time (or space, or other resource) **as a
function of input length**. When dealing with chess, what is the
"input"? A description of the board, most naturally. But this
description is of constant size, so there is no sense in which the
running time is a function of the input length. Thus, asking whether
chess is in NP doesn't have any meaning.
To get around this, you might try to formulate chess on variable-sized
boards. For example, you could easily imagine the game of checkers
played on an N by N board. Or the game of go. Both of these are
PSPACE-hard, according to Garey and Johnson. But, returning to chess,
it's not clear how to extend the rules to N by N boards. The second
row would obviously have N pawns, but what pieces would you use in the
first row?
As for your decision problem versus computation problem conundrum, the
standard technique is to study a related decision problem first. For
instance:
Q: Given a board configuration, does white have a forced win?
(This is how the checkers and go questions are phrased, btw)
[ ... ]
> But it would be very interesting if someone could show that chess is
> an NP-complete problem, where the size of the problem could for
> example be the depth of the game tree to be examined.
Ah! Now this is a different problem. If you only want to search to a
fixed depth, it sounds like a generic game-tree search problem. I
don't know offhand, but I suspect this would be NP-hard.
--
--
Steve Robbins <st...@nyongwa.montreal.qc.ca>
First, we take Manhattan, then we take Berlin.
Mike ROBSON
st...@nyongwa.montreal.qc.ca (Steve Robbins) writes:
>To get around this, you might try to formulate chess on variable-sized
>boards. For example, you could easily imagine the game of checkers
>played on an N by N board. Or the game of go. Both of these are
>PSPACE-hard, according to Garey and Johnson. But, returning to chess,
>it's not clear how to extend the rules to N by N boards. The second
>row would obviously have N pawns, but what pieces would you use in the
>first row?
>As for your decision problem versus computation problem conundrum, the
>standard technique is to study a related decision problem first. For
>instance:
> Q: Given a board configuration, does white have a forced win?
>--
>--
>Steve Robbins <st...@nyongwa.montreal.qc.ca>
>First, we take Manhattan, then we take Berlin.
All 3 of these games (chess, checkers, go) generalised to an n by n
board were shown to be Exptime complete in the early eighties.
Jasper Phillips
In article <5mem7l$2...@gap.cco.caltech.edu>,
Ilias Kastanas <ika...@alumnae.caltech.edu> wrote:
>In article <5mdtln$81t$1...@news.nero.net>,
>Jasper Phillips <phil...@tn.ENGR.ORST.EDU> wrote:
>>
>>Well, I seem to remember that there are more possible positions in
>>chess than there are atoms in the universe, presumably making it
>>impossible to "solve" -- which would make it at least as hard
>>as any NP complete problem.
>
>
>
> doesn't even apply to chess. You need N x N chess (or go, or checkers..),
> i.e. variable-size problem instances. And N x N chess, however defined,
> is not chess.
>
>
> Ilias
By the letter of NP, yes. I think you're missing the spirit though.
Although chess is finite (hmmmm, actually, I don't think anyone's
proved this, but lets assume), it is large enough that it is entirely
impractical to solve it (not enough time/matter in the universe, etc.).
Chess programs consequently are limited as to how far ahead in the game
they can look. Take the ply depth of your search as N, check the size of
your resultant search goes, and you have something that can be treated
as a variable size problem, with the length of time your heuristic takes
dependant on how far ahead you look. Now (if) chess is finite, this only
holds true while you stay inside the boundry where chess is actually
solved -- but this is so large that you can ignore it in practice.
I realize I'm stretching things a bit, since this heuristic doesn't
actually "solve" anything (although you can perhaps look at the case where it
wins most of the time as a solution), but I don't see it as so different
from NP.
Anyway, as far as my original post goes, perhaps I should have said
something more like "In practice chess is at least as difficult as
any NP complete problem" (hard having a little extra meaning) ;if
you look at it the way point out, the comparison isn't meaningless.
Patrick Juola
In article <5mgdlg$416$1...@news.nero.net> phil...@tx.ENGR.ORST.EDU (Jasper Phillips) writes:
>In article <5mem7l$2...@gap.cco.caltech.edu>,
>Ilias Kastanas <ika...@alumnae.caltech.edu> wrote:
>>In article <5mdtln$81t$1...@news.nero.net>,
>>Jasper Phillips <phil...@tn.ENGR.ORST.EDU> wrote:
>>>In article <svyafli...@alpha.hut.fi>,
>>>Antti Juhani Ylikoski <ylik...@alpha.hut.fi> wrote:
>>>
>>>[stuff about NP and chess snipped]
>>>
>>>Well, I seem to remember that there are more possible positions in
>>>chess than there are atoms in the universe, presumably making it
>>>impossible to "solve" -- which would make it at least as hard
>>>as any NP complete problem.
>>
>>
>> Hmm, too bad for all the atoms in the universe -- the notion of NP
>> doesn't even apply to chess. You need N x N chess (or go, or checkers..),
>> i.e. variable-size problem instances. And N x N chess, however defined,
>> is not chess.
>they can look. Take the ply depth of your search as N, check the size of
>your resultant search goes, and you have something that can be treated
>as a variable size problem, with the length of time your heuristic takes
>dependant on how far ahead you look. Now (if) chess is finite, this only
>holds true while you stay inside the boundry where chess is actually
>solved -- but this is so large that you can ignore it in practice.
>
>I realize I'm stretching things a bit, since this heuristic doesn't
>actually "solve" anything (although you can perhaps look at the case where it
>wins most of the time as a solution), but I don't see it as so different
>from NP.
Hmm...
Decision problem : Given a chess position, does white have a forced-win
in N ply or fewer?
The problem is that it's still solvable by a table lookup.
Excluding table solutions, it looks suspiciously exponential; but that
might be a circular exclusion.
-kitten
Patrick Juola
In article <ntnem5...@hilbert.nyongwa.montreal.qc.ca> st...@nyongwa.montreal.qc.ca (Steve Robbins) writes:
>In article <svyafli...@alpha.hut.fi>,
>Antti Juhani Ylikoski <ylik...@alpha.hut.fi> wrote:
>> contains some simple considerations dealing with that question.
>>
>> The classical theory of the NP problems, or, the theory of
>> nondeterministic Turing machines, mostly deals with decision problems,
>> in other words problems which have a YES/NO answer, and not function
>> problems such as the calculation of the optimal answer to a problem,
>> for example the calculation of the optimal move in chess.
>
>Actually, it's even more complicated than that. Complexity theory
>concerns itself with running time (or space, or other resource) **as a
>function of input length**.
Umm... I believe that this is overstating the case. Complexity theory
concerns itself with running time (&c) AS A FUNCTION OF PROBLEM SIZE,
which is usually related to input length, but not necessarily. For
example, database queries are usually expressed in terms of time
to resolve a given query relative to the size of the existing
database, but without dealing with the time necessary to "input" the
database (which is assumed to be fixed).
>To get around this, you might try to formulate chess on variable-sized
>boards. For example, you could easily imagine the game of checkers
>played on an N by N board. Or the game of go. Both of these are
>PSPACE-hard, according to Garey and Johnson. But, returning to chess,
>it's not clear how to extend the rules to N by N boards. The second
>row would obviously have N pawns, but what pieces would you use in the
>first row?
>
>As for your decision problem versus computation problem conundrum, the
>standard technique is to study a related decision problem first. For
>instance:
>
> Q: Given a board configuration, does white have a forced win?
>
>(This is how the checkers and go questions are phrased, btw)
Which can be generalized to "does white have a forced win in N ply
or less?"
But this is, as I pointed out earlier, solveable by a table-lookup.
Gargle Zndflxtzyh
>In article <svyafli...@alpha.hut.fi>,
>Antti Juhani Ylikoski <ylik...@alpha.hut.fi> wrote:
>
>[stuff about NP and chess snipped]
>
>Well, I seem to remember that there are more possible positions in
>chess than there are atoms in the universe, presumably making it
>impossible to "solve" -- which would make it at least as hard
>as any NP complete problem.
the number of positions have nothing whatsoever to do with if the
problem is NP complete or not!
(and neither does it have anything to do with if the problem is solvable).
imagine a (very dull) game, where to pieces have to walk from one
end of the board to another. The board is like a chess board only much much
bigger (100000000000 x 10000000000000 fields). And the pieces can move like a
king but not kill of each other.
In this game it's easy to see who will win. If both pieces start at the same end
the one who starts will win.
But there is many many different positions in this game.
--
- Artificial Intelligence: the art of making computers that behave like the
ones in movies. -
====================== Anders Nielsen, jo...@diku.dk =========================
Dr A. N. Walker
Mike ROBSON wrote:
> All 3 of these games (chess, checkers, go) generalised to an n by n
> board were shown to be Exptime complete in the early eighties.
I thought generalised checkers [draughts] had been shown to
be pspace-complete [like hex; and presumably Othello/reversi?]? But
perhaps that was a simplified version.
The proof that generalised chess is exptime-complete relies on
finding games of exponential length [as a function of the size of the
input]; provided that the 50-move rule is generalised in a sensible
way [eg, linear or quadratic, but not exponential, in the board size],
chess is "only" pspace-complete. "Even" this result makes it unlikely
that there is a "simple" function of position which would suffice to
generate correct play; in other words, we probably have to slog our
way through a large part of the game tree.
Of course, nothing above says anything of interest about real
8x8 chess, nor about the difficulty of solving particular positions,
such as the starting position.
_______
PS: A given chess position can be placed on an exponentially larger
board to give an exponential increase in the "50-move rule" at the
expense of a linear increase in the description of the position.
Explain, in words of one syllable or less, why this does not provide
an elementary proof that exptime = pspace.
--
Andy Walker, Maths Dept., Nott'm Univ., UK.
a...@maths.nott.ac.uk
Guy Del Mistro
indigo wrote:
> So basically, with some fixed number of operations, I can solve any position
> you care to give me. Granted, this number is very, very large, and has
> nothing to do with a practical solution, but it is nevertheless, a constant.
>
This is only correct within given restrictions. For example, you cannot
solve chess if your position is just 2 kings on the board. There is
also no a priori reason that chess can be solved at all! There are
obviously positions from which no matter what combination of moves
your opponent makes you can make a move to lead to a win and hence a
table-like look up solution exists. However, the reverse must also be
true for other positions. There are also a great many situations where
you can force a draw. In general, however, all situations are open, ie.
dependent.
The solution to chess, if one exists, is one which avoids all negative
states of play, ie. ones from which your opponent can force a win. My
personal belief is that if there is a solution to chess then it will
lead to a draw - any win/loss depending on non-forced mistakes.
Guy
-disclaimer-
unless stated otherwise, everything in the above message is personal opinion
and nothing in it is an official statement of molecular simulations inc.
Chris Malcolm
If the current "arguments" here about Deep Blue, Kasparov, the limits of
computers, artificial intelligence, and so on, are a representative
sample of the cognitive powers of human beings, then it is amazing that
humans beings can play chess at all.
--
Chris Malcolm c...@dai.ed.ac.uk +44 (0)131 650 3085
Department of Artificial Intelligence, Edinburgh University
5 Forrest Hill, Edinburgh, EH1 2QL, UK DoD #205
Ed Seedhouse
Guy Del Mistro <g...@msi.com> wrote:
>This is only correct within given restrictions. For example, you cannot
>solve chess if your position is just 2 kings on the board.
On the contrary, this position is already solved, since the FIDE rules
now state that it is a draw.
>There is
>also no a priori reason that chess can be solved at all!
Once again it has been mathematically proven that you are wrong.
PERIOD.
Ed Seedhouse
President, Victoria Chess Club.
CFC Rating: 2047
Tom Burgess
Chris Malcolm wrote:
>
> If the current "arguments" here about Deep Blue, Kasparov, the limits of
> computers, artificial intelligence, and so on, are a representative
> sample of the cognitive powers of human beings, then it is amazing that
> humans beings can play chess at all.
>
It IS amazing. Why should humans be good at this sort of reasoning?
Elementary probability (which should have been more useful in
evolutionary history) is counter-intuitive to most people. Also
reasoning about complex interacting systems, e.g. economics. So why
can we (or a few of us, at any rate) play chess well?
regards, tom
Patrick Juola
In article <338F62...@msi.com> Guy Del Mistro <g...@msi.com> writes:
>indigo wrote:
>> So basically, with some fixed number of operations, I can solve any position
>> you care to give me. Granted, this number is very, very large, and has
>> nothing to do with a practical solution, but it is nevertheless, a constant.
>>
>
>also no a priori reason that chess can be solved at all! There are
>obviously positions from which no matter what combination of moves
>your opponent makes you can make a move to lead to a win and hence a
>table-like look up solution exists. However, the reverse must also be
>true for other positions. There are also a great many situations where
>you can force a draw. In general, however, all situations are open, ie.
>dependent.
This is *NOT* true. For all positions, including the starting one,
at least one player must be able to force a win or a draw.
-kitten
Paul Speed
Patrick Juola (pat...@gryphon.psych.ox.ac.uk) wrote:
: -kitten
Ah, now if that is what is considered "solving chess" then the
assertion would be much easier to disprove than solving from the starting
position. One would only need to come up with one reachable board
positioning where the statement is false and it disproves the assertion.
Although finding that positioning is another problem unto itself.
-Paul
Guy Del Mistro
Patrick Juola wrote:
> >... There is
> >also no a priori reason that chess can be solved at all! There are
> >obviously positions from which no matter what combination of moves
> >your opponent makes you can make a move to lead to a win and hence a
> >table-like look up solution exists. However, the reverse must also be
> >true for other positions. There are also a great many situations where
> >you can force a draw. In general, however, all situations are open, ie.
> >dependent.
>
> This is *NOT* true. For all positions, including the starting one,
> at least one player must be able to force a win or a draw.
>
> -kitten
All you are saying here is that chess has only 3 conclusions, ie. win,
loss and draw. Which one will actually be the outcome depends on what
the other player does. What I said *IS* true. There IS NO GUARENTEE that
that you can force the game into a winning state, or drawing state for
that matter, from a random openning position. This is what finding a
solution to chess is all about but until someone proves there is such a
solution the question is still open.
For example, by following "the book" you might start an openning that
has 99.999% chance of winning or drawing based on move-tree analysis,
assuming that you always do the "best" move. However, if that 0.001%
chance, ie. 1 or 2 pivitol moves at some point in your opponent's game,
is obvious when it comes up then the 99.999% chance of not-losing means
nothing!
Patrick Juola
In article <2GLMBV$0...@prophecy.mnsinc.com> ke...@mnsinc.com (Paul Speed) writes:
>Patrick Juola (pat...@gryphon.psych.ox.ac.uk) wrote:
>: In article <338F62...@msi.com> Guy Del Mistro <g...@msi.com> writes:
>: >indigo wrote:
>: >> So basically, with some fixed number of operations, I can solve any position
>: >> you care to give me. Granted, this number is very, very large, and has
>: >> nothing to do with a practical solution, but it is nevertheless, a constant.
>: >>
>: >
>: >This is only correct within given restrictions. For example, you cannot
>: >also no a priori reason that chess can be solved at all! There are
>: >obviously positions from which no matter what combination of moves
>: >your opponent makes you can make a move to lead to a win and hence a
>: >table-like look up solution exists. However, the reverse must also be
>: >true for other positions. There are also a great many situations where
>: >you can force a draw. In general, however, all situations are open, ie.
>: >dependent.
>
>: This is *NOT* true. For all positions, including the starting one,
>: at least one player must be able to force a win or a draw.
>
>assertion would be much easier to disprove than solving from the starting
>position. One would only need to come up with one reachable board
>positioning where the statement is false and it disproves the assertion.
>Although finding that positioning is another problem unto itself.
Well, that would be the method of disproof, yes. But given that
the general solvability of perfect-information games is one of the
fundamental theorems of game theory, I offer the following analogy :
"For all pairs of odd numbers, the sum is even."
"One would only need to come up with one pair of odd numbers
where the statement is false and it disproves the assertion.
Although finding that pair is another problem unto itself."
I wish you luck.
-kitten
Patrick Juola
In article <3395DD...@msi.com> Guy Del Mistro <g...@msi.com> writes:
>Patrick Juola wrote:
>> >... There is
>> >also no a priori reason that chess can be solved at all! There are
>> >obviously positions from which no matter what combination of moves
>> >your opponent makes you can make a move to lead to a win and hence a
>> >table-like look up solution exists. However, the reverse must also be
>> >true for other positions. There are also a great many situations where
>> >you can force a draw. In general, however, all situations are open, ie.
>> >dependent.
>>
>> This is *NOT* true. For all positions, including the starting one,
>> at least one player must be able to force a win or a draw.
>
>loss and draw. Which one will actually be the outcome depends on what
>the other player does. What I said *IS* true. There IS NO GUARENTEE that
>that you can force the game into a winning state, or drawing state for
>that matter, from a random openning position.
Um, simple argument-by-pigeonhole. Take any position. Either black
can force a win, whatever white does, or he can't.
If he can force a win, then the position is a forced win for black.
If he can't force a win, then white has a forced draw (or win) from that
position.
Because chess is a perfect-information game, this is (in theory) known
to both players, and both players are capable of independently performing
the analysis. And therefore either black has a forced win -- and knows it,
and knows how to obtain it -- or else white has a forced draw (or win).
>For example, by following "the book" you might start an openning that
>has 99.999% chance of winning or drawing based on move-tree analysis,
>assuming that you always do the "best" move.
Nope. If you don't have 100% chance of forcing a win, then your opponent
has 100% chance of forcing a draw.
-kitten
Glen Barnett
In article <33912E...@bc.sympatico.ca>,
If we weren't good at it, we'd play something else, and the
argument would then be about whatever machine we'd just built
to play that. [The anthropomorphic argument rears its horrible head...]
So if we weren't good at the kind of reasoning required for chess,
we'd play jacks or something. Of course, one might argue that without
being able to use the kind of reasoning required for chess, we wouldn't
be able to build a machine to play jacks.
Glen
raven1
Could someone enlighten us non-scientists as to exactly what
this "NP" is that chess may or may not be in?
Henri H. Arsenault
In article <339B78...@planet.earthcom.net>, rav...@planet.earthcom.net
wrote:
> Could someone enlighten us non-scientists as to exactly what
> this "NP" is that chess may or may not be in?
I hope that a mathematicial will explain this better than me, but "NP" or
"NP-complete" refers to mathematical problems that are intractable.
Although I am not sure that this is really an NP problem, it can be proven
that there can be no mathematical (or computer) algorithm that can
determine whether or not any mathematical theorem is true or not. So IF the
solution of a game is "NP", then one could be assured that the game could
never be solved completely.
It is possible that without the 50-move rule in Chess, the game could not
be solved, but as was pointed out, becaue of that rule any Chess game will
terminate after some finite number of moves. So chess SEEMS solvable in
principle, assuming that a computer could calculate all the possible moves
in the longest possible game - which would require seeing at least a few
hundred moves ahead...I suppose that the game could be considered "solved"
in practice if a computer could see, say, 30 or 40 moves ahead - at least
in the sense that it could beat any human player.
Henri
This story has been attributed to both Capablanca and Reti: when asked how
many moves ahead that he could see, he replied "only one, but it is always
the best move!"
Apollo Hogan
In article <arseno-ya0234800...@132.203.250.22>,
Henri H. Arsenault <ars...@phy.ulaval.ca> wrote:
>In article <339B78...@planet.earthcom.net>, rav...@planet.earthcom.net
>wrote:
>
>> Could someone enlighten us non-scientists as to exactly what
>> this "NP" is that chess may or may not be in?
>
>I hope that a mathematicial will explain this better than me, but "NP" or
>"NP-complete" refers to mathematical problems that are intractable.
>Although I am not sure that this is really an NP problem, it can be proven
>that there can be no mathematical (or computer) algorithm that can
>determine whether or not any mathematical theorem is true or not. So IF the
>solution of a game is "NP", then one could be assured that the game could
>never be solved completely.
Ah, close but not quite. You're confusing undecidability with NP-ness.
Undecidability is a _much_ harder problem. An undecidable problem is one
that cannot be solved with any turing machine even if it's given unlimited
time and space to solve it. A problem in NP is just one that (probably)
requires exponential time to solve -- intractable, but in theory decidable.
(Generalized) chess is clearly decidable, but as it turns out, is
Exp-time complete. This means that it really would require exponential time
to solve the generalized case. This really doesn't say much about the
version of chess played on an 8x8 board, though. :-)
--Apollo Hogan
--
Professional Research Assistant
Dr. Elizabeth Bradley, Dept. of Computer Science
University of Colorado, Boulder
Guy Del Mistro
Patrick Juola wrote:
> Because chess is a perfect-information game, this is (in theory) known
> to both players, and both players are capable of independently performing
> the analysis. And therefore either black has a forced win -- and knows it,
> and knows how to obtain it -- or else white has a forced draw (or win).
>
> >For example, by following "the book" you might start an openning that
> >has 99.999% chance of winning or drawing based on move-tree analysis,
> >assuming that you always do the "best" move.
>
> Nope. If you don't have 100% chance of forcing a win, then your opponent
> has 100% chance of forcing a draw.
>
> -kitten
Ok Pat, all nice and neat. Now let's assume that chess is solvable just
because there are a finite number of positions.
First move: I play e2-e4. By your analysis I have already lost or won
the game (exclusively). Let's suppose I win.
First move: You play e2-e4. You win.
Ok. Before the first move the position is fixed. Therefore I choose to
be white: I win!
This is obviously unfair so we toss a coin for who goes first!
This seems unreasonable but is all perfectly true so long as a `book' of
solutions exists which both you and I are following to the letter.
However, I think your argument is only reasonable if you take "winning"
to mean not-losing. It is my belief that you can only force a true win
from a lack of forsight on the other player's behalf, ie. that if both
player's make the `best' move each time (from the `book') then every
resonable openning chess move utimately leads to a draw. This is why in
my earlier posting I used percentage win analysis as nobody would want
to buy a book called "how to force a draw in chess".
NP completeness is one thing but this does not tell if chess is solvable
in the sense that there is at least one move-tree branch that a player
(probably white) can take to always force a win.
Guy.
mykey
Guy Del Mistro wrote:
[snip]
> It is my belief that you can only force a true win from a lack of
> forsight on the other player's behalf, ie. that if both player's make
> the `best' move each time (from the `book') then every resonable
> openning chess move utimately leads to a draw.
> Guy.
This is the very question that "solving" chess seeks to answer.
For either side, does it require the opponent to make a mistake to win.
At this time I think there are just a large amount of positions
that the "best" players agree are leading to a draw.
Does this mean neither side has an advantage from the start.
No.
Even the "best" don't know EVERYTHING about chess.
Didn't the "scholars" once thing the earth was flat?
mykey
Tyson Richard DOWD
ars...@phy.ulaval.ca (Henri H. Arsenault) writes:
>In article <339B78...@planet.earthcom.net>, rav...@planet.earthcom.net
>wrote:
>> Could someone enlighten us non-scientists as to exactly what
>> this "NP" is that chess may or may not be in?
>I hope that a mathematicial will explain this better than me, but "NP" or
>"NP-complete" refers to mathematical problems that are intractable.
>Although I am not sure that this is really an NP problem, it can be proven
>that there can be no mathematical (or computer) algorithm that can
>determine whether or not any mathematical theorem is true or not. So IF the
>solution of a game is "NP", then one could be assured that the game could
>never be solved completely.
No. You are probably thinking of non-computable.
For NP the standard example is to find that there is an assignment of
truth values to statements such that a sentence in logic is true, eg
true/false values for a,b,c,d etc .... so that (a & b & not(c)) || (b &
d) is true. This is called the satisfiablility problem, or SAT. (I've
left some details out). It turns out that just this problem takes an
exponential amount of time in the number of variables, since you have to
check about 2^n values (true/false for every variable). Add one more
variable, and you'll check about 2^(n+1).
But if you had a nondeterministic machine - that alway checked the
"right-way", always picked the value true/false that would lead to
the answer (if there is one), it would only take a polynomial amount of
time to check. This is like getting a "lucky-hit" on the first truth
assignment you check. This is NP - if the problem is "polynomial with a
nondeterministic machine" it is NP. , NP problems seem to be
exponential, however, with a normal deterministic machine.
"NP-complete" is a different term, and refers to a problem that is both
NP (as above), and NP-hard.
A problem is NP-hard if every NP problem can be transformed into it in
polynomial time.
How on earth do you show that _every_ NP problem can be transformed into
it? NP is infinite, and there are enormous differences in the problems
in it. *Tricky step* - you show that a nondeterministic machine
(Actually, a Turing Machine - to be precise), can be simulated in terms
of your problem, with the conversion happening in polynomial timne.
Fortunately, someone already did this for SAT, so now people just show
that SAT can be transformed into your problem, so therefore all of NP
can be transformed into your problem, since it can be transformed into
SAT. This is a lot easier.
For more information on this, try "Languages and Machines", Thomas A.
Sudkamp.
>It is possible that without the 50-move rule in Chess, the game could not
>be solved, but as was pointed out, becaue of that rule any Chess game will
>terminate after some finite number of moves. So chess SEEMS solvable in
>principle, assuming that a computer could calculate all the possible moves
>in the longest possible game - which would require seeing at least a few
>hundred moves ahead...I suppose that the game could be considered "solved"
>in practice if a computer could see, say, 30 or 40 moves ahead - at least
>in the sense that it could beat any human player.
If someone would define what "chess" means in terms of a problem,
perhaps this would help talk about it. "chess" is a game, not a problem.
Henri H. Arsenault
In article <5nisb5$d...@mulga.cs.mu.OZ.AU>, t...@murlibobo.cs.mu.OZ.AU (Tyson
Richard DOWD) wrote:
> If someone would define what "chess" means in terms of a problem,
> perhaps this would help talk about it. "chess" is a game, not a problem.
The problem is programming a computer to ensure a win from any winning
position (or a draw, if the opponent doesn't let the computer reach a
winning position).This means evaluation all the possible positions that can
be reached from a starting position. Why do you think that this is not a
"problem"?
By the way, chess is not a "game" either in the sense of Von Neumann's
theory of games.So maybe chess is neither a game nor a problem?... Then
what is it?
Henri
Henri H. Arsenault
> For either side, does it require the opponent to make a mistake to win.
>
> At this time I think there are just a large amount of positions
> that the "best" players agree are leading to a draw.
>
It is generally believed that at least two "grandmaster" mistakes are
required before a win can be forced. So World Champion Lasker used to make
one "grandmaster" mistake on purpose to lead his opponent to think that he
had a won game and to overextend himself. This led to the belief that
Lasker had sold his soul to the devil to help extricate him from lost
games...
Henri
Patrick Juola
In article <arseno-ya0234800...@132.203.250.22> ars...@phy.ulaval.ca (Henri H. Arsenault) writes:
>In article <339B78...@planet.earthcom.net>, rav...@planet.earthcom.net
>wrote:
>
>> Could someone enlighten us non-scientists as to exactly what
>> this "NP" is that chess may or may not be in?
>
>I hope that a mathematicial will explain this better than me, but "NP" or
>"NP-complete" refers to mathematical problems that are intractable.
>Although I am not sure that this is really an NP problem, it can be proven
>that there can be no mathematical (or computer) algorithm that can
>determine whether or not any mathematical theorem is true or not. So IF the
>solution of a game is "NP", then one could be assured that the game could
>never be solved completely.
Um, no.
First, NP and NP-complete are two distinct concepts.
Second, NP-complete problems can be solved completely. They just
take a while (like, until the planets detach from their orbits "a while"
for large problems).
But TRAVELLING SALESMAN is an NP-complete problem, and we know at least
one "solution" to that....
-kitten
edwa...@cc5.crl.aecl.ca
In a previous article, raven1 <rav...@planet.earthcom.net> wrote:
->Could someone enlighten us non-scientists as to exactly what
->this "NP" is that chess may or may not be in?
NP stands for Non-Polynomial. Problems can be divided into two types.
In Polynomial problems, the amount of time to solve the problem goes up
as some power of the size of the problem. For example, solving a jigsaw
puzzle by trial and error. If there were N pieces you could pick one
piece, try N-1 pieces against it. When you found the fit, try the
remaining N-2 pieces against the combination etc. The largest number
of time to solve the puzzle is [(N-1)+(N-2)+(N-3)+ ... +2+1]*T = T*(N^2-N)/2.
The largest exponent in the polynomial, in this case, 2, dominates the
solution time for large N. P type problems are considered 'easy', because
if you can solve a reasonably simple problem then you can probably solve
any interesting problem by brute force, simply by building a faster
computer.
NP problems are problems for which the time to find a solution grows
exponentially with the size of the problem. A famous NP problem is the
Travelling Salesman problem. A salesman has N cities to visit and wants
to take the route which minimizes travel time. No known method can
solve this problem except to try all possible routes and compare the
travel times for each. Since there are N-1 second cities (the starting
city doesn't matter since he goes in a loop), N-2 third cities etc, the
number of possible routes is (N-1)*(N-2)*(N-3)...*2 = (N-1)! For large
numbers, factorials grow exponentially, so this problem is 'hard'. See
the difference between this problem and the jigsaw problem. If you
could do a hundred piece jigsaw in 10 minutes, then you could do a 101
piece in 101^2/100^2 *10 minutes = 10 minutes and 12 seconds. However,
if you could do the 100 city travelling salesman problem in 10 minutes,
it would take you 100 * 10 minutes = 16 hours 40 minutes to solve the
101 city problem.
Geoff
Ilias Kastanas
In article <5nlhek$r...@mulga.cs.mu.OZ.AU>,
Tyson Richard DOWD <t...@mundook.cs.mu.OZ.AU> wrote:
>ars...@phy.ulaval.ca (Henri H. Arsenault) writes:
>
>>Richard DOWD) wrote:
>
>
>>> If someone would define what "chess" means in terms of a problem,
>>> perhaps this would help talk about it. "chess" is a game, not a problem.
>
>>The problem is programming a computer to ensure a win from any winning
>>position (or a draw, if the opponent doesn't let the computer reach a
>>winning position).This means evaluation all the possible positions that can
>>be reached from a starting position. Why do you think that this is not a
>>"problem"?
>
>down and play. There isn't a computer involved at all. It's not like
>finding the shortest path between 10 cities, or a well defined problem
>like that.
>
>Problems in computer science are usually stated as "yes/no" questions,
>so that you can conceptually program a Turing machine that will stop and
>say "yes" if the answer is yes, and stop and say "no", or simply not
>stop at all if the answer is no.
>
>Probably the best way to state the chess problem you've state above is
>"can I force a win from this position", or "can I force a win or draw
>from this position". This seems to be an NP problem - if we had a
>nondeterministic machine that tried all possible moves at once (or,
>alternately viewed, always picked the correct move), it would take a
>polynomial amount of time (polynomial in the number of pieces, or the
>"size of the position/board" or something) to answer the question.
>It's still a little vaguely defined, however.
>I'm not even going to attempt to find whether it is NP-complete.
NP has nothing whatsoever to do with chess.
NP, and other computational complexity notions, apply to problems
with an _infinite_ number of possible instances. Boolean formulas to be
checked... graphs to be colored or traversed... If there are only finitely
many instances, the problem is computationally trivial; there is an immedi-
ate solution by table lookup.
A Turing Machine's finite control may be of any size. Any pre-chosen
amount of information may be embedded in it. There is a TM with a table of
all possible chess positions and appropriate information for each, best move,
outcome, or whatever. It responds as soon as it reads its input.
Unrealistic? Of course. But that is the way the theory goes. Its
practical significance etc. is a separate issue. Here, the theory would
only apply to N x N "chess" (go, checkers...) with no bound on N. Which
is not what we are concerned with!
Ilias
Dr A. N. Walker
Tyson Richard DOWD wrote:
> Problems in computer science are usually stated as "yes/no" questions,
Erm, well, *decision* problems are, but they are "yes"/"no"
by definition; other problems are usually stated in, well, other ways.
The main advantage of decision problems in this sort of context is that
you don't have to worry about how much output is being generated, so
the complexity of the problem is a function purely of the instance
under consideration.
> Probably the best way to state the chess problem you've state above is
> "can I force a win from this position", or "can I force a win or draw
> from this position". This seems to be an NP problem - if we had a
> nondeterministic machine that tried all possible moves at once (or,
> alternately viewed, always picked the correct move), it would take a
> polynomial amount of time (polynomial in the number of pieces, or the
> "size of the position/board" or something) to answer the question.
No, because a "lucky" guess would merely tell us "if I go here
and you go there and I then go here and ... then I win", and we can't
deduce much from that. We need to know "if I go here, then whatever
you do I can find a move such that whatever you do ... and I win",
which is a much harder problem.
> I'm not even going to attempt to find whether it is NP-complete.
Already done. Generalised chess [ie, on an arbitrarily large
board with many pieces] is PSPACE/EXPTIME-complete according as the
generalised "50-move rule" is extended [sensibly] or removed. If
you can sort out the relationships between P, NP, PSPACE and EXPTIME,
you will become very famous, but that has little to do with chess.
Dr A. N. Walker
Henri H. Arsenault wrote:
> In article <339B78...@planet.earthcom.net>, rav...@planet.earthcom.net
> wrote:
Probably not; I don't think it can be explained without some
use of reasonably advanced mathematical language. However, you will
find an attempt at an explanation at
http://www.maths.nott.ac.uk/personal/anw/G12FCO/lect10.html
[part of my lecture notes on our second-year "formal computation"
module]; surrounding pages [accessible from links or by obvious mods
to the above URL] give more context and developments. [Feedback, and
of course notification of any mistakes, welcome.]
> I hope that a mathematicial will explain this better than me, but "NP" or
> "NP-complete" refers to mathematical problems that are intractable.
Not really. More to problems that may seem intractable but
turn out to be easy *if* you are lucky. Problems that are intractable
even if you are lucky are not in NP ["Non-deterministic Polynomial",
which is math-speak for "if lucky, easy"].
> Although I am not sure that this is really an NP problem, it can be proven
> that there can be no mathematical (or computer) algorithm that can
> determine whether or not any mathematical theorem is true or not.
This is something quite different! This is [roughly] Godel's
theorem [maths] or "the unsolvability of the Halting Problem" [comp],
and "unsolvable" is different from "intractable" [ie, "unsolvable in
a reasonable time"]. The HP is unsolvable even in an *unreasonable*
time, and "[un]reasonable" here is a mathematical [un]reasonable, by
which a few thousand million years of computing by every single human
having access to a million computers each a million times faster than
Deepest-Imaginable Blue is perfectly reasonable.
> It is possible that without the 50-move rule in Chess, the game could not
> be solved, but as was pointed out, becaue of that rule any Chess game will
> terminate after some finite number of moves.
Actually, the 50-move rule is irrelevant to this precise
question, as the [brute force] analysis of the less than 10^70-odd
different legal positions is certainly much easier than of the
10^22000 or so legal games within the 50-move rule. 10^70 is already
totally unreasonable by "millions of Deepest Blue" standards, however
simple it looks just as a rather large number by arithmetic stanards.
> So chess SEEMS solvable in
> principle,
There is no [serious] question about this; it's *practice*
that makes it unsolvable by any known present-day technique [*unless*
quantum computation turns out surprisingly well -- after all, the
entire universe manages to compute its own future *in real time*!].
Guy Del Mistro
Henri H. Arsenault wrote:
> By the way, chess is not a "game" either in the sense of Von Neumann's
> theory of games.So maybe chess is neither a game nor a problem?...
If this is true then Von Neumann didn't choose a very good definition
of what a game is!
Guy
Tyson Richard DOWD
ika...@alumnae.caltech.edu (Ilias Kastanas) writes:
>In article <5nlhek$r...@mulga.cs.mu.OZ.AU>,
>Tyson Richard DOWD <t...@mundook.cs.mu.OZ.AU> wrote:
> NP has nothing whatsoever to do with chess.
> NP, and other computational complexity notions, apply to problems
>with an _infinite_ number of possible instances. Boolean formulas to be
>checked... graphs to be colored or traversed... If there are only finitely
>many instances, the problem is computationally trivial; there is an immedi-
>ate solution by table lookup.
Generating the table, however, is an NP problem in the size of the
instance. Once you have generated it, using it is trivial, of course.
I realize I wasn't being completely accurate, but does it really achieve
anything to introduce so much formalism in this newsgroup?
> A Turing Machine's finite control may be of any size. Any pre-chosen
>amount of information may be embedded in it. There is a TM with a table of
>all possible chess positions and appropriate information for each, best move,
>outcome, or whatever. It responds as soon as it reads its input.
> Unrealistic? Of course. But that is the way the theory goes. Its
>practical significance etc. is a separate issue. Here, the theory would
>only apply to N x N "chess" (go, checkers...) with no bound on N. Which
>is not what we are concerned with!
So what _are_ you concerned with? We all know the original question
wasn't "if you have a massive lookup table for 8x8 chess, is it NP?".
That's a pointless question. People wanted to know what realm of
difficulty chess was in, and what NP meant.
It seems you've defined the problem away, we just have to look up this
table and we can do it in constant time (maybe polynomial at worst).
But we don't generally have that table, and we've decided (from people's
previous discussions) that it is not practical to store it the way you
propose.
So really, we should state the problem a little differently - really, it
is "what is the complexity of chess if the size of the board is part of
the input?". Now it so happens we are particularly interested in 8x8,
but we don't want to restrict ourselves, because then the unrealistic
theories start to kick in ;-)
Ilias Kastanas
In article <5nnrel$k...@mulga.cs.mu.OZ.AU>,
Tyson Richard DOWD <t...@mundook.cs.mu.OZ.AU> wrote:
>ika...@alumnae.caltech.edu (Ilias Kastanas) writes:
>
>>In article <5nlhek$r...@mulga.cs.mu.OZ.AU>,
>>Tyson Richard DOWD <t...@mundook.cs.mu.OZ.AU> wrote:
>
>> NP has nothing whatsoever to do with chess.
>
>> NP, and other computational complexity notions, apply to problems
>>with an _infinite_ number of possible instances. Boolean formulas to be
>>checked... graphs to be colored or traversed... If there are only finitely
>>many instances, the problem is computationally trivial; there is an immedi-
>>ate solution by table lookup.
>Generating the table, however, is an NP problem in the size of the
>instance. Once you have generated it, using it is trivial, of course.
If you have one instance, if you have a million... no.
Suppose instance size is 4000, and it took 9700222 steps. What
is the complexity? Linear? Polynomial? Exponential?... It just doesn't
make sense.
If you meant arbitrary, size n instance... good; but then, no table
generation -- you cannot store them, they are infinitely many. Instead, it
is the actual problem -- and it might be in NP or PSPACE or whatever.
Generate a finite table anyway? No reason. Being fast finitely
often is negligible -- and doesn't alter one's being in P or NP or...
Fine for theory. As for Chess, there is no arbitrary size; just
finitely many inputs. No NP.
>I realize I wasn't being completely accurate, but does it really achieve
>anything to introduce so much formalism in this newsgroup?
On the contrary -- I'm trying to _remove_ formalism that is unhelp-
ful for the issue, irrelevant and possibly confusing.
>> A Turing Machine's finite control may be of any size. Any pre-chosen
>>amount of information may be embedded in it. There is a TM with a table of
>>all possible chess positions and appropriate information for each, best move,
>>outcome, or whatever. It responds as soon as it reads its input.
>
>> Unrealistic? Of course. But that is the way the theory goes. Its
>>practical significance etc. is a separate issue. Here, the theory would
>>only apply to N x N "chess" (go, checkers...) with no bound on N. Which
>>is not what we are concerned with!
>So what _are_ you concerned with? We all know the original question
>wasn't "if you have a massive lookup table for 8x8 chess, is it NP?".
>That's a pointless question. People wanted to know what realm of
>difficulty chess was in, and what NP meant.
And I'm trying to explain NP has no bearing here; chess difficulty
can be described, but let us use applicable terms.
>It seems you've defined the problem away, we just have to look up this
>table and we can do it in constant time (maybe polynomial at worst).
>But we don't generally have that table, and we've decided (from people's
>previous discussions) that it is not practical to store it the way you
>propose.
I'm not proposing it; I'm saying _NP_ works that way, defines the
problem away etc ... so let us leave it alone.
>So really, we should state the problem a little differently - really, it
>is "what is the complexity of chess if the size of the board is part of
>the input?". Now it so happens we are particularly interested in 8x8,
>but we don't want to restrict ourselves, because then the unrealistic
>theories start to kick in ;-)
Eh, since we are _not_ interested in NxN chess why the contortions
to fit unrealistic theories?! Let's talk about 8x8.
Ilias
Apollo Hogan
In article <10JUN97....@cc5.crl.aecl.ca>,
<edwa...@cc5.crl.aecl.ca> wrote:
>In a previous article, raven1 <rav...@planet.earthcom.net> wrote:
>->Could someone enlighten us non-scientists as to exactly what
>->this "NP" is that chess may or may not be in?
>
>NP stands for Non-Polynomial. Problems can be divided into two types.
>In Polynomial problems, the amount of time to solve the problem goes up
>
>NP problems are problems for which the time to find a solution grows
>exponentially with the size of the problem. A famous NP problem is the
Actually, NP stands for Non-deterministic Polynomial. NP problems _can_ be
solved in exponential time but it hasn't been proved that they _require_
exponential time. There are problems (Exp-time) problems that provably
require exponential time to solve. (You can also have NExp-Time for
non-deterministic exponential time problems, which would be even slower on
a deterministic machine... I think that Presburger arithmetic is in this
class.) The hierarchy of time complexity has many higher levels, though
even "merely" NP-hard problems are difficult enough to solve in any practical
sense.
A useful (and very readable IMHO) introduction is
_Computers_and_Intractibility:_A_guide_to_the_theory_of_NP-completeness_
Garey, M.R. & Johnson, D.S.
Tyson Richard DOWD
ika...@alumnae.caltech.edu (Ilias Kastanas) writes:
>In article <5nnrel$k...@mulga.cs.mu.OZ.AU>,
>Tyson Richard DOWD <t...@mundook.cs.mu.OZ.AU> wrote:
>>ika...@alumnae.caltech.edu (Ilias Kastanas) writes:
>>
>>> NP, and other computational complexity notions, apply to problems
>>>with an _infinite_ number of possible instances. Boolean formulas to be
>>>checked... graphs to be colored or traversed... If there are only finitely
>>>many instances, the problem is computationally trivial; there is an immedi-
>>>ate solution by table lookup.
>>Generating the table, however, is an NP problem in the size of the
>>instance. Once you have generated it, using it is trivial, of course.
> If you have one instance, if you have a million... no.
> Suppose instance size is 4000, and it took 9700222 steps. What
>is the complexity? Linear? Polynomial? Exponential?... It just doesn't
>make sense.
Did I *say* it was an NP problem if the instance size is 4000 or did I
say it was NP in the size of the instance? Do I have a big sticker on my
forehead that says "Please Patronize Me"?
> If you meant arbitrary, size n instance... good; but then, no table
Of course I did! That sticker on my forehead must have neon lights!
>generation -- you cannot store them, they are infinitely many. Instead, it
No, the problem is to generate one, but you don't know which one. It's
part of the input to the problem. Of course for any particular instance
it is finite - all NP problems share this property.
You can store one. Any particular one is finite. We just don't say which
one we want.
>is the actual problem -- and it might be in NP or PSPACE or whatever.
> Generate a finite table anyway? No reason. Being fast finitely
>often is negligible -- and doesn't alter one's being in P or NP or...
> Fine for theory. As for Chess, there is no arbitrary size; just
>finitely many inputs. No NP.
No, but I have a machine that solves arbitrary chess, the size of the
board, number of pieces, etc, are all input. I'd like to talk about the
complexity of it. The particular instances I give to it are nobody's
business but my own - I'm sorry I even mentioned I was going to try 8x8
chess (50 move limit, standard pieces) first.
>>I realize I wasn't being completely accurate, but does it really achieve
>>anything to introduce so much formalism in this newsgroup?
> On the contrary -- I'm trying to _remove_ formalism that is unhelp-
>ful for the issue, irrelevant and possibly confusing.
But you are wrong. "NP has nothing whatsoever to do with chess." you
said.
This is not correct. Chess (8x8 variety) is a specific instance of an NP
problem. Simple as that.
[deleted stuff]
> And I'm trying to explain NP has no bearing here; chess difficulty
>can be described, but let us use applicable terms.
But you're using a lookup table! So there's nothing practical to discuss
about it. Look up your position in the table. It's all encoded ahead of
time. The encoding can be done in constant time because its 8x8.
>>So really, we should state the problem a little differently - really, it
>>is "what is the complexity of chess if the size of the board is part of
>>the input?". Now it so happens we are particularly interested in 8x8,
>>but we don't want to restrict ourselves, because then the unrealistic
>>theories start to kick in ;-)
> Eh, since we are _not_ interested in NxN chess why the contortions
>to fit unrealistic theories?! Let's talk about 8x8.
Why the contortions?
Why talk about NxN chess?
Well we might want to avoid the consequences of chess being a finite
game so that we can talk about a practical problem in a practical way,
and see where a finite instance of a problem fits into formal schemes.
We might want to answer the original posters question.
We might want to discuss the general case of chess, and then look at the
practical difficulties of a specific instance as a consequence of the
theoretical difficulties of the general case. I don't think it's just
coincidence that NxN chess is NP, and 8x8 chess is hard to compute.
But as you keep carefully pointing out, chess it's finite. And no matter
how I try to generalize the problem, you keep coming back to this, and
claiming things like "NP has nothing whatsoever to do with chess" so
I think your suggestion that we drop this has merit.
Ilias Kastanas
In article <5nqnpt$n...@mulga.cs.mu.OZ.AU>,
If there is an upper bound, like 8x8, if only finitely many instances
are possible, then "part of the input" or "don't say which one" do not matter;
for complexity theory the problem is trivial.
If you do mean "arbitrary size n", then there is no kxk bound, for
any fixed k.
>>is the actual problem -- and it might be in NP or PSPACE or whatever.
>> Generate a finite table anyway? No reason. Being fast finitely
>>often is negligible -- and doesn't alter one's being in P or NP or...
>
>> Fine for theory. As for Chess, there is no arbitrary size; just
>>finitely many inputs. No NP.
>
>No, but I have a machine that solves arbitrary chess, the size of the
>board, number of pieces, etc, are all input. I'd like to talk about the
>complexity of it. The particular instances I give to it are nobody's
>business but my own - I'm sorry I even mentioned I was going to try 8x8
>chess (50 move limit, standard pieces) first.
Fine. But do you expect to draw any conclusions from what your
machine does in the 8x8 case? It might be handling it via a very wasteful
algorithm. Then again, you might look closely and notice your machine has
a lookup table for 8x8. Or any one of a number of things, _not_ affecting
the machine's complexity classification as "solver of NxN chess for arbi-
trary N".
>>>I realize I wasn't being completely accurate, but does it really achieve
>>>anything to introduce so much formalism in this newsgroup?
>
>> On the contrary -- I'm trying to _remove_ formalism that is unhelp-
>>ful for the issue, irrelevant and possibly confusing.
>
>But you are wrong. "NP has nothing whatsoever to do with chess." you
>said.
>
>This is not correct. Chess (8x8 variety) is a specific instance of an NP
>problem. Simple as that.
So? There are Turing Machines that solve 8x8 in 10^10^10^10^10
steps. There are others that solve 8x8 in 1 step. They don't even have to
be non-deterministic; they operate in P.
Chess (8x8) is a specific instance of infinitely many NP problems...
as well as of infinitely many P problems... or linear-time problems... etc.
Complexity theory is about "large n"; it abstracts away from an
individual specific instance, like 8x8 chess. P, NP and the like have
nothing whatsoever to do with it.
>[deleted stuff]
>
>> And I'm trying to explain NP has no bearing here; chess difficulty
>>can be described, but let us use applicable terms.
>
>But you're using a lookup table! So there's nothing practical to discuss
>about it. Look up your position in the table. It's all encoded ahead of
>time. The encoding can be done in constant time because its 8x8.
Not me; complexity theory.
>>>So really, we should state the problem a little differently - really, it
>>>is "what is the complexity of chess if the size of the board is part of
>>>the input?". Now it so happens we are particularly interested in 8x8,
>>>but we don't want to restrict ourselves, because then the unrealistic
>>>theories start to kick in ;-)
>
>> Eh, since we are _not_ interested in NxN chess why the contortions
>>to fit unrealistic theories?! Let's talk about 8x8.
>
>Why the contortions?
>Why talk about NxN chess?
>
>Well we might want to avoid the consequences of chess being a finite
>game so that we can talk about a practical problem in a practical way,
>and see where a finite instance of a problem fits into formal schemes.
>
>We might want to answer the original posters question.
>
>We might want to discuss the general case of chess, and then look at the
>practical difficulties of a specific instance as a consequence of the
>theoretical difficulties of the general case. I don't think it's just
>coincidence that NxN chess is NP, and 8x8 chess is hard to compute.
I'm afraid there is no implication like that, as per above.
And 4x4, or 3x3, are not exactly "hard to compute"!
>But as you keep carefully pointing out, chess it's finite. And no matter
>how I try to generalize the problem, you keep coming back to this, and
>claiming things like "NP has nothing whatsoever to do with chess" so
>I think your suggestion that we drop this has merit.
Okay; it's just that, as far as I can see, attempts to use NP
and the like in this matter are a waste of time.
Ilias
Antonio Leitao
>>>>> "edwardsg" =3D=3D edwardsg <edwa...@cc5.crl.aecl.ca> writes:
edwardsg> In a previous article, raven1 <rav...@planet.earthcom.net> wrote=
:
-> Could someone enlighten us non-scientists as to exactly what
-> this "NP" is that chess may or may not be in?
edwardsg> NP stands for Non-Polynomial.
I'm not an expert, but I think NP do *not* stands for
Non-Polynomial. It's quite the opposite. NP stands for
Non-deterministically polynomial.
The non-determinism comes from the fact that, whenever the machine has
to make a choice, it non-deterministically always choose the correct
one. In other terms, the machine never backtracks.
[...]
edwardsg> NP problems are problems for which the time to find a
edwardsg> solution grows exponentially with the size of the problem.
The previous sentence is not proved (yet). What is proved is that a
deterministic machine (like current computers) can solve NP problems
in exponential time, but no one knows if they can solve them
faster. In other terms, no one knows whether P=3DNP (although there is
strong evidence that P is really different than NP). Besides, a
non-deterministic machine can (by definition) solve any NP problem in
polynomial time.
IMHO, NP problems are problems which can be solved in polynomial time
in a non-deterministic machine.
Whether they can be solved in polynomial time in a deterministic
machine is still an open question.
[...]
Ant=F3nio Leit=E3o.
edwa...@cc5.crl.aecl.ca
In a previous article, Antonio Leitao <a...@gia.ist.utl.pt> wrote:
->>>>>> "edwardsg" =3D=3D edwardsg <edwa...@cc5.crl.aecl.ca> writes:
->
-> edwardsg> In a previous article, raven1 <rav...@planet.earthcom.net> wrote=
->:
-> -> Could someone enlighten us non-scientists as to exactly what
-> -> this "NP" is that chess may or may not be in?
->
-> edwardsg> NP stands for Non-Polynomial.
->
->I'm not an expert, but I think NP do *not* stands for
->Non-Polynomial. It's quite the opposite. NP stands for
->Non-deterministically polynomial.
->
->The non-determinism comes from the fact that, whenever the machine has
->to make a choice, it non-deterministically always choose the correct
->one. In other terms, the machine never backtracks.
->
->[...]
->
-> edwardsg> NP problems are problems for which the time to find a
-> edwardsg> solution grows exponentially with the size of the problem.
->
->The previous sentence is not proved (yet). What is proved is that a
->deterministic machine (like current computers) can solve NP problems
->in exponential time, but no one knows if they can solve them
->faster. In other terms, no one knows whether P=3DNP (although there is
->strong evidence that P is really different than NP). Besides, a
->non-deterministic machine can (by definition) solve any NP problem in
->polynomial time.
->
->IMHO, NP problems are problems which can be solved in polynomial time
->in a non-deterministic machine.
->
->Whether they can be solved in polynomial time in a deterministic
->machine is still an open question.
->
->[...]
->
->Ant=F3nio Leit=E3o.
Oh, I agree. NP stands for 'solvable in Polynomial time on a
Nondeterministic Turing machine'. The connection from that statement to
'solvable only in in exponential time on a deterministic Turing machine'
is still a matter of conjecture. However, this point really doesn't
advance the discussion very much unless you are teaching a theoretical
computation class, which we are not.
GeoffE