# [Retros] At home proof games in 7.0 moves

Mario Richter mri_two at t-online.de
Wed Feb 9 07:42:39 EST 2005

Hello,

Andrew wrote:

>

> It's all about finding questions at the right level of difficulty. How

> hard is the following one to answer?

>

> Which of the billion-odd at-home positions are (S)PGs?

This question is slightly harder to answer than a question

Which of the billion-odd at-home positions are SPGs with at most
8 plies?

I used the following algorithm to find the answer for the latter
question:

##############################################
# Initialisation

UNSOLVED = {empty set};
UNIQUE = {empty set};
COOKED = {empty set};

PLY_LIMIT = 9

NoP = 0; # Number of Plies

while ( NoP < PLY_LIMIT)
{
UNSOLVED += {Set of all At-Home-positions, which are theoretically
solveable
in NoP plies, but not in (NoP-1) plies}

foreach POS in UNSOLVED
{
number_of_solutions = solve (POS)

if ( number_of_solutions == 1)
{
- save PGN of the unique solution
- move POS from UNSOLVED to UNIQUE
}
elsif ( number_of_solutions > 1)
{
- move POS from UNSOLVED to COOKED
}
}

NoP = NoP + 1;

} # end of while

##############################################

Using this approach, the question about At-Home-SPGs in 8 or less plies
could be answered within some minutes.

Raising the PLY_LIMIT to an appropriate value, the question of how many
At-Home-SPGs (with a unique solution) there exist in total, could be
as well. (Probably in less than 1000 years, if each At-Home-Position can
be processed in less than 30s).

So it was interesting for me to compare this (backward) approach with
Francois Labelle's forward approach:

Francois> It took 50 days and 40 GB of temporary disk space on a
Francois> 800 MHz machine, but I don't claim that it *needed* that much.

(Sorry for my bad english - the info how long *it took* your program
to find the results was exactly what I wanted to know.)

I have the impression that the "backward" approach might be more
What do you think?

One last question to Francois:

Francois> ... This reminds me...
Francois>
Francois> Happy New Year at home! (a bit late)
Francois> rnbqkbn1/pppp2pp/8/8/8/8/PPP1PPPP/R1BQKBNR
Francois> SPG in 7.0 moves, how many solutions?

I tried to test it with my own program, but I get a number (2801) which
has nothing to do with New Year.
So clearly enough a bug has shown up in my program.
But before I start debugging it would be nice if you could confirm
that the position and the move number as given are correct (and that
the expected outcome should be something like 2005).

thanks,

mario