[Retros] At-home initial array challenge

[Francois Labelle]

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


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

 	Francois