OPR Formula
 

This is going to sound extremely stupid, but what is the formula for OPR?

Thanks in advance.

Re: OPR Formula
 

That is not a stupid question.

OPR is actually a system of simultaneous equations. The difficulty lies in solving that many simultaneous equations.

For instance. In a standard district event in Michigan, there might be 80 matches.

Each match has equations that lay out like this:
Robot_1_score+Robot_2_score+Robot_3_score=Red_Scor e
Robot_4_score+Robot_5_score+Robot_6_score=Blue_Sco re

So, in the end you'll have a system with 160 equations, and 40 variables (each robot is one variable, as shown in the equations above). The trick is solving those equations. Until just recently, excel didn't have the firepower to do it unless you used macros. However, with the newer versions, the Matrix formulas are powerful enough to do it. Keep in mind this isn't like algebra - the computer has to iterate to find an answer.

This is not a simple process. It is fairly complicated. Look up "solving simultaneous equations using matrices" in excel, and you should be able to find some examples. That is how we wrote our OPR. It requires pretty in-depth knowledge of excel though. You'll have to understand named arrays, matrix math functions, and array formulas.

2834 the Bionic Barons put out an awesome OPR sheet that handles the calculations through some open-source macro code. It is far more complex (to me) than using matrix formulae, because I have never used macros and vb programming in excel.

Of course, programs like matlab have more advanced equation solvers and you may be able to easily write a program to perform the calculations.

Re: OPR Formula
 

Tom,

I've done a fair amount of work with large overdetermined systems of equations (20,000 equations in 6,000 variables).

I'd like to play around with some of this data. Maybe I could write and post a small app. Do you know where I could get a couple of CSV, or whitespace-delimited, or fixed-field text files from 2011?

Thanks.

Re: OPR Formula
 

I believe you can copy and paste from the old scores on the FIRST website. For instance, here:

http://www2.usfirst.org/2011comp/eve...chresults.html

That is how I developed ours. I've never tried to do the whole web-scrape or download the scores automatically as they are posted by FIRST. If, however, someone could explain how that's done it would be absolutely wonderful!

Re: OPR Formula
 

In newer versions of Excel, go to the Data tab, and then click (under Get External Data - left most panel) "From Web". Then, you can put the URL of the results page into the little browser window that pops up and then select the table with match results. To refresh, click "Refresh All" in the Connections pane (still on the data tab).

Re: OPR Formula
 

Also, the FIRST FMS system uploads its data in twitter posts under @frcfms so you could scrape a lot more data from that since it tells of penalties point total for instance.

Re: OPR Formula
 

Is there a CSV or whitespace-delimited or fixed-field text file somewhere that has all the scores from all the matches around the country (world) in one file for 2011?

Re: OPR Formula
 

How's this? I just threw it together by scraping all the competitions and putting them in one big file.

Also, some fun facts I found:
- there were 5,258 FRC matches played in 2011
- There were 357,981 points scored total
- The average individual alliance score was 34.04 points
- The average total number of points per match was 68.08311145 points
- The highest alliance score was 147 points

Re: OPR Formula
 

Many thanks for all the info. Can I assume the same basic principles hold true with DPR as well?

Re: OPR Formula
 

I was not aware of this. Would someone be able to tap this data during the tournament to feed it into a scouting program? How much information is available there?

Also, I know OPR means offensive power rating, but what does this actually mean?

Re: OPR Formula
 

IIRC, OPR is the expected points contribution of any given robot to an alliance.

DPR... I don't think anybody's ever come up with a good way to calculate that. First you have to find a way to calculate a defensive score...

Re: OPR Formula
 

Couldn't you do it the same way Tom said he did the OPR, with the following twist?

Set up the equations like so:

red1+red2+red3 = blue_alliance_score

... then solve the system.

The lower the number, the better the DPR. Like golf.

Re: OPR Formula
 

If you want to learn more about OPR, CCWM, DPR, PMR, please refer to

http://www.chiefdelphi.com/media/papers/2174

I will post an updated 2012 version of the presentation file shortly.

Re: OPR Formula
 

