Is retrograde chess NP-hard?
tc...@lsa.umich.edu
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
Jeremy Spinrad
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
Hans Bodlaender
>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
Herman Rubin
>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
David desJardins
>> INSTANCE: Two generalized chess positions, a "start position" and an "end
>> position."
>
> 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
DAVID H LI
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