Chapter 12
Comparative Search

The typescript for chapter 12 is provided in AutomatedComposition12.pdf.

Comparative searches attempt to find optimal solutions to problems encompassing many decisions. The strategy consists of systematically enumerating every possible solution and of comparing each new solution, or candidate, to the best solution so-far encountered, or incumbent. The advantage of comparative search over all other methods of decision-making described in this book is that, given enough time, it always finds the best solution. Its disadvantage is that the number of solutions may be too large for even a computer to evaluate in any reasonable amount of time.

The first of my own writings to mention this search technique was the article describing my 1981 computer-composed Protocol for solo piano. At that time I called the technique “comparative evaluation”. Later in “Quantifying Musical Merit” (1992), the same technique is called “exhaustive search”, which term is employed by my 2011 production framework. The official AI term, “alpha-beta pruning” came to me by way of a Knuth & Moore's 1975 article, which attributes the term to John McCarthy, who had earlier coined the term “artificial intelligence”.

The first illustration given searches through the F major scale for a chord which is ‘optimally consonant’ in the sense of having as few or fewer dissonant intervals when compared to any other chord. The search comes down to enumerating all ways of selection four pitches out of seven. Chordal consonance is measured using a packed key or more specifically, a base four number with major 3rds or minor 6ths in the 1s place, minor 3rds or major 6ths in 4s place, major 2nds or minor 7ths in the 16s place, tritones in the 64s place, and minor 2nds or major 7ths in the 256s place. The ‘optimally consonant’ discovered by this search contains the notes F, G, B!, and D.

The next section explores combinatorial formulas which can be used to calculate the size of a solution space. For a problem with N decisions drawing from a pool of M options, four scenarios are considered:

• ordered selection with replacement,
• ordered selection without replacement,
• unordered selection with replacement, and
• unordered selection without replacement.

The practical programming content of Chapter 12 was provided by Demonstration 10: Comparative Search. The process illustrated the principle of bottom-up design in that its three stages of production began by generating chordal material, then used the properties of this material to determine how chords should progress:

• Stage I generated 12 chords, each by exhaustive search. The search sought to suppress sharing of common tones between chords, and to minimize the presence of consonant intervals within chords.
• The piece was organized into 12 segments, each alloted a certain number of chords. Stage II employed exhaustive searches to discover the progression of chords within each segment for which consecutive chords shared the fewest common chromatic degrees.
• Stage III arppeggiated the chords, using statistical feedback to ensure that the four chord tones all received their fair share of notes.