Offensive Power Rankings for 2008

[Bongle]

Originally Posted by sumadin

I understand that p is what we're looking to find, or the average number of points a team contributes per match. s and M we can calculate from the results coming from each regional. Since Mp = s, we can conclude that p = (M-1)s (where M-1 denotes M inverse). It seems to me from thinking about it that M is symmetric, and as such M = M-1. Is that actually the case?

M is indeed symmetric. M[i][j] indicates how many matches team i played with team j. Therefore, it makes sense that M[i][j] = M[j][i].

I don't think the inverse of a symmetric matrix is necessarily symmetric. The transpose of a symmetric matrix M would be equal to its non-transpose, but I don't think that carries for symmetry. To prove that M^-1 is not necessarily equal to M for a symmetric matrix, just think of the symmetric matrix 2I, where I is the identity matrix.

If (M)^-1 = (M) for symmetric matrices like you are proposing, and we know MM^-1 = I for any matrix and its inverse, then (2I)(2I) must equal I, but this is not the case.

I didn't have to write the matrix solver myself, I used a library I found online. If there are any tricks it used, I'm not aware of them.

[Guy Davidson]

You're right. For some reason, I was thinking of the transpose rather than the inverse. I'll see how I handle the inversion of the matrix when I get there. In the meantime, I'm working through the easy stuff: reading the csv and making and populating s and M.

[Mr. Lim]

Originally Posted by sumadin

It seems to me from thinking about it that M is symmetric, and as such M = M-1. Is that actually the case?

M is symmetric, but that doesn't mean M = M inverse.

Symmetry means that M = M transpose (flipped along the identity axis), which is different than M inverse.

It's easy to confuse the two (I remember doing that plenty of times, thank Ms. Martin).

Here's an example where M = M inverse, and you quickly see that M is definitely not symmetric:

|   9   5 | |   9   5 | - |   1   0 |
| -16  -9 | | -16  -9 | - |   0   1 |

[MCarron]

Just an FYI...all of the match data is NOT included from the Peachtree regional. The scoring system failed so all of the elimination matches and many of the qualifying matches from Saturday are not included. As an example...team 343 finished 12-4 at that regional. We are still shown as 5-3 on the Blue Alliance. That means there are eight matches not accounted for on us alone. That would/could be the same for many of the other teams who attended Peachtree.

Is there anybody that has that manual data? Can it be manually entered into the Blue Alliance?

Thanks,
Mike Carron
Team 343

[Joe Ross]

Originally Posted by MCarron

Is there anybody that has that manual data?

See here: http://www.chiefdelphi.com/media/papers/2102

[cziggy343]

Originally Posted by Joe Ross

See here: http://www.chiefdelphi.com/media/papers/2102

but...was anyone planning on putting this manuel score on tba... b/c i have no way to do it...

[Eugene Fang]

if there was a normally very high scoring team that happened to malfunction in a match where they were in your alliance, or was defended a lot in your particular round, wouldn't your score be highly skewed?

[Kyler]

Okay, I have created a basic program to make the n X n matrix as defined in the post that sort of explains the rankings but what do I do from there? I am only in trig and we have definitely not learned that stuff with matrices. Can somebody give me an example of "M(k1)p(1)+M(k2)p(2)+...+M(kn)p(n) should equal s(k)" or clarify that please? Thanks!

[fuzzy1718]

We were hevily defended all through GLR hurdling only 2-3 times a match where we usualy hurdle 4-6 times and at Detroit we were broken 3 of the matches, but we are still high on the list . That shouldn't effect it much.

[Guy Davidson]

Originally Posted by Kyler

Okay, I have created a basic program to make the n X n matrix as defined in the post that sort of explains the rankings but what do I do from there? I am only in trig and we have definitely not learned that stuff with matrices. Can somebody give me an example of "M(k1)p(1)+M(k2)p(2)+...+M(kn)p(n) should equal s(k)" or clarify that please? Thanks!

From there you need to invert M and multiply it by s. The are libraries doing the first all over the internet - however, I do not know the algorithm they use. I know how to do it manually, but that would take way too much time for anything this scale.

