110 views

Skip to first unread message

Mar 15, 2001, 11:52:49 AM3/15/01

to

Apparently no theorems are known about the computational complexity of

retrograde analysis in chess (or other well-known abstract games. I have

raised this question before but have a couple of new thoughts that maybe

someone can build on.

retrograde analysis in chess (or other well-known abstract games. I have

raised this question before but have a couple of new thoughts that maybe

someone can build on.

There are many ways to formalize the problem of retrograde analysis. I am

taking the following as a working definition.

INSTANCE: Two generalized chess positions, a "start position" and an "end

position."

QUESTION: Does there exist a legal sequence of moves taking us from the

start position to the end position?

As a variation, we could also specify a bound on the number of moves.

It is not even immediately clear that this problem is in NP, because the

obvious "certificate" (i.e., the list of moves) could be exponential in

length.

Leaving that aside, can we show that the problem is NP-hard? The thought

I have is to reduce 3-SAT to retrograde chess, along the following lines.

Given an instance of 3-SAT with n variables and m clauses, we design a

generalized chess position in which White has n "Capturers" (pieces or

pawns that will function as capturers of Black pieces) and Black has m

"Sacrificers" (pieces or pawns that will sacrifice themselves to the

White Capturers). In the start position, all the Capturers and Sacrificers

will be present, and in the end position, the Capturers will still be there

but the Sacrificers will be gone. The positions should be designed so that:

1. Each Capturer has two ways of getting from their start positions to

their end positions, and it is not immediately clear which path they

took. Label the two paths "0" and "1." Let's also require that the

paths be disjoint.

2. For each Sacrificer, there are just three places where it could have

been captured (call these places "altars"). Specifically, if the ith

clause in the 3-SAT instance is (for example) x_r V ~x_s V x_t, then

the three altars of the ith Sacrificer must appear on the "1" path of

the rth Capturer, the "0" path of the sth Capturer, and the "1" path

of the tth Capturer respectively.

However, I haven't been able to convert this rough outline into a specific

construction. Can anyone else do so?

--

Tim Chow tchow-at-alum-dot-mit-dot-edu

The range of our projectiles---even ... the artillery---however great, will

never exceed four of those miles of which as many thousand separate us from

the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences

Mar 15, 2001, 12:32:46 PM3/15/01

to

I also have made up a favorite chess-related complexity problem.

n-queen completion: given an n by n chessboard on which some set of queens has

already been placed, can you add queens to get a set of n queens none of which

are attacking each other?

Is this polynomial or NP-complete?

You might submit your retrograde problem to Hedetniemi; he keeps a file of

chessboard related problems.

Jerry Spinrad

Mar 16, 2001, 9:46:34 AM3/16/01

to

In <98qs11$5...@severi.mit.edu> tc...@lsa.umich.edu writes:

>Apparently no theorems are known about the computational complexity of

>retrograde analysis in chess (or other well-known abstract games. I have

>raised this question before but have a couple of new thoughts that maybe

>someone can build on.

>

>There are many ways to formalize the problem of retrograde analysis. I am

>taking the following as a working definition.

>

>INSTANCE: Two generalized chess positions, a "start position" and an "end

>position."

>

>QUESTION: Does there exist a legal sequence of moves taking us from the

>start position to the end position?

>

>As a variation, we could also specify a bound on the number of moves.

>It is not even immediately clear that this problem is in NP, because the

>obvious "certificate" (i.e., the list of moves) could be exponential in

>length.

>

Both versions are NP-hard.

Proofsketch: reduction from Hamiltonian circuit for grid graphs.

A graph is a grid graph, if we can give every vertex a pair of coordinates (i,j),

such that two vertices are adjacent if they are adjacent in the grid:

(i,j) is adjacent to (i',j') iff i=i' and |j-j'|=1, or j=j' and |i-i'|=1.

Now, for an instance of this problem, we transform it as follows to the starting

configuration.

For every vertex (i,j), put a black pawn on a square with coordinates (4i,4j).

Also, put a white pawn directly before it, such that it cannot be moved, i.e., on

(4i,4j-1).

Put a white knight on a square where it can capture one of these black pawns.

Put a black pawn on an otherwise empty column.

Then, the ending position has all these black pawns except the last one removed.

(Tiny mistake in the proof: we should specify the location of the white pawn. Not

really a problem, however; we can transform instead from Hamiltonian path between

specified endpoints.)

The last pawn moved on the column exactly the number of steps the knight must

move when it takes all the pawns with a Hamiltonian circuit (basically, twice the

number of pawns).

That should work, and probably with not a really hard proof, I think.

More interesting would, imho, be a position that does more `unravelling'.

Hans

--

Hans Bodlaender - Department of Computer Science - Utrecht University

P.O. Box 80.089 - 3508 TB Utrecht - the Netherlands

ha...@cs.uu.nl http://www.cs.uu.nl/~hansb/index.html

Mar 15, 2001, 4:53:09 PM3/15/01

to

In article <98qs11$5...@severi.mit.edu>, <tc...@lsa.umich.edu> wrote:

>Apparently no theorems are known about the computational complexity of

>retrograde analysis in chess (or other well-known abstract games. I have

>raised this question before but have a couple of new thoughts that maybe

>someone can build on.

>Apparently no theorems are known about the computational complexity of

>retrograde analysis in chess (or other well-known abstract games. I have

>raised this question before but have a couple of new thoughts that maybe

>someone can build on.

>There are many ways to formalize the problem of retrograde analysis. I am

>taking the following as a working definition.

>INSTANCE: Two generalized chess positions, a "start position" and an "end

>position."

>QUESTION: Does there exist a legal sequence of moves taking us from the

>start position to the end position?

>As a variation, we could also specify a bound on the number of moves.

>It is not even immediately clear that this problem is in NP, because the

>obvious "certificate" (i.e., the list of moves) could be exponential in

>length.

The question is definitely in P; in fact, finite. One could

list all the K positions in chess (on a sufficiently large

computer). Now take the KxK matrix, and start out by writing

0 in all the diagonal positions, 1 in the ij position if it

is possible to get from position i to position j in one move,

and K+1 otherwise. Now proceed to produce a new array by

replacing the ij-th element by the minimum of the sum over

m of the im-th and the mj-th elements. It is trivial to see

that this terminates (reduces no elements) in at less than

K^2 steps; the number is even less than K. The element in

the ij-th position on termination is the number of moves

needed to get from position i to position j.

--

This address is for information only. I do not claim that these views

are those of the Statistics Department or of Purdue University.

Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399

hru...@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558

Mar 15, 2001, 5:03:18 PM3/15/01

to

Herman Rubin <hru...@odds.stat.purdue.edu> writes:

>> INSTANCE: Two generalized chess positions, a "start position" and an "end

>> position."

>

>> INSTANCE: Two generalized chess positions, a "start position" and an "end

>> position."

>

> The question is definitely in P; in fact, finite. One could

> list all the K positions in chess (on a sufficiently large

> computer).

> list all the K positions in chess (on a sufficiently large

> computer).

Obviously, all problems on a regular chessboard are finite. That's why

the complexity questions refer to "generalized chess", which is played

on an NxN board, for arbitrarily large N.

David desJardins

Mar 17, 2001, 8:44:24 AM3/17/01

to dav...@erols.com

I assume retrograde chess is intended to improve one's deductive

ability. If so, it pales in comparison to Kriegspiel.

ability. If so, it pales in comparison to Kriegspiel.

1. Any retrograde position is artificial -- it is the handiwork of its

composer, deliberate and contrived. In comparison, Kriegspiel is both

real-time and ad hoc, dynamic and unpredictable.

2. Retrodgrade chess looks backward, while Kriegspiel is forward

looking. The former is logic for logic's sake, while the latter is

logic in the service of the player.

When computer was in its infancy, a program was written for the

computer by a professor at Carneige-Mellon to serve as a referee in

Kriegspiel. No one, to my knowledge, has written a program for the

computer to be a Kriegspiel player.

In my book, Chess Detective - Kriegspiel Strategies, Endgames and

Problems (Premier Publishing, 1996), there is a chapter that compares

Kriegspiel to retrograde chess.

David Li

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu