[Retros] Re: Massacre SPGs

[Andrew]

Francois Labelle writes:


> Andrew Buchanan wrote:

>> x=5 > 6x10^9 around ply 25.

> 

> At the bottom of my webpage I added a heuristic "graph alignment" 

> argument to show why I think that the peak will be around 3 billion 

> positions.


Interesting. Well, we'll see. The figures of 300 & 90 are presumably just 
fudge factors. How do they relate to the factor of 50 times the number of 
operations you estimate for x=6? 


> I would gladly trade space for time if time wasn't also an issue: 

> 

> x=3 took 1.51 min

> x=4 took 5.03 hours

> My estimate for x=5 is 25 days.


If you have the space, you would presumably always want to use it to the 
max. My only point was that if space runs out, you can take advantage of the 
fact that the problem is basically decomposable. How do you see the time 
increasing as you increase the number of batches? 


>> The number of batches for x=5 is probably not unwieldy, although it

>> might become so at x=6.

> 

> The main problem with x=6 is simply the gigantic number of operations you

> have to perform to get the answer, something like 50 times more than x=5.

> It takes a decade for computer performance to increase by that factor. It

> might not be a coincidence that x=4 was computed in 1994, and x=5 is

> attempted in 2004. I think that x=6 is a something to be tried in 2014.


Or maybe this could be distributed across many computers. However there 
would be a lot of work involved to set that up. 

How confident are you in the estimate 50 for x=6/x=5? 


> Just a small note to say that I'm counting PGs, not SPGs, because I think

> that it's interesting to publish what happens to the number of solutions

> when you allow more plies than necessary. The two "ply 33, x=3" diagrams

> reappear in "ply 34, x=4", so really there are 90 positions so far.


Then I suppose strictly there are 4x3612 cases to check. If a diagram has
solutions in ply n, then it certainly is not a PG in ply n+4. However in
principle it might be for plys n+1, n+2 & n+3, although this is unlikely. 


>> (4) Thanks for the 4 dead positions you showed. They are fun: please

>> keep tracking them. Were the 4 that you exhibited SPGs?

> Do you mean whether they were SPGs with unique solutions? 


Yes. There is this ambiguity running through the whole subject. But 
basically it's nothing different from what happens in orthodox chess 
problems. A mate in 2 (#2) contains a unique mate in 2 (solution). But 
somehow people  don't get confused very much about this. In exactly the same 
way, a shortest proof game (SPG) contains a unique shortest proof game 
(solution). The abbreviated terms (#2 & SPG) only refer to the composition 
as a whole, not to solutions contained therein. 


>Let me repeat that "efficient dead position detection" is still an

>open problem for me!


One way forward is to look at the endgame database, and verify the likely
hypothesis that for positions with > 7 units, the only dead positions are
those where there is a forced exchange of pieces resulting in pat or
insufficient material for mate. 

This would also confirm my belief that the smallest position with death by 
blocking has 7 units. 


> Ironically there is no SPG with the kings on their home squares yet (no

> wKe1, bKe8 for x=3,4).


I am confused by this, since it doesn't seem to square with what you
write later... 


> Here are the potentially interesting SPGs with a unique solution I have

> found for x=3,4 (so all these SPGs would have the additional label

> "massacre"): 

> 

> x=3:

> - at home in 11.5 (7+5)

> - at home in 11.5 (6+6)

> - at home in 13.5 (5+3)

> - checkmate in 13.5 (4+4) [many more exist < 13.5] 

> 

> x=4:

> - [about 800 at homes in 4.0..14.0]

> - at home in 14.5 [6 of them]

> - at home in 15.0 (2+4)

> - checkmate in 15.5 (4+1) [tons of them < 15.5]

> - checkmate in 15.5 (3+2)

> - stalemate in 15.5 (4+1)

> - vertical symmetry with KQ equivalent in 15.0 (4+2)

> - [lots with horizontal symmetry + color flip, 1.0..16.0, all even plies]

> - [about 50 with 180-deg symm. + color flip, 7.0..15.0, even & odd plies]

> - dead position in 16.0 (2+2), (1 ply before a KKN ending). 

> 

> I need some advice here. Should I attempt to get some of these problems

> officially published instead of giving them away "for free" on the 

> mailing list? If I post a problem on the mailing list, does it make it 

> unsuitable for publication later on? I don't really know what makes a 

> good problem. I assume that it should be "fun" to solve. For the 

> problems with few pieces left, maybe they are too hard and feel 

> too "computer-like" for a chess problem publication.


I think the best way forward for this work is to publish an article
in a chess problem magazine, and also a more CSish article in some journal
which accepts popular subject matter. 

Different chess problem magazines have different attitudes on whether 
problems have appeared on the internet before they appear in the magazine, 
but if you want to go for gold (world chess composition championships, or 
the FIDE album) then I think it would be better not to publish these 
compositions on the internet first. 

I guess the CS journal would not care whether the chess problems had 
appeared anywhere before. 

Some/many chess problem solvers, myself included, don't really enjoy solving 
these kinds of problems, but I do enjoy marvelling that these positions 
exist. That's why I think an article in a magazine which gives some of the 
background to the work is better than just submitting the problems to a 
magazine. 

However, that's just my own opinion.
Cheers,
Andrew.