[Retros] At Home SPGs, and more

[Francois Labelle]

(1) INTEGER SEQUENCES

First, I'd like to announce that the "On-Line Encyclopedia of Integer
Sequences" now contains its first sequence directly related to retro
problems!

The number of dual-free proof games in n plies.
http://www.research.att.com/projects/OEIS?Anum=A090051

I imagine that the true problemists among you will want to print those
numbers on a big banner and worship them every night. Here are some other
sequences of interest:

distinct chess diagrams
http://www.research.att.com/projects/OEIS?Anum=A019319

chess games
http://www.research.att.com/projects/OEIS?Anum=A048987

chess games that end in checkmate
http://www.research.att.com/projects/OEIS?Anum=A079485


These sequences (and more) can be viewed in table form on my webpages:
http://www.cs.berkeley.edu/~flab/chess/statistics-positions.html
http://www.cs.berkeley.edu/~flab/chess/statistics-games.html

And in graph form on my main chess page:
http://www.cs.berkeley.edu/~flab/chess/chess.html


(2) AT-HOME SPGs

Andrew wrote:


> With double solutions, the idea is to get 2 sets of moves which are as

> independent as possible. In the one that appears on the webpage, it is a

> definite flaw that the two solutions share the first move. How do your

> 12 SPGs compare from this perspective?


I don't know: my program doesn't give me the solutions, and I'm not very
good at solving SPGs! So please find the two solutions by hand (it should
be fun) and check if they're independent enough.


> I imagine there may be hundreds. It might be nice to have a file, to

> trawl through to see if there are any particularly interesting ones.


Ok, I've put the at-home diagrams with 1 or 2 solutions up to ply 9 on my
"chess positions" webpage (just click on the numbers in the table). As
always ply 10 is taking much longer and will be ready January 30. I don't
think that it'll be worth a post on the mailing list unless I find
something special like a non-shortest proof game, so go check on the
website in a week. With more programming I could make the search much
faster and possibly deeper, but I don't have time.

BTW, if you (or someone else) find a really good problem on my lists (i.e.
something publishable), I think that it would be reasonable to have both
our names associated with it. I'm supplying a list of possibilities, and
you're finding the needle in the haystack.

When the at-home search will be complete I'll start the mirror-symmetric
positions and the checkmates up to ply 10. Each will take between 1 and 2
weeks, which gives you plenty of time to inspect each group carefully.


(3) SPEEDING-UP PROOF GAME ENGINES?

Andrew wrote:


> There are existing search engines which will determine the legitimate

> proof games to reach a given diagram. At what point might it become more

> efficient for an engine not to begin with the initial game array, but

> with e.g. a database of 12 ply positions, filtering out those which

> clearly (due to captures and pawns moves) cannot lead to the goal

> position?


First, do you realize the sheer size of a 12-ply position database? My
list of ply 8 positions contains nearly a billion positions and takes 27
GB of disk space, and this is using a very tight Huffman encoding of each
position. This is why I stop at ply 8! Each additional ply requires about
10 times more space, so for ply 12 we're taking about 270 terabytes!

Engines like Natch work fast because they can eliminate whole subtrees in
one step. You'd have to use amazingly complicated database filtering to
obtain the same cut-off effect. The only gain that I can see is having the
transpositions already detected.

Noam Elkies wrote:


> Note that this approach, even if more efficient than the algorithm of

> (say) Natch, would serve only to solve sound proof games, but not to

> test for cooks


I assume that you're talking about using a database of *uniquely
realizable* positions, using the fact that every sub-proof-game of a
dual-free proof game must be dual-free. The point being that this database
is already 81 times smaller at ply 8 and doesn't grow as fast with
additional plies. As you pointed out, this would only guarantee a solution
if the proof game is sound, and finding exactly one solution would not
prove that there aren't more. So this short-cut doesn't work too well and
one must use the full database of positions instead.


(4) ABOUT MY PAGE ON CHESS POSITIONS

Andrew wrote:


> "Position" is used in varying ways by problemists, but for your purposes

> you need to pin it down. I suggest you just state the Laws definition,

> and use that. In a way, problemists have no right to redefine that term,

> since it's in the Laws. Yet we do.


Actually it's the other way around. I use the definition I use for
computer science reasons. It's a happy turn of events that the Laws use
the same definition in the "draw by repetition" rule, but if the Laws
didn't I couldn't care less, I would still use the definition that makes
sense for the analyses I want done.


> Actually, your definition of position is exactly that specified in the

> "draw by repetition rule". Think about it: if "position" included

> details of every move, it could never be repeated!


Yes I know that! The point is that I would need this alternative
definition to do my analyses. I'm not claiming it should be used in the
Laws. I'll add "for my purposes" to my page to clarify a little.


> Generally speaking, chess problemists prefer the pieces to do the

> talking, rather than add extraneous words to a problem.


Note that extraneous words wouldn't be needed if a graphical
representation existed. I can perfectly imagine an alternate universe
where in every chess publication rooks have a circle around them when
castling is available, and en passant squares contain a dashed pawn.
Problems asking to deduce castling or e.p. simply wouldn't exist.


> Neither "position" nor "diagram" has a standard definition for

> problemists, so it's too strong to say as you did: 'Diagrams are

> preferred by the chess problems community, and for these people

> "position" will always mean "diagram".'


Ok, I've replaced that sentence with a paragraph with a better
explanation.


> All your statistics can perfectly well be presented at the level of

> positions. As you point out, that's the canonical representation, at

> which recursion operates. It's just when you come to present composed

> proof games "Francois+computer" that it's perhaps more aesthetic to

> collapse the positions into diagrams.


Exactly. And in a sense it is fortunate that my first proof game had the
aesthetic problem that you pointed out, because otherwise I might have
never bothered about "diagrams", which I now view as equally interesting
as "positions".

Thank you Andrew for all your comments and chess problem suggestions up to
now, they are having a significant (positive!) impact on my webpage.

	Francois