Determine the key of a song by its chords

How can I programmatically find the key of a song just by knowing the chord sequence of the song?
I asked some people how they would determine the key of a song and they all said they do it 'by ear' or by 'trial and error' and by telling if a chord resolves a song or not... For the average musician that is probably fine, but as a programmer that really isn't the answer that I was looking for.

So I started looking for music related libraries to see if anyone else has written an algorithm for that yet. But although I found a really big library called 'tonal' on GitHub: https://danigb.github.io/tonal/api/index.html I couldn't find a method that would accept an array of chords and return the key.

My language of choice will be JavaScript (NodeJs), but I'm not necessarily looking for a JavaScript answer. Pseudo code or an explanation that can be translated into code without too much trouble would be totally fine.

As some of you mentioned correctly, the key in a song can change. I'm not sure if a change in key could be detected reliably enough. So, for now let's just say, I'm looking for an algorithm that makes a good approximation on the key of a given chord sequence.

... After looking into the circle of fifths, I think I found a pattern to find all chords that belong to each key. I wrote a function getChordsFromKey(key) for that. And by checking the chords of a chord sequence against every key, I can create an array containing probabilities of how likely it is that the key matches the given chord sequence: calculateKeyProbabilities(chordSequence). And then I added another function estimateKey(chordSequence), which takes the keys with the highest probability-score and then checks if the last chord of the chord sequence is one of them. If that is the case, it returns an array containing only that chord, otherwise it returns an array of all chords with the highest probability-score. This does an OK job, but it still doesn't find the correct key for a lot of songs or returns multiple keys with equal probabililty. The main problem being chords like A5, Asus2, A+, A°, A7sus4, Am7b5, Aadd9, Adim, C/G etc. that are not in the circle of fifths. And the fact that for instance the key C contains the exact same chords as the key Am, and G the same as Em and so on...
Here is my code:

'use strict'
const normalizeMap = {
    "Cb":"B",  "Db":"C#",  "Eb":"D#", "Fb":"E",  "Gb":"F#", "Ab":"G#", "Bb":"A#",  "E#":"F",  "B#":"C",
    "Cbm":"Bm","Dbm":"C#m","Eb":"D#m","Fbm":"Em","Gb":"F#m","Ab":"G#m","Bbm":"A#m","E#m":"Fm","B#m":"Cm"
}
const circleOfFifths = {
    majors: ['C', 'G', 'D', 'A',  'E',  'B',  'F#', 'C#', 'G#','D#','A#','F'],
    minors: ['Am','Em','Bm','F#m','C#m','G#m','D#m','A#m','Fm','Cm','Gm','Dm']
}

function estimateKey(chordSequence) {
    let keyProbabilities = calculateKeyProbabilities(chordSequence)
    let maxProbability = Math.max(...Object.keys(keyProbabilities).map(k=>keyProbabilities[k]))
    let mostLikelyKeys = Object.keys(keyProbabilities).filter(k=>keyProbabilities[k]===maxProbability)

    let lastChord = chordSequence[chordSequence.length-1]

    if (mostLikelyKeys.includes(lastChord))
         mostLikelyKeys = [lastChord]
    return mostLikelyKeys
}

function calculateKeyProbabilities(chordSequence) {
    const usedChords = [ ...new Set(chordSequence) ] // filter out duplicates
    let keyProbabilities = []
    const keyList = circleOfFifths.majors.concat(circleOfFifths.minors)
    keyList.forEach(key=>{
        const chords = getChordsFromKey(key)
        let matchCount = 0
        //usedChords.forEach(usedChord=>{
        //    if (chords.includes(usedChord))
        //        matchCount++
        //})
        chords.forEach(chord=>{
            if (usedChords.includes(chord))
                matchCount++
        })
        keyProbabilities[key] = matchCount / usedChords.length
    })
    return keyProbabilities
}

function getChordsFromKey(key) {
    key = normalizeMap[key] || key
    const keyPos = circleOfFifths.majors.includes(key) ? circleOfFifths.majors.indexOf(key) : circleOfFifths.minors.indexOf(key)
    let chordPositions = [keyPos, keyPos-1, keyPos+1]
    // since it's the CIRCLE of fifths we have to remap the positions if they are outside of the array
    chordPositions = chordPositions.map(pos=>{
        if (pos > 11)
            return pos-12
        else if (pos < 0)
            return pos+12
        else
            return pos
    })
    let chords = []
    chordPositions.forEach(pos=>{
        chords.push(circleOfFifths.majors[pos])
        chords.push(circleOfFifths.minors[pos])
    })
    return chords
}

// TEST

//console.log(getChordsFromKey('C'))
const chordSequence = ['Em','G','D','C','Em','G','D','Am','Em','G','D','C','Am','Bm','C','Am','Bm','C','Em','C','D','Em','Em','C','D','Em','Em','C','D','Em','Em','C','D','Am','Am','Em','C','D','Em','Em','C','D','Em','Em','C','D','Em','Em','C','D','Em','Em','C','D','Em','Em','C','D','Em','Em','C','D','Em','Em','C','D','Em']

