Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

Brute-force Music Composition

13 Post author: HughRistik 22 May 2009 06:02AM

Follow-up to: Heuristic is not a bad word

When I was in high school, I wanted to compose music. I wanted to write the music that I wanted to hear. There was only one problem: I have good aural imagination, but I don't have world-class aural imagination. I can look at sheet music and hear it in my head. I can hear chords. I can hear two-part harmony. Yet my aural imagination wasn't developed enough to generate novel music, except when I was in certain moods or about to fall asleep. And most of what I could hear in my head I found impossible to transcribe.

Nevertheless, I wanted to write cool music. I know what I like when I hear it. I had the ability to critique music; the only problem was creating it. So I developed my own technique for writing music: I composed using brute force. Before I describe how this worked, and how successful it was, I would like to talk more generally about brute force as a method for problem-solving.

Brute force: the null heuristic

In the language of heuristic, the art and science of discovery, brute-force search is the crudest method of heuristic there is, which is why I think it's a good place to start discussing heuristic methods. According to Wikipedia, "brute-force search or exhaustive search, also known as generate and test, is a trivial but very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement." Throw everything at the wall until something sticks.

Given a particular problem, imagine all possible solutions as points in space. In the terms of heuristic, this is the search space of the problem. Heuristic is about navigating through search space until you find the actual solution. Brute-force search proceeds by analyzing each point in search space, one at a time. On the Heuristic Wiki, Ben Kovitz refers to brute force as the "null heuristic":

Nearly all thought in heuristic pertains to how to find a solution, an optimum, or a pretty good combination without searching every point in the design space. Thus brute-force search is the null heuristic. It's what you do when you don't know of any heuristic that could simplify the problem. That said, though, brute force always has the last word. However you whittle down your search space, you still must examine one possibility at a time, even in your much-reduced search space.


Kovitz observes that even though many problems cannot be solved by brute force (such as a full chess game), sometimes you can solve part of a problem with brute-force (such as a chess endgame). This process—of using brute force once you have narrowed your search space as much as possible—is how I composed.

Brute force musical composition

When composing, I didn't use complete brute force. Doing so would have required exploring a massive search space of all possible combinations of sound. My search space was whittled down by certain factors. I was writing tonal music in the major or minor key in a neo-Romantic style on the piano. Furthermore, I composed only 2-4 measures at a time, one or two chords at a time, and I recapitulated themes and motifs.

My method was to plink around on the piano for a few measures, and then decide if I like what I heard . If I didn't, then I would back up and plink some more until I found something I did like. I would play the entire phrase or section now including the new two bars, to hear if I still liked them in context, and to prepare for writing the next two bars. The other name for brute-force search, "generate and test," sounds very appropriate: I generated a segment by pianistic experimentation (rather than from my aural imagination), then I tested it in context.

Messing around with the piano keys wasn't completely random. My fingers were proceeding with logical chord patterns, generally trying all consonant chords or chromatically nearby dissonant chords that I felt were consistent with the style I was going for. I realized that when I didn't have a basis to decide the next chord in my harmony (such as the need for a cadence, or borrowing a chord progression from another composer), the space of subsequent pianistic neo-Romantic-sounding candidate chords was low enough that I could brute-force my way through it: perhaps 4-10 points in chordal search space depending on what had already occurred in the phrase. I didn't even need to try them all; I just needed to try a bunch until I found something that I liked.

Results

Brute force composition was slow and tedious. But it worked surprisingly well for harmony. It just wasn't very good for melody and rhythm, which involved a much larger search space.

For a melody, the number of stylistically plausible subsequent notes within one octave of the current note might be 4 to 16. The number of stylistically plausible durations for holding a note (e.g. whole note, half note, quarter note, eighth note, sixteenth note, and intermediate durations such as dotted quarter note, etc...) might be be 2 to 8 depending on the phrase. This leads to a search space of 8-128 possibilities per note. Yet while I can compose a harmony one chord at a time, it doesn't work so well to compose a melody one note at a time. I have to work with combinations of notes, which is difficult to do linearly on a piano, and which enlarges the search space even more. Based on the previous assumptions, 4-16 plausible tones X 2-8 plausible durations X 4 notes = 32-512. And while I usually only have a few chords per 2 bars, I will usually have more than 4 notes. The minimum search space for melodies (representing relatively less creative composition) was an order of magnitude or two too big to brute-force through if I wanted to finish my opus before my death.

