# [Retros] Re: Happy New Year!

Noam Elkies elkies at math.harvard.edu
Fri Jan 23 14:10:54 EST 2004

Andrew writes:

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

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, nor to guess the composer's intention unless
the position at ply 12 happens (or was already checked) to be among
those with a unique solution. By the way, here we sometimes *would* need
to distinguish identical ply-12 diagrams with different castling states.

> The most surprising part of your email:

>> The lowest n without a diagram for ply <= 8 is n=3413.

> [...]

It's consistent with my guess, in reply to Juha Saukkola's query

|> What's the position (in shortest number of moves) with 2004 sols?

|> Or with n?

|> What's the lowest number n without that kind of position?

, that

| I suspect that in general

| 1) This function of n is quite unpredictable,

| 2) The minimal position(s) are too "accidental" to be constructed

| directly from n (as I constructed the above case with n=2004),

| 3) The minimal unreachable n is quite large,

| 4) The methods used by Francois Labelle

| can answer this question for impressively large values of n.

> I think there is a moral not just for composers of chess problems

> but also for engineers. [...]

It seems that drug companies are now using such exhaustive techniques
to search for effective drugs ("combinatorial drug design"), and indeed
Nature itself uses some version of this method both in our immune system
and in the viruses/bacteria/... that try to overwhelm it.

> The constrast between Noam's highly ingenious 2004

> and "Nature's" effortless retort is remarkable.

I note a further difference: they are not quite in the same genre.
I expect that Francois' methods easily apply also to one-sided proof games
-- either with no Black pieces on the board or to White series starting
at the orthodox 16+16 array -- and that in either case similar behavior
will be seen; but so far his data pertain only to two-sided proof games
(a.k.a. "helpgames").

NDE