Then you need to multiply M inverse by s. What you're looking to get out is another column vector, or list of numbers, similar to the one you have in s, although with different numbers. To do that, simply multiply each element in a column of M inverse (with a fixed row) by each element in the corresponding row in s (which has only one column). For example, to find the 10th element of p, or the average number of points contributed by the team in the 10th row, add up M(10,1)*s(1) + M(10,2)*s(2) + M(10,3)*s(3) + ...

Doing that for each row in M will get you p, the vector you're looking for.

If this didn't make much sense, look at http://mathdemos.gcsu.edu/mathdemos/matvec/matvec.html or http://en.wikipedia.org/wiki/Matrix_multiplication

[Greg Marra]

I added Peachtree missing matches to the database. I'll do another database dump after the NYC regional is finished. Thanks for pointing me to the data!

[BornaE]

Looks like the system is working well, but I think if we add a little to it it would work much better.

Right now it is set up to calculate the average points contributed to an alliance by one team. This method does not take care of the defence.

you guys who did the calculations, can you add defence to it as well.

so example:
Red Score = RedA_O + RedB_O + RedC_O - BlueA_D - BlueB_D - BlueC_D
then solve for Team_O which is the average points added to their alliance, and Team_D which is the average points one team take away from their Opponent's alliance.

[petek]

From the "throw a monkey wrench and see what happens dept.":
Has anyone looked to see how much effect surrogate matches have on these rankings? If the number of matches per team determines the matrix size, is the calculation looking to see how many matches a given team actually played? For example, in Philly all teams played 11 matches, but 304 and 381 each played 12: 11 plus one extra surrogate match.

For those not familiar, surrogates are called for to "fill out" the schedule when the number of teams x the number of matches / 6 is not a whole number. Without surrogates there would be some matches with un-filled robot positions. Surrogate match results are not counted in FIRST's ranking scores, and are identified by a "1" next to the team # in the qualifying schedule. This year it is always the third match for a surrogate team.

[Jay Lundy]

I noticed some people were requesting DPR scores. While the meaning of a DPR number isn't as straightforward as OPR, I think we may be able to improve the OPR calculation by taking it into account. If a team tends to play heavy defense, the teams they play against shouldn't have their OPR reduced when they play below average. Plus I love linear algebra so this gave me an excuse to use it.

<complex math warning>

So here's the equation:

( M -N ) ( p ) = ( s_t )
( N -M ) ( d ) = ( s_o )

