The typescript for chapter 14 is provided in AutomatedComposition14.pdf.
This final chapter introduces the technique of heuristically guided constrained searches with dependency-directed backtracking. Of all the decision-making discussed in this typescript, constrained search “undoubtedly comes closest to simulating how composers actually work.” The constraint-satisfaction mechanism works as follows:
For each decision, the search steps through potential options, testing for violations. Whenever it encounters an option meeting all of the constraints, the search advances to the next decision; should the search exhaust all available options, it backtracks, revises one or more earlier decisions, and tries again.
Constraints establish a minimal standard of acceptability. However it is possible to bias the search toward better-quality results through the agency of heuristic scheduling, previously expored in Chapter 9.
The technique is illustrated by a search which, given the dominant seventh chord G2 G3 D4 F4 B4 G5 seeks a six-part C-major resolution. A first attempt without heuristics achieves a solution after 22 steps. A second attempt applies heuristics: first to address the root motion, next to resolve the dissonance, next trying to satisfy the leading tone, next treating the top voice, then filling in the remaining inner voices. This attempt achieves a solution after merely 7 steps.
A FORTRAN program is described which implements a search through a sequence of generic decisions and which calls
out to method stubs where it needs to prioritize decisions, to evaluate
options, and to test for constraint violations. This program implements a non-rigorous approach to backtracking which
I no longer advocate because “the mechanism tends to loose track of the original impasse.” However, the
typescript goes on to discuss how this defect may be remedied by having the program “assemble a complete list
of conflicts for each decision”. Or more precisely, a complete list of the sources of conflict for each decision.
Historical antecedents for contrained search include the “try-again method” of Hiller and Isaacson's celebrated 1957 Illiac Suite. The “try-again method” allowed the Illiac to regenerate a note whenever it was confronted with a constraint violation; however, no provision was made to exclude notes which the program had previously rejected. A tree graph presented in a 1968 article by Stanley Gill suggests that Gill's program could backtrack, though probably without dependency direction. Larry Polansky also employed backtracking of a rudimentary sort for numbers 2 (1975) and 3 (1976) of his Four Voice Canons. By far the most impressive of early search-based composing programs have been those of Kemal Ebcioğlu, whose programs include a 1980 program for species counterpoint and a 1984 program to harmonize chorale melodies in the style of J.S. Bach.
I previously honored statistical feedback as an essential technology, that is, as an indispensible way of balancing resources in compositional choices. Constrained search richly deserves the same accolade. Although this decision-making strategy only appears here in the final chapter of this typescript, many of the previous chapters have been building toward it. Thus constraints were first introduced in connection with conditional decision-making in Chapter 6. Statistical feedback appeared as a single-criterion heuristic in Chapter 7. Packed keys were introduced as an implementation tactic for multi-criteria heuristics in Chapter 9, which also introduced the concept of heuristic scheduling. The application of recursion for rigorously enumerating solutions to a problem embracing many decisions was covered in Chapter 10 and Chapter 12.
My efforts to promote constrained search as a core implementation strategy began with my 1983 Computer Music Journal article, “Stylistic Automata in Gradient”. These promotional efforts have continued with the series of project reports in Interface: Journal of New Music Research: “Notes on Undulant”, “Two Pieces for Amplified Guitar”, “Concurrence”, plus a comprehensive general article on search techniques, “Quantifying Musical Merit”. There have also been two installations targeted towards mass audiences: Mix or Match was one of the suite of projects created for the U.S. Pavilion at Expo '85 in Tsukuba, Japan. The subsequent Cybernetic Composer installation toured U.S. science museums as part of the traveling exhibit Robots and Beyond: The Age of Intelligent Machines.
A collaboration between Lejaren Hiller's and myself, Mix or Match used constrained searches to generate melodies with accompaniments in what Hiller characterized as “Tin Pan Alley” style. To present Mix or Match, Bob Franki developed animated graphics which actively displayed the process as it worked its way forward, trying out compositional alternatives, then backtracked in the face of impasses. A snapshot of this graphic was reproduced in Perspectives of New Music. Further implementation details about the composing program developed by myself appear in the 1985 ICMC Proceedings. A Kurzweil 250 realization of several Mix or Match melodies is available on this site in MP3 format.
The Cybernetic Composer installation was created upon invitation from Ray Kurzweil. It took up where Mix or Match left off, generating accompanied melodies in four distinct genres: ‘standard’ jazz, Latin jazz, rock, and ragtime. Implementation details about this project appear in “Cybernetic Composer: An Overview”.
My advocacy of constrained searches continues with two interactive demonstrations created for this site. These are the Intelligent Part-Writer and the Complementary Rhythm Generator.
The practical programming content of Chapter 14 was provided by Demonstration 11: Constrained Search. The process illustrated the principle of bottom-up design in that its four stages of production began by generating melodic material, then used the properties of this material to determine how it should intertwine:
| © Charles Ames | Page created: 2017-03-12 | Last updated: 2017-03-12 |