[r-t] 147 TDMM

[Mark Davies]

RAS writes,

> The interesting bits are in the details of the first stage.
> The critical step is that I don't look at the lead ends in
> order.  If at some stage, I have a some lead ends with
> methods assigned to them, and some unassigned, the next lead
> I choose is the unassigned lead end with the fewest
> available viable methods.

This is obviously a good, and useful optimisation. Basically, you are 
looking at the most difficult nodes first, in order to apply pruning as 
early as possible in the search. With a "one-pass" search algorithm it 
is not normally possible to apply this technique, since you are forced 
to process nodes in the order they appear in the output composition. I 
guess what we're saying is that splitting the search into two passes 
allows new pruning techniques to be applied - that's even better news. 
Your third optimisation, taking methods in order of cross-falseness, is 
pursuing the same idea, I think.

> An interesting idea.  I hadn't thought about using it to
> look for musical touches.  However, what do you propose the
> nodes in the first stage to be?  If you intend to take the
> 5040 possible l.h.s / l.e.s, I can see serious problem.

No, I wasn't thinking about extents, and maybe not even tenors-split - 
certainly not the full nodespace, anyway. I wasn't even thinking about 
spliced, necessarily.

I didn't clearly elucidate the generalisation of "plan" I was thinking 
about, either. Your spliced Minor plans are complete partitions of all 
available nodes, but I don't think you need to completely partition to 
make use of the same idea. Definitely not in Major, maybe not even in 
Minor. By using incomplete plans, you reduce the number of plans, and 
the time taken to build them, but increase the work in the second search 
pass.

Here's an example. Tenors-together, peal-length, single-method Major 
(conceptually, a long way away from your search space!) is often 
intractable for one-pass searches, for all but multiparts. My usual line 
of attack on one-parts is to isolate a set of musical nodes that I 
require to be in the composition. These really form the "plan" - 
pre-selected nodes, not necessarily all joined up, which must be 
present. A linkage search is then run to join them up with any other 
touch fragments available from the remaining unselected nodes, i.e. 
those which weren't in the original plan.

Now, at the moment I do that manually. I'm the one building the "plan". 
But what you have done, in your very different search space, is to 
automate the plan builder, to have it produce every possible plan 
variant, and run linkage searches on each one. In theory I could do that 
too. I could simply list the music I want in the peal, and a first-pass 
plan builder could produce all those "partial plans" which guarantee the 
minimum specified musical content. We then run linkage searches for each.

This would dramatically change the nature of the searches one could 
attempt. Currently I focus on small numbers of relatively simple plans, 
and am content with correspondingly long linkage searches. But if the 
machine is creating the plans, we could instead look at much more 
complex plans (more pre-selected nodes); there would be vastly more of 
these, of course, but the corresponding linkage stages for each would be 
much shorter. It would also be possible to parallelize up much more easily.

That raises an important question - did you make use of multi-threading 
in any stage of your search? It strikes me the whole algorithm is 
inherently parallizable - as soon as the first pass has produced the 
first plan, you can start a linkage search on it; spawn a thread for 
each plan you create, in fact. I have to run at least 8 threads to make 
full use of my four-core hyperthreaded i7, and future chip architectures 
are likely to get even wider. A standard tree search is relatively 
difficult to parallelize, but with this algorithm, you are naturally 
wanting to do N concurrent searches, so its made for multicore, 
multithreaded hardware environments.

MBD