[Retros] At home proof games in 7.0 moves

[Francois Labelle]

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