Possibly. The hardest part about DPR is that a low blue_alliance_score could come from two possible sources. It could be that one or more red robots are playing really good defense. But, it could be that the blue alliance has a very low combined OPR (read: needs better offense even without defense being played). Without having an OPR-to-score comparison built in, there is no real way to determine whether red is playing good defense or blue is playing bad offense.

You might be able to do it with

red1+red2+red3 = blue_alliance_OPR - blue_alliance_score

and the higher the score the better (due to the OPR-score) but that involves knowing the blue alliance's combined OPR.

Re: OPR Formula
 

Numerically, DPR = OPR - CCWM (calculated contribution to winning margin). A team will have high DPR if their CCWM is low or negative comparing to OPR. Low DPR means a team is good in defense. Basically it means they do not allow their opponents to score much.
I do not agree with low DPR is a result of opposing alliance's inability to score. Over a number of matches, those teams with low OPRs will also cause other teams to experience the same thing. A team's DPR will only be higher or lower based on how they perform on average comparing to other teams. Remember OPR, DPR and CCWM are all calculations of that team's calculated contribution.

Re: OPR Formula
 

Phil, can you explain how you got the info from twitter?

Re: OPR Formula
 

The problem with DPR is that when teams do not play defence, DPR can be unpredictable. While it will take into account offensive hoarding by the team (if applicable), this is not always significant compared to mostly-random fluctuations, including schedule.

Occasionally, DPR will take into account non-random factors other than the team's robot, though. In 2011, a team's human player could play a significant role in determining opponents score. A human player's output (# of tubes thrown) and accuracy (% of tubes picked up by own alliance) definitely affect opponent score, for example. A human player who threw many tubes or wasn't very accurate could result in a team having a high DPR.

In 2012, human players aren't a factor, but hoarding as an alliance strategy certainly is (note that an alliance could control 15 of the 18 balls at a time). A low DPR by a team not playing defence would probably be indicative of such a strategy.

Re: OPR Formula
 

I didn't get it from twitter. I got it from the web based results (with a URL like this: http://www2.usfirst.org/2011comp/eve...chresults.html) by just going through all the event codes and putting it as a parameter in an excel query that would get the data from http://www2.usfirst.org/2011comp/events/event_code/matchresults.htm. Then, I just put them all in the table I posted.

To get this data from twitter, you'd have to use the API, and I'm not sure to go about that. Maybe you could fetch tweets using JSON?

Re: OPR Formula
 

Hey guys,

I took what all of you have contributed (great post by the way, very helpful) and constructed an excel file to do RUSH's post-competition analysis, or other competition scouting for states and nationals. So i wrote a macro (not very efficient at those, sorry) and it creates webquery files, obtains the data, and organizes it for however many teams are in the tournament. The only problem I am having is the OPR calculations. Can someone look at my macro and see what they can do about adding an OPR calculation formula or something? Or give me some feedback on how i can improve it cause I really am not too good at these. Thanks.

Re: OPR Formula
 

That's along the same lines I was thinking. If you could calculate the opposing score, then you would have your DPR.

Re: OPR Formula
 

Stingray, nice work! I'm going to include that in our OPR this year so we can auto-update it on the fly. Really outstanding.

Re: OPR Formula
 

Hi,

Nice work. If you want your spreadsheet to calculate OPR from the results that you get from the web query, you are welcome to copy any of the macros that I published. I did not put protection on them to allow other teams to use them and customize for their own use. However if that is all you are going to do, I don't see the purpose of it except as a learning process since I publish OPR/CCWM results of every regional and district after each week of competition and I have been doing it for the last 4 years. Please refer to the following white paper.
http://www.chiefdelphi.com/media/papers/2174
You will not see the weekly published spreadsheets from prior years since I delete them at the end of the season and only keep the last one.

Re: OPR Formula
 

Attachment shows OPR, CCWM, & DPR scores obtained by solving the 2052 simultaneous equations obtained for the 2052 teams in that "one big file".

On my 8-year-old computer, it took ½ second to read the file and create the 2052x2052 matrix. It took 19 seconds to factor the matrix and compute OPR, CCWM, and DPR.

Re: OPR Formula
 