const key = estimateKey(chordSequence)
console.log('Example chord sequence:',JSON.stringify(chordSequence))
console.log('Estimated key:',JSON.stringify(key)) // Output: [ 'Em' ]

Solution

One approach would be to find all the notes being played, and compare to the signature of different scales and see which is the best match.

Normally a scale signature is pretty unique. A natural minor scale will have the same notes as a major scale (that is true for all the modes), but generally when we say minor scale we mean the harmonic minor scale, which has a specific signature.

So comparing what notes are in the chords with your different scales should give you a good estimate. And you could refine by adding some weight to different notes (for example the ones that come up the most, or the first and last chords, the tonic of each chord, etc.)

This seems to handle most basic cases with some accuracy:

'use strict'
const allnotes = [
  "C", "C#", "D", "Eb", "E", "F", "F#", "G", "Ab", "A", "Bb", "B"
]

// you define the scales you want to validate for, with name and intervals
const scales = [{
  name: 'major',
  int: [2, 4, 5, 7, 9, 11]
}, {
  name: 'minor',
  int: [2, 3, 5, 7, 8, 11]
}];

// you define which chord you accept. This is easily extensible,
// only limitation is you need to have a unique regexp, so
// there's not confusion.

const chordsDef = {
  major: {
    intervals: [4, 7],
    reg: /^[A-G]$|[A-G](?=[#b])/
  },
  minor: {
    intervals: [3, 7],
    reg: /^[A-G][#b]?[m]/
  },
  dom7: {
    intervals: [4, 7, 10],
    reg: /^[A-G][#b]?[7]/
  }
}

var notesArray = [];

// just a helper function to handle looping all notes array
function convertIndex(index) {
  return index < 12 ? index : index - 12;
}


// here you find the type of chord from your 
// chord string, based on each regexp signature
function getNotesFromChords(chordString) {

  var curChord, noteIndex;
  for (let chord in chordsDef) {
    if (chordsDef[chord].reg.test(chordString)) {
      var chordType = chordsDef[chord];
      break;
    }
  }

  noteIndex = allnotes.indexOf(chordString.match(/^[A-G][#b]?/)[0]);
  addNotesFromChord(notesArray, noteIndex, chordType)

}

// then you add the notes from the chord to your array
// this is based on the interval signature of each chord.
// By adding definitions to chordsDef, you can handle as
// many chords as you want, as long as they have a unique regexp signature
function addNotesFromChord(arr, noteIndex, chordType) {

  if (notesArray.indexOf(allnotes[convertIndex(noteIndex)]) == -1) {
    notesArray.push(allnotes[convertIndex(noteIndex)])
  }
  chordType.intervals.forEach(function(int) {

    if (notesArray.indexOf(allnotes[noteIndex + int]) == -1) {
      notesArray.push(allnotes[convertIndex(noteIndex + int)])
    }

  });

}

// once your array is populated you check each scale
// and match the notes in your array to each,
// giving scores depending on the number of matches.
// This one doesn't penalize for notes in the array that are
// not in the scale, this could maybe improve a bit.
// Also there's no weight, no a note appearing only once
// will have the same weight as a note that is recurrent. 
// This could easily be tweaked to get more accuracy.
function compareScalesAndNotes(notesArray) {
  var bestGuess = [{
    score: 0
  }];
  allnotes.forEach(function(note, i) {
    scales.forEach(function(scale) {
      var score = 0;
      score += notesArray.indexOf(note) != -1 ? 1 : 0;
      scale.int.forEach(function(noteInt) {
        // console.log(allnotes[convertIndex(noteInt + i)], scale)

        score += notesArray.indexOf(allnotes[convertIndex(noteInt + i)]) != -1 ? 1 : 0;

      });

      // you always keep the highest score (or scores)
      if (bestGuess[0].score < score) {

        bestGuess = [{
          score: score,
          key: note,
          type: scale.name
        }];
      } else if (bestGuess[0].score == score) {
        bestGuess.push({
          score: score,
          key: note,
          type: scale.name
        })
      }



    })
  })
  return bestGuess;

}


document.getElementById('showguess').addEventListener('click', function(e) {
  notesArray = [];
  var chords = document.getElementById('chodseq').value.replace(/ /g,'').replace(/["']/g,'').split(',');
  chords.forEach(function(chord) {
    getNotesFromChords(chord)
  });
  var guesses = compareScalesAndNotes(notesArray);
  var alertText = "Probable key is:";
  guesses.forEach(function(guess, i) {
    alertText += (i > 0 ? " or " : " ") + guess.key + ' ' + guess.type;
  });
  
  alert(alertText)
  
})

<input type="text" id="chodseq" />

<button id="showguess">
Click to guess the key
</button>

For your example, it gives G major, that's because with a harmonic minor scale, there are no D major or Bm chords.

You can try easy ones: C, F, G or Eb, Fm, Gm

Or some with accidents: C, D7, G7 (this one will give you 2 guesses, because there's a real ambiguity, without giving more information, it could be both)

One with accidents but accurate: C, Dm, G, A