[Retros] Massacre SPGs

[Francois Labelle]

Andrew Buchanan wrote:


> (1) In the x=5 case, it looks as if you could well exceed the 6 billion

> position limit that you mentioned yesterday around before ply 25 where

> the number of positions might peak, since you are at 300 million already

> at ply 16.


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.


> But suppose you exceed 6 billion at ply n. Can't you just divide your

> ply n-1 data into k batches, and process each batch separately? Then you

> can just add together the data for the surviving positions when you the

> number of positions starts to thin out again.


Yes. Actually I said "about" 6 billion not really because I don't know the
exact limit, but because the limit is itself fuzzy. I knew that with some
extra effort I could push the limit a bit. The 6 billion figure already
assumes some tricks would be used.

Your suggestion is a sensible one. It's a way to trade "space" for "time".
Basically you'd be using less disk space at the expense of not detecting
every transposition during those specially-treated plies. The same
positions will be processed a few times, which will take longer.

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.


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


> (2) I make it that there are 3440 [revised to 3612] (1+1) positions. You

> have tested 92 so far.


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.


> Does anyone have any intuition as to whether the property of being an

> SPG becomes more or less likely as x increases for the next few values?

> Presumably these correspond to positions where the kings are

> progressively further from their start squares.


Ironically there is no SPG with the kings on their home squares yet (no
wKe1, bKe8 for x=3,4).


> (3) From a DR perspective, I'm interested in *any* position you have

> encountered in this quest (not necessarily a (1+1)) in which the number

> of solutions is 1, but without A1.3 is greater than 1.


I didn't find any such example yet.


> (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? No they had
multiple solutions.


> Have you any dead SPG positions identified so far?


I can't afford to check for dead positions along the way, it would take 5
times longer than 25 days. I'm just going to check toward the end of the
quest. Let me repeat that "efficient dead position detection" is still an
open problem for me!


> (5) From an "At Home" perspective, Thierry le Gleuher & myself are

> interested in the most depopulated "At Home" SPG. Thierry has a

> published but C- position with only 7 units at x=6.


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?

	Francois