And just for kicks attached is a histogram of the CCWM scores. I find it interesting how normal in shape the distribution is; I would have expected it to have a longer tail on the right than is apparent.

Re: OPR Formula
 

Hi Ether,

The numbers you have is slightly different than mine. Do you include elimination round matches?

Your 8-year-old computer must have been quite a powerful computer 8 years ago. Or is there a solver you used that is faster than the Cholesky Decomposition that I used. Here is the statistics that my son got when he was a junior in his independent study math class.

Computer Model Hewlett-Packard HP ProBook 6555b
Platform Mobile
OS Version Microsoft Windows XP Professional
CPU AMD Turion(tm) II P520 Dual-Core Processor
Memory 2807 MB

Here are the data table from tests: (time in seconds)
Size Gauss-Jordan method LU Factorization Cholesky Decomposition
100 0 0 0
300 9 1 0
500 46 8 1
750 159 27 4
1000 383 64 11
1400 1056 178 30
1800 2278 384 63

This was the 2010 data and it took 63 seconds on that slow machine.

Re: OPR Formula
 

Hi Ed,

The numbers you have is slightly different than mine. Do you include elimination round matches?

I used all the data in the "one big file" that Phil attached to post#8 in this thread. That file contains only raw data (no metadata) so I can't say for certain what Phil included.

@Phil: Can you jump in here and answer Ed's question?

Your 8-year-old computer must have been quite a powerful computer 8 years ago.

Pentium D 3.4GHz 1GB

Or is there a solver you used that is faster than the Cholesky Decomposition that I used.

I also used Cholesky, but all Choleskys are not created equal. There are various implementations. Some are column-oriented and some are row-oriented; some are in-place and some are not. It makes a difference. The one I used is a slightly modified version of one that I selected sometime back in the late 80s after testing several different algorithms from various texts. It's optimized for memory access. The 19 seconds was for a 2052x2052 matrix using double precision (64 bit) floats for the matrix and Intel extended precision 80-bit floats for intermediate calculations.

I just re-ran it with single-precision (32 bit) floats and it took a little less than 12 seconds to factor the 2052x2052 matrix.

1800 2278 384 63
This was the 2010 data and it took 63 seconds on that slow machine.

That's 63 seconds for an 1800x1800 matrix. Since Cholesky goes as O³, that would take ~93 seconds for a 2052x2052 matrix.

How are you computing the results in the "Worldrank" tab in the Team_2834 2011_Scouting_Database Championship v4 spreadsheet? My version of Excel (2000) only has 256 columns - not enough to hold a 2052x2052 matrix. I assume you are crunching the numbers in some other app?

I also computed the OPR & CCWM for the data (qualification matches only) in the link that Tom Line included in his post#4 in this thread. Attached are my results. The columns are Team#, OPR, CCWM, and DPR. If you would run your computation on the same data we could compare apples to apples.

Re: OPR Formula
 

You know, I might have actually forgot to put elimination rounds into that file. I forgot that I had to specifically tell excel to import a second table. Attached is a revised version of my entire workbook. Sorry about that, guys.

EDIT:
I attached another file that has some more information - regional names, match times, etc

Re: OPR Formula
 

Understand that in the twitter feed there is a lot of garbage data too. Various test posts as well as practice matches.

Re: OPR Formula
 

Attached is analysis for the data in the tab named "All Matches", less lines 5526, 5766, 6004, and 6196 (DQ).

Columns are Team#, OPR, CCWM, and DPR

Re: OPR Formula
 

Ether,

Your republished numbers are very close to mine now. I also used double precision. My implementation is done in Excel using VBA. I do not actually put the 2053 X 2053 matrix inside the spreadsheet so it works in older version. The program read in the match results and assemble the matrix. It is just stored in the memory for the calculation. Solving the equations inside Excel using VBA is probably slower than outside in another app. Tom Line mentioned they are solving the equations using Excel built-in solver. I am curious what algorithm they use and how fast that would be.

How come you only have 2052 teams? I have 2053 teams in 2011.

Re: OPR Formula
 

