Elf Help: Composing Technology |
Computer composing engines have been around for many decades, and with improvements in both algorithm design and computing speed, can now challenge the human composer in certain limited areas. Computer composition systems work by performing exhaustive tree searches. This is a "brute force" method that requires a lot of processing power and clever optimisation techniques if it is to provide useful results. Fundamentally, the computer tries every combination of calls (and in spliced, methods) by walking down a search tree of possibilities. For example, Elf might start looking for three-lead compositions of two-spliced in the following order:
CC CC CC CC CC CY CC CC YC CC CC YY CC CY CC... and so on. Every time a composition is found, or a path is rejected, the algorithm backtracks up the tree to try a different possibility. The search will eventually end with:
YY YY CY YY YY YC YY YY YY
Now an extent of Plain Bob Minor requires 12 courses, and if a computer is to be sure it has found the best compositions, it must search every one. Ignoring for the time being touches that are false, we can see there are at most 1712 possible branches of the tree to search. Unfortunately, this is a very big number indeed - around 500 trillion. Even if we can search 17 million calling positions in one second, our composing program will be running for a year. And that was only looking for touches with the 6th unaffected! Moreover, we can easily find applications which are much more difficult - peals of Bristol Major, for instance, or one-parts of Stedman Triples - there is not enough time left in the universe to solve some of these problems with brute force, even if we filled the entire universe with computers all working on the problem!
So are computers useless? Well, obviously not. Some refinements of the basic brute force search, such as pruning, rotational sorting, palindromic searching, and so on, can bring many compositional problems within reasonable computing range; you'll find a brief guide to these algorithms in the section below. Interestingly, it turns out that computers are also very useful for very false methods. A large number of false leadheads can make life hard for the human composer, but the computer can very quickly prove compositions as it searches, and the fact that most will be false causes huge branches to be lopped from the search tree. This highlights a fundamental principle in composing algorithm design: tree pruning is always the most effective optimisation, even if raw composing speed is decreased.
Node tables. Computer proving programs normally generate every change in the composition, using the method place notation. Modern computers are extremely fast, so even a peal length can be generated in this way in milliseconds - but that is still too slow for composing engines, which need to process millions of compositions per second. So instead of individual changes, nodes are used. A node is the step from one call to the next - for example, in a single-method composition it might represent the transition from a Middle to a Before; in spliced it is a lead; and in half-lead spliced it is half a lead (although the Indis build now collapses this down into a single lead by using composite methods!). There is one node for every possible coursing order in every calling position, and the composing program must first calculate a node table which lists them all. This is like a big graph where every node has arrows (pointers) linking it to the subsequent nodes produced by each type of call. Once the node table is built, composition can proceed extremely swift by hopping from node to node. The node table can also contain a summary of the music contained in every row of the node, and even a list of false nodes, so that music and proof checking also become atomic operations.
Pruning. As I've described above, computer composition is really an impossibly difficult problem. In computer parlance, it has "exponential running time": if we lengthen the composition by just one calling position, we double or triple the search time. By far the best way to cut down such problems is to "prune" the search tree. For example, if Elf is set to look for "Maximum Changes of Method", it will not consider any branches of the search tree beginning CC, YY, etc. Pruning the tree at this level can eliminate untold billions of worthless compositions!
Rotational Sort. Touches which come round at the leadhead have the property that they can be rotated to generate other true compositions. For instance, the simple touch 2H,3W,H can be rotated to give H,3W,2H or 3W,3H. The "conventional" tree search used by composing engines would find each of these touches separately, and treat them as separate compositions. However, the Rotationally Sorted Tree Search algorithm is designed to find just one rotation of each touch. It is much quicker to analyse this one touch to find its most musical rotation, than it is to search for all rotations separately. Elf has used this algorithm since the Indis build.
Multi-part search. Reduce the composition length, and search time is slashed. Composing algorithms take advantage of this by offering multi-part searches - effectively the search length is reduced to the length of just one of the parts. Because of the exponential nature of the tree search, it's often that case that a two- or three-part search can complete in minutes, whereas a one-part would take an eternity. And of course there is the happy coincidence that multi-parts are easier to call!
Palindromic search. A palindromic composition is one that is the same as its reverse. For instance, take the simple touch of London Major, MBW. If you reverse this, lead-by-lead, you get... MBW! Palindromic touches are a bit like two-parts, in that they can be produced by a composition search of half the final length. Interestingly, it's also often the case that the best compositions - the most elegant, or most musical - turn out to be palindromic. Currently, Elf does not offer this type of search.