Since I couldn't hear complete melodies in my head, I had to lower my standards for what constituted a satisfactory melodic solution to cut down the search space until it was brute-forcible. Most of the time,  I used strings of notes with the same duration (e.g. eights, triplets, sixteenths) in scales and arpeggios, more like Baroque music than like Romantic music. I used simple rhythms, themes, and motifs, and repeated them. Unfortunately, I had to cut out parts of the search space where some of the best solutions were lying, because I sacrificed melodies with notes of more varied duration that didn't proceed by scales or arpeggios. The result of my brute-force composing was harmonically interesting, but melodically and rhythmically lacking.

In case you are wondering what this music sounded like, I've uploaded a composition to YouTube from a performance during sophomore or junior year of high school. Turn up your volume a little, and keep in mind that I was a better composer than pianist, because I spent most of my time on the piano composing two bars at a time rather than actually practicing.

Does it sound how you expected?

Conclusion

For my initial problem, "how do I compose some music that sounds cool to me given that I don't hear new music in my head?" I arrived at a successful solution: I cut down the problem to a size where I could brute-force it. Brute force worked as long as I could keep the possibilities I had to plink through down to a manageable number. Yet after creating several compositions, I eventually tired of this methodology because brute-forcing two measures at a time was very tedious. Secondly, my standards rose, and I wanted to be able to do melody, not just harmony. As my desired solution became more complex, the search space I had to seek it in grew larger, until it was eventually impossible to traverse with brute force. Thirdly, I got better at other pursuits where I was able to achieve better results with my time. In the end, I abandoned composition, but some days I still plink around on the piano.

What is a problem that you have attempted to solve using brute force, and how well did it work? What kinds of problems seem amenable to brute force, and what kinds don't?

Comments (32)

Comment author: komponisto 24 May 2009 03:30:51AM 11 points [-]

Yet my aural imagination wasn't developed enough to generate novel music, except when I was in certain moods or about to fall asleep. And most of what I could hear in my head I found impossible to transcribe.

I can't speak with certainty about your particular situation, but there's a decent chance you would find these tasks easier if you had a more powerful theory of music at your disposal. Such things exist, and are known to experts; unfortunately, despite the fact that they have been around for a while now, one is still unlikely to be exposed to them without doing graduate work in music, preferably at an elite university. (The linked blog is one of very few places on the internet where I have ever seen such things discussed.)

But let me stop lamenting and instead try to improve the situation, such as can be done within the confines of a blog comment.

One thing I noticed right away about your compositional process, as you described it, was that it was almost entirely local. As you said, you only composed 2-4 measures at a time. (You did mention recaptiulating things, something which requires a bit of global planning, hence the "almost".) This is roughly like trying to paint a picture one detail at a time without knowing what it is you're painting a picture of. Maybe some painters work like this, but I doubt most do. (By the way, this has nothing to do with how abstract the painting is. I suspect that even the most abstract painters have some overall idea of what they want their painting to look like well before they finish it.)

Unfortunately, "traditional" music theory (by which I mean that which the layman can easily find online, or in bookstores, as opposed to what specialists have in their university libraries) does a very poor job of allowing one to think precisely about global phenomena. At its worst, it trains one to ask questions like "what chord should come next?", which is totally the wrong way to think about music.

In the early 20th century, an Austrian named Heinrich Schenker came up with a theory of the right sort: one that explicitly dealt with musical works on all levels of structure, from the most global and far-reaching down to the minutiae of individual notes. Schenker's own intellectual context for his achievement was of course quite different from the modern one in which his work is usually placed, but in any event his ideas were picked up and run with by anglophone music theorists, and now "Schenkerian theory" is a standard, literature-rich academic discipline that most readers probably didn't know about.

This comment is getting too long, so I'll close with a specific recommendation: musically-inclined LWers will definitely want to take a look at Peter Westergaard's book An Introduction to Tonal Theory. It's a favorite at the site I linked to above, and indeed, although it was originally written for college freshmen* I almost think its title could have been: "Music Theory For Smart People Who Care About Occam's Razor 'n Stuff".

*While, I hasten to add, Westergaard was teaching at Columbia and Princeton in the 1960s and 70s.

Comment author: HughRistik 28 May 2009 10:11:28PM 0 points [-]

My compositional method was indeed bad for working globally. As a professional level visual artist, I am very familiar with the problem of getting bogged down in the details, which can ruin the global effect of what you are working on.