Column " B" of the "Worldrank" tab of your Team_2834 2011_Scouting_Database Championship v4b.xls spreadsheet has
has teams 1366 and 2627 which were not in Phil's file. Phil's file has team 1702 which is not in your spreadsheet. So we still aren't using the same data. Do you have (or could you quickly generate) a single file in XLS, CSV, fixed-field, or whitespace-delimited format which has all the data you used¹?

Matrix factor time for double-precision 2052x2052 matrix elements with double-precision intermediate calculations (instead of Intel extended precision 80-bit) is 12.4 seconds.

I didn't know that the Solver could be used by a macro to operate on a matrix in memory. I'll have to look into that. Even so, I'm surprised that they let you solve a 2052x2052 matrix using Solver. The Solver in Excel is a limited (but still quite capable) version of a commercial product from a third party named Frontline.

¹ with fields red1, red2, red3, blue1, blue2, blue3, red_alliance_score, blue_alliance_ score

Re: OPR Formula
 

1702 registered for Los Angeles Regional but did not compete. 1366 did compete at Los Angeles Regional. 2627 is a Michigan team and attended Ann Arbor district last year.
I have attached the data I used. I am sure we will get the same results.
I did not use the Excel build in Solver. The algorithm I used was implemented by Sergey Bochkanov at the University of Tennessee

Re: OPR Formula
 

Yup. Identical.

Yes, I understood that. The remark in my previous post about Solver was in reference to your earlier post mentioning that Tom Line was using Solver.

Would that be ALGLIB ?

Re: OPR Formula
 

If you find me some time, I can whiteboard you through it :P

Re: OPR Formula
 

Yes, it is.

Re: OPR Formula
 

The "short" answer is, the "formula" for OPR is

[A][OPR]~[SCORE]

...where OPR for a given team is one of the N elements of the [OPR] Nx1 column vector approximate solution to the overdetermined system of linear equations shown above. N is the number of teams, M is the number of matches, and [SCORE] is a (2M)x1 column vector of alliance scores for each match in the database being used to do the computation. [A] is a (2M)xN matrix generated from the database¹.

There are several different methods for finding an approximate solution to an overdetermined system of linear equations¹, but for this particular problem using Normal Equations and Cholesky factorization to find the least squares solution is perhaps the most common.

Normal Equations solution method:



¹ I can provide the details if anyone's interested

² The matrix [P] and the vector [S] can be constructed directly from the database, rather than constructing [A] and [SCORES]. In fact, doing so is quicker and requires less memory. I show all the steps in order to make it clear that [OPR] is an approximate solution to the overdetermined data in the database, and that approximate solutions other than least squares are possible.

³ [P]=[A]^T[A] will be symmetric positive definite

Re: OPR Formula
 

I am having trouble understanding OPR. I had thought I had gotten it, but my results seem wrong. I'm pretty sure the problem lies with how i am performing the cholesky decomposition. I don't understand how to make a macro for it. I have looked into Ed Law's workbooks, but I still don't understand. Would it be possible for someone to explain how cholesky decomposition works, or is that too complicated?
Thanks

Re: OPR Formula
 

Would you like to test your Cholesky implementation first to see if that is really the problem?

Attached is a 64x64 test matrix and its Cholesky factorization.

Both files are CSV so Excel should be able to open them directly.

Re: OPR Formula
 

We're actually using matrix functions built into excel - no solver and no VB. It's three or four different pages of calculations. The first is the data, the second is the data sorted into the matrix, then we do the inverse matrix function, and output the final OPR values.

While it isn't the example I used to create our spreadsheet, this page will show you exactly how we go about it. Only the newer versions (2010 and newer) will allow large enough matrices to do the math.

http://www.duncanwil.co.uk/simult.html

Re: OPR Formula
 

Hi Tom,

Just curious: How long does it take to invert a 2053x2053 matrix in Excel?

Re: OPR Formula
 

Attached is a 2053x2053 invertible matrix.

Would someone be willing to pull it into Excel 2010 (or newer) and test how long it takes to invert it¹?

Thank you.



¹how to invert a matrix in Excel: http://opim.wharton.upenn.edu/~guign...matrix_inv.pdf

Re: OPR Formula
 

