Google Sheets OPR Calculator

[Ether]

Originally Posted by Rachel Lim

If you have any other suggestions on what else would be helpful, let me know

Can you post a brief overview of the method/algorithm you are using to compute OPR?

For example, are you forming the normal equations matrix N (square positive definite TxT matrix, where T is the number of teams) directly from the match scores data?

Or are you forming the 2MxT binary design matrix A (where M is the number of matches)?

Once you have N (or A), how are you using that to compute OPR?

.

[nuclearnerd]

You have to make a private copy of the sheet in order to be able to view / edit the code. I haven't looked at the algorithm myself, but I've pasted the code below.

BTW, thanks for this - it's nice to have a portable calculator to use. I've been meaning to write one forever, but I never get to it and have to rely on other people posting OPR databases to CD.

function onEdit(e) {
  var s = e.source.getActiveSheet();
  if(e.range.getA1Notation() == 'L14' && s.getSheetName() == 'data') {
    if(e.value == 'calculate OPR') {
      calculateOPR();
    }
    else if(e.value == 'update OPR') {
      updateOPR();
    }
    else if(e.value == 'clear data') {
      clearData();
    }
    e.range.clearContent();
  }
}

// *** create custom menu ***
// same functionality as drop down menu or buttons
function onOpen() {
  var ui = SpreadsheetApp.getUi();
  ui.createMenu('OPR calculations')
  .addItem('calculate OPR', 'calculateOPR')
  .addItem('update OPR', 'updateOPR')
  .addItem('clear data', 'clearData')
  .addToUi();
}


// *** calculates OPR from scratch ***
// input: alliances and scores in data tab:
// red1 red2 red3 blue1 blue2 blue3 redScore blueScore
// misc: sparse matrix and scores in data tab:
// team1 team2 team3 team4 ... teamN allianceScore      (teamX either 0 or 1 depending on whether they played that match)
// output: teams and OPRs, sorted ascending
// team1 OPR1
function calculateOPR() {
  var data = SpreadsheetApp.getActive().getSheetByName('data');
  var misc = SpreadsheetApp.getActive().getSheetByName('misc');
  var OPR = SpreadsheetApp.getActive().getSheetByName('OPR');
  
  var numMatches = data.getDataRange().getNumRows()-1; // number of matches
  var values = data.getRange(2, 1, numMatches, 8).getValues(); //get all data
  var scores = new Array();
  var teams = new Array();
  var alliances = new Array(3);
  for(var x = 0; x < 3; x++) {
    alliances[x] = new Array(numMatches*2);
  }
  var c = 0;
  var d = 0;
  
  // clear previous data
  clearCells();

  // create team, alliances, and score matrices
  for(var x = 0; x < numMatches; x++) {
    // list of all unique teams: team1 \n team2 \n ...
    for(var y = 0; y < 6; y++) {
      var unique = true;
      for(var z = 0; z < d+1; z++) {
        if(values[x][y] == teams[z]) {
          unique = false;
          break;
        }
      }
      if(unique == true) {
        teams[d] = values[x][y];
        d++;
      }
    }
    // list of all alliances: red \n blue \n ...
    for(var y = 0; y < 3; y++) {
      alliances[y][2*x] = values[x][y];
    }
    for(var y = 3; y < 6; y++) {
      alliances[y-3][2*x+1] = values[x][y];
    }
    // list of all scores: redScore \n blueScore \n ...
    for(var y = 6; y < 8; y++) {
      scores[c] = values[x][y];
      c++;
    }
  }
  
  // sort teams
  teams.sort(function(a, b) {return a - b;})
  // print out T matrix
  for(var x = 0; x < teams.length; x++) {
    OPR.getRange(x+2, 1).setValue(teams[x]);
  }
  
  // print out A matrix
  for(var x = 0; x < numMatches*2; x++) {
    for(var y = 0; y < teams.length; y++) {
      misc.getRange(x+1, y+1).setValue(0);
      for(var z = 0; z < 3; z++) { 
        if(alliances[z][x] == teams[y]) {
          misc.getRange(x+1, y+1).setValue(1);
          break;
        }
      }
    }
  }
  
  // print out b matrix
  for(var x = 0; x < numMatches*2; x++) {
    misc.getRange(x+1, teams.length+1).setValue(scores[x]);
  }
  
  // create and print formula
  var formula = createFormula(teams.length, numMatches);
  OPR.getRange(2, 2).setFormula(formula);
}