(By the way, this has nothing to do with how abstract the painting is. I suspect that even the most abstract painters have some overall idea of what they want their painting to look like well before they finish it.)

The realistic style I use for painting is often very abstract. I am not painting faces; I am painting abstract patches of light, shade, and color that happen to look like faces. Here is a video of one of my favorite artists at work in a highly global style; notice how abstract his brush work is, and how it is difficult to tell what he is even painting during the early stages.

Thanks for the recommendations.

Comment author: Kaj_Sotala 25 May 2009 09:50:12AM 6 points [-]

I get the impression you didn't keep up with this? I wonder whether, if you had, you would have gradually picked up the ability to compose without needing to resort to brute force. After all, what you did sounds like a lot like ordinary practice - do something, see if it works, if not correct, repeat until your brain starts to pick up on the correct pattern.

Comment author: HughRistik 26 May 2009 10:14:27PM 0 points [-]

I wonder whether, if you had, you would have gradually picked up the ability to compose without needing to resort to brute force.

I kept waiting for this to happen, but it never quite did. At least, not to an extent that satisfied me. I'm sure it would have eventually, but I got better at other things and gravitated in a different direction.

Comment author: Liron 22 May 2009 06:44:31AM *  4 points [-]

When I was 11, I wanted to write a game in which two players raced to get to the finish of a randomly generated maze. So I thought: How can I make a random maze?

My solution was to use two perpendicular walls to split the game area into four quadrants, and cut a 1-unit opening in a fixed location along each of the four wall sections separating pairs of quadrants.

Then I manually created 20 maze tiles -- 5 for each of the four quadrants, with pathways leading out of the block at the places where there were holes in the center divider. So for every new game, the program randomly drew one of a possible 625 mazes. It seemed random enough to me and others who played.

Rather than a brute force algorithm, this is an example of another "null heuristic": hard coding the solution space into the program.

Comment author: John_Maxwell_IV 24 May 2009 05:07:54AM 0 points [-]

Wow, I'm surprised your mazes seemed random enough!

Comment author: arthurlewis 24 May 2009 08:02:00AM 3 points [-]

In a sense, I think that all creative pursuits are served well by the type of "brute force" you're talking about. You write/play/draw something, decide if you like it, and then work from there. However, narrowing down the search space, as you described, can be easier if you leave it to the unconscious. If you've been listening to the style of music you're composing in, or reading the style you're writing in, etc., it should have at least a few heuristics already loaded up. In the case of your melodies, what happens if you just "hum something?"

I generated a segment by pianistic experimentation (rather than from my aural imagination)

This is how I write most of my music. Every once in a while, a melody or chord progression will just show up fully formed, usually on the subway or in the shower, but it's rare. Most of the other songwriters/composers I know work similarly. You say you don't hear new music in your head; a lot of the time, I don't either. I hear it as it comes out of my mouth or speakers in real-time.

Comment author: HughRistik 26 May 2009 10:07:45PM *  0 points [-]

In a sense, I think that all creative pursuits are served well by the type of "brute force" you're talking about. You write/play/draw something, decide if you like it, and then work from there.

I think you are absolutely correct.

In the case of your melodies, what happens if you just "hum something?"

I can hum things, but they sound rather classical and banal, like Eine Kleine Nachtmusik (which I hate with a passion). I'll try again when I'm in a different mood... it's been a while since I last tried to compose.

This is how I write most of my music. Every once in a while, a melody or chord progression will just show up fully formed, usually on the subway or in the shower, but it's rare. Most of the other songwriters/composers I know work similarly. You say you don't hear new music in your head; a lot of the time, I don't either. I hear it as it comes out of my mouth or speakers in real-time.

Interesting. I guess I always assumed that others had some capability I didn't.

Comment author: PhilGoetz 22 May 2009 05:53:44PM 3 points [-]

I can hear chords. I can hear two-part harmony. Yet my aural imagination wasn't developed enough to generate novel music, except when I was in certain moods or about to fall asleep. And most of what I could hear in my head I found impossible to transcribe.

I had exactly the same problem - and with the same strange exception: Music sometimes start to flow through my head just before I fall asleep, in multipart harmony.

I'd be interested in any ideas as to what makes this mental state different, and how to cultivate it.

I find it's easier to imagine novel music if I restrict myself to a particular genre+style. Just settling on the instruments helps a lot.

Comment author: HughRistik 22 May 2009 10:25:46PM 2 points [-]

I'd be interested in any ideas as to what makes this mental state different, and how to cultivate it.

