[r-t] Exhausted search spaces

[Don Morrison]

On Wed, Feb 3, 2010 at 3:31 PM, Don Morrison <dfm at ringing.org> wrote:
> This correspondence has made me think that when next I'm working on
> something, sometime in the next few days undoubtedly, I should keep a
> bit more statistical information about what I've done and so on. I
> suspect such will illuminate this a bit more.

Since I promised, here it is. Though I don't think that it's really all
that interesting. Perhaps the most interesting thing about it is how
otherwise uninteresting it is.

Between bouts of snow shoveling this afternoon, and attending to
neighbors who've been without power getting warm in our more fortunate
house, I've been working on a composition of Viking Delight Royal.
Here's where I ended up on this one (I will undoubtedly produce a few
more in other styles before I put them onto my web site, and reply to
the conductor that commissioned them for an attempt next month).

I finally ended up searching for compositions of Viking that

a) are round blocks of length 5040

b) use ordinary fourth place bobs and singles

c) are constructed from pieces of tenors together courses, with the
addition of the blocks below

d) contain three instances of the block B,V,F,B, one interpolated into
the 24365 course, one the 65432 course and one the 64523 course.

e) start with the full plain course

f) contain all 24 56s

g) contain at least 12 65s

h) contain at least 30 each 23456s and 65432s

i) and contain at least 350 runs of four or more consecutive bells,
ascending or descending, either at the back or at the front.

This search required 13.05 seconds to actually search the graph I
generated, though probably longer than that just setting up the graph
to be searched and doing other pre-search optimizations. It visited
12.09 million nodes, and resulted in 6 distinct solutions. I picked
what I thought the tidiest and otherwise best of those six by hand.
The 13.05 seconds includes IO time, which was unbuffered, and spit
straight out to a terminal, not written to a disk file.

I don't intend to add the preceding to the wiki. Between the grab bag
full of constraints, and it being a rarely rung method, it doesn't
seem something that would be of interest.

The end result was

    5,040 Viking Delight Royal
     23456   M  W  H
     _______________
     42356         -
     52364   s  s
    (64523)  2  -  a
     34256   -  2  -
     54263   s  s
    (24365)  -     a
     53462   -     -
    (65432)     -  a
     23456   -  -  -
     _______________
    a = B,V,F,B.
    Contains all 24 56s, 14 65s, 30 0987s, 33 7890s off the front, 9 0987s
    off the front, 124 little bell rollups at the back, including 30 each
    23456s and 65432s, 50 little bell rollups at the front, and a total of
    365 runs of four or more consecutive bells either at the back or at
    the front.

Nothing novel here. Simply something decent for the method that is in
a style that some conductors have liked in the past. Personally, I
like the distribution of varied music throughout the peal. Probably a
bit more linkage chaff than MDB would care for, though.

It may also be worth noting that I spent about 65 minutes tinkering by
hand, and running 18 other searches before settling on this one.

The relatively small search is typical of what I usually do. I guess
I'm just not patient enough to wait hours or days. I'm much more
likely to constrain things sufficiently to keep the search down to
seconds or minutes.

It is also worth noting that my software works under a radically
different philosophy than I believe many others' does. Rather than
aiming at the tightest possible inner loop to maximize the number of
nodes visited per second, I instead put some extra meat into the inner
loop in an effort to prune the graph to be searched as much as
possible.

LIke I think virtually everyone else does I, of course, precompute all
the nodes corresponding to some chunk of calling that has no
opportunities for branching. This might be a lead, though more likely
something like the stretch from M to W for a particular coursing
order, since no calls are allowed there. And with the falseness
between these chunks also precomputed. And at the same time which of
various musical rows or other features under consideration are
provided by the various chunks. Things are linked not by indicies, but
rather by pointers, though I doubt that makes a difference either way,
really.

When doing the search I attempt to prune the graph based on the
required features, mostly musical rows. I keep track of how many
allowed nodes provide various desired features. When the number of
rows available from still allowed nodes decreases to the minimum I'm
allowed by my constraints, all the remaining nodes providing them
become required. And thus all the nodes the required nodes are false
against are prohibited.

And this can propagate further: when a node, N, is noted as
prohibited, I look at all its successors. If one of them, S, no longer
has any allowed predecessors, I prohibit S as well (and transitively
look at its successors and predecessors). Similarly, I look at all the
predecessors of N, and if one of them, P, has no allowed successors, I
prohibit P (and transitively look at its successors and predecessors).
And, of course, some of these prohibitions may make some more nodes
required, etc.

A further, often useful, optimization I do before starting the search.
I do a breadth first search backwards from the final state, for a set
period of time. In this case, 10 seconds, which allowed me to go back
1880 changes. During this backwards, breadth first search I build up
lists of upper bounds on the possible numbers of the features desired
for a given length to the solution. So once I get within shouting
distance of a solution, in this case past 3160 changes, at each new
visitation of a node I can ask it if there is any path (albeit one not
necessarily available to me any longer) that provides all the features
my constraints need, and backtrack immediately if there isn't.

It's also worth noting that since I'm almost always interested in
constraining things to solutions containing features, usually musical
rows, that are not invariant under rotation I don't think there is any
point for me in modding out rotations. If I'm mistaken about this, I'd
be most interested in hearing folks further ideas about this, though.

I suppose another thing worth noting is the environment in which all
this runs. While the previous version of this software was written in
Lisp, the current version is written in Java, as is another, newer
version that I've started, but have not had time to make much progress
on. While I'm profligate with memory allocation during setup, and when
printing results, I've been careful to ensure no memory allocation
happens during the search per se. These days I run it primarily on
Macintosh machines, though in the past I've run it extensive on
Windows and LInux machines. My current main machine has a 2.8 GHz Core
2 Duo CPU, 1.08 GHz front side bus, and 6 MB L2 cache. I'm currently
using a 64 bit JVM, at least on that machine, though when for one
reason or another I use a different one it is likely to be a 32 bit
machine. While my main machine has a dual core processor, I currently
do no multi-threading. That is one of my goals for the embryonic next
version. Indeed, I have plans to attempt allowing use of multiple
machines, communicating over a network, to parallelize things
extensively, and using a heterogenous collection of machines. Such a
scheme is unlikely to make much of a difference for a search as quick
as 13 seconds, but it may allow making slightly larger searches that
might normally take an hour or two run in a few minutes with the
collection of machines available to me.



-- 
Don Morrison <dfm at ringing.org>
"Time has drawn us toward the commonsensical-sounding yet
elusive moral truth that people everywhere are people, just like us."
                                  -- Robert Wright, _The Evolution of God_