Where (n = total # of teams):
M = n x n matrix with M(ij) = # of times i played with j. M(ii) = # of times i played. (same as M from before)
N = n x n matrix with N(ij) = # of times i played against j. N(ii) = 0.
p = n x 1 column vector of OPRs. p(i) = OPR for team i. (same as p from before)
d = n x 1 column vector of DPRs. d(i) = DPR for team i.
s_t = n x 1 column vector of total scores. s_t(i) = Sum of all of team i's match scores. (same as s from before)
s_o = n x 1 column vector of total opponent scores. s_o(i) = Sum of all of team i's opponents' match scores.

In other words, the first n equations add all the offense played by team i's allies, subtracts all the defense played by team i's opponents, and equates that with team i's total score. The second n equations sums all the offense played by team i's opponents, subtracts all the defense played by team i's allies, and equates it with team i's opponents' total score.

We can rewrite the equation as Ax = y where A = (M -N; N -M), x = (p; d), and y = (s_t; s_o).

In the data set I used, there are 2 isolated sets of teams that played no matches with teams outside their set: the Israeli and non-Israeli teams. We can separate these sets and write an equation for each one, and I think it's easier if we do:

A_1 * x_1 = y_1
A_2 * x_2 = y_2

We can solve each equation completely independently, so I'm just going to focus on one equation and call it Ax = y. A has a null space of dimension 1 so it's not invertible. We can increase all the OPRs and DPRs by the same amount without having any effect on the scores, so the null space is the span of x = (1 1 1 ... 1). We can get a unique solution by adding one more equation. I (somewhat arbitrarily) chose the equation by saying: if there was no defense, scores would be 25% higher. In equation form that is:

M(11)*p(1) + M(22)*p(2) + ... + M(nn)*p(n) = 1.25 * (sum(s_t) / 3)

or

( E 0 ) ( p ) = 1.25 * (sum(s_t) / 3)
        ( d )

E = ( M(11) M(22) ... M(nn) )

You can tack the last equation onto the end of A like so:

A = ( M -N )
    ( N -M )
    ( E  0 )

And just ask Matlab to solve Ax = y for you. Or replace a random row in A with ( E 0 ) so A becomes invertible and solve x = A_inv * y.

</complex math warning>

I ran this against the first csv Greg posted and here are the results (top 50, ordered by OPR):

Team   OPR      DPR      OPR + DPR
1114   71.6377  0.9474   72.5852
1124   53.2773  15.2694  68.5467
2056   51.7991  6.8767   58.6759
217    51.6703  13.4995  65.1698
233    51.5346  11.4470  62.9816
39     51.0832  4.8484   55.9316
330    50.1059  0.1292   50.2351
525    50.0129  1.2725   51.2855
175    47.6712  11.6710  59.3422
40     46.3240  10.1761  56.5001
1731   46.1172  -0.0044  46.1128
987    45.9656  7.0006   52.9662
103    45.0985  10.9291  56.0276
191    44.6783  12.1649  56.8432
79     44.1938  6.1087   50.3025
1024   43.9389  5.5522   49.4911
16     43.2490  6.0931   49.3421
67     43.2308  11.1761  54.4070
20     42.3096  6.3370   48.6466
469    41.9469  -5.4304  36.5165
494    41.2950  -1.9009  39.3941
1806   40.8038  5.2194   46.0232
365    40.6742  2.5704   43.2446
47     40.3067  -1.6335  38.6732
148    39.3002  9.0662   48.3663
1493   39.0307  -0.9984  38.0323
383    38.9932  5.5749   44.5681
1625   38.8912  5.1900   44.0813
1519   38.8147  6.3316   45.1463
1126   38.6616  0.8032   39.4648
141    38.6570  7.6568   46.3137
1718   38.4372  3.7425   42.1797
663    38.2419  14.4349  52.6767
126    37.8160  6.3778   44.1938
121    37.7131  12.7949  50.5080
195    37.7043  -1.5850  36.1192
1477   37.4595  10.8694  48.3289
368    37.1072  -2.7458  34.3614
25     37.0417  -3.1295  33.9121
1717   36.5859  6.3136   42.8995
71     36.1253  8.4642   44.5895
836    35.9330  6.4528   42.3859
93     35.5093  1.6895   37.1989
69     35.3987  2.3330   37.7317
61     35.3566  5.7965   41.1532
968    34.7835  4.2148   38.9984
2345   34.6020  1.6196   36.2216
1086   34.5104  10.6218  45.1321
58     34.4129  6.7595   41.1725
935    34.3941  7.7033   42.0974

Compare this with Guy's results from the same dataset. The results are fairly similar, but there's definitely some movement in the rankings. Make of it what you will.

Personally, I don't think it tells you a whole lot to know a team's DPR. The two OPRs tell you slightly different things about a team. The old OPR tries to tell you how much a team actually scored each match. The new OPR tries to tell you how much a team could have scored each match if there was no defense. They are both potentially useful numbers.

Finally, knowing both OPR and DPR does allow you to better predict the score of a match. If you define error as:

 error = actual_red_score - ( p(red1) + p(red2) + p(red3) - d(blue1) - d(blue2) - d(blue3) )

then both methods are the least squares solution for their respective vector spaces, but method #2 has a lower MSE (mean square error) and ME (mean (abs) error) because it has a bigger vector space (less information loss).

Method #1 MSE = 245.0446, ME = 12.306
Method #2 MSE = 180.8867, ME = 10.514

So it's better at predicting past scores. Is it better at predicting future scores? I guess we'll see.

[Guy Davidson]

Jay, this is some very inpressive Linear Algebra. This is pretty awesome!

Two thoughts: Would it be possible for you, at some point, to post all DPR rankings from the overall data set? Also, maybe something more interesting for the results, could you try and solve for which correction factor (in the arbitrarily chosen equation) makes for the lowest ME? Maybe that can make it even more vaulble of a tool. I'll also shoot you a PM with another idea I have to make OPR (and probably DPR) even more meaningful.