Excel 2010, 5 minutes 30 seconds.

i3 core @ 2.13, 8 GB ram, windows 7 64 bit home premium.

Re: OPR Formula
 

Thanks Tom.

An optimized Cholesky algorithm solves the 2053x2053 system in a little over 12 seconds on a 3.4GHz Pentium D with 1GB RAM 32bit WinXP Pro SP3.

Re: OPR Formula
 

Ok, it works, thanks. Now, where do I go from here?

Re: OPR Formula
 

What version of Excel do you have?

And just curious: where did you get your Cholesky algorithm from?

Re: OPR Formula
 

I have excel 2007.

And I found the algorithm somewhere online, I don't remember where from. Sorry. I'll attach it.

Re: OPR Formula
 

You're trying to solve

[A][x]=[b]

for [x],

where [A] is a symmetric nonnegative-definite matrix,

[x] is the vector of OPR's,

and

[b] is the vector of alliance score sums.


If you factor [A] using Cholesky, you get [L] such that [L][L]^T=[A],

so you can substitute that for [A] to get

[L][L]^T[x]=[b]

... and that is easily solved in two steps:

substitute [y] for [L]^T[x] to get

[L][y]=[b]

and solve for [y] using forward substitution,

then once [y] is known solve

[L]^T[x]=[y]

for [x] using back substitution.


[EDIT] I hope you get this working. I'm quite curious to see how fast it runs in an Excel VBA macro. The whole process -- Cholesky factorization, forward substitution and backward substitution to get OPR, then forward substitution and backward substitution again to get CCWM -- takes a bit over 12 seconds for a 2053x2053 [A] matrix on my machine using a 32-bit Delphi console app. [/EDIT]

[EDIT2] Instead of the lower triangular matrix [L], some Cholesky implementations give give an upper triangular [U] such that [U]^T[U]=[A]. The solution process is similar. The algorithm you posted produces [L]. [/EDIT2]

Re: OPR Formula
 

I have worked everything out, and am wondering what I have done wrong. I used data from the 2011 Florida, and compared my results to Ed Law's, and mine is similar, but some of the results vary by as much as five and most are about 2 or so off.
I have attached the matrices that I used for A, L, U, B, and Y, and the results for OPR are in X.
Thanks

Re: OPR Formula
 

There were no attachments to your post.

Why did you use both [L] and [U]? It's one or the other.

Attached ZIP file contains test matrix [A] and test vector [b].

Run your code on that test matrix and test vector, and compare your results to the [L] matrix and the [y] and [x] vectors (also in the ZIP file) to locate where the problem is.

Re: OPR Formula
 

Sorry, I now have it attached.

I'm Using U as the transpose as L, didn't mean for any confusion.

I ran my code, and it works, so my problem must be in how I'm getting either A or b. I'll double check my code. Is there any way that I could find what those are supposed to be?

Re: OPR Formula
 

Attached ZIP file contains rawData.txt, which was used to generate the matrix [A].CSV and the vector [b].CSV

See if you can generate those from the raw data.

Data is fixed-field; columns are:

red1 red2 red3 blu1 blu2 blu3 redAllianceScore blueAllianceScore


There are different ways to populate the [A] matrix and [b] vector as the data file is being read. This is how I did it:

The data file is read and processed in a single pass.

For each line of the data file, as the team numbers are being read, each new team number encountered is assigned a TeamID, starting with 1 and incrementing by 1 with each new team. The TeamID is used as the index into the [A] matrix and [b] vector.

Re: OPR Formula
 

Are you using only qualifying matches to assemble your Matrix A and vector b? There is a general consensus that elimination round matches should not be included in the calculation of OPR and CCWM.

Re: OPR Formula
 

Attached where? Not to either of your posts.

Re: OPR Formula
 

Yes. Post your raw data file and I will generate the [A] matrix and [b] vector for it.

Re: OPR Formula
 

@Dinosaur: Haven't heard back from you. If you are struggling with processing the raw data directly into the normal equations ([A][x]=[b]), there is a conceptually simpler way to do it. Create matrix [M] and vector [s] from the raw data as follows:

[M] has dimensions 2m x n, where m is the # of matches in the raw data file and n is the number of teams.

[s] has dimensions n x 1.

As you read the data file, for each new team# you encounter assign a sequential TeamID. Use that TeamID (instead of the team#) as the index into [M] and [s].

For each line (match) read from the raw data file, do the following:

row+=1;
M[row,red1TeamID]=1;
M[row,red2TeamID]=1;
M[row,red3TeamID]=1;
s[row]=redAllianceScore;

row+=1;
M[row,blu1TeamID]=1;
M[row,blu2TeamID]=1;
M[row,blu3TeamID]=1;
s[row]=bluAllianceScore;

When you are done, you will have a set of overdetermined linear equations

[M][x]≈[s]

If you multiply both sides by [M]^T, you get

[M]^T[M][x]=[M]^T[s]

The above are called the normal equations (of the overdetermined linear system), and solving these normal equations for [x] gives the least-squares solution.

Notice that [M]^T[M] is [A] and [M]^T[s] is [b].

So this approach takes more storage space and more computing, but it might be less confusing to code.

Re: OPR Formula
 

I am having trouble with the assigning of a Team ID. I understand it fully well, it's just drastically different from how I build the matrix. Do you have code I could take a look at, to see if I could understand how to switch mine over? I had previously just been inputting the data in numerical order of the team.

Yes, I am only using qualifying matches to assemble the matrix.

The data will be attached.

Also attached is the spreadsheet from earlier I had neglected to attach by accident, twice.

Re: OPR Formula
 

Create an array, let's call it TeamID[]. Size it to be bigger than the maximum expected TeamNumber (in the data file you are analyzing). Initialize all values in the array to 0.

Also create an array named TeamNum[]. Size it to be bigger than the expected total number of teams (in the data file you are analyzing).

As you read each TeamNumber from the data file, do the following logic:

if (TeamID[TeamNumber]==0) {_id++; TeamID[TeamNumber]=_id; TeamNum[_id]=TeamNumber;}

The above arrays are then used to lookup a team's ID if you know the team's NUMBER, or to lookup a team's NUMBER if you know the team's ID.

Re: OPR Formula
 

Attached is a ZIP file containing:

rawdata.txt your raw data file

A.csv the [A] matrix of the Normal Equations [A][x]=[b]

b.csv the [b] vector

L.csv the Cholesky lower-triangular factorization of [A]

y.csv the solution to [L][y]=[b]

x.csv the solution to [L]^T[x]=[y]

stats.txt the analysis report

Re: OPR Formula
 

I've been following this and other OPR discussions for awhile, and I thought I'd share my Excel template for calculating it on the fly (requires an Internet connection).

I use mmult(minverse(play count matrix), total score vector).

Re: OPR Formula
 

Is this limited to processing single tournaments, or can it process an entire year's worth of data (in one large matrix) to get a year-end ranking?

Re: OPR Formula
 

I tried adapting the file to do this, but my current computing resources lack the memory to pull this off with my current algorithm. It does pull data and calculate for single competitions, though.

Re: OPR Formula
 

I see you are using Excel 2007 Mac. Is the problem a limit in the maximum number of columns in a worksheet?

If so, there are options:

1) You could upgrade to Excel 2010 which I believe has substantially expanded the maximum number of columns in a worksheet

2) You could construct the matrix in a VBA macro instead of spreadsheet cells and do the math on it there.

If you do option 2, you should seriously consider factoring the matrix instead of inverting. It's far faster and less susceptible to numerical instability.

Re: OPR Formula
 

1) Nope, already using Excel 2010 on a Purdue University Windows computer.
2) Already doing this, all the calculations are done in code

I'll look into factoring. This was a quick-and-dirty, how easy can I make this solution originally intended for just finding OPR's for a given regional.

Re: OPR Formula
 

I was going by what was posted here.


Why are you running out of memory? Even 2 Gig should be plenty, no?


Google Cholesky. It's not hard to code.

Re: OPR Formula
 

Finally got it. Thanks for all your help Ether. Phew, it's very satisfying to finally have it working. Thanks again.

Re: OPR Formula
 

Way to hang in there !!!