// *** updates OPR ***
// must have previously calculated with all teams
function updateOPR() {
  var data = SpreadsheetApp.getActive().getSheetByName('data');
  var misc = SpreadsheetApp.getActive().getSheetByName('misc');
  var OPR = SpreadsheetApp.getActive().getSheetByName('OPR');
   
  var numOldMatches = (misc.getDataRange().getNumRows())/2; // number of matches in previous calculation
  var numNewMatches = data.getDataRange().getNumRows() - 1; // current number of matches
  var numTeams = OPR.getDataRange().getNumRows() - 1; // number of teams
  
  
  var teams = OPR.getRange(2, 1, numTeams, 1).getValues();
  var matches = data.getRange(numOldMatches+2, 1, numNewMatches-numOldMatches+1, 8).getValues();
  
  // update A matrix
  for(var x = 0; x < numNewMatches-numOldMatches; x++) {
    for(var y = 0; y < numTeams; y++) {
      misc.getRange(2*numOldMatches + 2*x + 1, y+1).setValue(0);
      misc.getRange(2*numOldMatches + 2*x + 2, y+1).setValue(0);
      for(var z = 0; z < 3; z++) {
        if(matches[x][z] == teams[y]) {
           misc.getRange(2*numOldMatches + 2*x + 1, y+1).setValue(1);
        }
      }
      for(var z = 3; z < 6; z++) {
        if(matches[x][z] == teams[y]) {
          misc.getRange(2*numOldMatches + 2*x + 2, y+1).setValue(1);
        }
      }
    }
    misc.getRange(2*numOldMatches + 2*x + 1, teams.length+1).setValue(matches[x][6]);
    misc.getRange(2*numOldMatches + 2*x + 2, teams.length+1).setValue(matches[x][7]);
  }
  
  var formula = createFormula(numTeams, numNewMatches);
  OPR.getRange(2, 2).setFormula(formula);
}


// *** clears all non-header cells (data, misc, OPR tabs) ***
function clearData() {
  var data = SpreadsheetApp.getActive().getSheetByName('data');
  var rows = data.getDataRange().getNumRows();
  
  clearCells();
  data.getRange(2, 1, rows, 8).clearContent();
}


// input: integer (0, 1, ... 25, 26, 26, etc.)
// output: letter (A, B, ... Z, AA, AB, etc.)
// can only take up to ZZ
function columnToLetter(num) {
  var letter, letter1, letter2;
  if(num < 26) {
    letter = String.fromCharCode(65 + num);
  }
  else {
    letter1 = String.fromCharCode(65 + num/26 - 1);
    letter2 = String.fromCharCode(65 + num%26);
    letter = letter1 + letter2;
  }
  return letter;
}

// input: number of teams, number of matches
// output: formula
function createFormula(numTeams, numMatches) {
  var aRange = 'misc!A1:' + columnToLetter(numTeams-1) + numMatches*2;
  var bRange = 'misc!' + columnToLetter(numTeams) + '1:' + columnToLetter(numTeams) + numMatches*2;
  var formula = '=mmult(minverse(mmult(transpose(' + aRange + '), ' + aRange + ')), mmult(transpose(' + aRange + '), ' + bRange + '))';
  return formula;
}


// clears data from misc and OPR tabs (for calculations)
function clearCells() {
  var misc = SpreadsheetApp.getActive().getSheetByName('misc');
  var OPR = SpreadsheetApp.getActive().getSheetByName('OPR');
  var rows = OPR.getDataRange().getNumRows();
  
  misc.getDataRange().clearContent();
  OPR.getRange(2, 1, rows, 2).clearContent();
}

[CVR]

Rachel,

the IMPORTHTML function in google docs might be very useful to you. I've used it during many competitions to pull data from TBA and analyze it in Google Sheets.

If you put

=IMPORTHTML("https://www.thebluealliance.com/event/2016onwa","table",1)

in your google sheet, it'll pull the match results data from TBA and put it directly into the sheet. The format is a bit strange, but that can be dealt with easily enough.

I can't seem to find any of my spreadsheets, but there is a way you can have it auto-update the function. It will then load any new data from TBA, which is great for crunching numbers during competitions. Want to know what an alliance member's opr is in an upcoming match, even if this is their first event and they've only played 5 matches? Easy. (although the number may not be accurate... opr caveats and all that)

It also has the advantage of allowing you to change events (and even years) very easily since TBA uses a consistent url scheme.

[Rachel Lim]

Originally Posted by CVR

Rachel,

the IMPORTHTML function in google docs might be very useful to you. I've used it during many competitions to pull data from TBA and analyze it in Google Sheets.