Usually just being tired and stopping myself from falling asleep is enough. But nothing I hear this way can be written down, as if it's another type of music altogether.

I find it's easier to imagine novel music if I restrict myself to a particular genre+style. Just settling on the instruments helps a lot.

I've found the same thing with any kind of composition. And with many kinds of problems, adding constraints (e.g. choosing an instrument or form in music, choosing rhyme or meter in poetry), even arbitrary constraints, actually makes them easier to solve. More on this in the future.

Comment author: CronoDAS 22 May 2009 11:43:32PM 3 points [-]

Mark Rosewater says, all the time, that restrictions breed creativity.

Comment author: Jordan 24 May 2009 12:59:08AM 0 points [-]

I have no musical ability, but I find that my creativity is greatly heightened when I'm trying to fall asleep, and, to a lesser extent, when I wake up in the morning. I'm tempted to say that a small part of the reason is just that my head is getting more blood when I'm horizontal... but there's probably some chemical thing going on too.

Comment author: thomblake 22 May 2009 02:38:20PM 3 points [-]

What is a problem that you have attempted to solve using brute force, and how well did it work? What kinds of problems seem amenable to brute force, and what kinds don't?

Often if I'm trying to work out an algorithm to solve a problem that is possibly solvable by brute force, I'll start by writing a quick brute-force algorithm to perform the task. Then I'll leave it running in the background while I'm working on a better algorithm - that way, my time to implement the 'more efficient' algorithm is never more than the time it would have taken to brute force it.

But now that I think of it, I don't think I've actually used this solution since the days when computers were a lot slower.

Comment author: John_Maxwell_IV 24 May 2009 05:04:57AM 0 points [-]

But now that I think of it, I don't think I've actually used this solution since the days when computers were a lot slower.

So presumably you now just use the brute-force algorithm and forget about it?

Also, these must be one-off problems you're solving, right?

Comment author: HughRistik 22 May 2009 10:21:40PM 0 points [-]

I like this... And if there is no more efficient algorithm you can find, then your brute-force has already gotten a head start.

Comment author: Vladimir_Nesov 22 May 2009 10:03:01AM 3 points [-]

It's better to see heuristic search as an order of enumeration, always exhaustive, but prioritizing specific elements, perhaps those representative of the elements in some simplified representation. When you need to choose from 100 options, it's better to let your intuition do the prioritization, to refine whatever heuristic you are following consciously, instead of starting from 1 up. And conversely, it's important to train intuition to implement good prioritization heuristics, even if you know an explicit algorithm guaranteed to lead to solution.

Comment author: HughRistik 22 May 2009 07:50:52PM 0 points [-]

I think the method you describe would indeed be superior to pure brute force. In my case, my intuition was guiding my fingers a lot I'm sure. I also did prioritize certain elements (e.g. I didn't try chords which I knew wouldn't fit the style). The brute force came in at the level of searching through elements that were generated by my intuition and/or consciously prioritized. My intuition was getting trained in the process. The more I think about it, the more it sounds like I was doing exactly what you describe.

Comment author: cousin_it 22 May 2009 07:53:36AM *  3 points [-]

Can't speak with authority as a composer here, but I found your piece harmonically okay and spoiled only by lack of logic and form, not lack of melody.

Here's how you may get form: take a few measures of your piece that form a cohesive block, maybe from the beginning to the notes d c#, and play them repeatedly until your ears bleed and you desperately want the music to go somewhere else. Then go somewhere else - do something outrageous on the piano, and then return to your first few measures. Voila, instant verse-chorus form :-) The music should shift when you want it to shift, not just because a new measure has started and demands new chords. There's nothing wrong with repeating a lot and rephrasing a lot.

Here's something born from this kind of methodology. I lack your hearing and harmonic sense, so I just make the music as stupidly obvious and self-similar as possible.

Comment author: HughRistik 22 May 2009 07:46:18PM 0 points [-]

Can't speak with authority as a composer here, but I found your piece harmonically okay and spoiled only by lack of logic and form, not lack of melody.

Yeah, composing one chord at a time without writing it down wasn't good for structure, either.

I think your idea is interesting, and I'll listen to your piece when I'm not at work.

Comment author: John_Maxwell_IV 24 May 2009 04:59:07AM *  2 points [-]

Knights and knaves puzzles are a perfect example of brute force working. Since every participant must be either a knight (truth-teller) or a knave (liar), and there is (presumably) only one working configuration, then you only have to enumerate two possibilities: that the first person who spoke was a knight, or that the first person who spoke was a knave. Here's one of my own design.

