| |
Main
Date: 19 Sep 2007 23:03:03
From: Proginoskes
Subject: Source for Eight Officers Problem?
|
Last night, I googled the Web for information about the Eight Officers
problem. (Put two rooks, two knights, two bishops, a queen, and a king
on a blank chessboard so that every square is attacked --- not just
occupied.) I found a solution where both bishops are on the same
colored square, and about a dozen positions where 63 squares are
attacked. The general consensus is that 63 is best possible, and that
the Eight Officers problem is impossible.
My question is this: Can anyone reference a book or a journal where a
full analysis of the impossibility of the Eight Officers appears? I am
seeking something along the lines of mathematical proof or a report of
doing brute force.
Thank you.
--- Christopher Heckman
|
|
| |
Date: 20 Oct 2007 07:04:49
From: Proginoskes
Subject: Re: Two more puzzles: "100 Moves" and "36 Mates": Was: Re: Source for Eight Officers Problem?
|
On Oct 15, 2:21 pm, Peter Osterlund <pete...@telia.com > wrote:
> Proginoskes <CCHeck...@gmail.com> writes:
> >> Btw, this problems seems a lot easier to prove formally than the first
> >> "eight officers" problem. For example, I was able to prove that if
> >> there is a solution with >= 101 moves, then there is such a solution
> >> with a bishop on c3, d3 or d4. (Note that the theoretical max is 105,
> >> not 108.)
>
> > I must have mis-counted the maximum number of squares a bishop can
> > move to, then.
>
> You correctly wrote
>
> 8 + 27 + 13 + 13 + 8 + 8 + 14 + 14
>
> but that sum equals 105, not 108.
>
>
>
> >> > (2) Place any (but not necessarily?) all pieces (both colors) from a
> >> > standard chess set on the board so that the Black king is not in
> >> > check, but the number of moves which checkmate Black is maximized.
> >> > Dudeney has a position which produces 36 mates (below) in his
> >> > _Amusements in Mathematics_. I don't think you can brute-force this
> >> > one. 8-)
>
> >> > r1b2n1B/6R1/pQ1R3n/NpNB1p1p/1P1k1KpP/P1ppp1P1/2PPPP1b/r2q4
>
> >> That position uses all 32 pieces and the position seems to be
> >> reachable from the initial position. I can improve on the 36 by
> >> breaking those assumptions, but is that allowed?
>
> > Good question. Dudeney doesn't say one way or another (and he's dead,
> > so we can't ask him), but he said that "no one had been able to beat
> > [36]." He probably insisted on a "legal" position, seeing as how fast
> > you were able to beat 36.
>
> Just move the white b4 pawn to b2. Then there are two more possible
> mates, bxc3# and dxc3#. However, then there would be no way for the
> white bishop to have gotten away from the c1 square.
>
> If you are allowed to remove some pieces, you can remove Ra8, Bc8,
> Nf8, move the white rook from d6 to d8, move the white pawn from h4 to
> b2. Then another mate would be Qf6#.
>
> Also, if you remove Pg4, Bh2, Pg3, three additional mates are Rg3#,
> Rg2# and Rg1#. That would give a position with 42 mates.
>
> Looks like we finally found the question for which 42 is the answer :)
Well, maybe not ...
I did more digging in the back issues of Chess Life today. In Andy
Soltis's column "Chess to Enjoy" in the February 1981 issue, he
mentions four unsolved problems, three of which I've already mentioned
in this thread.
The fourth is DOUBLE STALEMATE: Construct a legal position with all 32
pieces and pawns so that neither side can move. The record was held by
Karl Fabel, who in 1947 constructed such a position with only one
possible move.
He calls the problem of a legal position with the most mates-in-one-
move MAXIMUM MATE [which I called "36 Mates"], and there is a position
with 47 mates, but not all the pieces are on the board. So 42 isn't
the answer (not expressed in base 10, anyway ... but you could hope
for base 13, where in fact 6*9=42).
The BREAKING 100 problem [which I called "100 Moves"] was proven (it
seems formally) independently by Paul Flore, Waye Pineault, and Chris
Ferrante [Aug 1981, CTE].
Wayne Pineault used a computer to show that the EIGHT OFFICERS problem
was unsolvable. The machine took 400 hours to run [Feb 1984, CTE].
As of March, 1984, that's where it stands; two down, two to go.
[To be continued...]
--- Christopher Heckman
|
| |
Date: 15 Oct 2007 07:54:50
From: Proginoskes
Subject: Re: Two more puzzles: "100 Moves" and "36 Mates": Was: Re: Source for Eight Officers Problem?
|
On Oct 14, 7:32 am, Peter Osterlund <pete...@telia.com > wrote:
> Proginoskes <CCHeck...@gmail.com> writes:
> > (1) Arrange the "eight officers" (king, queen, 2 bishops -- opposite
> > colors, 2 knights, 2 rooks) on an otherwise blank board so that the
> > total number of moves is maximized. (This is not the same problem as
> > the Eight Officers problem, since a square attacked by two or more
> > pieces is counted twice.) An arrangement giving 100 moves ---
> > purported to be the answer --- is given below in FEN notation. (Yeah,
> > I know that's redundant ...) There is also a variation that also has
> > 100 moves. As of 1980, this problem was unsolved. (This is another old
> > problem, from 1848.)
>
> > Note that the maximum is at most 8 + 27 + 13 + 13 + 8 + 8 + 14 + 14 =
> > 108 (obtained by adding the maximum number of squares that a piece
> > attacks; however, not all pieces can be placed optimally). And you
> > don't need to bother counting castling; no maximum solution has the
> > possibility of castling.
>
> > FEN: 8/2R5/3N4/6R1/3BBN2/1Q6/3K4/8
> > (Seehttp://en.wikipedia.org/wiki/FEN)
>
> That problem is very easy for a computer. A simple and very efficient
> B&B rule is:
>
> The already available moves + the theretical maximum for the
> remaining pieces must be at least as large as the best solution
> found so far.
>
> Using that rule, the search space basically vanishes, and after a 30ms
> calculation (on only one CPU), the program concludes that the best
> possible is 100 moves, and that there are two solutions. The first one
> is the one you gave and the second one can be obtained from the first
> by moving just one rook.
Yes, to a5, I think.
> Btw, this problems seems a lot easier to prove formally than the first
> "eight officers" problem. For example, I was able to prove that if
> there is a solution with >= 101 moves, then there is such a solution
> with a bishop on c3, d3 or d4. (Note that the theoretical max is 105,
> not 108.)
I must have mis-counted the maximum number of squares a bishop can
move to, then.
> > (2) Place any (but not necessarily?) all pieces (both colors) from a
> > standard chess set on the board so that the Black king is not in
> > check, but the number of moves which checkmate Black is maximized.
> > Dudeney has a position which produces 36 mates (below) in his
> > _Amusements in Mathematics_. I don't think you can brute-force this
> > one. 8-)
>
> > r1b2n1B/6R1/pQ1R3n/NpNB1p1p/1P1k1KpP/P1ppp1P1/2PPPP1b/r2q4
>
> That position uses all 32 pieces and the position seems to be
> reachable from the initial position. I can improve on the 36 by
> breaking those assumptions, but is that allowed?
Good question. Dudeney doesn't say one way or another (and he's dead,
so we can't ask him), but he said that "no one had been able to beat
[36]." He probably insisted on a "legal" position, seeing as how fast
you were able to beat 36. Promotions, and underpromitions, are
probably okay as well.
I suspect the problem is already hard enough without insisting on
legality; you would need retrograde analysis to determine whether a
position is legal. (Of course, if you find out it _is_ legal,
constructing a game would be the only necessary proof. But you would
need to answer the question first.)
--- Christopher Heckman
|
| | |
Date: 15 Oct 2007 21:21:27
From: Peter Osterlund
Subject: Re: Two more puzzles: "100 Moves" and "36 Mates": Was: Re: Source for Eight Officers Problem?
|
Proginoskes <CCHeckman@gmail.com > writes:
>> Btw, this problems seems a lot easier to prove formally than the first
>> "eight officers" problem. For example, I was able to prove that if
>> there is a solution with >= 101 moves, then there is such a solution
>> with a bishop on c3, d3 or d4. (Note that the theoretical max is 105,
>> not 108.)
>
> I must have mis-counted the maximum number of squares a bishop can
> move to, then.
You correctly wrote
8 + 27 + 13 + 13 + 8 + 8 + 14 + 14
but that sum equals 105, not 108.
>> > (2) Place any (but not necessarily?) all pieces (both colors) from a
>> > standard chess set on the board so that the Black king is not in
>> > check, but the number of moves which checkmate Black is maximized.
>> > Dudeney has a position which produces 36 mates (below) in his
>> > _Amusements in Mathematics_. I don't think you can brute-force this
>> > one. 8-)
>>
>> > r1b2n1B/6R1/pQ1R3n/NpNB1p1p/1P1k1KpP/P1ppp1P1/2PPPP1b/r2q4
>>
>> That position uses all 32 pieces and the position seems to be
>> reachable from the initial position. I can improve on the 36 by
>> breaking those assumptions, but is that allowed?
>
> Good question. Dudeney doesn't say one way or another (and he's dead,
> so we can't ask him), but he said that "no one had been able to beat
> [36]." He probably insisted on a "legal" position, seeing as how fast
> you were able to beat 36.
Just move the white b4 pawn to b2. Then there are two more possible
mates, bxc3# and dxc3#. However, then there would be no way for the
white bishop to have gotten away from the c1 square.
If you are allowed to remove some pieces, you can remove Ra8, Bc8,
Nf8, move the white rook from d6 to d8, move the white pawn from h4 to
b2. Then another mate would be Qf6#.
Also, if you remove Pg4, Bh2, Pg3, three additional mates are Rg3#,
Rg2# and Rg1#. That would give a position with 42 mates.
Looks like we finally found the question for which 42 is the answer :)
> I suspect the problem is already hard enough without insisting on
> legality; you would need retrograde analysis to determine whether a
> position is legal. (Of course, if you find out it _is_ legal,
> constructing a game would be the only necessary proof. But you would
> need to answer the question first.)
Agreed. I don't see how to solve this problem using brute force in a
reasonable amount of time.
--
Peter Osterlund - petero2@telia.com
http://web.telia.com/~u89404340
|
| |
Date: 14 Oct 2007 09:13:02
From: Proginoskes
Subject: Two more puzzles: "100 Moves" and "36 Mates": Was: Re: Source for Eight Officers Problem?
|
On Sep 19, 4:03 pm, Proginoskes <CCHeck...@gmail.com > wrote:
> Last night, I googled the Web for information about the Eight Officers
> problem. (Put two rooks, two knights, two bishops, a queen, and a king
> on a blank chessboard so that every square is attacked --- not just
> occupied.) I found a solution where both bishops are on the same
> colored square, and about a dozen positions where 63 squares are
> attacked. The general consensus is that 63 is best possible, and that
> the Eight Officers problem is impossible.
>
> My question is this: Can anyone reference a book or a journal where a
> full analysis of the impossibility of the Eight Officers appears? I am
> seeking something along the lines of mathematical proof or a report of
> doing brute force.
On Saturday, I went through the back issues of Chess Life up through
1980 at the local public library; still no mention of the Eight
Officers problem. I hope to get back in the next few weeks and search
some more.
For those of you who liked working on this problem, here are a couple
more in this vein. The first one should be a slight variation, in
terms of programming. The second will be much more difficult.
(1) Arrange the "eight officers" (king, queen, 2 bishops -- opposite
colors, 2 knights, 2 rooks) on an otherwise blank board so that the
total number of moves is maximized. (This is not the same problem as
the Eight Officers problem, since a square attacked by two or more
pieces is counted twice.) An arrangement giving 100 moves ---
purported to be the answer --- is given below in FEN notation. (Yeah,
I know that's redundant ...) There is also a variation that also has
100 moves. As of 1980, this problem was unsolved. (This is another old
problem, from 1848.)
Note that the maximum is at most 8 + 27 + 13 + 13 + 8 + 8 + 14 + 14 =
108 (obtained by adding the maximum number of squares that a piece
attacks; however, not all pieces can be placed optimally). And you
don't need to bother counting castling; no maximum solution has the
possibility of castling.
FEN: 8/2R5/3N4/6R1/3BBN2/1Q6/3K4/8
(See http://en.wikipedia.org/wiki/FEN )
(2) Place any (but not necessarily?) all pieces (both colors) from a
standard chess set on the board so that the Black king is not in
check, but the number of moves which checkmate Black is maximized.
Dudeney has a position which produces 36 mates (below) in his
_Amusements in Mathematics_. I don't think you can brute-force this
one. 8-)
r1b2n1B/6R1/pQ1R3n/NpNB1p1p/1P1k1KpP/P1ppp1P1/2PPPP1b/r2q4
--- Christopher Heckman
|
| | |
Date: 14 Oct 2007 14:32:14
From: Peter Osterlund
Subject: Re: Two more puzzles: "100 Moves" and "36 Mates": Was: Re: Source for Eight Officers Problem?
|
Proginoskes <CCHeckman@gmail.com > writes:
> (1) Arrange the "eight officers" (king, queen, 2 bishops -- opposite
> colors, 2 knights, 2 rooks) on an otherwise blank board so that the
> total number of moves is maximized. (This is not the same problem as
> the Eight Officers problem, since a square attacked by two or more
> pieces is counted twice.) An arrangement giving 100 moves ---
> purported to be the answer --- is given below in FEN notation. (Yeah,
> I know that's redundant ...) There is also a variation that also has
> 100 moves. As of 1980, this problem was unsolved. (This is another old
> problem, from 1848.)
>
> Note that the maximum is at most 8 + 27 + 13 + 13 + 8 + 8 + 14 + 14 =
> 108 (obtained by adding the maximum number of squares that a piece
> attacks; however, not all pieces can be placed optimally). And you
> don't need to bother counting castling; no maximum solution has the
> possibility of castling.
>
> FEN: 8/2R5/3N4/6R1/3BBN2/1Q6/3K4/8
> (See http://en.wikipedia.org/wiki/FEN )
That problem is very easy for a computer. A simple and very efficient
B&B rule is:
The already available moves + the theretical maximum for the
remaining pieces must be at least as large as the best solution
found so far.
Using that rule, the search space basically vanishes, and after a 30ms
calculation (on only one CPU), the program concludes that the best
possible is 100 moves, and that there are two solutions. The first one
is the one you gave and the second one can be obtained from the first
by moving just one rook.
Btw, this problems seems a lot easier to prove formally than the first
"eight officers" problem. For example, I was able to prove that if
there is a solution with >= 101 moves, then there is such a solution
with a bishop on c3, d3 or d4. (Note that the theoretical max is 105,
not 108.)
> (2) Place any (but not necessarily?) all pieces (both colors) from a
> standard chess set on the board so that the Black king is not in
> check, but the number of moves which checkmate Black is maximized.
> Dudeney has a position which produces 36 mates (below) in his
> _Amusements in Mathematics_. I don't think you can brute-force this
> one. 8-)
>
> r1b2n1B/6R1/pQ1R3n/NpNB1p1p/1P1k1KpP/P1ppp1P1/2PPPP1b/r2q4
That position uses all 32 pieces and the position seems to be
reachable from the initial position. I can improve on the 36 by
breaking those assumptions, but is that allowed?
--
Peter Osterlund - petero2@telia.com
http://web.telia.com/~u89404340
|
| |
Date: 08 Oct 2007 06:07:45
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?
|
On Oct 7, 6:39 am, Peter Osterlund <pete...@telia.com > wrote:
> Proginoskes <CCHeck...@gmail.com> writes:
> > First of all, Laurence Reeves's algorithm is branch-and-bound (which
> > he originally called "heuristic"). Second, he can't produce histogram
> > data _for all values of N_, where N is the number of squares covered.
> > After he places the queen, bishops, and rooks, he counts how many
> > squares are not attacked, and if this number is greater than 24, he
> > doesn't bother with placing the king and knights, since these pieces
> > can attack at most 24 squares.* Thus, the histogram data will be
> > incorrect for N < 40. However, for larger values of N, it will be
> > correct, because he does check all cases.
>
> > * This number is smaller in some configurations, and in some cases,
> > the king and or a knight might block a piece's attack, but the latter
> > will only increase the number of squares that need to be attacked. He
> > does a slightly more clever check: He counts how many black squares
> > and how many white squares are not attacked. A king and two knights
> > can attack at most 12 white (resp. black) squares, which will catch
> > more of the "hopeless" cases before trying all possibilities for the
> > king and 2 knights.
>
> A king and two knights can attack at least 19 white squares.
SMACK!!! (That was directed at my forehead.)
Yes; I just divided 24 by 12. It should have been: king and two
knights can attack at most 8+8+4 = 20 white squares, since.the squares
that the knight attacks are all of the same color (opposite from where
the knight is).
Actually, it will be at most (20 of one color and 4 of the other
color), or at most 12 of each.
--- Christopher Heckman
> Is this a bug in the branch and bound implementation, or was your
> description just simplified in some way?
>
> (I actually implemented your description in my program before
> realizing this problem, but the program found 144 63-solutions
> anyway.)
|
| |
Date: 03 Oct 2007 22:18:38
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?
|
On Oct 3, 2:08 pm, tew...@lycos.com wrote:
> In one of the previous posts, I believe you mentioned that all of the
> 63 square solutions had the Queen on a d4 type square. I'm wondering
> if it might be possible to prove that having the Queen on a d4 type
> square is superior than having the Queen anywhere else. If this proof
> were not too difficult, you'd only need to run through the cases where
> the Queen is on a d4 type square. There would still be an awful lot
> of cases to consider though, wouldn't there?
Yes, it would help, and yes the number of cases will be in the
hundreds of billions (about 10^11) instead of about 12 trillion (the
1.2 * 10^13 number I derived elsewhere in this post).
> Maybe there's some other observations that could be made about the
> placement of the pieces that could cut down the number of cases you
> need to consider.
This is actually along the lines of one of my suggestions earlier:
that you could prove some results that say: "If you have all 64
squares covered, then [certain piece] has to be on [certain square or
set of squares]." If you could establish that five of the eight pieces
had to be on certain squares, then the computer search wouldn't be so
bad, and you've moved away from a "computer proof" of the result to a
"computer-assisted proof" (where the computer searched through a lot
of cases, which suggested the way to the proof) of the result.
I think there will still have to be a computer search *somewhere*,
mostly because otherwise the problem would have been solved much
earlier. (Some 63-square solutions go back to the 1930s; this is an
OLD problem. It would be nice to find out who first asked it, as part
of the "official report".)
--- Christopher Heckman
|
| |
Date: 03 Oct 2007 14:08:44
From:
Subject: Re: Source for Eight Officers Problem?
|
In one of the previous posts, I believe you mentioned that all of the
63 square solutions had the Queen on a d4 type square. I'm wondering
if it might be possible to prove that having the Queen on a d4 type
square is superior than having the Queen anywhere else. If this proof
were not too difficult, you'd only need to run through the cases where
the Queen is on a d4 type square. There would still be an awful lot
of cases to consider though, wouldn't there?
Maybe there's some other observations that could be made about the
placement of the pieces that could cut down the number of cases you
need to consider.
|
| |
Date: 01 Oct 2007 21:57:26
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?
|
On Oct 1, 5:12 am, Laurence Reeves <l...@bergbland.info > wrote:
> Proginoskes wrote:
> > ... First of all, Laurence Reeves's algorithm is branch-and-bound (which
> > he originally called "heuristic"). ...
>
> A minor "point of order". I never called my method "heuristic". I went
> to some pains to explain that, to me, a "heuristic" approach would mean
> "not guaranteed to find all solutions". It might find 144 solutions, but
> could only EVER give that as a lower bound (unless there happened to be
> some a priori reason why it was known that there were exactly 144
> solutions). I use an algorithm (to find *the* solutions to the problem)
> not a heuristic (to maybe find *some* solutions to the problem).
>
> Having never come across the terminology of "branch and bound" before, I
> looked it up.
>
> Technically, I'm not sure that my algorithm is that either, as it does
> not do any branching.
The branching is done when you decide which square a certain piece
goes on. It's like a proof "by cases", where each possibility is
considered.
> I suppose you can interpret it that way, in that I
> progress each time from one specific (branched?) layout of five, six or
> seven pieces, and discard (bound) by rejecting further processing of a
> partial layout if it is provably not able to produce any solutions to
> the problem at hand (i.e. coverings of >= 63 squares).
Yes, that's exactly how I'm interpretting it. And, as a consequence,
each arrangement of chesspieces will either be (a) rejected because
fewer than 40 squares will covered,* or (b) accepted and counted in
the histogram. So this algorithm won't give correct results for the
number of ways to place the pieces so that exactly 20 squares are
attacked, but it will for the number of ways where 45 are attacked.
* I'm leaving out the discussion involving black and white squares,
for clarity's sake.
> Another distinction from "branch and bound" might be that my algorithm
> is exact and guaranteed to terminate, whereas B&B seems not to imply
> that it should go that far.
An algorithm terminates (by definition). And algorithms also solve
their problem (by definition). "Programs" or "code" might not.
--- Christopher Heckman
|
| | |
Date: 02 Oct 2007 00:34:48
From: Laurence Reeves
Subject: Re: Source for Eight Officers Problem?
|
Proginoskes wrote:
> ... An algorithm terminates (by definition). And algorithms also solve
> their problem (by definition). "Programs" or "code" might not.
:)
An algorithm, by definition, does not necessarily terminate. I can quite
happily give you an algorithm for calculating the decimal expansion of
pi. It does not terminate.
I can also give an algorithm for calculating the decimal expansion of
2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2. It
could terminate, but it won't.
Also, to quote Wikipedia "The analysis of algorithms for their
likelihood of termination is called Termination analysis."
Algorithms do NOT necessarily solve their problems. They are techniques
that maybe /intend/ to solve a problem. An algorithm doesn't cease to be
an algorithm just because it fails to solve the problem is was meant to
solve. It may even solve a different problem, which it transpires was a
good problem to have solved.
Indeed, an algorithm may not have any specific aim in view. I can
present an algorithm for constructing things out of bricks, without
having a specific problem to solve (building to construct).
My, ain't terminology fun.
OED. 2. Math. A process, or set of rules, usually one expressed in
algebraic notation, now used esp. in computing, machine translation and
linguistics.
Merriam-Webster leans toward your definition(?), but that seems silly,
to me. It means that you do not have a word to describe what I call an
algorithm, until you have shown that it terminates and gets the correct
solution to a particular problem.
--
Lau AS! d-(!) a++ c++++ p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++
ASC Decoder at <http://www32.brinkster.com/ascdecode/ >
|
| |
Date: 01 Oct 2007 05:57:06
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?
|
On Sep 30, 12:17 am, Peter Osterlund <pete...@telia.com > wrote:
> Proginoskes <CCHeck...@gmail.com> writes:
> > On Sep 29, 2:31 pm, Peter Osterlund <pete...@telia.com> wrote:
>
> >> My brute force program is currently running on a 2.4GHz Intel Core 2
> >> Quad computer in 64 bit mode at a speed of approximately 120 million
> >> positions per second. Since I didn't implement any symmetry detection
> >> at all, the search space size is about 1.13e13, which means that the
> >> computation should be finished in about 26 hours.
>
> >> The output will be the histogram data and the "maximum" positions.
> >> (Actually split up in 32 files because of how I implemented the
> >> parallel search and checkpointing, but merging should be simple.)
>
> > The code Laurence Reeves sent me took two hours (plus or minus 30
> > seconds) unmodified. I got a couple of basic ideas for speeding up the
> > process and have started another run. No information on processor
> > speed at the moment, though. (I got a new computer a few weeks ago.)
>
> I might be wrong, but I thought his program was using branch and
> bound, and was therefore not able to produce the histogram data.
First of all, Laurence Reeves's algorithm is branch-and-bound (which
he originally called "heuristic"). Second, he can't produce histogram
data _for all values of N_, where N is the number of squares covered.
After he places the queen, bishops, and rooks, he counts how many
squares are not attacked, and if this number is greater than 24, he
doesn't bother with placing the king and knights, since these pieces
can attack at most 24 squares.* Thus, the histogram data will be
incorrect for N < 40. However, for larger values of N, it will be
correct, because he does check all cases.
* This number is smaller in some configurations, and in some cases,
the king and or a knight might block a piece's attack, but the latter
will only increase the number of squares that need to be attacked. He
does a slightly more clever check: He counts how many black squares
and how many white squares are not attacked. A king and two knights
can attack at most 12 white (resp. black) squares, which will catch
more of the "hopeless" cases before trying all possibilities for the
king and 2 knights.
> Also, if I were to consider symmetries, I think it would be possible
> to cut down the run time to about 4 hours by only considering 10
> squares for the king. However, that would produce a different
> histogram.
Yes, because you can't get as good of a bound on the number of squares
that the last 3 pieces can attack, which will require more case-
checking and more configurations. The numbers near the top should be
the same, though.
--- Christopher Heckman
|
| | |
Date: 07 Oct 2007 13:39:47
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?
|
Proginoskes <CCHeckman@gmail.com > writes:
> First of all, Laurence Reeves's algorithm is branch-and-bound (which
> he originally called "heuristic"). Second, he can't produce histogram
> data _for all values of N_, where N is the number of squares covered.
> After he places the queen, bishops, and rooks, he counts how many
> squares are not attacked, and if this number is greater than 24, he
> doesn't bother with placing the king and knights, since these pieces
> can attack at most 24 squares.* Thus, the histogram data will be
> incorrect for N < 40. However, for larger values of N, it will be
> correct, because he does check all cases.
>
> * This number is smaller in some configurations, and in some cases,
> the king and or a knight might block a piece's attack, but the latter
> will only increase the number of squares that need to be attacked. He
> does a slightly more clever check: He counts how many black squares
> and how many white squares are not attacked. A king and two knights
> can attack at most 12 white (resp. black) squares, which will catch
> more of the "hopeless" cases before trying all possibilities for the
> king and 2 knights.
A king and two knights can attack at least 19 white squares. For
example, Nc3, Ne5, Kg2 will attack:
b1,d1,e2,e4,d5,b5,a4,a2,
d3,f3,g4,g6,f7,d7,c6,c4,
f1,h1,h3
Is this a bug in the branch and bound implementation, or was your
description just simplified in some way?
(I actually implemented your description in my program before
realizing this problem, but the program found 144 63-solutions
anyway.)
--
Peter Osterlund - petero2@telia.com
http://web.telia.com/~u89404340
|
| | | |
Date: 07 Oct 2007 14:43:22
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?
|
Peter Osterlund <petero2@telia.com > writes:
> Proginoskes <CCHeckman@gmail.com> writes:
>
>> First of all, Laurence Reeves's algorithm is branch-and-bound (which
>> he originally called "heuristic"). Second, he can't produce histogram
>> data _for all values of N_, where N is the number of squares covered.
>> After he places the queen, bishops, and rooks, he counts how many
>> squares are not attacked, and if this number is greater than 24, he
>> doesn't bother with placing the king and knights, since these pieces
>> can attack at most 24 squares.* Thus, the histogram data will be
>> incorrect for N < 40. However, for larger values of N, it will be
>> correct, because he does check all cases.
>>
>> * This number is smaller in some configurations, and in some cases,
>> the king and or a knight might block a piece's attack, but the latter
>> will only increase the number of squares that need to be attacked. He
>> does a slightly more clever check: He counts how many black squares
>> and how many white squares are not attacked. A king and two knights
>> can attack at most 12 white (resp. black) squares, which will catch
>> more of the "hopeless" cases before trying all possibilities for the
>> king and 2 knights.
>
> A king and two knights can attack at least 19 white squares. For
> example, Nc3, Ne5, Kg2 will attack:
>
> b1,d1,e2,e4,d5,b5,a4,a2,
> d3,f3,g4,g6,f7,d7,c6,c4,
> f1,h1,h3
I implemented the following B&B rule instead:
// Return true if it is found to be impossible to get at least numWanted
// squares attacked by placing numKnights knights and one king, if the
// number of already attacked squares is given by whiteAttacked and
// blackAttacked.
static inline bool
hopeless(int numWanted, int whiteAttacked, int blackAttacked, int numKnights)
{
if (whiteAttacked + blackAttacked + numKnights * 8 + 8 < numWanted)
return true;
int minAttacked = std::min(whiteAttacked, blackAttacked);
int minNeeded = numWanted - 32;
if (minAttacked + 8 * numKnights + 4 < minNeeded)
return true;
return false;
}
With that rule, finding all 64-solutions (ie 0) takes 39 seconds and
finding all 63-solutions (ie 144) takes 64 seconds. This is on the
2.4GHz Core 2 Quad machine. On a 3GHz P4 machine, the program runs
about 8 times slower.
The updated program is available here:
http://web.telia.com/~u89404340/officer2.tar.bz2
--
Peter Osterlund - petero2@telia.com
http://web.telia.com/~u89404340
|
| | | | |
Date: 09 Oct 2007 05:09:28
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?
|
Peter Osterlund <petero2@telia.com > writes:
> I implemented the following B&B rule instead:
>
> static inline bool
> hopeless(int numWanted, int whiteAttacked, int blackAttacked, int numKnights)
> {
> if (whiteAttacked + blackAttacked + numKnights * 8 + 8 < numWanted)
> return true;
> int minAttacked = std::min(whiteAttacked, blackAttacked);
> int minNeeded = numWanted - 32;
> if (minAttacked + 8 * numKnights + 4 < minNeeded)
> return true;
> return false;
> }
That rule is quite inefficient though. New rule:
static inline bool
hopeless(int numWanted, int whiteAttacked, int blackAttacked, int numKnights)
{
for (int whiteKnights = 0; whiteKnights <= numKnights; whiteKnights++) {
int blackKnights = numKnights - whiteKnights;
int white = whiteAttacked + whiteKnights * 8 + 4;
int black = blackAttacked + blackKnights * 8 + 4;
if (std::min(white, 32) + std::min(black, 32) >= numWanted)
return false;
}
return true;
}
With that rule, finding all 64-solutions takes 8 seconds and finding
all 63-solutions takes 20 seconds.
--
Peter Osterlund - petero2@telia.com
http://web.telia.com/~u89404340
|
| | | | | |
Date: 09 Oct 2007 05:07:47
From: =?ISO-8859-1?Q?=AA=BA=AA_rrock?=
Subject: Re: Source for Eight Officers Problem?
|
Peter Osterlund wrote:
> Peter Osterlund <petero2@telia.com> writes:
>
>
>>I implemented the following B&B rule instead:
>>
>> static inline bool
>> hopeless(int numWanted, int whiteAttacked, int blackAttacked, int numKnights)
>> {
>> if (whiteAttacked + blackAttacked + numKnights * 8 + 8 < numWanted)
>> return true;
>> int minAttacked = std::min(whiteAttacked, blackAttacked);
>> int minNeeded = numWanted - 32;
>> if (minAttacked + 8 * numKnights + 4 < minNeeded)
>> return true;
>> return false;
>> }
>
>
> That rule is quite inefficient though. New rule:
>
> static inline bool
> hopeless(int numWanted, int whiteAttacked, int blackAttacked, int numKnights)
> {
> for (int whiteKnights = 0; whiteKnights <= numKnights; whiteKnights++) {
> int blackKnights = numKnights - whiteKnights;
> int white = whiteAttacked + whiteKnights * 8 + 4;
> int black = blackAttacked + blackKnights * 8 + 4;
> if (std::min(white, 32) + std::min(black, 32) >= numWanted)
> return false;
> }
> return true;
> }
>
> With that rule, finding all 64-solutions takes 8 seconds and finding
> all 63-solutions takes 20 seconds.
>
It looks like you are getting closer to a formal proof. Why does it take
8 seconds to find zero solutions? A formal proof would find zero solutions
in zero seconds.
|
| | | | | | |
Date: 09 Oct 2007 19:01:37
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?
|
ªºª rrock <invalid@address.here > writes:
> Peter Osterlund wrote:
>> Peter Osterlund <petero2@telia.com> writes:
>>
>>
>>>I implemented the following B&B rule instead:
>>>
>>> static inline bool
>>> hopeless(int numWanted, int whiteAttacked, int blackAttacked, int numKnights)
>>> {
>>> if (whiteAttacked + blackAttacked + numKnights * 8 + 8 < numWanted)
>>> return true;
>>> int minAttacked = std::min(whiteAttacked, blackAttacked);
>>> int minNeeded = numWanted - 32;
>>> if (minAttacked + 8 * numKnights + 4 < minNeeded)
>>> return true;
>>> return false;
>>> }
>>
>>
>> That rule is quite inefficient though. New rule:
>>
>> static inline bool
>> hopeless(int numWanted, int whiteAttacked, int blackAttacked, int numKnights)
>> {
>> for (int whiteKnights = 0; whiteKnights <= numKnights; whiteKnights++) {
>> int blackKnights = numKnights - whiteKnights;
>> int white = whiteAttacked + whiteKnights * 8 + 4;
>> int black = blackAttacked + blackKnights * 8 + 4;
>> if (std::min(white, 32) + std::min(black, 32) >= numWanted)
>> return false;
>> }
>> return true;
>> }
>>
>> With that rule, finding all 64-solutions takes 8 seconds and finding
>> all 63-solutions takes 20 seconds.
>
> It looks like you are getting closer to a formal proof. Why does it take
> 8 seconds to find zero solutions? A formal proof would find zero solutions
> in zero seconds.
It takes 8 seconds because the program has to analyze 36202866
positions. All other positions are discarded by the B&B rule and the
symmetry discarding logic. The result is the following incomplete
histogram:
43 5
44 14
45 35
46 203
47 830
48 2365
49 6247
50 13674
51 31684
52 137021
53 605595
54 1674620
55 3284892
56 9405862
57 11132660
58 6811766
59 2456563
60 559083
61 74414
62 5224
63 109
64 0
This shows (together with a proof that the program, compiler, cpu, etc
is correct) that there is no 64-solution to the problem.
However, it's still quite far away from a formal proof. Analyzing
those 36 million positions by hand and proving that the other
1416336714894 positions can be safely ignored, would probably take a
human being more than a lifetime.
--
Peter Osterlund - petero2@telia.com
http://web.telia.com/~u89404340
|
| | | | | | | |
Date: 09 Oct 2007 15:24:15
From: =?UTF-8?B?wqrCusKqIHJyb2Nr?=
Subject: Re: Source for Eight Officers Problem?
|
Peter Osterlund wrote:
> ªºª rrock <invalid@address.here> writes:
>
>
>>Peter Osterlund wrote:
>>
>>>Peter Osterlund <petero2@telia.com> writes:
>>>
>>>
>>>
>>>>I implemented the following B&B rule instead:
>>>>
>>>> static inline bool
>>>> hopeless(int numWanted, int whiteAttacked, int blackAttacked, int numKnights)
>>>> {
>>>> if (whiteAttacked + blackAttacked + numKnights * 8 + 8 < numWanted)
>>>> return true;
>>>> int minAttacked = std::min(whiteAttacked, blackAttacked);
>>>> int minNeeded = numWanted - 32;
>>>> if (minAttacked + 8 * numKnights + 4 < minNeeded)
>>>> return true;
>>>> return false;
>>>> }
>>>
>>>
>>>That rule is quite inefficient though. New rule:
>>>
>>> static inline bool
>>> hopeless(int numWanted, int whiteAttacked, int blackAttacked, int numKnights)
>>> {
>>> for (int whiteKnights = 0; whiteKnights <= numKnights; whiteKnights++) {
>>> int blackKnights = numKnights - whiteKnights;
>>> int white = whiteAttacked + whiteKnights * 8 + 4;
>>> int black = blackAttacked + blackKnights * 8 + 4;
>>> if (std::min(white, 32) + std::min(black, 32) >= numWanted)
>>> return false;
>>> }
>>> return true;
>>> }
>>>
>>>With that rule, finding all 64-solutions takes 8 seconds and finding
>>>all 63-solutions takes 20 seconds.
>>
>>It looks like you are getting closer to a formal proof. Why does it take
>>8 seconds to find zero solutions? A formal proof would find zero solutions
>>in zero seconds.
>
>
> It takes 8 seconds because the program has to analyze 36202866
> positions. All other positions are discarded by the B&B rule and the
> symmetry discarding logic. The result is the following incomplete
> histogram:
>
> 43 5
> 44 14
> 45 35
> 46 203
> 47 830
> 48 2365
> 49 6247
> 50 13674
> 51 31684
> 52 137021
> 53 605595
> 54 1674620
> 55 3284892
> 56 9405862
> 57 11132660
> 58 6811766
> 59 2456563
> 60 559083
> 61 74414
> 62 5224
> 63 109
> 64 0
>
> This shows (together with a proof that the program, compiler, cpu, etc
> is correct) that there is no 64-solution to the problem.
>
> However, it's still quite far away from a formal proof. Analyzing
> those 36 million positions by hand and proving that the other
> 1416336714894 positions can be safely ignored, would probably take a
> human being more than a lifetime.
I don't know about that. I don't think your catching my drift, either.
The first time anything at all about a histogram or symmetry was mentioned,
it was in regards to my questions on what was originally asked for. And
during the interim of then and now, a number of people have had a number
of different inputs on just what is or isn't worthwhile, what is or isn't
symmetry, or even how many cases were actually under "formal" consideration.
Your program is *not* by any means a brute force program, rather, it is
a tool that is helping you whittle down that larger number, and you and
others have made quite a few small discoveries in what, only a week or
so? Each of those little rules is a small part of the ultimate formal
proof. I don't think you're giving yourself or the group interested in
this thread as much credit as you deserve and/or are underestimating the
combined capabilities. As a programmer you should be looking at the rules
mathematically to discover those small underlying logic clues that lead
to bigger revelations. You're not giving up, are you?
By the way, completely on a different note, did i miss something earlier
or is there a reason 63 has only 109 cases now instead of the 144? If i
missed that post, please let me know. I'd hate to find my old dog over
here had come up with 109 after a month of waiting, figure i screwed up
and... lol delete the files. Was the 144 with or without symmetry? That
still wouldn't make sense. Let me know. I understand the histogram is
incomplete, but i don't understand how it could not fill in all of the
63 coverage states and still be competent enough to say it had checked
all of the 64's. If that is correct, and the 144 still hasn't changed,
then THERE is a heap of data for checking out regarding another rule.
For example, which of the 63's has it forsaken, and WHY? Any pattern?
(even a plaid pattern for egg-heads?). Quit worrying about the 36 million
positions and pay attention to the 109. Just my two cents.
>
|
| | | | | | | | |
Date: 09 Oct 2007 21:59:59
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?
|
ªºª rrock <invalid@address.here > writes:
> Peter Osterlund wrote:
>
>> It takes 8 seconds because the program has to analyze 36202866
>> positions. All other positions are discarded by the B&B rule and the
>> symmetry discarding logic. The result is the following incomplete
>> histogram:
...
>> This shows (together with a proof that the program, compiler, cpu, etc
>> is correct) that there is no 64-solution to the problem.
>>
>> However, it's still quite far away from a formal proof. Analyzing
>> those 36 million positions by hand and proving that the other
>> 1416336714894 positions can be safely ignored, would probably take a
>> human being more than a lifetime.
>
> I don't know about that. I don't think your catching my drift, either.
> The first time anything at all about a histogram or symmetry was mentioned,
> it was in regards to my questions on what was originally asked for. And
> during the interim of then and now, a number of people have had a number
> of different inputs on just what is or isn't worthwhile, what is or isn't
> symmetry, or even how many cases were actually under "formal" consideration.
>
> Your program is *not* by any means a brute force program, rather, it is
> a tool that is helping you whittle down that larger number, and you and
> others have made quite a few small discoveries in what, only a week or
> so? Each of those little rules is a small part of the ultimate formal
> proof. I don't think you're giving yourself or the group interested in
> this thread as much credit as you deserve and/or are underestimating the
> combined capabilities. As a programmer you should be looking at the rules
> mathematically to discover those small underlying logic clues that lead
> to bigger revelations. You're not giving up, are you?
I haven't given up on making my program faster, but unfortunately I
don't see much hope in transforming my program into a formal proof
short enough to be verified by a human without computer help.
One idea I'm planning to test is to first let the program spend some
time computing more efficient B&B rules, then use those rules to
further reduce the number of positions it needs to evaluate.
> By the way, completely on a different note, did i miss something earlier
> or is there a reason 63 has only 109 cases now instead of the 144? If i
> missed that post, please let me know. I'd hate to find my old dog over
> here had come up with 109 after a month of waiting, figure i screwed up
> and... lol delete the files. Was the 144 with or without symmetry? That
> still wouldn't make sense. Let me know. I understand the histogram is
> incomplete, but i don't understand how it could not fill in all of the
> 63 coverage states and still be competent enough to say it had checked
> all of the 64's. If that is correct, and the 144 still hasn't changed,
> then THERE is a heap of data for checking out regarding another rule.
> For example, which of the 63's has it forsaken, and WHY? Any pattern?
> (even a plaid pattern for egg-heads?). Quit worrying about the 36 million
> positions and pay attention to the 109. Just my two cents.
There are indeed 144 solutions, but in some cases the program can
realize after placing all pieces except the king that there is no
point placing the king, because it is impossible to attack all 64
squares. In that case, the program doesn't test all available king
positions, even though some of those positions might lead to a
63-solution.
An example:
......R.
.......R
........
.K......
..B.....
...Q....
.B....N.
...N....
In this position, all squares except g1 are attacked. However, if you
remove the king, the squares a5, b4, b6, c5 are also unattacked. All
those five squares are black, and the program knows that a king can
only attack at most 4 black squares. Therefore it doesn't even try to
place the king, which means that it will not find the 63-solution.
--
Peter Osterlund - petero2@telia.com
http://web.telia.com/~u89404340
|
| | | | | | | | | |
Date: 14 Oct 2007 12:00:45
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?
|
Peter Osterlund <petero2@telia.com > writes:
> I haven't given up on making my program faster, but unfortunately I
> don't see much hope in transforming my program into a formal proof
> short enough to be verified by a human without computer help.
>
> One idea I'm planning to test is to first let the program spend some
> time computing more efficient B&B rules, then use those rules to
> further reduce the number of positions it needs to evaluate.
I implemented this idea. The program starts by computing the following
array:
unsigned char numUnAttackedByKnights_[65536];
If the attacked squares on two adjacent rows on the board are given by
"mask" (16 bits), numUnAttackedByKnights_[mask] equals the minimum
number of remaining unattacked squares on those two rows, when the
knights are allowed to be placed anywhere on the board.
During the search, after placing BBQRR, the array is used to find out
how many more squares the king is required to attack on rows 1-2, 3-4,
5-6 and 7-8. Using the fact that the king can only attack squares in
at most two of the four regions, about 70% of the positions can be
pruned. (The old pruning rule that considered the maximum number of
white and black squares possible to attack with N knights and a king
is also used.)
With the above rule, finding all 64-solutions takes 4.4 seconds and finding
all 63-solutions takes 18.3 seconds.
I don't think I can get the program much faster, unless someone
manages to prove some property of the form Proginoskes has brought up,
such as:
"if the 8-O problem is possible, then the queen has to be on
d4 (or one of the other three central squares)"
--
Peter Osterlund - petero2@telia.com
http://web.telia.com/~u89404340
|
| | | | | | | | | |
Date: 10 Oct 2007 16:42:39
From: Laurence Reeves
Subject: Re: Source for Eight Officers Problem?
|
Peter Osterlund wrote:
....
> In this position, all squares except g1 are attacked. However, if you
> remove the king, the squares a5, b4, b6, c5 are also unattacked. All
> those five squares are black, and the program knows that a king can
> only attack at most 4 black squares. Therefore it doesn't even try to
> place the king, which means that it will not find the 63-solution.
A very minor point, but out of interest, have you tried placing the
knights as the the last two pieces? I suspect you will trim a little off
your timings, as it is much less likely to attempt the final knight's
57-way positioning. The constraint of all eight (nine) remaining
un-attacked squares being the same colour (bar one) should cause far
more rejections than the condition of them splitting (roughly) half and
half for the king.
As I measured earlier, the largest ratio of savings occurs at that final
test. Applying the test prior to the final three pieces saves 16%
(IIRC), the penultimate test does save a solid ratio (4 to 1), but the
final test is the important one.
And...
=================
What has just this moment occurred to me, as I typed, is that I've been
stupid. When down to that final knight, I didn't limit it properly. Once
one has made the B/W test, for the 63-cover, one has four cases
remaining: 9W, 8W+1B, 1W+8B or 9B. In the former pair, the knight MUST
go on a black square, in the latter pair, on a white. So, even when it
needs to be attempted, this chops the final loop in half. I suspect that
this will easily halve your run time.
Rule of thumb: Never try to improve your run times by percentages.
Always look for factors of improvement, preferably greater than two, but
that'll do. (See hashlife/Golly)
--
Lau AS! d-(!) a++ c++++ p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++
ASC Decoder at <http://www32.brinkster.com/ascdecode/ >
|
| | | | | | | | | | |
Date: 10 Oct 2007 20:42:08
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?
|
Laurence Reeves <l@bergbland.info > writes:
> Peter Osterlund wrote:
> ....
>> In this position, all squares except g1 are attacked. However, if you
>> remove the king, the squares a5, b4, b6, c5 are also unattacked. All
>> those five squares are black, and the program knows that a king can
>> only attack at most 4 black squares. Therefore it doesn't even try to
>> place the king, which means that it will not find the 63-solution.
>
> A very minor point, but out of interest, have you tried placing the
> knights as the the last two pieces? I suspect you will trim a little
> off your timings, as it is much less likely to attempt the final
> knight's 57-way positioning. The constraint of all eight (nine)
> remaining un-attacked squares being the same colour (bar one) should
> cause far more rejections than the condition of them splitting
> (roughly) half and half for the king.
I did try this, but placing the king last is fastest in my program.
At 170 million positions per second, those 36 million positions in the
inner loop only amounts to about 0.2 seconds, so there is little point
optimizing the inner loop any more.
The major part of the cpu time is spent evaluating the pruning rules
and building up the partial positions. With the N,N,K placement order,
the number of times the program passes the first, second, and third
pruning rule is:
9882165 17709070 635138
With the K,N,N placement order, I instead get:
9882165 81773282 180490
Indeed, the number of positions that make it into the innermost loop
is reduced by a factor of 3.5 However, the number of positions that
make it into the second-to-innermost loop is increased by a factor of
4.6. The runtime for the K,N,N case is also about 5 times larger than
for the N,N,K case.
> What has just this moment occurred to me, as I typed, is that I've
> been stupid. When down to that final knight, I didn't limit it
> properly. Once one has made the B/W test, for the 63-cover, one has
> four cases remaining: 9W, 8W+1B, 1W+8B or 9B.
There could also be one white and one black square left. Then you
would have to try all squares for the final knight. The number of
those cases would probably be very small though, since one of my
previous runs found only 17 positions that attack 62 squares when one
knight is missing.
--
Peter Osterlund - petero2@telia.com
http://web.telia.com/~u89404340
|
| | | | | | | | | |
Date: 09 Oct 2007 17:40:40
From: =?UTF-8?B?wqrCusKqIHJyb2Nr?=
Subject: Re: Source for Eight Officers Problem?
|
Peter Osterlund wrote:
> ªºª rrock <invalid@address.here> writes:
>
>
>>Peter Osterlund wrote:
>>
>>
>>>It takes 8 seconds because the program has to analyze 36202866
>>>positions. All other positions are discarded by the B&B rule and the
>>>symmetry discarding logic. The result is the following incomplete
>>>histogram:
>
> ...
>
>>>This shows (together with a proof that the program, compiler, cpu, etc
>>>is correct) that there is no 64-solution to the problem.
>>>
>>>However, it's still quite far away from a formal proof. Analyzing
>>>those 36 million positions by hand and proving that the other
>>>1416336714894 positions can be safely ignored, would probably take a
>>>human being more than a lifetime.
>>
>>I don't know about that. I don't think your catching my drift, either.
>>The first time anything at all about a histogram or symmetry was mentioned,
>>it was in regards to my questions on what was originally asked for. And
>>during the interim of then and now, a number of people have had a number
>>of different inputs on just what is or isn't worthwhile, what is or isn't
>>symmetry, or even how many cases were actually under "formal" consideration.
>>
>>Your program is *not* by any means a brute force program, rather, it is
>>a tool that is helping you whittle down that larger number, and you and
>>others have made quite a few small discoveries in what, only a week or
>>so? Each of those little rules is a small part of the ultimate formal
>>proof. I don't think you're giving yourself or the group interested in
>>this thread as much credit as you deserve and/or are underestimating the
>>combined capabilities. As a programmer you should be looking at the rules
>>mathematically to discover those small underlying logic clues that lead
>>to bigger revelations. You're not giving up, are you?
>
>
> I haven't given up on making my program faster, but unfortunately I
> don't see much hope in transforming my program into a formal proof
> short enough to be verified by a human without computer help.
>
> One idea I'm planning to test is to first let the program spend some
> time computing more efficient B&B rules, then use those rules to
> further reduce the number of positions it needs to evaluate.
I'm unsure if it would fit, but have you considered using a neural-net?
Myself, i'm headed the opposite direction, since my goal is different.
To remain "pure" to the dog-task, my concentration is on a better
permutations algorithm as well as considering the superset question,
i.e. same question on any sized board with any number of pieces of
any type. The challenge for me is to consider every case completely
within what you would call a "reasonable" amount of time, while still
on a slow box. It may not be possible (since you are such an impatient
fellow.. j/k), but getting it "as good as it can get" by means of
algorithm is my only true goal.
>
>>By the way, completely on a different note, did i miss something earlier
>>or is there a reason 63 has only 109 cases now instead of the 144? If i
>>missed that post, please let me know. I'd hate to find my old dog over
>>here had come up with 109 after a month of waiting, figure i screwed up
>>and... lol delete the files. Was the 144 with or without symmetry? That
>>still wouldn't make sense. Let me know. I understand the histogram is
>>incomplete, but i don't understand how it could not fill in all of the
>>63 coverage states and still be competent enough to say it had checked
>>all of the 64's. If that is correct, and the 144 still hasn't changed,
>>then THERE is a heap of data for checking out regarding another rule.
>>For example, which of the 63's has it forsaken, and WHY? Any pattern?
>>(even a plaid pattern for egg-heads?). Quit worrying about the 36 million
>>positions and pay attention to the 109. Just my two cents.
>
>
> There are indeed 144 solutions, but in some cases the program can
> realize after placing all pieces except the king that there is no
> point placing the king, because it is impossible to attack all 64
> squares. In that case, the program doesn't test all available king
> positions, even though some of those positions might lead to a
> 63-solution.
>
> An example:
>
> ......R.
> .......R
> ........
> .K......
> ..B.....
> ...Q....
> .B....N.
> ...N....
>
> In this position, all squares except g1 are attacked. However, if you
> remove the king, the squares a5, b4, b6, c5 are also unattacked. All
> those five squares are black, and the program knows that a king can
> only attack at most 4 black squares. Therefore it doesn't even try to
> place the king, which means that it will not find the 63-solution.
Yes, this is where we completely part company. My program is "not-allowed"
to know such things and all pieces must be placed before any calculation
is made about attack coverage. Fortunately for you, you haven't got any
X-Ray chess reputation to live down. On the other hand, your problem is
more specific than mine since what i'm after is the permutations of the
attacks (eventually) rather than the pieces. Seems to me that is where
the underlying answer is, anyhow. The permutations of pieces have two types
of "movement", one of which has two sub-types (bishops). The attack
permutations have two types as well, but only the king is a member of
both sets.
|
| | | | | | | | | | |
Date: 10 Oct 2007 05:32:45
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?
|
ªºª rrock <invalid@address.here > writes:
> Peter Osterlund wrote:
>> An example:
>>
>> ......R.
>> .......R
>> ........
>> .K......
>> ..B.....
>> ...Q....
>> .B....N.
>> ...N....
>>
>> In this position, all squares except g1 are attacked. However, if you
>> remove the king, the squares a5, b4, b6, c5 are also unattacked. All
>> those five squares are black, and the program knows that a king can
>> only attack at most 4 black squares. Therefore it doesn't even try to
>> place the king, which means that it will not find the 63-solution.
>
> Yes, this is where we completely part company. My program is "not-allowed"
> to know such things and all pieces must be placed before any calculation
> is made about attack coverage.
My program is can be run in pure brute-force mode too. Just change the
"prune" variable to -1 and recompile. Then you get a program that
analyzes all 1.4e12 positions. At a speed of about 170 million
positions per second, this means that the computation takes about 2
hours and 20 minutes. If you don't want to consider symmetries, you
can remove two lines of source code and get a program that analyzes
all 1.1e13 positions. The run-time for that program would be about 18
hours and 30 minutes.
My program does have some assumptions though. First it assumes that
the board has at most 64 squares. That assumption means that "attack
bitmaps" fit in a single 64-bit integer, which can be handled very
efficiently on a 64-bit computer. Changing that assumption in the code
wouldn't be that hard, but would make the program run slower, if more
than one 64-bit integer is required to hold each "attack bitmap".
The second assumption is that pieces either have X-ray capability or
they don't. An imaginary piece that could attack through one other
piece but not through two, can't be handled by the current attack
bitmap calculation algorithm.
The key idea that makes the program so fast is that it starts by
computing all entries in the following array:
uint64_t attackShadow_[5][64][64];
The entries in that array are computed such that
attackShadow_[piece][square][otherSquare]
contains a bitmap with all squares attacked by "piece" when it is
placed on "square" and there is another piece at "otherSquare" that
potentially blocks the attacks of the first piece.
Using that array, it is possible to compute all attacked squares for
an arrangement of the 8 pieces using about 15 array lookups, 15 "and"
operations and 7 "or" operations.
Counting the number of one bits in a 64-bit integer is done with
another array, so that each array access counts 16 bits.
--
Peter Osterlund - petero2@telia.com
http://web.telia.com/~u89404340
|
| | | | | | | | | | | |
Date: 10 Oct 2007 10:36:29
From: =?UTF-8?B?wqrCusKqIHJyb2Nr?=
Subject: Re: Source for Eight Officers Problem?
|
Peter Osterlund wrote:
> ªºª rrock <invalid@address.here> writes:
>
>
>>Peter Osterlund wrote:
>
>
>>>An example:
>>>
>>> ......R.
>>> .......R
>>> ........
>>> .K......
>>> ..B.....
>>> ...Q....
>>> .B....N.
>>> ...N....
>>>
>>>In this position, all squares except g1 are attacked. However, if you
>>>remove the king, the squares a5, b4, b6, c5 are also unattacked. All
>>>those five squares are black, and the program knows that a king can
>>>only attack at most 4 black squares. Therefore it doesn't even try to
>>>place the king, which means that it will not find the 63-solution.
>>
>>Yes, this is where we completely part company. My program is "not-allowed"
>>to know such things and all pieces must be placed before any calculation
>>is made about attack coverage.
>
>
> My program is can be run in pure brute-force mode too. Just change the
> "prune" variable to -1 and recompile. Then you get a program that
> analyzes all 1.4e12 positions. At a speed of about 170 million
> positions per second, this means that the computation takes about 2
> hours and 20 minutes. If you don't want to consider symmetries, you
> can remove two lines of source code and get a program that analyzes
> all 1.1e13 positions. The run-time for that program would be about 18
> hours and 30 minutes.
What is the clock speed on that box, again?
> My program does have some assumptions though. First it assumes that
> the board has at most 64 squares. That assumption means that "attack
> bitmaps" fit in a single 64-bit integer, which can be handled very
> efficiently on a 64-bit computer. Changing that assumption in the code
> wouldn't be that hard, but would make the program run slower, if more
> than one 64-bit integer is required to hold each "attack bitmap".
So, when you say "at most 64 squares", are you saying that it would run
just fine on a 7x7 board?
> The second assumption is that pieces either have X-ray capability or
> they don't. An imaginary piece that could attack through one other
> piece but not through two, can't be handled by the current attack
> bitmap calculation algorithm.
>
> The key idea that makes the program so fast is that it starts by
> computing all entries in the following array:
>
> uint64_t attackShadow_[5][64][64];
>
> The entries in that array are computed such that
>
> attackShadow_[piece][square][otherSquare]
>
> contains a bitmap with all squares attacked by "piece" when it is
> placed on "square" and there is another piece at "otherSquare" that
> potentially blocks the attacks of the first piece.
>
> Using that array, it is possible to compute all attacked squares for
> an arrangement of the 8 pieces using about 15 array lookups, 15 "and"
> operations and 7 "or" operations.
i do the same, but only for kings and knights, and only a [width][height]
sized array of double-quads since the max board size for my program is
128 squares.
> Counting the number of one bits in a 64-bit integer is done with
> another array, so that each array access counts 16 bits.
do you use x&(x-1)?
|
| | | | | | | | | | | | |
Date: 10 Oct 2007 19:41:47
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?
|
ªºª rrock <invalid@address.here > writes:
> Peter Osterlund wrote:
>>
>> My program is can be run in pure brute-force mode too. Just change the
>> "prune" variable to -1 and recompile. Then you get a program that
>> analyzes all 1.4e12 positions. At a speed of about 170 million
>> positions per second, this means that the computation takes about 2
>> hours and 20 minutes. If you don't want to consider symmetries, you
>> can remove two lines of source code and get a program that analyzes
>> all 1.1e13 positions. The run-time for that program would be about 18
>> hours and 30 minutes.
>
> What is the clock speed on that box, again?
It's an Intel Core 2 Quad machine, running at 2.4GHz. My program uses
all four CPUs, so I guess you could say the effective clock speed is
9.6GHz. I'm also running a 64 bit OS (Linux, Fedora 7), which is
really great for 64-bit aware programs.
As I reported before, a 3.07GHz Intel Pentium 4 machine (not
hyperthreaded) is roughly 8 times slower than the Quad core machine,
when running this program.
>> My program does have some assumptions though. First it assumes that
>> the board has at most 64 squares. That assumption means that "attack
>> bitmaps" fit in a single 64-bit integer, which can be handled very
>> efficiently on a 64-bit computer. Changing that assumption in the code
>> wouldn't be that hard, but would make the program run slower, if more
>> than one 64-bit integer is required to hold each "attack bitmap".
>
> So, when you say "at most 64 squares", are you saying that it would run
> just fine on a 7x7 board?
It would need some small modifications, because "board size 8" is
hardcoded at a couple of places. What I meant was that the program
could quite easily be modifed to handle smaller board sizes and still
be able to process 170 million positions per second.
>> Counting the number of one bits in a 64-bit integer is done with
>> another array, so that each array access counts 16 bits.
>
> do you use x&(x-1)?
I did initially, but the table lookup method was much faster. The code
now looks like this:
inline int
BitBoard::numOneBits() const
{
int cnt = 0;
uint64_t tmp = board_;
for (int i = 0; i < 4; i++) {
cnt += bits_[tmp & 0xffff];
tmp >>= 16;
}
return cnt;
}
As you can see, 16 bits are counted at a time by a single lookup in
the bits_ array. The bits_ array is computed once when the program
starts with the following code:
void
BitBoard::init()
{
for (int i = 0; i < 65536; i++) {
int cnt = 0;
int tmp = i;
while (tmp) {
cnt++;
tmp &= (tmp - 1);
}
bits_[i] = cnt;
}
}
So, as you can see, I'm using the x&(x-1) trick only when initializing
the array.
--
Peter Osterlund - petero2@telia.com
http://web.telia.com/~u89404340
|
| | | | | | | | | | | | | |
Date: 10 Oct 2007 15:36:56
From: =?UTF-8?B?wqrCusKqIHJyb2Nr?=
Subject: Re: Source for Eight Officers Problem?
|
Peter Osterlund wrote:
> ªºª rrock <invalid@address.here> writes:
>
>
>>Peter Osterlund wrote:
>>
>>>My program is can be run in pure brute-force mode too. Just change the
>>>"prune" variable to -1 and recompile. Then you get a program that
>>>analyzes all 1.4e12 positions. At a speed of about 170 million
>>>positions per second, this means that the computation takes about 2
>>>hours and 20 minutes. If you don't want to consider symmetries, you
>>>can remove two lines of source code and get a program that analyzes
>>>all 1.1e13 positions. The run-time for that program would be about 18
>>>hours and 30 minutes.
>>
>>What is the clock speed on that box, again?
>
>
> It's an Intel Core 2 Quad machine, running at 2.4GHz. My program uses
> all four CPUs, so I guess you could say the effective clock speed is
> 9.6GHz. I'm also running a 64 bit OS (Linux, Fedora 7), which is
> really great for 64-bit aware programs.
>
> As I reported before, a 3.07GHz Intel Pentium 4 machine (not
> hyperthreaded) is roughly 8 times slower than the Quad core machine,
> when running this program.
>
>
>>>My program does have some assumptions though. First it assumes that
>>>the board has at most 64 squares. That assumption means that "attack
>>>bitmaps" fit in a single 64-bit integer, which can be handled very
>>>efficiently on a 64-bit computer. Changing that assumption in the code
>>>wouldn't be that hard, but would make the program run slower, if more
>>>than one 64-bit integer is required to hold each "attack bitmap".
>>
>>So, when you say "at most 64 squares", are you saying that it would run
>>just fine on a 7x7 board?
>
> It would need some small modifications, because "board size 8" is
> hardcoded at a couple of places. What I meant was that the program
> could quite easily be modifed to handle smaller board sizes and still
> be able to process 170 million positions per second.
>
So all of your shadow masks are already setup for both odd and even
width boards, and your permutations algorithm already handles the
differences of the positions for the bishops of both odd and even
width boards?
>>>Counting the number of one bits in a 64-bit integer is done with
>>>another array, so that each array access counts 16 bits.
>>
>>do you use x&(x-1)?
>
>
> I did initially, but the table lookup method was much faster. The code
> now looks like this:
>
> inline int
> BitBoard::numOneBits() const
> {
> int cnt = 0;
> uint64_t tmp = board_;
> for (int i = 0; i < 4; i++) {
> cnt += bits_[tmp & 0xffff];
> tmp >>= 16;
> }
> return cnt;
> }
>
> As you can see, 16 bits are counted at a time by a single lookup in
> the bits_ array. The bits_ array is computed once when the program
> starts with the following code:
>
> void
> BitBoard::init()
> {
> for (int i = 0; i < 65536; i++) {
> int cnt = 0;
> int tmp = i;
> while (tmp) {
> cnt++;
> tmp &= (tmp - 1);
> }
> bits_[i] = cnt;
> }
> }
>
> So, as you can see, I'm using the x&(x-1) trick only when initializing
> the array.
lol, so much for the old days of expensive ram. It would take the old '88
four machines just to hold that table. lololol
|
| | | | | | | | | | | | | | |
Date: 10 Oct 2007 21:24:21
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?
|
ªºª rrock <invalid@address.here > writes:
> Peter Osterlund wrote:
>
>> ªºª rrock <invalid@address.here> writes:
>>
>>>So, when you say "at most 64 squares", are you saying that it would run
>>>just fine on a 7x7 board?
>>
>> It would need some small modifications, because "board size 8" is
>> hardcoded at a couple of places. What I meant was that the program
>> could quite easily be modifed to handle smaller board sizes and still
>> be able to process 170 million positions per second.
>
> So all of your shadow masks are already setup for both odd and even
> width boards,
The shadow masks are computed at program start, and all that is
required to make them work with a smaller board is to change the
following function in the obvious way:
inline bool
BitBoard::inRange(int x, int y)
{
return (x >= 0) && (x < 8) && (y >= 0) && (y < 8);
}
> and your permutations algorithm already handles the
> differences of the positions for the bishops of both odd and even
> width boards?
Yes.
>>>>Counting the number of one bits in a 64-bit integer is done with
>>>>another array, so that each array access counts 16 bits.
>>>
>>>do you use x&(x-1)?
...
>> So, as you can see, I'm using the x&(x-1) trick only when initializing
>> the array.
>
> lol, so much for the old days of expensive ram. It would take the old '88
> four machines just to hold that table. lololol
That table is only 64KB though, because bits_ is an array of chars,
not ints. The big array is the attackShadow_ array, which is
5*64*64*8=160KB. And I actually use two attackShadow_ arrays, one
indexed like [piece][square][blockingSquare] and the other indexed
like [piece][blockingSquare][square]. That wastes another 160KB of
memory, but makes the compiler generate better assembly code in the
inner loop. Since all three arrays combined are much smaller than the
L2 cache in the CPU, the extra memory usage isn't a problem.
--
Peter Osterlund - petero2@telia.com
http://web.telia.com/~u89404340
|
| | | | | | | | | | | | | | | |
Date: 10 Oct 2007 18:23:14
From: =?UTF-8?B?wqrCusKqIHJyb2Nr?=
Subject: Re: Source for Eight Officers Problem?
|
Peter Osterlund wrote:
> ªºª rrock <invalid@address.here> writes:
>
>
>>Peter Osterlund wrote:
>>
>>
>>>ªºª rrock <invalid@address.here> writes:
>>>
>>>
>>>>So, when you say "at most 64 squares", are you saying that it would run
>>>>just fine on a 7x7 board?
>>>
>>>It would need some small modifications, because "board size 8" is
>>>hardcoded at a couple of places. What I meant was that the program
>>>could quite easily be modifed to handle smaller board sizes and still
>>>be able to process 170 million positions per second.
>>
>>So all of your shadow masks are already setup for both odd and even
>>width boards,
>
>
> The shadow masks are computed at program start, and all that is
> required to make them work with a smaller board is to change the
> following function in the obvious way:
>
> inline bool
> BitBoard::inRange(int x, int y)
> {
> return (x >= 0) && (x < 8) && (y >= 0) && (y < 8);
> }
ahhh, i see your point. I don't use x or y functions, but instead
use bit widths since there aren't any multiplications.
>
>>and your permutations algorithm already handles the
>>differences of the positions for the bishops of both odd and even
>>width boards?
>
>
> Yes.
>
>
>>>>>Counting the number of one bits in a 64-bit integer is done with
>>>>>another array, so that each array access counts 16 bits.
>>>>
>>>>do you use x&(x-1)?
>
> ...
>
>>>So, as you can see, I'm using the x&(x-1) trick only when initializing
>>>the array.
>>
>>lol, so much for the old days of expensive ram. It would take the old '88
>>four machines just to hold that table. lololol
>
>
> That table is only 64KB though, because bits_ is an array of chars,
> not ints.
okay, 1 machine then. lol. i still think it's funny how in only a few
short years... (well, okay 25 or 30 short years) ... nevermind... lol
seems to me since 256K isn't very much at all these days, you'd might
get a little better performance by making it an array of int rather than
char (if it was aligned to begin with especially).
> The big array is the attackShadow_ array, which is
> 5*64*64*8=160KB. And I actually use two attackShadow_ arrays, one
> indexed like [piece][square][blockingSquare] and the other indexed
> like [piece][blockingSquare][square]. That wastes another 160KB of
> memory, but makes the compiler generate better assembly code in the
> inner loop. Since all three arrays combined are much smaller than the
> L2 cache in the CPU, the extra memory usage isn't a problem.
>
all together it's less than a meg.
|
| | |
Date: 01 Oct 2007 13:12:23
From: Laurence Reeves
Subject: Re: Source for Eight Officers Problem?
|
Proginoskes wrote:
> ... First of all, Laurence Reeves's algorithm is branch-and-bound (which
> he originally called "heuristic"). ...
A minor "point of order". I never called my method "heuristic". I went
to some pains to explain that, to me, a "heuristic" approach would mean
"not guaranteed to find all solutions". It might find 144 solutions, but
could only EVER give that as a lower bound (unless there happened to be
some a priori reason why it was known that there were exactly 144
solutions). I use an algorithm (to find *the* solutions to the problem)
not a heuristic (to maybe find *some* solutions to the problem).
Having never come across the terminology of "branch and bound" before, I
looked it up.
Technically, I'm not sure that my algorithm is that either, as it does
not do any branching. I suppose you can interpret it that way, in that I
progress each time from one specific (branched?) layout of five, six or
seven pieces, and discard (bound) by rejecting further processing of a
partial layout if it is provably not able to produce any solutions to
the problem at hand (i.e. coverings of >= 63 squares).
Another distinction from "branch and bound" might be that my algorithm
is exact and guaranteed to terminate, whereas B&B seems not to imply
that it should go that far.
--
Lau AS! d-(!) a++ c++++ p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++
ASC Decoder at <http://www32.brinkster.com/ascdecode/ >
|
| |
Date: 30 Sep 2007 06:34:34
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?
|
On Sep 29, 2:31 pm, Peter Osterlund <pete...@telia.com > wrote:
> Laurence Reeves <l...@bergbland.info> writes:
> > =AA=BA=AA rrock wrote:
>
> >> Laurence Reeves wrote:
>
> >>> Finally, and this is probably the only option, it would be a huge
> >>> confirmation if, /before/ I publish the results and program,
> >>> someone else were to at least confirm the count, and maybe publish
> >>> what I say is the unique solution where just the one rook remains
> >>> unmolested.
>
> >> Well, if you hang around for another few months... (grin)
>
> > OK. I'm waiting...
>
> You shouldn't have to wait that long.
>
> My brute force program is currently running on a 2.4GHz Intel Core 2
> Quad computer in 64 bit mode at a speed of approximately 120 million
> positions per second. Since I didn't implement any symmetry detection
> at all, the search space size is about 1.13e13, which means that the
> computation should be finished in about 26 hours.
>
> The output will be the histogram data and the "maximum" positions.
> (Actually split up in 32 files because of how I implemented the
> parallel search and checkpointing, but merging should be simple.)
The code Laurence Reeves sent me took two hours (plus or minus 30
seconds) unmodified. I got a couple of basic ideas for speeding up the
process and have started another run. No information on processor
speed at the moment, though. (I got a new computer a few weeks ago.)
--- Christopher Heckman
|
| | |
Date: 30 Sep 2007 07:17:20
From: Peter Osterlund
Subject: Re: Source for Eight Officers Problem?
|
Proginoskes <CCHeckman@gmail.com > writes:
> On Sep 29, 2:31 pm, Peter Osterlund <pete...@telia.com> wrote:
>>
>> My brute force program is currently running on a 2.4GHz Intel Core 2
>> Quad computer in 64 bit mode at a speed of approximately 120 million
>> positions per second. Since I didn't implement any symmetry detection
>> at all, the search space size is about 1.13e13, which means that the
>> computation should be finished in about 26 hours.
>>
>> The output will be the histogram data and the "maximum" positions.
>> (Actually split up in 32 files because of how I implemented the
>> parallel search and checkpointing, but merging should be simple.)
>
> The code Laurence Reeves sent me took two hours (plus or minus 30
> seconds) unmodified. I got a couple of basic ideas for speeding up the
> process and have started another run. No information on processor
> speed at the moment, though. (I got a new computer a few weeks ago.)
I might be wrong, but I thought his program was using branch and
bound, and was therefore not able to produce the histogram data.
Also, if I were to consider symmetries, I think it would be possible
to cut down the run time to about 4 hours by only considering 10
squares for the king. However, that would produce a different
histogram.
--
Peter Osterlund - petero2@telia.com
http://web.telia.com/~u89404340
|
| |
Date: 29 Sep 2007 07:30:12
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?
|
On Sep 28, 2:47 am, =AA=BA=AA rrock <inva...@address.here > wrote:
> Proginoskes wrote:
> > On Sep 27, 8:32 pm, =AA=BA=AA rrock <inva...@address.here> wrote:
>
> >>Proginoskes wrote:
>
> >>>On Sep 27, 2:34 pm, Laurence Reeves <l...@bergbland.info> wrote:
>
> >>>>=AA=BA=AA rrock wrote:
>
> >>>>...> If those aren't heuristics, then what is the proper terminology?
>
> >>>>...
>
> >>>>My use of the term:
>
> >>>>heuristic: an approach in problem solving where some avenues of
> >>>>exploration of the problem are never explored because the solution is
> >>>>not expected to be found there.
>
> >>>If you change "not expected to be" to "cannot be", this method is
> >>>called "branch and bound". This method also seems to have been used in
> >>>your code, based on this comment that you make later on:
>
> >>>>A second aspect is that I do not continue
> >>>>placing pieces when I can simply count that those pieces cannot bring
> >>>>the total under attack up to 63 (even if they did not block any other
> >>>>pieces and each gave rise to a fresh attack on every square they could
> >>>>possibly reach).
>
> >>>[back to the beginning:]
>
> >>>>I seem not to agree with the OED on this one. Their definition are all
> >>>>very vague and full of waffle. Maybe I should complain to them? [...]
>
> >>>A heuristic is an algorithm which solves most but not all instances of
> >>>a problem.
>
> >>>>If there were a 64 coverage solution to the "Eight Officers" problem,=
a
> >>>>heuristic approach that found at least one such solution would be fin=
e=2E
>
> >>>Actually, the final diagram would be the proof itself, regardless of
> >>>where it came from. "Whether discovered by expert, undergraduate, or
> >>>janitor, correct mathematics is correct mathematics." (butchering a
> >>>quote that appeared in a James Harris thread.)
>
> >>>>To prove that no such solution exists is another matter.
>
> >>>>Anyway, my program solves completely both questions "Is there a full
> >>>>coverage solution?", to which the answer is "no" and "How many distin=
ct
> >>>>63 square coverage solutions are there?", being 144. (I think :) )
>
> >>>Depending on how you define "different positions".
>
> >>>>The program finished its second run a while ago, with a little better
> >>>>pruning, and all optimisations turned on (but debug still in place - a
> >>>>mistake). This time it took 278 minutes, so no huge improvement over
> >>>>last night's 350 minutes. The solution list was identical (phew!).
>
> >>>Maybe you should send me your code, so that I can run it on another
> >>>machine. Getting the same result on different machines is one step
> >>>towards "reproducability"; i.e., someone else being able to derive the
> >>>same results you did.
>
> >>A different machine? Or a different architecture?
>
> > Ideally, both. But even running correctly a different machine is
> > enough to suggest that the program works.
>
> Program or algorithm? An algorithm is independent of hardware.
Using the same code will (tend to) rule out the possibility that the
compiler might be wrong. So if there's a fault, it's with the original
code, not the compiler.
Knowing this makes it easier to say that the code produces the answer
it should. Of course, the code (the program) or the algorithm, or
both, could still be faulty. And I didn't say it couldn't be. 8-)
> Good code is portable. Fast code isn't. On a particular architecture,
> running an identical executable on two different boxes won't tell
> you anything about the algorithm at all. At best, it will only
> expose environment issues and programmer "miscalculations" about
> the environment. For example, a program set up with the programmer's
> miscalculation that all people use a mouse. oops!
I'm thinking about coming up with a paper in two phases. In phase 1,
the known information is gathered together in one place, and *an*
algorithm (with the C code) is presented, most likely being posted to
xxx.lanl.gov. The algorithm allows for other people to develop their
own code, even their own algorithm, to verify that the result is true.
I'm also allowing for the possibility that someone will say, "This was
all done in **** (some specific place)", which was the original
intention of this thread. In phase 2, an algorithm with proof of
correctness will be presented, along with all the information related
to the problem, and will show up in something like the Journal of
Recreational Mathematics.
--- Christopher Heckman
|
| | |
Date: 29 Sep 2007 05:43:38
From: =?ISO-8859-1?Q?=AA=BA=AA_rrock?=
Subject: Re: Source for Eight Officers Problem?
|
Proginoskes wrote:
> On Sep 28, 2:47 am, ªºª rrock <inva...@address.here> wrote:
>
>>Proginoskes wrote:
>>
>>>On Sep 27, 8:32 pm, ªºª rrock <inva...@address.here> wrote:
>>
>>>>Proginoskes wrote:
>>
>>>>>On Sep 27, 2:34 pm, Laurence Reeves <l...@bergbland.info> wrote:
>>
>>>>>>ªºª rrock wrote:
>>
>>>>>>...> If those aren't heuristics, then what is the proper terminology?
>>
>>>>>>...
>>
>>>>>>My use of the term:
>>
>>>>>>heuristic: an approach in problem solving where some avenues of
>>>>>>exploration of the problem are never explored because the solution is
>>>>>>not expected to be found there.
>>
>>>>>If you change "not expected to be" to "cannot be", this method is
>>>>>called "branch and bound". This method also seems to have been used in
>>>>>your code, based on this comment that you make later on:
>>
>>>>>>A second aspect is that I do not continue
>>>>>>placing pieces when I can simply count that those pieces cannot bring
>>>>>>the total under attack up to 63 (even if they did not block any other
>>>>>>pieces and each gave rise to a fresh attack on every square they could
>>>>>>possibly reach).
>>
>>>>>[back to the beginning:]
>>
>>>>>>I seem not to agree with the OED on this one. Their definition are all
>>>>>>very vague and full of waffle. Maybe I should complain to them? [...]
>>
>>>>>A heuristic is an algorithm which solves most but not all instances of
>>>>>a problem.
>>
>>>>>>If there were a 64 coverage solution to the "Eight Officers" problem, a
>>>>>>heuristic approach that found at least one such solution would be fine.
>>
>>>>>Actually, the final diagram would be the proof itself, regardless of
>>>>>where it came from. "Whether discovered by expert, undergraduate, or
>>>>>janitor, correct mathematics is correct mathematics." (butchering a
>>>>>quote that appeared in a James Harris thread.)
>>
>>>>>>To prove that no such solution exists is another matter.
>>
>>>>>>Anyway, my program solves completely both questions "Is there a full
>>>>>>coverage solution?", to which the answer is "no" and "How many distinct
>>>>>>63 square coverage solutions are there?", being 144. (I think :) )
>>
>>>>>Depending on how you define "different positions".
>>
>>>>>>The program finished its second run a while ago, with a little better
>>>>>>pruning, and all optimisations turned on (but debug still in place - a
>>>>>>mistake). This time it took 278 minutes, so no huge improvement over
>>>>>>last night's 350 minutes. The solution list was identical (phew!).
>>
>>>>>Maybe you should send me your code, so that I can run it on another
>>>>>machine. Getting the same result on different machines is one step
>>>>>towards "reproducability"; i.e., someone else being able to derive the
>>>>>same results you did.
>>
>>>>A different machine? Or a different architecture?
>>
>>>Ideally, both. But even running correctly a different machine is
>>>enough to suggest that the program works.
>>
>>Program or algorithm? An algorithm is independent of hardware.
>
>
> Using the same code will (tend to) rule out the possibility that the
> compiler might be wrong. So if there's a fault, it's with the original
> code, not the compiler.
>
> Knowing this makes it easier to say that the code produces the answer
> it should. Of course, the code (the program) or the algorithm, or
> both, could still be faulty. And I didn't say it couldn't be. 8-)
>
>
>>Good code is portable. Fast code isn't. On a particular architecture,
>>running an identical executable on two different boxes won't tell
>>you anything about the algorithm at all. At best, it will only
>>expose environment issues and programmer "miscalculations" about
>>the environment. For example, a program set up with the programmer's
>>miscalculation that all people use a mouse. oops!
>
>
> I'm thinking about coming up with a paper in two phases. In phase 1,
> the known information is gathered together in one place, and *an*
> algorithm (with the C code) is presented, most likely being posted to
> xxx.lanl.gov. The algorithm allows for other people to develop their
> own code, even their own algorithm, to verify that the result is true.
> I'm also allowing for the possibility that someone will say, "This was
> all done in **** (some specific place)", which was the original
> intention of this thread. In phase 2, an algorithm with proof of
> correctness will be presented, along with all the information related
> to the problem, and will show up in something like the Journal of
> Recreational Mathematics.
>
> --- Christopher Heckman
I doubt you'll want my algorithm, then, because it is very, very simple,
doesn't consider relflection or symmetry, and i'm even considering at
the moment with doing away entirely with redundancy as well.
|
| |
Date: 29 Sep 2007 07:21:49
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?
|
On Sep 28, 10:39 am, =AA=BA=AA rrock <inva...@address.here > wrote:
> Laurence Reeves wrote:
> > =AA=BA=AA rrock wrote:
> [procedure to count the total number of ways to place the eight officers]
The big problem here is the bishops. If you place some pieces, then
the bishops, then you have to worry not only about how many squares
are left, but also how many *of each color*. Thus it is a whole lot
easier to place the bishops first (32*32), then the rest of the pieces
(C(62,2)*C(60,2)*58*57). (Here, as throughout the thread, C(n,r) is
the binomial coefficient "n choose r", equal to n!/((n-r)! r!).) This
gives you a total of 11,330,983,342,080, where symmetry is not
accounted for. (Earlier, I had 59*58 in my formula, which is slightly
wrong.)
If you are allowing bishops on the same color, then the answer is
C(64,2)*C(62,2)*C(60,2)*58*57 =3D 22,307,873,454,720.
--- Christopher Heckman
|
| | |
Date: 29 Sep 2007 05:39:43
From: =?ISO-8859-1?Q?=AA=BA=AA_rrock?=
Subject: Re: Source for Eight Officers Problem?
|
Proginoskes wrote:
> On Sep 28, 10:39 am, ªºª rrock <inva...@address.here> wrote:
>
>>Laurence Reeves wrote:
>>
>>>ªºª rrock wrote:
>>
>>[procedure to count the total number of ways to place the eight officers]
>
>
> The big problem here is the bishops. If you place some pieces, then
> the bishops, then you have to worry not only about how many squares
> are left, but also how many *of each color*. Thus it is a whole lot
> easier to place the bishops first (32*32), then the rest of the pieces
> (C(62,2)*C(60,2)*58*57). (Here, as throughout the thread, C(n,r) is
> the binomial coefficient "n choose r", equal to n!/((n-r)! r!).) This
> gives you a total of 11,330,983,342,080, where symmetry is not
> accounted for. (Earlier, I had 59*58 in my formula, which is slightly
> wrong.)
>
> If you are allowing bishops on the same color, then the answer is
> C(64,2)*C(62,2)*C(60,2)*58*57 = 22,307,873,454,720.
>
> --- Christopher Heckman
>
The reason for trying to figure this out, beyond knowing if the tabulation
of the histogram is correct, is to pre-determine the amount of time that
particular algorithms i am working on will take for completion.
The current and fastest so far, is using a 46-bit number to represent the
entire board. in this fashion, each bishop has only 5 bits to represent it,
and is therefore on a "bishop relative" position of 0 to 31. In the number
of the board itself, the two bishops will necessarily have many instances
where they are the same digit (0..31) which is where the "bishop relative"
comes in to play. Each of the other pieces uses a number between 0 and 63.
The total number of possible states, then, legal, or illegal, is actually
what my newer version "considers" partially. As the number is incremented,
there will be both legal and illegal cases such as two pieces occupying the
same square. After legality is determined, the program will loop back and
increment to the next state if there is an illegal case. The total number
of partial considerations then, is from the first "legal" setup number,
to the final "legal" setup number:
FIRST_LEGAL_BOARD 0x000420C41463 = 17729590371
FINAL_LEGAL_BOARD 0x3FFBDF3BEB9C = 70351014587292
The difference is 70,333,284,996,921 so 70,333,284,996,922 cases total.
My previous version used a counting method that would force the positions
of the knights and rooks such that they met the 64*(63/2) idea, in that
the position of one knight (for example) would be forced always greater
than its mate.
I am considering doing away with those checks, though, because of the
branching involved. How exactly is it determined then INCLUDING the
redundant cases, but such that only the legal cases are considered?
|
| |
Date: 28 Sep 2007 08:54:54
From: Proginoskes
Subject: Re: Source for Eight Officers Problem?
|
On Sep 27, 8:32 pm, =AA=BA=AA rrock <inva...@address.here > wrote:
> Proginoskes wrote:
> > On Sep 27, 2:34 pm, Laurence Reeves <l...@bergbland.info> wrote:
>
> >>=AA=BA=AA rrock wrote:
>
> >>...> If those aren't heuristics, then what is the proper terminology?
>
> >>...
>
> >>My use of the term:
>
> >>heuristic: an approach in problem solving where some avenues of
> >>exploration of the problem are never explored because the solution is
> >>not expected to be found there.
>
> > If you change "not expected to be" to "cannot be", this method is
> > called "branch and bound". This method also seems to have been used in
> > your code, based on this comment that you make later on:
>
> >>A second aspect is that I do not continue
> >>placing pieces when I can simply count that those pieces cannot bring
> >>the total under attack up to 63 (even if they did not block any other
> >>pieces and each gave rise to a fresh attack on every square they could
> >>possibly reach).
>
> > [back to the beginning:]
>
> >>I seem not to agree with the OED on this one. Their definition are all
> >>very vague and full of waffle. Maybe I should complain to them? [...]
>
> > A heuristic is an algorithm which solves most but not all instances of
> > a problem.
>
> >>If there were a 64 coverage solution to the "Eight Officers" problem, a
> & |
|
