[r-t] 147 TDMM
mark at snowtiger.net
Mon Oct 4 20:13:10 UTC 2010
> 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
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
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.
More information about the ringing-theory