If you put

=IMPORTHTML("https://www.thebluealliance.com/event/2016onwa","table",1)

in your google sheet, it'll pull the match results data from TBA and put it directly into the sheet. The format is a bit strange, but that can be dealt with easily enough.

I can't seem to find any of my spreadsheets, but there is a way you can have it auto-update the function. It will then load any new data from TBA, which is great for crunching numbers during competitions. Want to know what an alliance member's opr is in an upcoming match, even if this is their first event and they've only played 5 matches? Easy. (although the number may not be accurate... opr caveats and all that)

It also has the advantage of allowing you to change events (and even years) very easily since TBA uses a consistent url scheme.

Thank you! I'd found the UrlFetchApp class but it sounds like this might be easier, and I'll definitely look into including it.

[Rachel Lim]

Originally Posted by Ether

Can you post a brief overview of the method/algorithm you are using to compute OPR?

For example, are you forming the normal equations matrix N (square positive definite TxT matrix, where T is the number of teams) directly from the match scores data?

Or are you forming the 2MxT binary design matrix A (where M is the number of matches)?

Once you have N (or A), how are you using that to compute OPR?

.

I'm forming matrices A, b, and T: T is the list of teams (Tx1), b is the list of scores (2Mx1), and A is a matrix of which teams were playing which matches represented as 0s and 1s (2MxT). I think that's the same A you're referring to, but if not, A was created so that if team2, team3, and team5 played a match and got 100 points at an event with 10 teams, that row in the matrix would look like this:

0 1 1 0 1 0 0 0 0 0

And that row in b would be 100.

A and b are printed into the "misc" tab (b is the right-most column). T is printed directly into row 1 of the OPR tab. The equation to solve for OPR is put into the second row of the OPR tab:

=mmult(minverse(mmult(transpose(misc!A1:CX408), misc!A1:CX408)), mmult(transpose(misc!A1:CX408), misc!CY1:CY408))

which is the line (A'*A)\(A'*b) in your octave/matlab code


For anyone confused over what those equations do, it's just solving the following equation:




That equation is generated in the code because the size/location of the matrices varies (the one above is for MICMP data), which as Brendan said, you can access by making a copy of the sheet.


If that doesn't answer your question or I wasn't clear about something please let me know.

[Caleb Sykes]

Do you have a good idea of which operation(s) are taking up the most time for your program? You mentioned 45 seconds total runtime earlier, if you could break this down a bit more we could find out where to make improvements.

Most of this time probably comes from the createFormula function, but it would be good to check before working on alternative solutions to the [A][x]=[b] equation.

[Ether]

Originally Posted by Rachel Lim

I'm forming matrices A, b, and T: T is the list of teams (Tx1), b is the list of scores (2Mx1), and A is a matrix of which teams were playing which matches represented as 0s and 1s (2MxT). I think that's the same A you're referring to...

Yes, that is called the "design matrix" of the system of linear equations. In the case of FRC OPR, it is dichotomous (binary) and very sparse.

The equation to solve for OPR is put into the second row of the OPR tab:

=mmult(minverse(mmult(transpose(misc!A1:CX408), misc!A1:CX408)), mmult(transpose(misc!A1:CX408), misc!CY1:CY408))

That may well be your problem right there.

Try replacing that entire mess with one call to the LINEST function of Google Sheets.


EDIT: make sure the 3rd parameter in the LINEST function call is FALSE.

[Ether]

LINEST(alliance_scores_column_vector, 2M-by-T_design_matrix_A, FALSE, TRUE)

If that last parameter is true, you get not only the least-squares model coefficients (OPRs), but also a lot of extra statistics (that you may or may not want).

[Ether]

If you find that your code for creating A, b, and T is the time-consuming culprit, try creating the T-by-T N matrix and the T-by-1 d column vector directly, rather than computing them from A and b.

[Rachel Lim]

Originally Posted by Caleb Sykes

Do you have a good idea of which operation(s) are taking up the most time for your program? You mentioned 45 seconds total runtime earlier, if you could break this down a bit more we could find out where to make improvements.

Most of this time probably comes from the createFormula function, but it would be good to check before working on alternative solutions to the [A][x]=[b] equation.

My last run took about 50 seconds to finish, approximately broken down as follows:

