[Retros] At home proof games in 7.0 moves
Francois Labelle
flab at EECS.Berkeley.EDU
Tue Feb 8 04:46:55 EST 2005
Juha Saukkola wrote:
> The idea "number of solutions" in n moves came again.
> What is the smallest m, that there are no position of m solutions in
> spg's.
This question is so hard we might never get an answer. So I'm afraid there
hasn't been much progress since last year when you asked the same
question. :)
You ask for SPGs, but we can also ask the question for PGs.
For SPGs it's clear that the number exists, because there is only a finite
number of legal diagrams, and each can only be shortest for one length
stipulation.
For PGs it's harder to prove that the number exists, because there is an
infinite number of diagram+length combinations, but the number does exist.
My proof is as follows: Note that if a diagram has n solutions in p plies,
then it has at least 16*n solutions in p+4 plies, because one can do an
initial knight dance. So each diagram can contribute at most 4 PGs with a
number of solutions between n and 16*n-1, for arbitrary n. For n large
enough, the number of integers between n and 16*n-1 exceeds 4 times the
number of legal diagrams, and therefore an integer will be missing in that
interval.
Last year I mentioned that 3413 was the smallest m that cannot be obtained
by a PG in 4.0 moves or less.
http://www.pairlist.net/pipermail/retros/2004-January/000623.html
For at-home PGs in 7.0 moves or less:
first missing = 2375
maximum = 366347697
achieved by rnbqkbnr/ppp1pppp/8/8/8/8/PPPP1PPP/RNBQKBNR in 7.0 moves
For at-home SPGs in 7.0 moves or less:
first missing = 1306
maximum = 365966
achieved by rnbqkbnr/1ppppppp/8/8/8/8/PPPP1P1P/RNBQKBNR in 7.0 moves
> What's the number of 1-solution "correct" spg's in x moves?
> Any calculations?
For PGs, this is known up to ply 8:
http://www.research.att.com/projects/OEIS?Anum=A090051
Ply 9 is within reach and I plan to compute it someday. I haven't counted
SPGs, but could. The numbers should be similar.
Francois
More information about the Retros
mailing list