[Retros] At-home initial array challenge

Francois Labelle flab at EECS.Berkeley.EDU
Thu Mar 24 15:57:21 EST 2005

Mario Richter wrote:

> The missing black piece is the pawn d7.

Good! Naturally, this was the most likely pawn. But here are some slightly
cooked PGs with the rook pawns:

1.e3 a6 2.Bxa6 Rxa6 3.a3 Rxa3 4.Qe2 Rxe3 5.Na3 Rxa3 6.Qa6 Rxa1 7.Qa8 Rxa8
1.g4 h5 2.Bg2 hxg4 3.Bf3 gxf3 4.h3 fxe2 5.Qxe2 Rxh3 6.Qh5 Rxh1 7.Qh8 Rxh8

In fact, the number of attainable diagrams in each case:

rnbqkbnr/1ppppppp (14 diagrams)
rnbqkbnr/p1pppppp (2 diagrams)
rnbqkbnr/ppp1pppp (128 diagrams)
rnbqkbnr/pppp1ppp (28 diagrams)
rnbqkbnr/ppppppp1 (15 diagrams)

> I find it interesting that only one SPG for the (10+15)-case exists.

Yes, especially considering that in the (15+10) case there are 16 PGs in
7.0 moves, and even 4 in 6.5 moves.

> I simply tried to save some seconds by not even trying to solve those

> positions at ply N, which definitively cannot have a solution at ply N

> (e.g. too much missing pieces.

Well, I claim that it is the job of the solving program to decide this.

> Or use your favourite proof game solving program to check the following

> problem: rnbqkbnr/pppppppp/8/8/8/8/PPPP1PPP/RNB1KBNR, PG in 9.0 - how

> long do you have to wait to get the answer "No solution"?).

The solving programs are taking a lot of time on your example. But this
only shows that these programs aren't perfect, and that they could be
improved by adding the initial tests that you're suggesting.

> Yes, but while my algorithm requires a constant amount of memory

> independent of ply count, the memory requirements of your algorithm seem

> to increase with the number of plies

Not necessarily. In my at-home calculation I started from my ply08 file (a
file containing every position after 8 plies with transpositions merged)
and for each position I just played 6 more plies. Normally to go further
it is preferable to start from a (bigger) file at a higher ply count, but
I can always start from the same ply08 file. Doing this, the memory
requirement stays the same.

For long PGs like massacres, detecting transpositions at each step is more
important and the computation would be very slow without enough disk
space, although in theory it would work.

Anyway, my technique isn't provably better, I can think of cases where
it's worse. It's just that in the at-home enumeration case I get the
impression that it's faster, at least for the plies that are realistic to

> I didn't try to construct - let alone "compose" - anything. So I think

> the attribute "dirty" isn't really justified here.

Well then the attribute doesn't apply to what you're doing, but it can
apply to other situations. For example, after anyone here is done
composing a proof game, isn't it tempting to remove a piece or another and
fire a solver to see if by luck there is a twin? Once in a while you could
find something, and the odds should be reasonable for short PGs. The
search could be automated to try all twinning possibilities. This is what
I call "dirty composing". I'm not saying that it is wrong, just dirty.

Finally, Mario, did you find the bug with the 2005-solution at-home
problem? I want to encourage your work on your chess composing engine,
we're so few people doing this. And feel free to do things differently
than I do, that's how discoveries are made.

Andrew Buchanan wrote:

> I have found a longer White-pristine at-home position (C+) which is now

> published as H0006 at http://www.problemonline.com/. I conjecture that

> it is the longest such. (Feel free to refute.)

Nice problem! (and nice timing!)

> So how far have you explored pristine at-home positions? I don't want to

> stumble away searching for butterflies in regions of the rain-forest

> that you have already bull-dozed. :-)

So far I only looked at the <= 7.0 moves at-home problems that I already
have, but now that you have drawn my attention to this part of the
rain-forest, I adapted my bulldozer to the terrain. :)

With it I can reproduce my 6.0-move PG in 5 minutes. It seems that I could
explore the range 7.5-8.5 moves in maybe a week.

However I note that in the known examples, the pristine camp makes a
massacre, with 2 or 3 non-captures. Adding massacre as a constraint makes
the program much faster. Here is everything with x<=2 up to 8.0 moves:

1n2kb1r/1ppp1ppp/8/8/8/8/PPPPPPPP/RNBQKBNR in 7.5
rn2k2r/1ppp1ppp/8/8/8/8/PPPPPPPP/RNBQKBNR in 7.5 (similar to previous)
rnbqkbnr/pppppppp/8/8/8/8/1PPP1PPP/1N2K1NR in 8.0 (R127, Andrew Buchanan)
rnbqkbnr/pppppppp/8/8/8/8/P4P1P/RN1QKBNR in 8.0

Probably I can push this farther with more computer time.

There are other ways to attack the problem too. For example, Mario's
technique might work well on this as there are only 2^16 diagrams to try.


More information about the Retros mailing list