1sec: get sheets, get ranges, initialize arrays, etc.
23sec: get unique team list, get alliance teams (T) and scores (b) in 2Mx3 and 2Mx1 formats respectively
printing team list was nearly instantaneous so I couldn't get a time on that
25sec: creating and printing out A matrix (2MxT)
printing b, creating/printing the formula, and doing the calculations for the formula were all very fast (i.e. fast enough I couldn't time them)

These times were all done by hand, I'll see tonight if I can add in a timer, but I think these give the rough percentages. I believe most of the time is taken up by looping through arrays, especially T while looking for unique teams and creating the A matrix. I could probably print A and b directly instead of creating the alliances/scores arrays which would save some time. If you have any suggestions on what else to try, let me know.

Originally Posted by Ether

LINEST(alliance_scores_column_vector, 2M-by-T_design_matrix_A, FALSE, TRUE)

If that last parameter is true, you get not only the least-squares model coefficients (OPRs), but also a lot of extra statistics (that you may or may not want).

I don't think much time is actually taken by the final calculation, but this is definitely cleaner.
However, is there a reason this is giving me team OPRs in the reverse transpose of the team vector? (And a reason for the added zero at the end?)

(i.e. i'm getting teamNOPR, teamN-1OPR, ... team1OPR, 0 instead of team1OPR \n team2OPR \n ... teamNOPR. I did take the transpose to flip it, but it's still upside down)

Originally Posted by Ether

If you find that your code for creating A, b, and T is the time-consuming culprit, try creating the T-by-T N matrix and the T-by-1 d column vector directly, rather than computing them from A and b.

Is N = [A^T][A], where each row corresponds to the sum of all the rows from A where a given team played? (and thus d is [A^T][b], or the sum of all the alliance scores from matches where that team played)

I'm not sure if this would necessarily be much faster, since it'd still require looping through the team matrix to form N (and now it'd require it to form d too), but I can definitely try it.

[Caleb Sykes]

Originally Posted by Rachel Lim

These times were all done by hand, I'll see tonight if I can add in a timer, but I think these give the rough percentages. I believe most of the time is taken up by looping through arrays, especially T while looking for unique teams and creating the A matrix. I could probably print A and b directly instead of creating the alliances/scores arrays which would save some time. If you have any suggestions on what else to try, let me know.

Here would be my suggestions for speeding up the unique team search and creating the A matrix:
Unique team search: Make an array of size 6*(matches), let's call it [C].
Place every team from the match list into a unique spot in this array.
Sort [C]
Either delete duplicates within [C] or map unique teams into your "teams" matrix.
This process should go much faster than your current method goes, and it has the added bonus of giving you a sorted list so you don't have to sort it later.

Creating the A matrix:
Create a LUT that maps teams to their index in the sorted "teams" matrix.
Set all entries of the A matrix to zero.
Fill the A matrix using something like this (pseudocode):

for each half-match
    for each team in the half-match
        A[half-match number][LUT(team)] = 1
    end for
end for

This should also save time since you are cycling through far fewer values.

[Ether]

Originally Posted by Rachel Lim

I believe most of the time is taken up by looping through arrays, especially T while looking for unique teams and creating the A matrix.

There should be no looping involved.

Here's some pseudo-code which creates A, b, and T with one non-looping pass thru the 8column data

//one pass thru the 8col data;
//for each row do the following:
 
//populate the b column vector (alliance scores):
b[++ib]=rs; b[++ib]=bs; 

//assign a unique Column Number to each team:
f1(r1); f1(r2); f1(r3); f1(b1); f1(b2); f1(b3);
  

//populate the A matrix:
row++;
A[row,aTeamCol[r1]]=1;
A[row,aTeamCol[r2]]=1;
A[row,aTeamCol[r3]]=1;
row++;
A[row,aTeamCol[b1]]=1;
A[row,aTeamCol[b2]]=1;
A[row,aTeamCol[b3]]=1;


function f1(n:word); //n is team number
 if aTeamCol[n]==0 { Col++; aTeamCol[n]=Col; T[Col]=n }

[Ether]

Originally Posted by Ether

There should be no looping involved.

Here's some pseudo-code which creates A, b, and T with one non-looping pass thru the 8column data

I just ran that code on my 10-year-old desktop PC using a simple non-compiled (scripting) language.

It took 220 milliseconds to read your 8column data (102 teams and 204 matches)
from a disk file and populate A, b, and T.

I would hope Google's scripting language could do the same in a comparable time.

[Ether]

Originally Posted by Ether

Here's some pseudo-code which creates A, b, and T with one non-looping pass thru the 8column data

Compute the OPR column vector using LINEST on A and b, and place it next to the T column vector (actual team numbers), so you can sort by OPR or Team Number if you like.

[Rachel Lim]

Originally Posted by Caleb Sykes

Here would be my suggestions for speeding up the unique team search and creating the A matrix:
[...]

Originally Posted by Ether

There should be no looping involved.

Here's some pseudo-code which creates A, b, and T with one non-looping pass thru the 8column data

[...]

Thank you both for your suggestions--I really appreciate the help. I finally had some time to go through them, and combined both suggestions (or at least think I did) in the code below. I'm not sure if this is what the aTeamCol[] did, but I created another array to map teams to indexes (i.e. teamIndex[teamNum] = index, where teams[index] = teamNum). The new times I logged were as follows (I'm excluding the initialization time since it varies greatly each time I run it, which I suspect it has to do with my wifi connection because it runs much faster at home than when I'm out):

printing T (creating full team list, sorting it, getting unique values, printing) is too fast to time manually
printing b and A: ~21sec to create/print both
printing formula: fast

One weird thing I noted is that the first 188 rows of A (first 94 matches) are printed very quickly, then there's a long pause (at least 15sec the last time I ran it) before the remaining lines are printed. I'm not sure what's behind this, but I'll look into it more.

function calculateOPR2() {
  var data = SpreadsheetApp.getActive().getSheetByName('data');
  var misc = SpreadsheetApp.getActive().getSheetByName('misc');
  var OPR = SpreadsheetApp.getActive().getSheetByName('OPR');
  
  var numMatches = data.getDataRange().getNumRows()-1; // number of matches
  var alliances = data.getRange(2, 1, numMatches, 8).getValues(); //get all data
  var allTeams = new Array();
  var teams = new Array();
  var teamIndex = new Array();
  var c = 0;
  
  data.getRange(1, 14).setValue('done initializing');

  // list of all teams
  for(var x = 0; x < numMatches; x++) {
    for(var y = 0; y < 6; y++) {
      allTeams[c] = alliances[x][y];
      c++;
    }
  }
  
  data.getRange(2, 14).setValue('list of all teams');
  
  // sorts all teams
  allTeams.sort(function(a, b) {return a - b;})
  data.getRange(3, 14).setValue('list of sorted teams');
  
  // list of all unique teams;
  c = 1;
  teams[0] = allTeams[0];
  teamIndex[teams[0]] = 0;
  OPR.getRange(2, 1).setValue(teams[0]);
  for(var x = 1; x < allTeams.length; x++) {
    if(allTeams[x] != allTeams[x-1]) {
      teams[c] = allTeams[x];
      teamIndex[teams[c]] = c;
      OPR.getRange(c+2, 1).setValue(teams[c]);
      c++;
    }
  }
  
  data.getRange(3, 14).setValue('list of unique teams');
  
  for(var x = 0; x < numMatches; x++) {
    // create and set b
    misc.getRange(2*x+1, teams.length+1).setValue(alliances[x][6]);
    misc.getRange(2*x+2, teams.length+1).setValue(alliances[x][7]);
    
    // create and set A
    for(var y = 0; y < teams.length; y++) {
      misc.getRange(2*x+1, y+1).setValue(0);
      misc.getRange(2*x+2, y+1).setValue(0);
    }
    misc.getRange(2*x+1, teamIndex[(alliances[x][0])]+1).setValue(1);
    misc.getRange(2*x+1, teamIndex[(alliances[x][1])]+1).setValue(1);
    misc.getRange(2*x+1, teamIndex[(alliances[x][2])]+1).setValue(1);
    misc.getRange(2*x+2, teamIndex[(alliances[x][3])]+1).setValue(1);
    misc.getRange(2*x+2, teamIndex[(alliances[x][4])]+1).setValue(1);
    misc.getRange(2*x+2, teamIndex[(alliances[x][5])]+1).setValue(1);
  }
  
  var formula = createFormula(teams.length, numMatches);
  OPR.getRange(2, 2).setFormula(formula);
}

Originally Posted by Ether

I just ran that code on my 10-year-old desktop PC using a simple non-compiled (scripting) language.

It took 220 milliseconds to read your 8column data (102 teams and 204 matches)
from a disk file and populate A, b, and T.

I would hope Google's scripting language could do the same in a comparable time.

I'm not sure what the time to create the matrices is exactly, but I'll try to time the difference between creating them and printing them sometime soon. I don't know how much time is taken up by printing to the spreadsheet, but that may account for some of the differences, because I've run similar programs to this outside of google scripts, with even larger data sets, and it's significantly faster.