Jason Brazile
As a computer scientist and novice musician who decided to learn to play the guitar, I was motivated to write a program to help me do it. There are many problems that come up that a computer could help with. Here, I focus on 2 of them.
Upon learning how the guitar is traditionally tuned, I was a little irritated that is not done consistently. In standard tuning, all strings are tuned a 4th apart except the second to highest which is tuned a 3th away. This anomaly is more frustrating when one starts practicing scales which cause regular fingering patterns on all strings but this one.
I got into an argument with my brother who is a good guitar player over why the standard guitar tuning is illogical. After a long and fruitless argument (the only kind you can have with siblings), my theory is that it may be easier to finger complex chords (7th chords, 9th chords, etc.) with the tuning that way. My brother thinks that the standard tuning is the best because if it weren't it wouldn't be standard (He obviously doesn't follow computer standards). In any case, my brother suggests the best way to find out is to ask experts. I would be more satisfied with an answer achieved scientifically.
I figured that one good way to find out is to write a program that enumerates good fingerings for a series of chords. I could then change the guitar model in my program so that it uses a consistent tuning (perfect 4ths) and see if it could come up with just as many good fingerings.
If my program can find reasonable fingerings for songs that I want to
play using a logical tuning (which would only change the top 2 strings)
then I would prefer to use that rather than the less logical but
standard tuning.
A second irritation arose when I started to transcribe from recorded
media the songs that I wanted to play. It is relatively easy to discern
which types of chords (e.g. major 7th, diminished, etc.) are being
played by listening to them. However, knowing the chord types is only
part of the problem in discovering how they are fingered on the
guitar. For one thing, a chord can be instantiated in many inversions
(e.g. a 4 note chord can have the notes in any order and each note can
be in different octaves). However, for each instantiation of a chord in
a particular inversion, there may still be many ways to finger it. To
give some idea, I have one book which enumerates common guitar chord
fingerings. I estimate that according to this book there is an
average of 20 different ways a particular chord can be fingered.
If I wrote my program to solve my first problem of tuning, it could be helpful here as well - with slight modification.
The idea is that I want to mimic, as closely as possible, which chords are being played on my recordings, whereas my program would generate fingerings (and chord inversions) that may or may not be the same as those being played. What is needed is for me to give my program hints about certain chords.
To give an example, once that I have determined through listening that a particular chord type is being played (e.g. C major 7th), with little extra effort I can usually hear 1 or 2 notes in particular and be able to tell what octave they are in (e.g. the C is 3rd space C on the treble clef). Just knowing this isn't entirely helpful because that particular C can still be fingered 3 different ways (10th fret on the D string, 5th fret on the G string, or 1st fret on the B string). However, it does narrow down the search somewhat.
If I could give these hints to my program then it would lock those notes down and be more likely to generate the fingerings that are being used on the recording.
There are 2 major steps that this program would need to go through.
As it turns out, the first step above is non-trivial. One would need to go through at least the following steps.
Another step that could be added is a further musical classification
for use in the sequence generating process. For instance, a given
voicing for a chord can be considered either ``open'' or ``closed''
depending on how large the interval is between the most extreme notes
in the chord. There are well-known but informal rules that describe
when one voicing may be preferred over another.
The hardest part would be the last step -- coming up with the heuristics that defined ``good'' fingerings. An easy rule would be that you shouldn't assign a higher numbered finger to a lower numbered fret than another (finger,fret) assignment you have already made - that kind of finger crossing is often difficult if not impossible. However, other finger assignments are more open to interpretation. For instance, if the same fret on 4 adjacent strings should be played, one way to assign the fingers would be 1st on the top string, 2nd on the next string, 3rd on the next, and 4th on the next. Another way would be to just use one finger, say, the 1st, to bar across all strings. Another curious method that is mentioned in the guitar book, is to use 1 finger for the top string, and then bar the rest with the next finger.
This second major step of generating ``good'' sequences is where AI comes into play. The following steps need to be done:
Probably the most interesting part of this program for me was coming up with heuristics to evaluate the cost of moving from one chord to the next. I will explain this in more detail in the next section.
Determining a good way to traverse the search space is definitely
needed. Assuming that I could generate an average of 20 ``good''
fingerings for every chord in a chord sequence, and that I have
given no ``hints'' that limit these, exhaustive search would get
prohibitively expensive quite fast. For example, a song consisting
of a sequence of 8 chords would need to examine the cost of 
different sequences.
As the deadline drew near, I had to limit the scope of the intended program to be able to produce some worthwhile results. Of the 2 ``main'' steps mentioned above, I have a working implementation of step 2 and a partial implementation of step 1 in PROLOG.
While I think prolog was a fairly good language choice for this problem (due to its backtracking and ease of formulating rules) this was the second prolog program I had ever written and so the choice of language turned out to be a detriment in how much I could implement in a fixed amount of time.
My first heuristic for assigning a cost to changing from one chord to another was based on a kind of pattern similarity. The idea behind this heuristic is that a good chord transition occurs if the fingering pattern doesn't change much. I intentionally neglected the fact that this could give a good cost even if one jumps several frets away. My thinking was that it was pretty easy to just slide my whole hand up or down a few frets as long as I didn't have to move my fingers.
To implement this heuristic, I reduced a chord fingering to a vector of 6 integers that represents it. The vector entry is -1 if that string is not used, otherwise it is the distance away from the lowest fret used in that chord.
Example:
1 2 3 1 +-+-+-+-+-+ o | | | o | 4 +-+-+-+-+-+ chord((1,4)(-1,-1)(2,5)(3,5)(1,4)(-1,-1)) | | o o | | +-+-+-+-+-+ vector(0,-1,1,1,0,-1) | | | | | | +-+-+-+-+-+ x x
To find the cost of moving from one chord to the next, I just computed the difference between 2 vectors (if either entry was -1, I made the difference 0) and summed up the entries (not including the -1s) of the result.
After going through a few test runs with a small chord database, I went ahead and ran it with the full chord database on a sequence of the first 3 chords of a song to see what it would come up with as the best fingering. This is the sole winner it chose with the very low cost of 2!
1 3 2 4 2 1 4 1 3 2 4 1
+-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+
o | | | | | 4 | | | | | o 1 | | | | | o 9
+-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+
| | | o | | | | | o | | | | | o | |
+-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+
| o | | | | | o | | | | | o | | o |
+-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+
| | | | | | | | | | o | | | | | | |
+-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+
| | | | o | | | | | | | | | | | | |
+-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+
x x x x x x
I doubt that any guitarist would come up with this as the best progression between these 3 chords. The most obvious problem is that it jumps from fret 4 down to 1 then back up to 9. This would be a forgivable sin if the fingering patterns were extremely close, but they aren't really.
I determined that there are 2 problems with my heuristic. The first is that my earlier idea about jumping around is OK in certain circumstances but in general should be discouraged. The second was a representation problem. In analyzing why it thought that the fingering sequence above should only have a cost of 2, I noticed 2 problems.
The first problem is that in computing the difference between 2 vector entries, if one of them was -1 (that string is not used) then I set the cost to the value of the other entry. This is wrong for 2 reasons. First, there are times that the other entry might be 0, giving it a cost of 0. This is bad. The more important reason why this is wrong is that the fact that one entry is -1 and the other isn't means that you have changed strings. I decided that in general, changing strings is worse than not changing strings and in fact, think that it should be as bad as moving a finger 4 frets (the max you would move a finger up one string).
The second problem is related to the first problem. In this scheme the best one can do is not move (making the vector difference 0). I correctly score this when you don't move but I had also assigned a value of 0 inadvertently when one vector entry was -1. This would reward a lot of string changes where either the new string or the old string had a vector entry of 0. This doesn't make much sense.
My new heuristic went about solving the 2 problems of the old. First, I wanted to penalize string changes. I did this by changing my vector difference routine. If one vector entry is -1 but the other is not, then I set the difference to MAX (4).
The next thing to do was to discourage big fret jumps. For this, I added the difference between chord frets to the total cost of the chord change.
Both of these changes seemed to work out fairly well. Here is the new
best fingering:
1 1 1 3 1 3 2 4 2 3 1 4 +-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+ | | o o o | 1 | | o | o | 1 | | | | o | 2 +-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+ | | | | | | | | | o | o | | o o | | +-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+ | | | | | o | | | | | | | | | | | o +-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+ x x x x x x
Even with these solutions, there is still room for improvement. Since I used fixed fingerings from the guitar book as my ``good'' fingerings, my program wasn't able to figure out that it would be easier to finger the second chord as a bar across fret 1, and just put down finger 2 on the G string and move 3 from the 3rd fret down to 2 - giving 1 2 1 3 as the fingering for the same notes played. Had it done that, it would be easy to move to the third chord by moving the first finger bar up one fret, shifting 2 and 3 over to the new strings and putting 4 down.
It is perhaps interesting that none of the 3 ``best'' solutions included the one that is used in the recording, which I have painfully transcribed as this:
1 2 3 1 2 1 3 1 2 1 3 4 2 1 3 4 +-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+ o | | | o | 4 | | o | o | 4 | | | | | | 5 | | o | | | 5 +-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+ | | o o | | o | | o | | o | o o o | o | | o o | +-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+ | | | | | | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+ x x x x x x x x
Among similarities, however, one notes that in the recording, the artist heeds the string changing tabu. The same 4 strings are used in the first 4 chords. Each of my 3 best fingerings do this as well (although not the same 4 strings).
There are many things that still need to be done. Some of them need to be done to consider this a complete program. The others need to be done to make it a useful program.
For completeness, the program needs to be generalized to an arbitrary sized input chord sequence. This would entail working on the ``better search problem'' mentioned earlier. Right now, while the program is syntactically able to run arbitrarily long chord sequences, it would be infeasible to give it more than say 5 or 6. Perhaps it could use different search techniques based on how large the input is. Small inputs could go ahead and perform optimal exhaustive search while larger inputs would perform other search techniques (like a dynamic programming approach that finds the best fingering between all pairs then uses that to find the best fingering between all triples, etc).
Another completeness item that needs to be done is the finishing of the first part of the program (the generation of ``good'' chords) and its incorporation into this program. I am not sure how important this really is because there is no reason why the generation of ``good'' chords should be done more than once (unless the user wants to change the heuristics that were used to determine them). Otherwise, there would seem to be no problem with just using a pre-computed database of good chords (which is what I did here).
One of the usefulness items needed is for me to finish implementing the ``hinting'' feature. The framework for it is already there in my non-finished first part of the program but there are still some details to work out in merging it with the second stage of the program.
There are 2 more features that would be really nice to add. One would be to add an easy way for a naive user to customize the cost function to suit his needs because it may turn out that the decision criteria should be different for different people. There are two examples that immediately come to mind. One, a person with fleshy figures would prefer bar chords (one finger bars across the whole neck) where a person with boney fingers would rank bar chords less desirable. Another might be that a person prefers chord sequences further up or further down on the neck for different reasons. One might be because they are playing a duet with another guitarist and want to play a higher part or another would be that it is easier to hold the strings down because they are closer to the fingerboard (as is the case on an classical acoustic guitar).
The other fun feature would be to have the program actually generate one of these tablature diagrams as opposed to giving the answer as a vector of pairs of integers.
As a pie-in-the-sky feature, it would be nice if I could write the output as a standard MIDI file and therefore play the resulting chords on a MIDI musical instrument (e.g. a digital sampling synthesizer that has a convincing acoustic guitar sound).
The other 2 best fingerings were:
1 4 2 3 2 4 1 3 2 3 1 1
+-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+
o | | | | | 4 | | o | | | 4 | | o o | | 3
+-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+
| | o o | | o | | o | | o o | | | |
+-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+
| o | | | | | o | | | | | | | | | |
+-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+
x x x x x x
1 3 2 4 2 3 1 4 2 3 1 4
+-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+
| o | | | | 11 | | | o | | 11 | | | o | | 10
+-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+
| | | o | | | o | | | | | o o | o |
+-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+
| | o | o | | | o | o | | | | | | |
+-+-+-+-+-+ +-+-+-+-+-+ +-+-+-+-+-+
x x x x x x