33 views

Skip to first unread message

May 26, 1997, 3:00:00 AM5/26/97

to

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

May 27, 1997, 3:00:00 AM5/27/97

to

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/

May 27, 1997, 3:00:00 AM5/27/97

to

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

May 27, 1997, 3:00:00 AM5/27/97

to

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

May 27, 1997, 3:00:00 AM5/27/97

to

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.

May 27, 1997, 3:00:00 AM5/27/97

to

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

May 27, 1997, 3:00:00 AM5/27/97

to

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.

May 27, 1997, 3:00:00 AM5/27/97

to

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

May 27, 1997, 3:00:00 AM5/27/97

to

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

May 27, 1997, 3:00:00 AM5/27/97

to

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.

May 27, 1997, 3:00:00 AM5/27/97

to

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.

May 27, 1997, 3:00:00 AM5/27/97

to

> 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.

> 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.

May 28, 1997, 3:00:00 AM5/28/97

to

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.

May 28, 1997, 3:00:00 AM5/28/97

to

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:

>>[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.

>

>

>

>>

>>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

> 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.

May 29, 1997, 3:00:00 AM5/29/97

to

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.

>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.

>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

May 29, 1997, 3:00:00 AM5/29/97

to

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:

>> 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.

>

>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**.

>> 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.

May 29, 1997, 3:00:00 AM5/29/97

to

>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 =========================

May 29, 1997, 3:00:00 AM5/29/97

to

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

May 30, 1997, 3:00:00 AM5/30/97

to

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.

May 30, 1997, 3:00:00 AM5/30/97

to

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

Jun 1, 1997, 3:00:00 AM6/1/97

to

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

Jun 1, 1997, 3:00:00 AM6/1/97

to

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

Jun 2, 1997, 3:00:00 AM6/2/97

to

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

>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.

>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

Jun 3, 1997, 3:00:00 AM6/3/97

to

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

Jun 4, 1997, 3:00:00 AM6/4/97

to

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!

Jun 5, 1997, 3:00:00 AM6/5/97

to

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.

>

> 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.

>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

Jun 5, 1997, 3:00:00 AM6/5/97

to

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.

>

>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.

>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

Jun 5, 1997, 3:00:00 AM6/5/97

to

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

Jun 8, 1997, 3:00:00 AM6/8/97

to

Could someone enlighten us non-scientists as to exactly what

this "NP" is that chess may or may not be in?

Jun 9, 1997, 3:00:00 AM6/9/97

to

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!"

Jun 9, 1997, 3:00:00 AM6/9/97

to

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

Jun 9, 1997, 3:00:00 AM6/9/97

to

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.

Jun 9, 1997, 3:00:00 AM6/9/97

to

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

Jun 10, 1997, 3:00:00 AM6/10/97

to

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.

Jun 10, 1997, 3:00:00 AM6/10/97

to

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

Jun 10, 1997, 3:00:00 AM6/10/97

to

> 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

Jun 10, 1997, 3:00:00 AM6/10/97

to

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

Jun 10, 1997, 3:00:00 AM6/10/97

to

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

Jun 11, 1997, 3:00:00 AM6/11/97

to

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:

>

>>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"?

>

>Stated like this, it is a problem. "Chess" is something two people sit>>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

Jun 11, 1997, 3:00:00 AM6/11/97

to

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.

Jun 11, 1997, 3:00:00 AM6/11/97

to

Henri H. Arsenault 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?

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*!].

Jun 12, 1997, 3:00:00 AM6/12/97

to

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

Jun 12, 1997, 3:00:00 AM6/12/97

to

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 ;-)

Jun 12, 1997, 3:00:00 AM6/12/97

to

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

Jun 12, 1997, 3:00:00 AM6/12/97

to

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.

Jun 13, 1997, 3:00:00 AM6/13/97

to

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.

Jun 15, 1997, 3:00:00 AM6/15/97

to

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

Jun 18, 1997, 3:00:00 AM6/18/97

to

>>>>> "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.

Jun 20, 1997, 3:00:00 AM6/20/97

to

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

Reply all

Reply to author

Forward

0 new messages