Five natives (call them A, B, C, D, and E) come up to you.

  • A says: B is a knave.
  • B says: D is a knave.
  • C says: B and D are both knaves.
  • D says: E is a knave.
  • E says: There are even number of knights in this group.

Which are knights, and which are knaves?

Comment author: MichaelHoward 24 May 2009 09:03:25PM 4 points [-]

perfect example of where brute force working

We don't need no stinkin' brute force! When things look so black-and-white, this is a job for... the Mind-Killer!

We see two factions accusing one-another, AD vs BE. So we know one side is all good, the other side is all evil.

As for C, well if we know one side has all the answers, then anyone claiming otherwise must be a dirty liar. So there can only be 2 knights. Guess E was right, so CAD are cads.

Nice little heuristic. What could possibly go wrong?

Comment author: thomblake 22 May 2009 02:41:59PM 2 points [-]

Do you have more of this music to share? Perhaps in a format other than embedded flash video? MP3 maybe?

Comment author: jimmy 22 May 2009 05:56:18PM 2 points [-]

flv2mp3.com will take in youtube videos and spit out mp3s. It seems to be frequently down though (it's working now).

Comment author: HughRistik 22 May 2009 07:11:32PM 1 point [-]

I actually have the music originally in MP3, but I don't know of good MP3 upload or streaming sites, so I just went with YouTube. Anyone have a recommendation for where I should host it?

Comment author: contrabalance 19 June 2009 11:49:11PM 0 points [-]

http://www.playlist.io is a good one with no signup or hassle http://www.soundcloud.com has more robust audio-specific features

Comment author: HughRistik 22 May 2009 10:28:18PM 0 points [-]

I don't actually have any more recordings of music I wrote in this manner. I do have a recording of a string quartet I wrote in a more Baroque/classical style. I didn't use such a high degree of brute force for this style of composition, though. Rather, I logically combined motifs or scale/arpeggio patterns based on my empirical knowledge of Baroque and classical music.

Comment author: Nominull 23 May 2009 04:48:04PM *  1 point [-]

I'm a big fan of this comic on this subject.

Comment author: composerzane 23 May 2009 02:17:23PM 1 point [-]

excellent piece of music, to my ears. i consider myself a musician (amateur composer?) with an adequate knowledge of theory. even though the notion of a confined search-space was already priming me for a possibly less continuous melody, the melody still struck me, even emotionally. the brute-force method, to generalize from a single example, seems to be excellent (when well-constrained) for writing novel chord progressions. perhaps if you use the second chord of each sequence as the first chord of a new sequence, afterward piecing them together, you could increase continuity even further. i think this piece, however, might say more about the qualities that would satisfy your goals (IOW, a solution to the problem) than the search-space you covered, perhaps? to clean up this particular example, perhaps one might more clearly define what qualifies as a solution in the first place? for example, how "good" did one phrase need to sound before it was acceptable?

Comment author: John-Henry 22 May 2009 02:20:39PM 1 point [-]

I'm unsure whether you were using brute force as a hack to spur your musical imagination and create a good song or whether it was intended to isolate parts of composition you wanted to become more proficient in. Was the goal to create individual good songs or create a better understanding of music to apply later to a non-brute force style? It seems the brute force style is clearly wrongheaded as far as creating fully developed music, but you probably knew that going in (and it does serve as a good example of the null heuristic).

If it was instead a method to better learn music theory, did it work?

Comment author: HughRistik 22 May 2009 08:04:23PM 1 point [-]

A little bit of everything you mention. Consciously, I just wanted to write something I liked. Yet using brute force did teach me compositional skills I was able to try later. I got a better sense of which chords would proceed from others. This let me reduce the search space in the future. Unfortunately, it also made my compositions have a mood that was too similar, because I was re-using the same chord patterns.

In the end, brute force gave me empirical knowledge of interesting chord structures, but that didn't fix my struggles with melody and rhythm.

Comment author: asciilifeform 27 May 2009 05:28:21PM *  0 points [-]

I have largely the opposite problem. I am able to compose endless original music in my head on a whim, but all of my attempts to get it out in any form have met with failure. I have recently come up with a possible new approach, but have not yet tried it.

Comment deleted 23 May 2009 03:15:34AM [-]
Comment author: HughRistik 23 May 2009 06:02:00AM *  0 points [-]

Yup, thanks. Dot is now added.